@article{2246,
abstract = {Muller games are played by two players moving a token along a graph; the winner is determined by the set of vertices that occur infinitely often. The central algorithmic problem is to compute the winning regions for the players. Different classes and representations of Muller games lead to problems of varying computational complexity. One such class are parity games; these are of particular significance in computational complexity, as they remain one of the few combinatorial problems known to be in NP ∩ co-NP but not known to be in P. We show that winning regions for a Muller game can be determined from the alternating structure of its traps. To every Muller game we then associate a natural number that we call its trap depth; this parameter measures how complicated the trap structure is. We present algorithms for parity games that run in polynomial time for graphs of bounded trap depth, and in general run in time exponential in the trap depth. },
author = {Grinshpun, Andrey and Phalitnonkiat, Pakawat and Rubin, Sasha and Tarfulea, Andrei},
issn = {03043975},
journal = {Theoretical Computer Science},
pages = {73 -- 91},
publisher = {Elsevier},
title = {{Alternating traps in Muller and parity games}},
doi = {10.1016/j.tcs.2013.11.032},
volume = {521},
year = {2014},
}
@inproceedings{475,
abstract = {First cycle games (FCG) are played on a finite graph by two players who push a token along the edges until a vertex is repeated, and a simple cycle is formed. The winner is determined by some fixed property Y of the sequence of labels of the edges (or nodes) forming this cycle. These games are traditionally of interest because of their connection with infinite-duration games such as parity and mean-payoff games. We study the memory requirements for winning strategies of FCGs and certain associated infinite duration games. We exhibit a simple FCG that is not memoryless determined (this corrects a mistake in Memoryless determinacy of parity and mean payoff games: a simple proof by Bj⋯orklund, Sandberg, Vorobyov (2004) that claims that FCGs for which Y is closed under cyclic permutations are memoryless determined). We show that θ (n)! memory (where n is the number of nodes in the graph), which is always sufficient, may be necessary to win some FCGs. On the other hand, we identify easy to check conditions on Y (i.e., Y is closed under cyclic permutations, and both Y and its complement are closed under concatenation) that are sufficient to ensure that the corresponding FCGs and their associated infinite duration games are memoryless determined. We demonstrate that many games considered in the literature, such as mean-payoff, parity, energy, etc., satisfy these conditions. On the complexity side, we show (for efficiently computable Y) that while solving FCGs is in PSPACE, solving some families of FCGs is PSPACE-hard. },
author = {Aminof, Benjamin and Rubin, Sasha},
booktitle = {Electronic Proceedings in Theoretical Computer Science, EPTCS},
location = {Grenoble, France},
pages = {83 -- 90},
publisher = {Open Publishing Association},
title = {{First cycle games}},
doi = {10.4204/EPTCS.146.11},
volume = {146},
year = {2014},
}
@inproceedings{495,
abstract = {An automaton with advice is a finite state automaton which has access to an additional fixed infinite string called an advice tape. We refine the Myhill-Nerode theorem to characterize the languages of finite strings that are accepted by automata with advice. We do the same for tree automata with advice.},
author = {Kruckman, Alex and Rubin, Sasha and Sheridan, John and Zax, Ben},
booktitle = {Proceedings GandALF 2012},
location = {Napoli, Italy},
pages = {238 -- 246},
publisher = {Open Publishing Association},
title = {{A Myhill Nerode theorem for automata with advice}},
doi = {10.4204/EPTCS.96.18},
volume = {96},
year = {2012},
}
@inproceedings{496,
abstract = {We study the expressive power of logical interpretations on the class of scattered trees, namely those with countably many infinite branches. Scattered trees can be thought of as the tree analogue of scattered linear orders. Every scattered tree has an ordinal rank that reflects the structure of its infinite branches. We prove, roughly, that trees and orders of large rank cannot be interpreted in scattered trees of small rank. We consider a quite general notion of interpretation: each element of the interpreted structure is represented by a set of tuples of subsets of the interpreting tree. Our trees are countable, not necessarily finitely branching, and may have finitely many unary predicates as labellings. We also show how to replace injective set-interpretations in (not necessarily scattered) trees by 'finitary' set-interpretations.},
author = {Rabinovich, Alexander and Rubin, Sasha},
location = {Dubrovnik, Croatia},
publisher = {IEEE},
title = {{Interpretations in trees with countably many branches}},
doi = {10.1109/LICS.2012.65},
year = {2012},
}