A1 Vertaisarvioitu alkuperäisartikkeli tieteellisessä lehdessä
Integer Weighted Automata on Infinite Words
Tekijät: Halava Vesa, Harju Tero, Niskanen Reino, Potapov Igor
Kustantaja: WORLD SCIENTIFIC PUBL CO PTE LTD
Julkaisuvuosi: 2023
Journal: International Journal of Foundations of Computer Science
Tietokannassa oleva lehden nimi: INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE
Lehden akronyymi: INT J FOUND COMPUT S
Sivujen määrä: 20
ISSN: 0129-0541
eISSN: 1793-6373
DOI: https://doi.org/10.1142/S0129054122440014
Verkko-osoite: https://www.worldscientific.com/doi/10.1142/S0129054122440014
Rinnakkaistallenteen osoite: https://researchonline.ljmu.ac.uk/id/eprint/17943/1/HHNP_author_copy.pdf
Tiivistelmä
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 with fixed transitions. This automaton has an additional integer input that allows it to simulate any semi-Thue system.
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 with fixed transitions. This automaton has an additional integer input that allows it to simulate any semi-Thue system.
Turun yliopiston Tutkimustietojärjestelmän portaali