Two-way deterministic multi-weak-counter machines

DOI10.1016/0304-3975(82)90086-XzbMath0486.68085MaRDI QIDQ1165028

Satoru Miyano

Publication date: 1982

Published in: Theoretical Computer Science (Search for Journal in Brave)

zbMATH Keywords

bounded language; language recognition; semilinear language; two-way deterministic machines

Mathematics Subject Classification ID

68Q45: Formal languages and automata

Related Items

Remarks on two-way automata with weak-counters, Interference automata, GENERALIZED COUNTERS AND REVERSAL COMPLEXITY, On two-way weak counter machines

Cites Work

• Unnamed Item
• Recursive unsolvability of Post's problem of Tag und other topics in theory of Turing machines
• Simple counter machines and number-theoretic problems
• A note on semilinear sets and bounded-reversal multihead pushdown automata
• On tape-bounded complexity classes and multihead finite automata
• Remarks on the complexity of nondeterministic counter languages
• Finite automata with multiplication
• Remarks on blind and partially blind one-way multicounter machines
• Restricted one-counter machines with undecidable universe problems
• Some open problems in the theory of computation as questions about two-way deterministic pushdown automaton languages
• Reversal-Bounded Multicounter Machines and Their Decision Problems
• Bounded-reversal multihead finite automata languages
• On Context-Free Languages
• Two-way pushdown automata
• Counter machines and counter languages
• Multi-stack-counter languages