Facial reconstruction

Search LJMU Research Online

Browse Repository | Browse E-Theses

Integer Weighted Automata on Infinite Words

Halava, V, Harju, T, Niskanen, R and Potapov, I (2022) Integer Weighted Automata on Infinite Words. International Journal of Foundations of Computer Science. ISSN 0129-0541

HHNP_author_copy.pdf - Accepted Version

Download (494kB) | Preview


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.

Item Type: Article
Additional Information: Electronic version of an article published as International Journal of Foundations of Computer Science, https://doi.org/10.1142/S0129054122440014 © World Scientific Publishing Company
Uncontrolled Keywords: 08 Information and Computing Sciences; Computation Theory & Mathematics
Subjects: Q Science > QA Mathematics > QA75 Electronic computers. Computer science
Divisions: Computer Science & Mathematics
Publisher: World Scientific Publishing
SWORD Depositor: A Symplectic
Date Deposited: 26 Oct 2022 13:40
Last Modified: 31 Oct 2023 00:50
DOI or ID number: 10.1142/S0129054122440014
URI: https://researchonline.ljmu.ac.uk/id/eprint/17943
View Item View Item