One-reversal counter machines and multihead automata: revisited
From MaRDI portal
Publication:714812
DOI10.1016/J.TCS.2012.04.002zbMATH Open1247.68133OpenAlexW2028475750MaRDI QIDQ714812FDOQ714812
Authors: Ehsan Chiniforooshan, Mark Daley, Oscar H. Ibarra, Lila Kari, Shinnosuke Seki 
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
Recommendations
Formal languages and automata (68Q45) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Cites Work
- Reversal-bounded multipushdown machines
- Some decision problems concerning semilinearity and commutation.
- Reversal-Bounded Multicounter Machines and Their Decision Problems
- On computational complexity of graph inference from counting
- On Multi-Head Finite Automata
- Recursive unsolvability of Post's problem of Tag und other topics in theory of Turing machines
- Title not available (Why is that?)
- Title not available (Why is that?)
- A note on semilinear sets and bounded-reversal multihead pushdown automata
- On stateless multicounter machines
- Hierarchies and Characterizations of Stateless Multicounter Machines
- String-matching cannot be done by a two-head one-way deterministic finite automaton
- One-reversal counter machines and multihead automata: revisited
- On reversal-bounded counter machines and on pushdown automata with a bound on the size of the pushdown store
- On spiking neural P systems and partially blind counter machines
Cited In (30)
- Title not available (Why is that?)
- The effect of end-markers on counter machines and commutativity
- Simulating one-reversal multicounter machines by partially blind multihead finite automata
- On the intersection of the class of linear context-free languages and the class of single-reset languages
- Reversal-bounded nondeterministic multicounter machines and complementation
- Counter machines and crystallographic structures
- Pseudo-inversion: closure properties and decidability
- Input-Position-Restricted Models of Language Acceptors
- The Power of Alternating One-Reversal Counters and Stacks
- Title not available (Why is that?)
- One-reversal counter machines and multihead automata: revisited
- Title not available (Why is that?)
- Title not available (Why is that?)
- On families of full trios containing counter machine languages
- Reversal-Bounded Acceptors and Intersections of Linear Languages
- On the intersection of stacks and queues
- Automata with modulo counters and nondeterministic counter bounds
- Grammatical characterizations of NPDAs and VPDAs with counters
- Notes on looping deterministic two-way pushdown automata
- On the density of context-free and counter languages
- Title not available (Why is that?)
- On the density of context-free and counter languages
- Fooling a two-way nondeterministic multihead automaton with reversal number restriction
- Reversible computations of one-way counter automata
- On the overlap assembly of strings and languages
- Remarks on two-way automata with weak-counters
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Reversible Computations of One-Way Counter Automata
This page was built for publication: One-reversal counter machines and multihead automata: revisited
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q714812)
