A hierarchy of real-time deterministic languages and their equivalence

DOI10.1016/0022-0000(82)90057-5zbMath0487.68068OpenAlexW2001606855MaRDI QIDQ1165588

Amiram Yehudai

Publication date: 1982

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0022-0000(82)90057-5

zbMATH Keywords

decidabilitydeterministic pushdown automatainfinite hierarchy of real-time deterministic context free languages

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 ⋮ An extended direct branching algorithm for checking equivalence of deterministic pushdown automata

Cites Work

• Unnamed Item
• A hierarchy of deterministic languages
• On LR(k) grammars and languages
• A representation of trees by languages. I
• Strict deterministic grammars
• A direct branching algorithm for checking equivalence of some classes of deterministic pushdown automata
• The equivalence problem for real-time strict deterministic languages
• A real-time strictness test for deterministic pushdown automata
• Properties of deterministic top-down grammars
• Real-Time Strict Deterministic Languages