Monoidal Closed Categories of Tree Automata
Résumé
We propose a fibred monoidal closed category of automata on infinite trees, with existential and universal quantifications. Our notion is inspired from Dialectica-like categories, suggested by the specific logical form of the transitions of alternating automata, and which gives the shape of linear implication automata and a notion of ∃∀-normal form of automata. We thus obtain a realizability interpretation where proofs in a first-order multiplicative linear logic over automata are interpreted as winning strategies in a generalization of usual acceptance games.
Origine : Fichiers produits par l'(les) auteur(s)
Loading...