3 papers
cs.FL2026
Layered automata: A canonical model for automata over infinite words
Antonio Casares, Christof Löding, Igor Walukiewicz
We introduce layered automata, a subclass of alternating parity automata that generalises deterministic automata. Assuming a consistency property, these automata are history determ…
cs.FL2025
Transition-based vs stated-based acceptance for automata over infinite words
Antonio Casares
Automata over infinite objects are a well-established model with applications in logic and formal verification. Traditionally, acceptance in such automata is defined based on the s…
cs.FL2023
Simple and tight complexity lower bounds for solving Rabin games
Antonio Casares, Marcin Pilipczuk, Michał Pilipczuk +2
We give a simple proof that assuming the Exponential Time Hypothesis (ETH), determining the winner of a Rabin game cannot be done in time , where $k…