I'm looking for the name of the following concept.

Given a monoid $(M,\oplus)$, and a finite set of generators $x_1,\ldots,x_n$. The generators are the alphabets.

We define the regular expression on the words formed by the generators. We treat those words just like strings.

For words $x$ and $y$, we write $x\equiv y$ if $x$ and $y$ represent the same element in $M$.

If $R$ is a regular expression, we define $L(R)$ to be the set of strings matched by $R$ and $L_M(R)$ as

$$L_M(R) = \{w'|w'\equiv w,w\in L(R)\}$$.

I'm interested to know if there exist known literature on $L_M(R)$.

Many problems related to $L_M(R)$ are undecidable, because the word problem on $M$ might be undecidable. I wonder if $M$ has a decidable word problem, does it imply we can decide if $L_M(R)=L_M(R')$ for 2 regular expressions $R$ and $R'$.


The sets that can be defined this way are called rational. As an example, the pairs of input-output strings $(u,v) \in \Sigma^*\times\Delta^*$ of accepted computations in finite state automata on two tapes define rational subsets in $\Sigma^*\times\Delta^*$ (with pair-wise concatenation as monoid operation). The word problem in $\Sigma^*\times\Delta^*$ is trivially decidable, but equality for their rational languages (of pairs of words) is not.

A special collection of monoids that were extensively studied for their rational language decision problems are the so-called trace monoids (or free partially commutative monoids). A special case of these monoids is $\Sigma^*\times\Delta^*$.

An overview of the literature in that area is given by Sakarovich, in his paper "The "last" decision problem for rational trace languages".


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.