Simple counter machines and number-theoretic problems

DOI10.1016/0022-0000(79)90025-4zbMath0426.68036OpenAlexW2011408144MaRDI QIDQ1136223

Oscar H. Ibarra, Eitan M. Gurari

Publication date: 1979

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0022-0000(79)90025-4

zbMATH Keywords

deterministic two-way multicounter machine

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Decidability (number-theoretic aspects) (11U05) Automata and formal grammars in connection with logical questions (03D05) Diophantine equations (11D99)

Related Items

Finite automata and unary languages ⋮ The complexity of the equivalence problem for two characterizations of Presburger sets ⋮ Descriptional complexity of two-way pushdown automata with restricted head reversals ⋮ Two-way deterministic multi-weak-counter machines ⋮ New decidability results concerning two-way counter machines and applications ⋮ Removing nondeterminism in constant height pushdown automata ⋮ A note on bounded-reversal multipushdown machines ⋮ Counter machines and verification problems. ⋮ A characterization of reversal-bounded multipushdown machine languages

Cites Work

• Unnamed Item
• Unnamed Item
• Recursive unsolvability of Post's problem of Tag und other topics in theory of Turing machines
• Reversal-bounded multipushdown machines
• Finite automata with multiplication
• A characterization of semilinear sets
• Reversal-Bounded Multicounter Machines and Their Decision Problems
• An NP-Complete Number-Theoretic Problem