2 citations · 3 across the 3 of their papers we have counts for
6 papers · 1 filter
Collapsible Pushdown Parity Games
Christopher H. Broadbent, Arnaud Carayol, Matthew Hague +3
This paper studies a large class of two-player perfect-information turn-based parity games on infinite graphs, namely those generated by collapsible pushdown automata. The main mot…
How Good Is a Strategy in a Game With Nature?
Arnaud Carayol, Olivier Serre
We consider games with two antagonistic players --- Éloïse (modelling a program) and Abélard (modelling a byzantine environment) --- and a third, unpredictable and uncontrollable p…
Alternating Tree Automata with Qualitative Semantics
Raphaël Berthon, Nathanaël Fijalkow, Emmanuel Filiot +7
We study alternating automata with qualitative semantics over infinite binary trees: alternation means that two opposing players construct a decoration of the input tree called a r…
Emptiness of Stack Automata is NEXPTIME-complete: A Correction
Christopher Broadbent, Arnaud Carayol, Matthew Hague +1
A saturation algorithm for collapsible pushdown systems was published in ICALP 2012. This work introduced a class of stack automata used to recognised regular sets of collapsible p…
Two-way Two-tape Automata
Olivier Carton, Léo Exibard, Olivier Serre
In this article we consider two-way two-tape (alternating) automata accepting pairs of words and we study some closure properties of this model. Our main result is that such altern…
Counting Branches in Trees Using Games
Arnaud Carayol, Axel Haddad, Olivier Serre
We study finite automata running over infinite binary trees. A run of such an automaton is usually said to be accepting if all its branches are accepting. In this article, we relax…