Bounded-reversal multihead finite automata languages

DOI10.1016/S0019-9958(74)90994-2MaRDI QIDQ4768638zbMATH OpenOpenAlexFDO

Authors I. H. Sudborough

Publication date 1974

Published in Information and Control (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/s0019-9958(74)90994-2

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Turing machines and related notions (03D10)

Cited in

(14)

• Tradeoffs for language recognition on alternating machines
• scientific article; zbMATH DE number 79114 (Why is no real title available?)
• Some open problems in the theory of computation as questions about two-way deterministic pushdown automaton languages
• Tight hierarchy of data-independent multi-head automata
• Complexity of multi-head finite automata: origins and directions
• On tape-bounded complexity classes and multihead finite automata
• Investigations on automata and languages over a unary alphabet
• Head and state hierarchies for unary multi-head finite automata
• A useful device for showing the solvability of some decision problems
• On the power of two-way multihead quantum finite automata
• Descriptional complexity of regular languages
• Finite automata with multiplication
• Two-way deterministic multi-weak-counter machines
• Simulations of unary one-way multi-head finite automata

This page was built for publication: Bounded-reversal multihead finite automata languages

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