Deterministic one-counter automata

✍ Scribed by Leslie G. Valiant; Michael S. Paterson

• Publisher: Elsevier Science
• Year: 1975
• Tongue: English
• Weight: 471 KB
• Volume: 10
• Category: Article
• ISSN: 0022-0000
• DOI: 10.1016/s0022-0000(75)80005-5

✦ Synopsis

The equivalence problem for deterministic one-counter automata is shown to be decidable. A corollary for schema theory is that equivalence is decidable for Ianov schemas with an auxiliary counter.