A1 Vertaisarvioitu alkuperäisartikkeli tieteellisessä lehdessä
Weighted automata on infinite words in the context of Attacker-Defender games
Tekijät: Halava V, Harju T, Niskanen R, Potapov I
Kustantaja: ACADEMIC PRESS INC ELSEVIER SCIENCE
Kustannuspaikka: SAN DIEGO
Julkaisuvuosi: 2017
Journal: Information and Computation
Tietokannassa oleva lehden nimi: INFORMATION AND COMPUTATION
Lehden akronyymi: INFORM COMPUT
Vuosikerta: 255
Aloitussivu: 27
Lopetussivu: 44
Sivujen määrä: 18
ISSN: 0890-5401
eISSN: 1090-2651
DOI: https://doi.org/10.1016/j.ic.2017.05.001
Verkko-osoite: 10.1016/j.ic.2017.05.001
Tiivistelmä
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. (C) 2017 Elsevier Inc. All rights reserved.
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. (C) 2017 Elsevier Inc. All rights reserved.
Turun yliopiston Tutkimustietojärjestelmän portaali