A4 Vertaisarvioitu artikkeli konferenssijulkaisussa
Integer Weighted Automata on Infinite Words
Tekijät: Halava Vesa, Harju Tero, Niskanen Reino, Potapov Igor
Toimittaja: Moreira Nelma, Reis Rogério
Konferenssin vakiintunut nimi: International Conference on Developments in Language Theory
Kustantaja: Springer Science and Business Media Deutschland GmbH
Kustannuspaikka: Cham
Julkaisuvuosi: 2021
Journal: Lecture Notes in Computer Science
Kokoomateoksen nimi: Developments in Language Theory: 25th International Conference, DLT 2021, Porto, Portugal, August 16–20, 2021, Proceedings
Tietokannassa oleva lehden nimi: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Sarjan nimi: Lecture Notes in Computer Science
Vuosikerta: 12811
Aloitussivu: 167
Lopetussivu: 179
ISBN: 978-3-030-81507-3
eISBN: 978-3-030-81508-0
ISSN: 0302-9743
DOI: https://doi.org/10.1007/978-3-030-81508-0_14
In this paper we combine two classical generalisations of finite automata (weighted automata and automata on infinite words) into a model of integer weighted automata on infinite words and study the universality and the emptiness problems under zero weight acceptance. We show that the universality problem is undecidable for three-state automata by a direct reduction from the infinite Post correspondence problem. We also consider other more general acceptance conditions as well as their complements with respect to the universality and the emptiness problems. Additionally, we build a universal integer weighted automaton where the automaton is fixed and the word problem is undecidable.
