Numerical and experimental study of a niobium reactor preheating for titanium production by a vapor-phase reduction

2020

Tally languages accepted by alternating multitape finite automata

1997

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 (respe…

Tally languages accepted by Monte Carlo pushdown automata

1997

Rather often difficult (and sometimes even undecidable) problems become easily decidable for tally languages, i.e. for languages in a single-letter alphabet. For instance, the class of languages recognizable by 1-way nondeterministic pushdown automata equals the class of the context-free languages, but the class of the tally languages recognizable by 1-way nondeterministic pushdown automata, contains only regular languages [LP81]. We prove that languages over one-letter alphabet accepted by randomized one-way 1-tape Monte Carlo pushdown automata are regular. However Monte Carlo pushdown automata can be much more concise than deterministic 1-way finite state automata.