6533b86dfe1ef96bd12c9346

RESEARCH PRODUCT

Tally languages accepted by alternating multitape finite automata

subject

description

We consider k-tape 1-way alternating finite automata (k-tape lafa). We say that an alternating automaton accepts a language L\(\subseteq\)(Σ*)k with f(n)-bounded maximal (respectively, minimal) leaf-size if arbitrary (respectively, at least one) accepting tree for any (w1, w2,..., wk) ∈ L has no more than $$f\mathop {(\max }\limits_{1 \leqslant i \leqslant k} \left| {w_i } \right|)$$ leaves. The main results of the paper are the following. If k-tape lafa accepts language L over one-letter alphabet with o(log n)-bounded maximal leaf-size or o(log log n)-bounded minimal leaf-size then the language L is semilinear. Moreover, if a language L is accepted with o(log log(n))-bounded minimal (respectively, o(log(n))-bounded maximal) leaf-size then it is accepted by constant-bounded minimal (respectively, maximal) leaf-size by the same automaton. To show that this bound is optimal we prove that 4-tape lafa can accept a non-semilinear languages over one-letter alphabet with O(log log n)-bounded minimal leaf-size. For maximal leaf-size our bound is optimal due to King's results.