World's most popular travel blog for travel bloggers.

[Solved]: Regular expression over a monoid

, , No Comments
Problem Detail: 

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'$.

Asked By : Chao Xu

Answered By : Hendrik Jan

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".

Best Answer from StackOverflow

Question Source :

3.2K people like this

 Download Related Notes/Documents


Post a Comment

Let us know your responses and feedback