Capabilities of Ultrametric Automata with One, Two, and Three States
| Autor: | Maksims Dimitrijevs |
|---|---|
| Rok vydání: | 2016 |
| Předmět: |
Discrete mathematics
Binary tree Computation Prime number 020206 networking & telecommunications 02 engineering and technology Nonlinear Sciences::Cellular Automata and Lattice Gases Condensed Matter::Disordered Systems and Neural Networks Automaton Turing machine symbols.namesake Regular language 0202 electrical engineering electronic engineering information engineering symbols Mathematics::Metric Geometry 020201 artificial intelligence & image processing Promise problem Ultrametric space Computer Science::Databases Computer Science::Formal Languages and Automata Theory Mathematics |
| Zdroj: | Lecture Notes in Computer Science ISBN: 9783662491911 SOFSEM |
| DOI: | 10.1007/978-3-662-49192-8_21 |
| Popis: | 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|