2015/04/10 by Jiri Adamek, Adamek, Jiri, Stefan Milius +3
Computer Science · Mathematics · #Category Theory (math.CT) #FOS: Computer and information sciences #FOS: Mathematics #Formal Languages and Automata Theory (cs.FL) #Logic in Computer Science (cs.LO) #cs.FL #cs.LO #math.CT
paper · pdf · doi:10.48550/arxiv.1504.02694
arxiv created 2015/06/16 · arxiv updated 2015/06/17
The syntactic monoid of a language is generalized to the level of a symmetric monoidal closed category D. This allows for a uniform treatment of several notions of syntactic algebras known in the literature, including the syntactic monoids of Rabin and Scott (D = sets), the syntactic semirings of Polak (D = semilattices), and the syntactic associative algebras of Reutenauer (D = vector spaces). Assuming that D is an entropic variety of algebras, we prove that the syntactic D-monoid of a language L can be constructed as a quotient of a free D-monoid modulo the syntactic congruence of L, and that it is isomorphic to the transition D-monoid of the minimal automaton for L in D. Furthermore, in case the variety D is locally finite, we characterize the regular languages as precisely the languages with finite syntactic D-monoids.