Alternating simple multihead finite automata

DOI10.1016/0304-3975(85)90048-9MaRDI QIDQ1058853zbMATH OpenOpenAlexFDO

Authors 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

accepting powersclosure propertiescomplexity classescomplexity measure

Mathematics Subject Classification ID

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

Review text

This paper introduces the alternating simple multihead finite automaton (ASPMHFA), which can be considered as an alternating version of a simple multihead finite automaton (SPMHFA). We first show that ASPMHFA's are equivalent to ordinary alternating multihead finite automata. We investigate a relationship among the accepting powers of SPMHFA's, ASPMHFA's, and ASPMHFA's with only universal states. We next introduce a simple, natural complexity measure for ASPMHFA's, called 'leaf-size', and provide a spectrum of complexity classes of ASPMHFA's, based on simultaneously leaf-size, the number of heads, and the move directions of heads. We finally investigate closure properties (under Boolean operations) of ASPMHFA's.

Recommendations

• Alternating multihead finite automata
• scientific article; zbMATH DE number 3980491
• scientific article; zbMATH DE number 30303
• scientific article; zbMATH DE number 1088283
• scientific article; zbMATH DE number 3911710

Cites work

• (Semi)alternating stack automata
• A useful device for showing the solvability of some decision problems
• Alternating multihead finite automata
• Alternating simple multihead finite automata
• Alternation
• Finite automata with multiplication
• scientific article; zbMATH DE number 3311755 (Why is no real title available?)
• Multi-tape and multi-head pushdown automata
• On alternation
• On tape-bounded complexity classes and multihead finite automata
• On two-way multihead automata
• One-way multihead writing finite automata
• One-way simple multihead finite automata
• One-way simple multihead finite automata are not closed under concatenation
• Tree-size bounded alternation
• Two-dimensional alternative Turing machines

Cited in

(9)

• Alternating simple multihead finite automata
• Alternating multihead finite automata
• Tradeoffs for language recognition on alternating machines
• On space-bounded synchronized alternating Turing machines
• Some characterizations of multihead finite automata
• scientific article; zbMATH DE number 3980491 (Why is no real title available?)
• scientific article; zbMATH DE number 30303 (Why is no real title available?)
• scientific article; zbMATH DE number 79114 (Why is no real title available?)
• A note on real-time one-way alternating multicounter machines

This page was built for publication: Alternating simple multihead finite automata

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