Alternating simple multihead finite automata

DOI10.1016/0304-3975(85)90048-9zbMath0565.68055OpenAlexW2034524526MaRDI QIDQ1058853

Hiroshi Matsuno, Katsushi Inoue, Hiroshi Taniguchi, Itsuo Takanami

Publication date: 1985

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

Full work available at URL: https://doi.org/10.1016/0304-3975(85)90048-9

zbMATH Keywords

closure propertiescomplexity classescomplexity measureaccepting powers

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45)

Related Items

Tradeoffs for language recognition on alternating machines ⋮ On space-bounded synchronized alternating Turing machines ⋮ Unnamed Item ⋮ Alternating simple multihead finite automata ⋮ A note on real-time one-way alternating multicounter machines

Cites Work

• Unnamed Item
• Two-dimensional alternative Turing machines
• One-way simple multihead finite automata are not closed under concatenation
• Alternating simple multihead finite automata
• Alternating multihead finite automata
• On alternation
• Tree-size bounded alternation
• On tape-bounded complexity classes and multihead finite automata
• A useful device for showing the solvability of some decision problems
• Finite automata with multiplication
• One-way simple multihead finite automata
• On two-way multihead automata
• Alternation
• (Semi)alternating stack automata
• One-way multihead writing finite automata
• Multi-tape and multi-head pushdown automata