New families of non real time dpda's and their decidability results
From MaRDI portal
Publication:799385
DOI10.1016/0304-3975(84)90054-9zbMath0548.68077OpenAlexW2053101727MaRDI QIDQ799385
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
polynomial time algorithmsdeterministic pushdown automataequivalence problemlinearity teston-line regularity indicationreal time strictnesssubclass containment problems
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
