Integer Weighted Automata on Infinite Words
: Halava Vesa, Harju Tero, Niskanen Reino, Potapov Igor
: Moreira Nelma, Reis Rogério
: International Conference on Developments in Language Theory
Publisher: Springer Science and Business Media Deutschland GmbH
: Cham
: 2021
: Lecture Notes in Computer Science
: Developments in Language Theory: 25th International Conference, DLT 2021, Porto, Portugal, August 16–20, 2021, Proceedings
: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
: Lecture Notes in Computer Science
: 12811
: 167
: 179
: 978-3-030-81507-3
: 978-3-030-81508-0
: 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.