B1 Vertaisarvioimaton kirjoitus tieteellisessä lehdessä

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




TekijätHalava V, Harju T, Niskanen R, Potapov I

ToimittajaArnold Beckmann, Victor Mitrana, Mariya Soskova

Konferenssin vakiintunut nimi11th Conference on computability in Europe, CiE 2015

Julkaisuvuosi2014

JournalTUCS Publication Series

Kokoomateoksen nimiEvolving computability

Tietokannassa oleva lehden nimiEVOLVING COMPUTABILITY

Sarjan nimiLecture notes in computer science

Vuosikerta1118

ISBN978-3-319-20027-9

ISSN0302-9743

Verkko-osoitehttp://tucs.fi/publications/view/?pub_id=tHaHaNiPo14b


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 2024-26-11 at 17:04