All Questions
Tagged with formal-languages semigroups-and-monoids
10 questions
2
votes
0
answers
64
views
A particular generalization of free partially commutative monoids
A trace monoid, or free partially commutative monoid, is one with the presentation $\langle \Sigma \mid a_1b_1 = b_1a_1, \dots, a_nb_n = b_na_n\rangle$. The theory of trace monoids has been well ...
- 21
4
votes
0
answers
170
views
Corollaries of Kleene's Theorem (Regular Languages)
Kleene's theorem that finite automata (specifically, nondeterministic) are expressively equivalent to regular expressions seems to be a powerful and not immediately obvious tool for untangling the ...
- 429
2
votes
1
answer
220
views
Alternative notation for Kleene star
I am writing a paper which use two different operations on sets of works $X$, both of which I want to denote by a star, $X^{\ast}$. One of these operations is the Kleene star, and for whatever reason ...
- 21
5
votes
2
answers
387
views
Concatenation of strings [closed]
We have two strings (i. e., finite tuples) $A$ and $B$.
We have to find if for some positive integers $n$ and $m$, the string $A$ concatenated $n$ times equals the string $B$ concatenated $m$ times or ...
- 59
4
votes
1
answer
191
views
Progress on group languages characterizations
Def. A group language is a recognizable language whose syntactic monoid is a group.
q1. Is it known a "nice" combinatorial characterization of group languages ?
q1.1. If no, is it well understood ...
- 424
3
votes
1
answer
529
views
Study of free monoids of the recursive S. Eilenberg.
Compared to the usual treatises on recursion (eg, Rogers H. "Computability and Undecidability." McGraw-Hill, New York) the book of Samuel Eilenberg & Calvin C. Elgot "Recursiveness" treats such ...
- 4,165
1
vote
1
answer
260
views
The intersection of Block Groups and R-trivial (finite) monoids
Let $\textbf{BG}$ be the pseudovariety of block groups, also known as $\textbf{EJ}, \textbf{PG},\ldots,\text{etc.}$(see [1]), and let $\textbf{R}$ be the pseudovariety of R-trivial monoids, by the ...
- 424
6
votes
1
answer
516
views
Growth zeta-functions of regular languages
Dear All,
my following question may be known and ought to be known, so in case it is folklore please could you give me the references.
To start, it is obvious that growth of rational languages are ...
- 1,437
3
votes
2
answers
571
views
What is the relation between the number syntactic congruence classes, and the number of Nerode relation classes?
For a monoid $M$ and a subset $S$ of $M$, define the syntactic congruence $\equiv_S$ of $S$ as the least congruence on $M$ that saturates $S$, i.e. :
$$u \equiv_S v \Leftrightarrow (\forall x, y)[xuy \...
- 786
4
votes
1
answer
405
views
Vocabulary on monoid periodicity
I'm learning about periodic languages, and I'm confused over the vocabulary used to describe the periodicity of (syntactic) monoids.
If I understand correctly, a monoid M is periodic if :
$$(\forall ...
- 786