Fibred Categories of Tree Automata
summary
Builds a category whose objects are tree automata and morphisms = strategies in the acceptance games and shows concrete constructions: product and unit, contraction only for nondeterministic automata, and existential/universal quantification as adjoints given by moving moves between players. Translates alternating to nondeterministic automata via the usual exponential simulation and uses game semantics to encode MSO on infinite trees and words, yielding an operational account of quantifier elimination and program extraction for the word case.
AI-written summary · about
chapters (9)
- 0:00Categories of automata
- 3:45Automata as games
- 7:19Alternating automata definition
- 12:00Automata games structure
- 22:03Categorical setting examples
- 25:34Monoidal and Cartesian structure
- 27:00Quantification in model
- 28:37Exponential modality rules
- 30:53MSO to automata translation
related talks
24mChoice Trees: Representing Nondeterministic, Recursive, and Impure Programs in C...
18mLanguages with Decidable Learning: A Meta-theorem
20mPolyregular functions on unordered trees of bounded height
24mBounded Treewidth, Multiple Context-Free Grammars, and Downward Closures
30mComputation-Tree Semantics: An Algorithmic Approach to Structurally Defined Relations
02h 24mCategory Theory Track
20mAlgebras for Deterministic Computation are Inherently Incomplete
30mRecognizing regular patterns in mixed type sequences using Symbolic Finite Automata