Jiří Adamek ; Stefan Milius ; Henning Urbat - A Categorical Approach to Syntactic Monoids

lmcs:4436 - Logical Methods in Computer Science, May 15, 2018, Volume 14, Issue 2 - https://doi.org/10.23638/LMCS-14(2:9)2018
A Categorical Approach to Syntactic MonoidsArticle

Authors: Jiří Adamek ; Stefan Milius ; Henning Urbat

    The syntactic monoid of a language is generalized to the level of a symmetric monoidal closed category $\mathcal 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 ($\mathcal D=$ sets), the syntactic ordered monoids of Pin ($\mathcal D =$ posets), the syntactic semirings of Polák ($\mathcal D=$ semilattices), and the syntactic associative algebras of Reutenauer ($\mathcal D$ = vector spaces). Assuming that $\mathcal D$ is a commutative variety of algebras or ordered algebras, we prove that the syntactic $\mathcal D$-monoid of a language $L$ can be constructed as a quotient of a free $\mathcal D$-monoid modulo the syntactic congruence of $L$, and that it is isomorphic to the transition $\mathcal D$-monoid of the minimal automaton for $L$ in $\mathcal D$. Furthermore, in the case where the variety $\mathcal D$ is locally finite, we characterize the regular languages as precisely the languages with finite syntactic $\mathcal D$-monoids.


    Volume: Volume 14, Issue 2
    Published on: May 15, 2018
    Accepted on: April 11, 2018
    Submitted on: April 11, 2018
    Keywords: Computer Science - Logic in Computer Science

    Consultation statistics

    This page has been seen 1590 times.
    This article's PDF has been downloaded 388 times.