On partially blind multihead finite automata.

DOI10.1016/J.TCS.2006.01.030MaRDI QIDQ2490819zbMATH OpenOpenAlexFDO

Authors Oscar H. Ibarra, B. Ravikumar

Publication date 18 May 2006

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

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

zbMATH Keywords

blind headcounter machinefinite automatonprobabilistic automatonsemilinear language

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Recommendations

• On computational power of partially blind automata
• Simulating one-reversal multicounter machines by partially blind multihead finite automata
• Multi-head finite automata: characterizations, concepts and open problems
• One-reversal counter machines and multihead automata: revisited
• scientific article; zbMATH DE number 3928351

Cites work

• A note on semilinear sets and bounded-reversal multihead pushdown automata
• A Note on Tape-Bounded Complexity Classes and Linear Context-Free languages
• FSTTCS 2004: Foundations of Software Technology and Theoretical Computer Science
• scientific article; zbMATH DE number 3664335 (Why is no real title available?)
• scientific article; zbMATH DE number 3765145 (Why is no real title available?)
• scientific article; zbMATH DE number 1318511 (Why is no real title available?)
• Knapsack problems for NL
• Multi-tape and multi-head pushdown automata
• On a complexity hierarchy between L and NL
• Probabilistic automata
• Remarks on blind and partially blind one-way multicounter machines
• Remarks on the complexity of nondeterministic counter languages
• Reversal-Bounded Multicounter Machines and Their Decision Problems
• Reversal-bounded multipushdown machines
• The Unsolvability of the Equivalence Problem for \varepsilon -Free NGSM’s with Unary Input (Output) Alphabet and Applications

Cited in

(7)

• On the descriptional complexity of Watson-Crick automata
• Simulating one-reversal multicounter machines by partially blind multihead finite automata
• On computational power of partially blind automata
• Automata with modulo counters and nondeterministic counter bounds
• Automata with modulo counters and nondeterministic counter bounds
• Complexity of multi-head finite automata: origins and directions
• On the universe, disjointness, and containment problems for simple machines

This page was built for publication: On partially blind multihead finite automata.

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2490819)