6533b853fe1ef96bd12abfcd

RESEARCH PRODUCT

Capabilities of Ultrametric Automata with One, Two, and Three States

Maksims Dimitrijevs

subject

Discrete mathematicsBinary treeComputationPrime number020206 networking & telecommunications02 engineering and technologyNonlinear Sciences::Cellular Automata and Lattice GasesCondensed Matter::Disordered Systems and Neural NetworksAutomatonTuring machinesymbols.namesakeRegular language0202 electrical engineering electronic engineering information engineeringsymbolsMathematics::Metric Geometry020201 artificial intelligence & image processingPromise problemUltrametric spaceComputer Science::DatabasesComputer Science::Formal Languages and Automata TheoryMathematics

description

Ultrametric automata use p-adic numbers to describe the random branching of the process of computation. Previous research has shown that ultrametric automata can have a significant decrease in computing complexity. In this paper we consider the languages that can be recognized by one-way ultrametric automata with one, two, and three states. We also show an example of a promise problem that can be solved by ultrametric integral automaton with three states.

yearjournalcountryeditionlanguage
2016-01-01
https://doi.org/10.1007/978-3-662-49192-8_21