Weighted automata on infinite words in the context of Attacker-Defender games

Vesa Halava, Tero Harju, Reino Niskanen, Igor Potapov

We consider 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.

Knowledge Graph

arrow_drop_up

Comments

Sign up or login to leave a comment