Halava, Vesa, Harju, Tero, Niskanen, Reino 
ORCID: 0000-0002-2210-1481 and PotapoV, Igor
(2021)
Integer Weighted Automata on Infinite Words.
In: Developments in Language Theory, 2021-8-16 - 2021-8-20, Porto, Portugal.
|
Text
Infinite_weighted_automata.pdf - Author Accepted Manuscript Download (331kB) | Preview |
Abstract
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.
| Item Type: | Conference or Workshop Item (Unspecified) |
|---|---|
| Divisions: | Faculty of Science and Engineering > School of Electrical Engineering, Electronics and Computer Science |
| Depositing User: | Symplectic Admin |
| Date Deposited: | 21 Jun 2021 07:38 |
| Last Modified: | 22 Nov 2023 22:42 |
| DOI: | 10.1007/978-3-030-81508-0_14 |
| Related URLs: | |
| URI: | https://livrepository.liverpool.ac.uk/id/eprint/3127135 |
Dimensions
Dimensions
