B1 Kirjoitus tieteellisessä aikakauslehdessä
Weighted Automata on Infinite Words in the Context of Attacker-Defender Games




Julkaisun tekijät: Halava V, Harju T, Niskanen R, Potapov I
Julkaisuvuosi: 2014
Journal: TUCS Publication Series
Kirjan nimi *: Evolving computability
Tietokannassa oleva lehden nimi: EVOLVING COMPUTABILITY
Sarjan nimi: Lecture notes in computer science
Volyymi: 1118
ISBN: 978-3-319-20027-9
ISSN: 0302-9743

Tiivistelmä


We consider several infinite-state Attacker-Defender games with reachability objectives. The results of the paper are twofold. Firstly we prove a new language-theoretic result for weighted automata on infinite words and show its encoding into the framework of Attacker-Defender games. Secondly we use this novel concept to prove undecidability for checking existence of a winning strategy in several low-dimensional mathematical games including vector reachability games, word games and braid games.



Last updated on 2019-21-08 at 22:26