This paper explores the language classes that arise with respect to the head count of a finite ultrametric automaton. First we prove that in the one-way setting there is a language that can be recognized by a one-head ultrametric finite automaton and cannot be recognized by any
-head non-deterministic finite automaton. Then we prove that in the two-way setting the class of languages recognized by ultrametric finite
-head automata is a proper subclass of the class of languages recognized by (
+ 1)-head automata. Ultrametric finite automata are similar to probabilistic and quantum automata and have only just recently been introduced by Freivalds. We introduce ultrametric Turing machines and ultrametric multi-register machines to assist in proving the results.
Bitte loggen Sie sich ein, um Zugang zu diesem Inhalt zu erhalten