Prefix-independent objectives over finite colors are positionally determined on vertex-colored one- and two-player games iff they are generalized parity objectives on ordered pairs of colors.
Allen Emerson and Charanjit S
5 Pith papers cite this work, alongside 742 external citations. Polarity classification is still indexing.
5
Pith papers citing it
742
external citations · external index
representative citing papers
The Random-Action-Removal algorithm solves n-state, m-action 2-player games in e^{O(√(n ln(m/n)))} time, improving the previous e^{O(√(n ln(m/√n)))} bound by exploiting the hypercube structure of the game.
Prefix-independent Σ₀² objectives with neutral letters are positional over arbitrary graphs exactly when recognized by history-deterministic monotone co-Büchi automata over countable ordinals, with proofs for mean-payoff positionality and a completeness lifting from finite graphs.
Provides complexity results for the constrained existence problem of five equilibrium notions in multiplayer graph games.
The paper gives a new proof that subsumption in FL_reg and FL_bot_reg with TBoxes is ExpTime-complete by reduction to parity pushdown games, and reproves the PSpace result without TBoxes.
citing papers explorer
-
Positional Determinacy with Colored Vertices: a 1-to-2-Player Lift
Prefix-independent objectives over finite colors are positionally determined on vertex-colored one- and two-player games iff they are generalized parity objectives on ordered pairs of colors.
-
Improved subexponential analysis of the Random-Action-Removal algorithm for 2-player turn-based games and non-binary AUSOs
The Random-Action-Removal algorithm solves n-state, m-action 2-player games in e^{O(√(n ln(m/n)))} time, improving the previous e^{O(√(n ln(m/√n)))} bound by exploiting the hypercube structure of the game.
-
Positionality in $\Sigma_0^2$ and a completeness result
Prefix-independent Σ₀² objectives with neutral letters are positional over arbitrary graphs exactly when recognized by history-deterministic monotone co-Büchi automata over countable ordinals, with proofs for mean-payoff positionality and a completeness lifting from finite graphs.
-
Equilibria in Multiplayer Graph Games: An Algorithmic Study
Provides complexity results for the constrained existence problem of five equilibrium notions in multiplayer graph games.
-
Subsumption in $\mathcal{FL}_{\bot \mathit{reg}}$ with TBoxes Is in ExpTime
The paper gives a new proof that subsumption in FL_reg and FL_bot_reg with TBoxes is ExpTime-complete by reduction to parity pushdown games, and reproves the PSpace result without TBoxes.