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, Incompleteness Theorems, Large Cardinals, and Automata Over Finite Words, Undecidability in matrices over Laurent polynomials., On the universe, disjointness, and containment problems for simple machines, Two-way deterministic multi-weak-counter machines, Word problems of groups: formal languages, characterizations and decidability, Incompleteness Theorems, Large Cardinals, and Automata over Finite Words, On two-way weak counter machines, On restricted one-counter machines
Cites Work
- 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
- Unnamed Item