Hot answers tagged

13 votes

On the realisation of monoids as syntactic monoids of languages

The terminology rigid seems to be relatively new compared to the term disjunctive used in the late 70's (and probably before, I didn't check for earlier references). A subset $P$ of a monoid $M$ is ...
J.-E. Pin's user avatar
  • 4,781
12 votes
Accepted

On the realisation of monoids as syntactic monoids of languages

It seems there is a paper answering this exact question, and even in the more general case of $\omega$-regular languages, but I cannot find an open-access version. If somebody finds a link without ...
Denis's user avatar
  • 8,678
11 votes

On the realisation of monoids as syntactic monoids of languages

In a more elementary way than Denis's answer, the following is extracted from Pippenger's "Theories of Computability", p.87, and immediate to check. Definition: Let $M$ be a monoid, and $Y \subseteq ...
Michaël Cadilhac's user avatar
9 votes

Transition monoid membership for DFAs

Decidability It's decidable. There are only finitely many possible functions $f:Q \to Q$, so you can model this as a graph reachability problem, with one vertex per function and an edge $g \to h$ if ...
D.W.'s user avatar
  • 12k
9 votes

Post correspondence problem for finite monoids

Yes, it is decidable. Build a graph where each vertex is a pair $(r,s)$ of elements from $M$. Add all edges of the form $(r,s) \to (r m_i, s m'_i)$ for all $r,s,i$. Then, your question asks whether ...
D.W.'s user avatar
  • 12k
7 votes
Accepted

star height of star-free languages

The examples of arbitrary star-height given on the wikipedia page on the star-height problem are star-free: On arbitrary alphabet: :\begin{alignat}{2} e_1 &= a_1^* \\ e_2 &= \left(a_1^*a_2^*...
Denis's user avatar
  • 8,678
5 votes
Accepted

Generalisation of the statement that a monoid recognizes language iff syntactic monoid divides monoid

Yes, these monoids have received attention in the research literature and actually lead to difficult questions. Definition. A monoid $N$ is called projective if the following property holds: if $f:N \...
J.-E. Pin's user avatar
  • 4,781
4 votes
Accepted

Complexity of the inevitability problem over monoids

I think it is PSpace-complete, here is a proof scheme. We can go back to the proof scheme for PSpace-completeness of regular expression universality, e.g. described in this answer. There we can see ...
Denis's user avatar
  • 8,678
2 votes

Example of monoid $M$ such that $\operatorname{RAT}(M) \not\subseteq \operatorname{REC}(M)$

A well known and studied example: the monoïde $\mathbb{N}^k$. Indeed, for $k\geq 2$, $\text{Rec}(\mathbb{N}^k)$ are more or less periodic rectangles meanwhile $\text{Rat}(\mathbb{N}^k)$ is the class ...
C.P.'s user avatar
  • 992
2 votes
Accepted

Example of monoid $M$ such that $\operatorname{RAT}(M) \not\subseteq \operatorname{REC}(M)$

If $M$ is an infinite monoid that has no nontrivial finite quotient, then the only recognizable subsets of $M$ are $\varnothing$ and $M$ itself, whereas there are many more rational subsets. As a ...
Emil Jeřábek's user avatar
1 vote

Example of monoid $M$ such that $\operatorname{RAT}(M) \not\subseteq \operatorname{REC}(M)$

The simplest example is probably $\mathbb{Z}$. The set $\{0\}$ is rational in $\mathbb{Z}$ but is not recognizable.
J.-E. Pin's user avatar
  • 4,781

Only top scored, non community-wiki answers of a minimum length are eligible