Alternating simple multihead finite automata

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

Katsushi Inoue, Itsuo Takanami, Hiroshi Taniguchi, Hiroshi Matsuno

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 properties; complexity classes; complexity measure; accepting powers

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68Q45: Formal languages and automata

Related Items

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

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