Buchumschlag

Attractors Is All You Need: Parity Games In Polynomial Time

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
1. Verfasser:	van der Heijden, Rick
Format:	Preprint
Veröffentlicht:	2025
Schlagworte:	Data Structures and Algorithms Computational Complexity Formal Languages and Automata Theory Computer Science and Game Theory Logic in Computer Science
Online-Zugang:	Acceder al recurso
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!

Ähnliche Einträge

The Existential Theory of the Reals as a Complexity Class: A Compendium
von: Schaefer, Marcus, et al.
Veröffentlicht: (2024)

Data Structures for Finite Downsets of Natural Vectors: Theory and Practice
von: Cadilhac, Michaël, et al.
Veröffentlicht: (2025)

A Myhill-Nerode Theorem for Generalized Automata, with Applications to Pattern Matching and Compression
von: Cotumaccio, Nicola
Veröffentlicht: (2023)

Constant-delay enumeration for SLP-compressed documents
von: Muñoz, Martín, et al.
Veröffentlicht: (2022)

A positional $\mathbfΠ^0_3$-complete objective
von: Casares, Antonio, et al.
Veröffentlicht: (2024)

The Complexity of Pure Strategy Relevant Equilibria in Concurrent Games
von: Bhaduri, Purandar
Veröffentlicht: (2025)

Dynamic direct (ranked) access of MSO query evaluation over SLP-compressed strings
von: Muñoz, Martín
Veröffentlicht: (2026)

The Power of Counting Steps in Quantitative Games
von: Bose, Sougata, et al.
Veröffentlicht: (2024)

Games on Graphs: From Logic and Automata to Algorithms
von: Fijalkow, Nathanaël, et al.
Veröffentlicht: (2023)

Arena-Independent Finite-Memory Determinacy in Stochastic Games
von: Bouyer, Patricia, et al.
Veröffentlicht: (2021)

Hardness of Regular Expression Matching with Extensions
von: Nogami, Taisei, et al.
Veröffentlicht: (2026)

Symbolic Functional Decomposition: A Reconfiguration Approach
von: Oliveira, Mateus de Oliveira, et al.
Veröffentlicht: (2026)

Finding Diverse Strings and Longest Common Subsequences in a Graph
von: Shida, Yuto, et al.
Veröffentlicht: (2024)

The NFA Acceptance Hypothesis: Non-Combinatorial and Dynamic Lower Bounds
von: Bringmann, Karl, et al.
Veröffentlicht: (2023)

Proceedings Fifteenth International Symposium on Games, Automata, Logics, and Formal Verification
von: Achilleos, Antonis, et al.
Veröffentlicht: (2024)

Parity Games on Temporal Graphs
von: Austin, Pete, et al.
Veröffentlicht: (2023)

Reasoning about Strategic Abilities in Stochastic Multi-agent Systems
von: Zhang, Yedi, et al.
Veröffentlicht: (2024)

On the Existence of Reactive Strategies Resilient to Delay
von: Fränzle, Martin, et al.
Veröffentlicht: (2023)

Half-Positional Objectives Recognized by Deterministic Büchi Automata
von: Bouyer, Patricia, et al.
Veröffentlicht: (2022)

Different Strokes in Randomised Strategies: Revisiting Kuhn's Theorem under Finite-Memory Assumptions
von: Main, James C. A., et al.
Veröffentlicht: (2022)

Fine-Grained Complexity of Regular Path Queries
von: Casel, Katrin, et al.
Veröffentlicht: (2021)

Non-commutative linear logic fragments with sub-context-free complexity
von: Nishimiya, Yusaku, et al.
Veröffentlicht: (2025)

Nets-within-Nets through the Lens of Data Nets
von: Di Cosmo, Francesco, et al.
Veröffentlicht: (2025)

On Higher Order Busy Beaver Function
von: Cao, Zining
Veröffentlicht: (2025)

A Complexity Dichotomy for Semilinear Target Sets in Automata with One Counter
von: Shakiba, Yousef, et al.
Veröffentlicht: (2025)

Reachability in Geometrically $d$-Dimensional VASS
von: Fu, Yuxi, et al.
Veröffentlicht: (2025)

The $\mathsf{AC}^0$-Complexity Of Visibly Pushdown Languages
von: Göller, Stefan, et al.
Veröffentlicht: (2023)

Stochastic Process Turing Machines
von: Wolpert, David, et al.
Veröffentlicht: (2024)

The Complexity of Nested Reset Counter Systems
von: Balasubramanian, A. R., et al.
Veröffentlicht: (2026)

Attractors of Parikh mapping iterations
von: Chunikhin, Alexander
Veröffentlicht: (2024)

From Width-Based Model Checking to Width-Based Automated Theorem Proving
von: Oliveira, Mateus de Oliveira, et al.
Veröffentlicht: (2022)

Characterizing the Polynomial-Time Minimizable $ω$-Automata
von: Radi, Bader Abu, et al.
Veröffentlicht: (2025)

Rabin Games and Colourful Universal Trees
von: Majumdar, Rupak, et al.
Veröffentlicht: (2024)

Counting and Sampling Traces in Regular Languages
von: de Colnet, Alexis, et al.
Veröffentlicht: (2025)

Cypher is Turing-Complete: A Formal Proof via 2-Counter Machine Simulation
von: Halftermeyer, Pierre
Veröffentlicht: (2026)

Taming Infinity one Chunk at a Time: Concisely Represented Strategies in One-Counter MDPs
von: Ajdarów, Michal, et al.
Veröffentlicht: (2025)

Faster and Smaller Solutions of Obliging Games
von: Hausmann, Daniel, et al.
Veröffentlicht: (2024)

Computing Threshold Budgets in Discrete-Bidding Games
von: Avni, Guy, et al.
Veröffentlicht: (2022)

Winning Strategies for the Synchronization Game on Subclasses of Finite Automata
von: Fernau, Henning, et al.
Veröffentlicht: (2024)

An Automata-Based Approach to Games with $ω$-Automatic Preferences
von: Bruyère, Véronique, et al.
Veröffentlicht: (2026)