6533b7d1fe1ef96bd125c099

RESEARCH PRODUCT

On the Hierarchy Classes of Finite Ultrametric Automata

Rihards KrišlauksKaspars Balodis

subject

Discrete mathematicsClass (set theory)TheoryofComputation_COMPUTATIONBYABSTRACTDEVICESFinite-state machineHierarchy (mathematics)Nonlinear Sciences::Cellular Automata and Lattice GasesCondensed Matter::Disordered Systems and Neural NetworksAutomatonAlgebraTuring machinesymbols.namesakeTheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGESsymbolsMathematics::Metric GeometryQuantum finite automataAutomata theoryUltrametric spaceComputer Science::Formal Languages and Automata TheoryMathematicsofComputing_DISCRETEMATHEMATICSMathematics

description

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.

yearjournalcountryeditionlanguage
2015-01-01
https://doi.org/10.1007/978-3-662-46078-8_26