Document Open Access Logo

Fibrations of Tree Automata

Author Colin Riba

PDF
Thumbnail PDF

File

LIPIcs.TLCA.2015.302.pdf
  • Filesize: 0.54 MB
  • 15 pages

Document Identifiers

Author Details

Colin Riba

Cite As Get BibTex

Colin Riba. Fibrations of Tree Automata. In 13th International Conference on Typed Lambda Calculi and Applications (TLCA 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 38, pp. 302-316, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015) https://doi.org/10.4230/LIPIcs.TLCA.2015.302

Abstract

We propose a notion of morphisms between tree automata based on game semantics. Morphisms are winning strategies on a synchronous restriction of the linear implication between acceptance games. This leads to split indexed categories, with substitution based on a suitable notion of synchronous tree function. By restricting to tree functions issued from maps on alphabets, this gives a fibration of tree automata. We then discuss the (fibrewise) monoidal structure issued from the synchronous product of automata. We also discuss how a variant of the usual projection operation on automata leads to an existential quantification in the fibered sense. Our notion of morphism is correct (it respects language inclusion), and in a weaker sense also complete.

Subject Classification

Keywords
  • Tree automata
  • Game semantics
  • Categorical logic.

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. S. Abramsky. Semantics of Interaction. In A. M. Pitts and P. Dybjer, editors, Semantics and Logics of Computation, volume 14 of Publications of the Newton Institute, page 1. Cambridge University Press, 1997. Google Scholar
  2. T. Colcombet and C. Löding. The Non-deterministic Mostowski Hierarchy and Distance-Parity Automata. In ICALP 2008, volume 5126 of Lecture Notes in Computer Science, pages 398-409. Springer, 2008. Google Scholar
  3. J. Duparc, F. Facchini, and F. Murlak. Definable Operations On Weakly Recognizable Sets of Trees. In FSTTCS, volume 13 of LIPIcs, pages 363-374. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2011. Google Scholar
  4. E. A. Emerson and C. S. Jutla. Tree Automata, Mu-Calculus and Determinacy (Extended Abstract). In FOCS, pages 368-377. IEEE Computer Society, 1991. Google Scholar
  5. A. Facchini, F. Murlak, and M. Skrzypczak. Rabin-Mostowski Index Problem: A Step beyond Deterministic Automata. In LICS, pages 499-508. IEEE Computer Society, 2013. Google Scholar
  6. E. Grädel, W. Thomas, and T. Wilke, editors. Automata, Logics, and Infinite Games: A Guide to Current Research, volume 2500 of LNCS. Springer, 2002. Google Scholar
  7. J. M. E. Hyland. Game Semantics. In A. M. Pitts and P. Dybjer, editors, Semantics and Logics of Computation, volume 14 of Publications of the Newton Institute, page 131. Cambridge University Press, 1997. Google Scholar
  8. J. M. E. Hyland. Proof theory in the abstract. Ann. Pure Appl. Logic, 114(1-3):43-78, 2002. Google Scholar
  9. J. M. E. Hyland and A. Schalk. Abstract Games for Linear Logic. Electr. Notes Theor. Comput. Sci., 29:127-150, 1999. Google Scholar
  10. B. Jacobs. Categorical Logic and Type Theory. Studies in logic and the foundations of mathematics. Elsevier, 2001. Google Scholar
  11. S. Mac Lane. Categories for the Working Mathematician. Springer, 2 edition, 1998. Google Scholar
  12. D. A. Martin. Borel Determinacy. The Annals of Mathematics, Second Series, 102(2):363-371, 1975. Google Scholar
  13. P.-A. Melliès. Categorical semantics of linear logic. In Interactive models of computation and program behaviour, volume 27 of Panoramas et Synthèses. SMF, 2009. Google Scholar
  14. D. E. Muller and P. E. Schupp. Alternating Automata on Infinite Trees. Theor. Comput. Sci., 54:267-276, 1987. Google Scholar
  15. D. E. Muller and P. E Schupp. Simulating Alternating Tree Automata by Nondeterministic Automata: New Results and New Proofs of the Theorems of Rabin, McNaughton and Safra. Theor. Comput. Sci., 141(1&2):69-107, 1995. Google Scholar
  16. M. Shulman. Framed bicategories and monoidal fibrations. Theory and Applications of Categories, 20(18):650-738, 2008. Google Scholar
  17. W. Thomas. Languages, Automata, and Logic. In G. Rozenberg and A. Salomaa, editors, Handbook of Formal Languages, volume III, pages 389-455. Springer, 1997. Google Scholar
  18. I. Walukiewicz. Monadic second-order logic on tree-like structures. Theor. Comput. Sci., 275(1-2):311-346, 2002. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact