Halava, V, Harju, T, Niskanen, R ORCID: 0000-0002-2210-1481 and Potapov, I
(2017)
Weighted Automata on Infinite Words in the Context of
Attacker-Defender Games.
Information and Computation, 255 (1).
pp. 27-44.
This is the latest version of this item.
Text (admin)
2017-05-12T11:23:27Z.atom - Unspecified Access to this file is embargoed until Unspecified. Download (9kB) |
|
Text
HHNP15IandC_elements.pdf - Author Accepted Manuscript Download (505kB) |
Abstract
The paper is devoted to several infinite-state Attacker–Defender games with reachability objectives. We prove the undecidability of checking for the existence of a winning strategy in several low-dimensional mathematical games including vector reachability games, word games and braid games. To prove these results, we consider a model of weighted automata operating on infinite words and prove that the universality problem is undecidable for this new class of weighted automata. We show that the universality problem is undecidable by using a non-standard encoding of the infinite Post correspondence problem.
Item Type: | Article |
---|---|
Uncontrolled Keywords: | Weighted automata on infinite words, Attacker–Defender games, Vector reachability, Braid group, Undecidability |
Depositing User: | Symplectic Admin |
Date Deposited: | 13 Jun 2017 11:24 |
Last Modified: | 19 Jan 2023 07:03 |
DOI: | 10.1016/j.ic.2017.05.001 |
Related URLs: | |
URI: | https://livrepository.liverpool.ac.uk/id/eprint/3007966 |
Available Versions of this Item
-
Weighted Automata on Infinite Words in the Context of Attacker-Defender Games. (deposited 08 May 2017 10:46)
- Weighted Automata on Infinite Words in the Context of Attacker-Defender Games. (deposited 13 Jun 2017 11:24) [Currently Displayed]