Experiments in Complexity of Probabilistic and Ultrametric Automata

Abstract. We try to compare the complexity of deterministic, nonde-terministic, probabilistic and ultrametric finite automata for the same language. We do not claim to have final upper and lower bounds. Rather these results can be considered as experiments to find advantages of one type of automata versus another type.