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




Halava V, Harju T, Niskanen R, Potapov I

Arnold Beckmann, Victor Mitrana, Mariya Soskova

11th Conference on computability in Europe, CiE 2015

2014

TUCS Publication Series

Evolving computability

EVOLVING COMPUTABILITY

Lecture notes in computer science

1118

978-3-319-20027-9

0302-9743

http://tucs.fi/publications/view/?pub_id=tHaHaNiPo14b



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