Cover Image

A positional $\mathbfΠ^0_3$-complete objective

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Casares, Antonio, Ohlmann, Pierre, Vandenhove, Pierre
Format:	Preprint
Published:	2024
Subjects:	Computational Complexity Formal Languages and Automata Theory Computer Science and Game Theory Logic in Computer Science
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

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

Characterising memory in infinite games
by: Casares, Antonio, et al.
Published: (2022)

Arena-Independent Finite-Memory Determinacy in Stochastic Games
by: Bouyer, Patricia, et al.
Published: (2021)

The Power of Counting Steps in Quantitative Games
by: Bose, Sougata, et al.
Published: (2024)

Positional $ω$-regular languages
by: Casares, Antonio, et al.
Published: (2024)

Games on Graphs: From Logic and Automata to Algorithms
by: Fijalkow, Nathanaël, et al.
Published: (2023)

The memory of $ω$-regular and BC($Σ_2^0$) objectives
by: Casares, Antonio, et al.
Published: (2025)

Expregular functions
by: Colcombet, Thomas, et al.
Published: (2026)

The Complexity of Pure Strategy Relevant Equilibria in Concurrent Games
by: Bhaduri, Purandar
Published: (2025)

Cypher is Turing-Complete: A Formal Proof via 2-Counter Machine Simulation
by: Halftermeyer, Pierre
Published: (2026)

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

Attractors Is All You Need: Parity Games In Polynomial Time
by: van der Heijden, Rick
Published: (2025)

Reasoning about Strategic Abilities in Stochastic Multi-agent Systems
by: Zhang, Yedi, et al.
Published: (2024)

On the Existence of Reactive Strategies Resilient to Delay
by: Fränzle, Martin, et al.
Published: (2023)

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

Non-commutative linear logic fragments with sub-context-free complexity
by: Nishimiya, Yusaku, et al.
Published: (2025)

A Complexity Dichotomy for Semilinear Target Sets in Automata with One Counter
by: Shakiba, Yousef, et al.
Published: (2025)

Stochastic Process Turing Machines
by: Wolpert, David, et al.
Published: (2024)

Proceedings Fifteenth International Symposium on Games, Automata, Logics, and Formal Verification
by: Achilleos, Antonis, et al.
Published: (2024)

Nets-within-Nets through the Lens of Data Nets
by: Di Cosmo, Francesco, et al.
Published: (2025)

On Higher Order Busy Beaver Function
by: Cao, Zining
Published: (2025)

Reachability in Geometrically $d$-Dimensional VASS
by: Fu, Yuxi, et al.
Published: (2025)

The Complexity of Nested Reset Counter Systems
by: Balasubramanian, A. R., et al.
Published: (2026)

LTL$_f$ Learning Meets Boolean Set Cover
by: Bathie, Gabriel, et al.
Published: (2025)

A Myhill-Nerode Characterization and Active Learning for One-Clock Timed Automata
by: Doveri, Kyveli, et al.
Published: (2026)

Counting and Sampling Traces in Regular Languages
by: de Colnet, Alexis, et al.
Published: (2025)

A Uniform Framework for Language Inclusion Problems
by: Doveri, Kyveli, et al.
Published: (2024)

A Framework for Universality in Physics, Computer Science, and Beyond
by: Gonda, Tomáš, et al.
Published: (2023)

CMSO-transducing tree-like graph decompositions
by: Campbell, Rutger, et al.
Published: (2024)

Weighted basic parallel processes and combinatorial enumeration
by: Clemente, Lorenzo
Published: (2024)

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

Mixing Any Cocktail with Limited Ingredients: On the Structure of Payoff Sets in Multi-Objective POMDPs and its Impact on Randomised Strategies
by: Main, James C. A., et al.
Published: (2025)

A formal query language and automata model for aggregation in complex event recognition
by: Bourhis, Pierre, et al.
Published: (2026)

Kofola 1.0: A Modular Approach to ω-Regular Complementation and Inclusion Checking (Technical Report)
by: Alexaj, Ondrej, et al.
Published: (2026)

A complete formalization of Fermat's Last Theorem for regular primes in Lean
by: Best, Alex, et al.
Published: (2024)

AutoQ 2.0: From Verification of Quantum Circuits to Verification of Quantum Programs (Technical Report)
by: Chen, Yu-Fang, et al.
Published: (2024)

Simulation by Rounds of Letter-to-Letter Transducers
by: Nassar, Antonio Abu, et al.
Published: (2021)

Winning Strategies for the Synchronization Game on Subclasses of Finite Automata
by: Fernau, Henning, et al.
Published: (2024)

Non-cooperative rational synthesis problem for probabilistic strategies
by: Koide, So, et al.
Published: (2024)

Faster and Smaller Solutions of Obliging Games
by: Hausmann, Daniel, et al.
Published: (2024)