Antonio Casares Santos

I am a postdoctoral researcher in Theoretical Computer Science at the RPTU, University of Kaiserslautern-Landau (Germany), working in the group of Anthony Lin.

My research interests lie in the intersection of logic, formal languages and games on graphs. More specifically, my research focuses on ω-automata, algorithms for solving infinite duration games and finite model theory.

Before coming to Kaiserslautern, I was a postdoc at the University of Warsaw (Poland) with Mikołaj Bojańczyk. I received my doctoral degree in 2023 from the University of Bordeaux, under the supervision of Nathanaël Fijalkow and Igor Walukiewicz. Before that, I obtained my master's degree in Mathematical Logic and Foundations of Computer Science at Université de Paris-Cité (France).

You will find more information in my CV.

Links:

I gathered some links with advice about different aspects of academic life here.

I support:

PhD Thesis

I defended my PhD thesis entitled Structural properties of automata over infinite words and memory for games on 23 November 2023. Below you can find:

• Manuscript of the thesis (pdf)
• How to cite (bibtex)
• Slides (Opens in a browser. Visualization in different browsers/computers might slightly differ.)

Research

A full list of my publications can also be found in my dblp and Google Scholar sites.

Book chapters

• Chapter Positionality and Memory in the book Games on Graphs: From Logic and Automata to Algorithms (coauthored by Pierre Ohlmann and Pierre Vandenhove) - arxiv link - bibtex of chapter.

Surveys

• Transition-based vs stated-based acceptance for automata over infinite words - pdf.

Publications in peer-reviewed journals and conference proceedings

• The memory of ω-regular and BC(Σ₂) objectives (with Pierre Ohlmann). In: ICALP 2025 - conference version- bibtex.
• Fast value iteration: A uniform approach to efficient algorithms for energy games (with Michaël Cadilhac and Pierre Ohlmann). In: TACAS 2025 - pdf.
• From Muller to Parity and Rabin Automata: Optimal Transformations Preserving (History) Determinism (with Thomas Colcombet, Nathanaël Fijalkow and Karoliina Lehtinen). In: TheoretiCS 2024 - pdf - bibtex.
• Positional ω-regular languages (with Pierre Ohlmann). In: LICS 2024 - short version - full version- bibtex.
• On the Minimisation of Deterministic and History-Deterministic Generalised (co)Büchi Automata (with Olivier Idir, Denis Kuperberg, Corto Mascle and Aditya Prakash). In: CSL 2025 - pdf.
• The Complexity of Simplifying ω-Automata through the Alternating Cycle Decomposition (with Corto Mascle). In: MFCS 2024 - short version - full version- bibtex.
• Simple and Tight Complexity Lower Bounds for Solving Rabin Games (with Marcin Pilipczuk, Michał Pilipczuk, Uéverton S. Souza, K. S. Thejaswini). In: SOSA 2024 - pdf - bibtex.
• Characterising Memory in Infinite Games (with Pierre Ohlmann). In: ICALP 2023 - full version - short version - bibtex.
• Half-Positional Objectives Recognized by Deterministic Büchi Automata (with Patricia Bouyer, Mickael Randour and Pierre Vandenhove). In: CONCUR 2022 & IJCAI 2023 & LMCS - journal version - conf version - extended abstract - bibtex.
• On the Size of Good-For-Games Rabin Automata and Its Link with the Memory in Muller Games (with Thomas Colcombet and Karoliina Lehtinen). In: ICALP 2022 - pdf - bibtex.
• Practical Applications of the Alternating Cycle Decomposition (with Alexandre Duret-Lutz, Klara J. Meyer, Florian Renkin and Salomon Sickert). In: TACAS 2022 - full version - bibtex.
• On the Minimisation of Transition-Based Rabin Automata and the Chromatic Memory Requirements of Muller Conditions. In: CSL 2022 - short version - full version - bibtex. Best Student Paper Award.
• Optimal Transformations of Games and Automata using Muller Conditions (with Thomas Colcombet and Nathanaël Fijalkow). In: ICALP 2021 - conf version - journal version - bibtex.

Preprints

• Infinite lexicographic products of positional objectives (with Pierre Ohlmann, Michał Skrzypczak and Igor Walukiewicz). Submitted to: LMCS - pdf.