Alternating simple multihead finite automata
1985; Elsevier BV; Volume: 36; Linguagem: Inglês
10.1016/0304-3975(85)90048-9
ISSN1879-2294
AutoresHiroshi Matsuno, Katsushi Inoue, Hiroshi Taniguchi, Itsuo Takanami,
Tópico(s)DNA and Biological Computing
ResumoThis 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.
Referência(s)