Showing cs.FLShow all
3 papers · 1 filter
cs.FL2026
Automata for MSO over Infinite Trees with Quantification over Borel Sets of Branches
Mikołaj Bojańczyk, Antonio Casares, Sven Manthe +1
Rabin's Tree Theorem says that the MSO theory of the infinite binary tree is decidable. Shelah showed that MSO logic becomes undecidable if this tree is extended to $2^{\le ω…
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…