| Summary: | 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\'ak ($\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.
|
|---|