New families of non real time dpda's and their decidability results

DOI10.1016/0304-3975(84)90054-9zbMath0548.68077OpenAlexW2053101727MaRDI QIDQ799385

Yair Itzhaik, Amiram Yehudai

Publication date: 1984

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0304-3975(84)90054-9

zbMATH Keywords

polynomial time algorithmsdeterministic pushdown automataequivalence problemlinearity teston-line regularity indicationreal time strictnesssubclass containment problems

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items (3)

The extended equivalence problem for a class of non-real-time deterministic pushdown automata ⋮ Some negative results concerning DPDA's ⋮ Some remarks on subclass containment problems for several classes of dpda's

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Superdeterministic DPDAs: The method of accepting does affect decision problems
• The equivalence problem for two dpda's, one of which is a finite-turn or one-counter machine
• A result on the equivalence problem for deterministic pushdown automata
• An improvement on Valiant's decision procedure for equivalence of deterministic finite turn pushdown machines
• On equivalence and subclass containment problems for deterministic context-free languages
• A note on non-singular deterministic pushdown automata
• Linearity is polynomially decidable for realtime pushdown store automata
• Optimality of a Two-Phase Strategy for Routing in Interconnection Networks
• A real-time strictness test for deterministic pushdown automata
• The equivalence problem for some non-real-time deterministic pushdown automata
• Regularity and Related Problems for Deterministic Pushdown Automata
• On jump-deterministic pushdown automata
• The decidability of equivalence for deterministic stateless pushdown automata
• The equivalence problem for deterministic finite-turn pushdown automata
• Jump PDA’s and Hierarchies of Deterministic Context-Free Languages
• A regularity test for pushdown machines
• Properties of deterministic top-down grammars
• Real-Time Strict Deterministic Languages

This page was built for publication: New families of non real time dpda's and their decidability results