Where academic tradition
meets the exciting future

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

Vesa Halava, Tero Harju, Reino Niskanen, Igor Potapov, Weighted Automata on Infinite Words in the Context of Attacker-Defender Games. TUCS Technical Reports 1118, TUCS, 2014.

Abstract:

We consider infinite-state Attacker-Defender games with reachability objectives.
The results of the paper are twofold. Firstly we show a number of previously
defined and new Attacker-Defender games (vector addition games,
matrix games, word games, braid games) where the problem of finding a
winning strategy is undecidable. Secondly we prove new language-theoretic
result for weighted automata on infinite words which was successfully used
in the context of two-payer games

Files:

Full publication in PDF-format

BibTeX entry:

@TECHREPORT{tHaHaNiPo14b,
  title = {Weighted Automata on Infinite Words in the Context of Attacker-Defender Games},
  author = {Halava, Vesa and Harju, Tero and Niskanen, Reino and Potapov, Igor},
  number = {1118},
  series = {TUCS Technical Reports},
  publisher = {TUCS},
  year = {2014},
  keywords = {Reachability problems, Attacker-Defender games, Winning strategy, Weighted automata, Infinite words, Undecidability},
  ISBN = {978-952-12-3096-7},
}

Belongs to TUCS Research Unit(s): FUNDIM, Fundamentals of Computing and Discrete Mathematics

Edit publication