Timeline for Finite State Automata Inequivalence?
Current License: CC BY-SA 3.0
5 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Aug 18, 2016 at 14:41 | comment | added | Narad Rampersad | The key to finding and checking an an exponential length binary string in PSPACE is to apply Savitch's Theorem, which states that NPSPACE = PSPACE. So you are allowed to use non-determinism here. A good reference for this material would be J. Shallit, A Second Course in Formal Languages and Automata Theory (Section 6.7), Cambridge 2009. | |
| Aug 17, 2016 at 16:35 | comment | added | TheoryQuest1 | Moreover, if the string size is exponential, haven't we proved that PSPACE is strictly greater than NP. | |
| Aug 17, 2016 at 16:02 | comment | added | TheoryQuest1 | thanks. i somewhat got the basic of the argument: In case of unary alphabet, the essence is convert exponential unary string to binary which leads to polynomial length certificate. This certificate could then be checked in P time (i am still unclear how despite the hint). This process isn't possible in binary alphabet. Here in i am lost. doubts is as follows: 1. How can one find/check an exponential length binary string in PSPACE in case of DTM. This was the part I was confused about. Some references (for beginners) would be helpful regarding this specific prob. | |
| Aug 17, 2016 at 15:44 | review | First posts | |||
| Aug 17, 2016 at 16:05 | |||||
| Aug 17, 2016 at 15:43 | history | answered | Narad Rampersad | CC BY-SA 3.0 |