The equivalence problem for some non-real-time deterministic pushdown automata

DOI10.1145/322344.322357zbMath0489.68075OpenAlexW2034209817MaRDI QIDQ3951577

Esko Ukkonen

Publication date: 1982

Published in: Journal of the ACM (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/322344.322357

zbMATH Keywords

decision problemdeterministic languagesfinite-turn dpdasreal time dpdas

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items

The extended equivalence problem for a class of non-real-time deterministic pushdown automata, Efficient Equivalence Checking Technique for Some Classes of Finite-State Machines, The equivalence problem for two dpda's, one of which is a finite-turn or one-counter machine, New families of non real time dpda's and their decidability results, Some remarks on subclass containment problems for several classes of dpda's, An extended direct branching algorithm for checking equivalence of deterministic pushdown automata