State complexity advantages of ultrametric automata

Maksims Dimitrijevs

State complexity advantages of ultrametric automata

Maksims Dimitrijevs^*

^*Šī darba korespondējošais autors

Datorikas nodaļa

Zinātniskās darbības rezultāts: Devums žurnālam › Konferences zinātniskais raksts › koleģiāli recenzēts

1 Atsauce (Scopus)

Kopsavilkums

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.

Oriģinālvaloda	Angļu
Lapas (no-līdz)	13-24
Lapu skaits	12
Žurnāls	CEUR Workshop Proceedings
Sējums	1548
Publikācijas statuss	Publicēts - 2016
Pasākums	Student Research Forum Papers and Posters at SOFSEM 2016, SOFSEM-SP 2016 - Harrachov, Čehija Ilgums: 23 janv. 2016 → 28 janv. 2016

Citi faili un saites

Saite uz publikāciju Scopus

Citēt šo

@article{bf99b5aa91a1479f870c8e4fcbec2d9f,

title = "State complexity advantages of ultrametric automata",

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.",

author = "Maksims Dimitrijevs",

note = "Publisher Copyright: Copyright {\textcopyright} 2016 for the individual papers by the papers' authors.; Student Research Forum Papers and Posters at SOFSEM 2016, SOFSEM-SP 2016 ; Conference date: 23-01-2016 Through 28-01-2016",

year = "2016",

language = "English",

volume = "1548",

pages = "13--24",

journal = "CEUR Workshop Proceedings",

issn = "1613-0073",

publisher = "CEUR-WS",

}

TY - JOUR

T1 - State complexity advantages of ultrametric automata

AU - Dimitrijevs, Maksims

PY - 2016

Y1 - 2016

N2 - 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.

AB - 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.

UR - https://www.scopus.com/pages/publications/84964039193

M3 - Conference article

AN - SCOPUS:84964039193

SN - 1613-0073

VL - 1548

SP - 13

EP - 24

JO - CEUR Workshop Proceedings

JF - CEUR Workshop Proceedings

T2 - Student Research Forum Papers and Posters at SOFSEM 2016, SOFSEM-SP 2016

Y2 - 23 January 2016 through 28 January 2016

ER -

State complexity advantages of ultrametric automata

Kopsavilkums

Citi faili un saites

Nospiedums

Citēt šo