A4 Refereed article in a conference publication
Integer Weighted Automata on Infinite Words
Authors: Halava Vesa, Harju Tero, Niskanen Reino, Potapov Igor
Editors: Moreira Nelma, Reis Rogério
Conference name: International Conference on Developments in Language Theory
Publisher: Springer Science and Business Media Deutschland GmbH
Publishing place: Cham
Publication year: 2021
Journal: Lecture Notes in Computer Science
Book title : Developments in Language Theory: 25th International Conference, DLT 2021, Porto, Portugal, August 16–20, 2021, Proceedings
Journal name in source: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Series title: Lecture Notes in Computer Science
Volume: 12811
First page : 167
Last page: 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.
