Weighted Automata on Infinite Words in the Context of Attacker-Defender Games - UTU Tutkimustietojärjestelmä

A4 Vertaisarvioitu artikkeli konferenssijulkaisussa

Weighted Automata on Infinite Words in the Context of Attacker-Defender Games

Tekijät: Halava V, Harju T, Niskanen R, Potapov I

Konferenssin vakiintunut nimi: Computability in Europe

Kustantaja: SPRINGER-VERLAG NEW YORK, MS INGRID CUNNINGHAM, 175 FIFTH AVE, NEW YORK, NY 10010 USA

Julkaisuvuosi: 2015

Journal: Lecture Notes in Computer Science

Tietokannassa oleva lehden nimi: EVOLVING COMPUTABILITY

Lehden akronyymi: LECT NOTES COMPUT SC

Vuosikerta: 9136

Aloitussivu: 206

Lopetussivu: 215

Sivujen määrä: 10

ISBN: 978-3-319-20027-9

ISSN: 0302-9743

DOI: https://doi.org/10.1007/978-3-319-20028-6_21

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.