@inproceedings{f8d0ace66aea42dcb8e7398be79e7c97,
title = "On the hierarchy classes of finite ultrametric automata",
abstract = "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 k-head non-deterministic finite automaton. Then we prove that in the two-way setting the class of languages recognized by ultrametric finite k-head automata is a proper subclass of the class of languages recognized by (k + 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.",
author = "Rihards Kri{\v s}lauks and Kaspars Balodis",
note = "Publisher Copyright: {\textcopyright} Springer-Verlag Berlin Heidelberg 2015.; 41st International Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2015 ; Conference date: 24-01-2015 Through 29-01-2015",
year = "2015",
doi = "10.1007/978-3-662-46078-8\_26",
language = "English",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Verlag",
pages = "314--326",
editor = "Italiano, \{Giuseppe F.\} and Tiziana Margaria-Steffen and Jaroslav Pokorn{\'y} and Jean-Jacques Quisquater and Roger Wattenhofer",
booktitle = "SOFSEM 2015",
address = "Germany",
}