On some decision questions concerning pushdown machines
From MaRDI portal
Publication:593781
DOI10.1016/0304-3975(83)90006-3zbMath0525.68028OpenAlexW1989148041MaRDI QIDQ593781
Publication date: 1983
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0304-3975(83)90006-3
equivalenceambiguity1-turn deterministic pushdown automatonfinite- turn nondeterministic counter automatonpushdown acceptorspushdown transducersunrestricted deterministic counter automaton
Related Items (3)
A direct branching algorithm for checking the equivalence of two deterministic pushdown transducers, one of which is real-time strict ⋮ On the finite-valuedness problem for sequential machines ⋮ On the equivalence of some transductions involving letter to letter morphisms on regular languages
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Superdeterministic DPDAs: The method of accepting does affect decision problems
- A-transducers and the monotonicity of IL schemes
- The equivalence problem for two dpda's, one of which is a finite-turn or one-counter machine
- Deterministic one-counter automata
- Reversal-bounded multipushdown machines
- Some decidability results about regular and pushdown translations
- Two decidability results for deterministic pushdown automata
- What makes some language theory problems undecidable
- Optimization of LR(k) parsers
- Optimality of a Two-Phase Strategy for Routing in Interconnection Networks
- The equivalence problem for real-time strict deterministic languages
- Reversal-Bounded Multicounter Machines and Their Decision Problems
- The decidability of equivalence for deterministic stateless pushdown automata
- The equivalence problem for deterministic finite-turn pushdown automata
- An Infinite Hierarchy of Context-Free Languages
This page was built for publication: On some decision questions concerning pushdown machines
