patternMinor
Regular expression over a monoid
Viewed 0 times
expressionmonoidregularover
Problem
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'$.
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'$.
Solution
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".
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".
Context
StackExchange Computer Science Q#17897, answer score: 2
Revisions (0)
No revisions yet.