Abstract MSO languages over monads

ABSTRACT. The algebraic approach of automata and recognizable languages shown in [2] and the use of monads as a natural categorical generalization of universal algebra has led to the study of algebraic language theory from a categorical point of view. On the other hand, the logical characterization of regular languages as the MSO definable languages, see, e. g. , [3], has inspired the possibility of developing an abstract categorical framework for MSO [1]. In this presentation, I will summarize some of the first steps towards the study of abstract MSO languages for algebras over a monad. Definitions and properties for an abstract MSO framework are inspired on the classical case of words and monoids and its corresponding proof. Such properties are stated in a categorical setting in order to restrict the kind of monads that in some sense allows us an abstract study of MSO languages. This is an ongoing joint work with Mikolaj Bojanczyk and Bartek Klin. References [1] M. Bojanczyk. Recognisable languages over monads. CoRR, abs/1502. 04898, 2015. [2] J. Mezei and J. Wright. Algebraic automata and context-free sets. Information and Control, 11(1): 3 – 29, 1967. [3] W. Thomas. Languages, Automata, and Logic, pages 389–455. Springer, Berlin, Heidelberg, 1997.

Authors

• Julian Salamanca

Keywords

No keywords are indexed for this paper.