One-way simple multihead finite automata

DOI10.1016/0304-3975(79)90033-1MaRDI QIDQ1258608zbMATH OpenOpenAlexFDO

Authors K. Appert

Publication date 1979

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

Full work available at URL https://doi.org/10.1016/0304-3975(79)90033-1

zbMATH Keywords

One-Way Multihead Finite AutomataTape-Bounded Turing Machines

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Cites work

• scientific article; zbMATH DE number 3509706 (Why is no real title available?)
• scientific article; zbMATH DE number 3311755 (Why is no real title available?)
• k + 1 Heads Are Better than k
• A note on semilinear sets and bounded-reversal multihead pushdown automata
• A useful device for showing the solvability of some decision problems
• Counter machines and counter languages
• Erasable context-free languages
• Finite automata with multiplication
• Multi-tape and multi-head pushdown automata
• On 3-head versus 2-head finite automata
• On Multi-Head Finite Automata
• On tape-bounded complexity classes and multihead finite automata
• One-way multihead writing finite automata
• Remarks on the complexity of nondeterministic counter languages
• Some open problems in the theory of computation as questions about two-way deterministic pushdown automaton languages
• The equivalence of stack-counter acceptors and quasi-realtime stack- counter acceptors

Cited in

(8)

• Tradeoffs for language recognition on alternating machines
• Sensing versus nonsensing automata
• Some classes of languages in \(NC^ 1\)
• Multiprocessor automata
• One-way simple multihead finite automata are not closed under concatenation
• Hierarchies of one-way multihead automata languages
• A NOTE ON REBOUND TURING MACHINES
• Alternating simple multihead finite automata

This page was built for publication: One-way simple multihead finite automata

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