Restricted one-counter machines with undecidable universe problems

DOI10.1007/BF01744294zbMath0428.03038OpenAlexW1965755333MaRDI QIDQ3864502

Oscar H. Ibarra

Publication date: 1979

Published in: Mathematical Systems Theory (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf01744294

zbMATH Keywords

restricted nondeterminismsubclasses of one-counter machinesundecidable universe problem

Mathematics Subject Classification ID

Undecidability and degrees of sets of sentences (03D35) Turing machines and related notions (03D10)

Related Items

Word problems of groups: formal languages, characterizations and decidability ⋮ On differentiation functions, structure functions, and related languages of context-free grammars ⋮ On two-way weak counter machines ⋮ Two-way deterministic multi-weak-counter machines ⋮ Incompleteness Theorems, Large Cardinals, and Automata Over Finite Words ⋮ 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 ⋮ 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