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

PublisherSpringer 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

DOIhttps://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.



Last updated on 2024-26-11 at 12:49