Timeline for Finite State Automata Inequivalence?
Current License: CC BY-SA 3.0
8 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Aug 17, 2016 at 15:43 | answer | added | Narad Rampersad | timeline score: 5 | |
| Aug 17, 2016 at 15:42 | comment | added | TheoryQuest1 | if possible can you please provide refrences for the reduction. i assumed, since integer programming over binary alphabet is NPComplete, a binary alphabet NFA can be converted to it. | |
| Aug 17, 2016 at 15:05 | comment | added | Benjamin Steinberg | How does that contradict what I said | |
| Aug 17, 2016 at 13:44 | comment | added | TheoryQuest1 | I think that might not be correct. Because Integer Programming over {0,1} is one of Dr. Karp's original NPComplete problems. | |
| Aug 17, 2016 at 13:40 | comment | added | Benjamin Steinberg | Over a 1-letter alphabet you can transform things into integer programming. I guess that's how they may do it. | |
| Aug 17, 2016 at 13:22 | comment | added | TheoryQuest1 | Much thanks. "Checking if an non deterministic automation accepts all strings is PSPACE compete." I think that part is just the definition stated. I want to understand what changes when the no. of alphabets change. Why can't we do the same for {1, 0} what we did for {1}. What limits us which does not in the {1} case. | |
| Aug 17, 2016 at 13:19 | comment | added | Benjamin Steinberg | Checking if an non deterministic automation accepts all strings is PSPACE compete. The issue is determinizing an automation is a big blowup | |
| Aug 17, 2016 at 13:06 | history | asked | TheoryQuest1 | CC BY-SA 3.0 |