Abstract
Ultrametric automata have properties similar to the properties of probabilistic automata but the descriptional power of these types of automata can differ very much. In this paper, we compare ultrametric automata with deterministic, nondeterministic, probabilistic and al-ternating automata with various state complexities. We also show that two-way ultrametric automata can have a smaller state complexity than one-way ultrametric automata.
| Original language | English |
|---|---|
| Pages (from-to) | 13-24 |
| Number of pages | 12 |
| Journal | CEUR Workshop Proceedings |
| Volume | 1548 |
| Publication status | Published - 2016 |
| Event | Student Research Forum Papers and Posters at SOFSEM 2016, SOFSEM-SP 2016 - Harrachov, Czech Republic Duration: 23 Jan 2016 → 28 Jan 2016 |
Fingerprint
Dive into the research topics of 'State complexity advantages of ultrametric automata'. Together they form a unique fingerprint.Cite this
- APA
- Author
- BIBTEX
- Harvard
- Standard
- RIS
- Vancouver