Hacker News new | past | comments | ask | show | jobs | submit login

Isn't it possible to decide the equivalence of deterministic pushdown automata? Wouldn't DPDAs be considered more powerful than FSMs due to the addition of a stack?

Wikipedia [1] shows there's a paper called "The equivalence problem for deterministic pushdown automata is decidable" that won the Gödel Prize is 2002. I haven't read the paper nor do I currently have access to it though.

[1] https://en.wikipedia.org/wiki/Deterministic_pushdown_automat...




Here you go!

http://link.springer.com.sci-hub.cc/chapter/10.1007/3-540-63...

It was initially published in 1997.


Huh! Well there you go.




Join us for AI Startup School this June 16-17 in San Francisco!

Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: