Integer Weighted Automata on Infinite Words

Halava, Vesa, Harju, Tero, Niskanen, Reino and Potapov, Igor (2023) Integer Weighted Automata on Infinite Words. INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE, 34 (02N03). pp. 163-182.

Access the full-text of this item by clicking on the Open Access link.

Official URL: http://dx.doi.org/10.1142/s0129054122440014

Abstract

<jats:p> 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. </jats:p>

Item Type:	Article
Uncontrolled Keywords:	Weighted automata, automata on infinite words, undecidability
Depositing User:	Symplectic Admin
Date Deposited:	27 Oct 2022 07:46
Last Modified:	18 Apr 2023 22:57
DOI:	10.1142/S0129054122440014
Open Access URL:	https://researchonline.ljmu.ac.uk/id/eprint/17943/
Related URLs:	Author Publisher
URI:	https://livrepository.liverpool.ac.uk/id/eprint/3165801