Refereed journal article or data article (A1)

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




List of AuthorsHalava V, Harju T, Niskanen R, Potapov I

PublisherACADEMIC PRESS INC ELSEVIER SCIENCE

PlaceSAN DIEGO

Publication year2017

JournalInformation and Computation

Journal name in sourceINFORMATION AND COMPUTATION

Journal acronymINFORM COMPUT

Volume number255

Start page27

End page44

Number of pages18

ISSN0890-5401

eISSN1090-2651

DOIhttp://dx.doi.org/10.1016/j.ic.2017.05.001

URL10.1016/j.ic.2017.05.001


Abstract
The paper is devoted to several infinite-state Attacker-Defender games with reachability objectives. We prove the undecidability of checking for the existence of a winning strategy in several low-dimensional mathematical games including vector reachability games, word games and braid games. To prove these results, we consider a model of weighted automata operating on infinite words and prove that the universality problem is undecidable for this new class of weighted automata. We show that the universality problem is undecidable by using a non-standard encoding of the infinite Post correspondence problem. (C) 2017 Elsevier Inc. All rights reserved.


Last updated on 2021-24-06 at 11:43