One-reversal counter machines and multihead automata: revisited

DOI10.1016/j.tcs.2012.04.002zbMath1247.68133OpenAlexW2028475750MaRDI QIDQ714812

Mark Daley, Oscar H. Ibarra, Lila Kari, Shinnosuke Seki, Ehsan Chiniforooshan

Publication date: 11 October 2012

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

Full work available at URL: https://doi.org/10.1016/j.tcs.2012.04.002

zbMATH Keywords

incomparabilitybounded languageinclusionmultihead automatonreversal-bounded counter machine

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (9)

On the Density of Context-Free and Counter Languages ⋮ Deletion operations on deterministic families of automata ⋮ Insertion operations on deterministic reversal-bounded counter machines ⋮ Input-Position-Restricted Models of Language Acceptors ⋮ On the Density of Context-Free and Counter Languages ⋮ Pseudo-inversion: closure properties and decidability ⋮ Counter machines and crystallographic structures ⋮ On the overlap assembly of strings and languages ⋮ Unnamed Item

Cites Work

• Unnamed Item
• Unnamed Item
• On computational complexity of graph inference from counting
• Recursive unsolvability of Post's problem of Tag und other topics in theory of Turing machines
• On spiking neural P systems and partially blind counter machines
• String-matching cannot be done by a two-head one-way deterministic finite automaton
• A note on semilinear sets and bounded-reversal multihead pushdown automata
• Reversal-bounded multipushdown machines
• Some decision problems concerning semilinearity and commutation.
• One-Reversal Counter Machines and Multihead Automata: Revisited
• On Stateless Multicounter Machines
• On reversal-bounded counter machines and on pushdown automata with a bound on the size of the pushdown store
• Reversal-Bounded Multicounter Machines and Their Decision Problems
• Hierarchies and Characterizations of Stateless Multicounter Machines
• On Multi-Head Finite Automata

This page was built for publication: One-reversal counter machines and multihead automata: revisited