Restricted one-counter machines with undecidable universe problems
From MaRDI portal
Publication:3864502
DOI10.1007/BF01744294zbMath0428.03038MaRDI QIDQ3864502
Publication date: 1979
Published in: Mathematical Systems Theory (Search for Journal in Brave)
Related Items
On differentiation functions, structure functions, and related languages of context-free grammars, Undecidability in matrices over Laurent polynomials., On the universe, disjointness, and containment problems for simple machines, Two-way deterministic multi-weak-counter machines, On two-way weak counter machines, On restricted one-counter machines
Cites Work
- Unnamed Item
- Deterministic one-counter automata
- Reversal-bounded multipushdown machines
- Multitape one-way nonwriting automata
- Reversal-Bounded Multicounter Machines and Their Decision Problems
- The equivalence problem for deterministic finite-turn pushdown automata
- The unsolvability of the Equivalence Problem for Λ-Free nondeterministic generalized machines
- An Infinite Hierarchy of Context-Free Languages