# Tag Info

11

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 disjunctive if and only if the syntactic congruence of $P$ in $M$ is the equality relation. Thus a monoid is the syntactic monoid of a language if and only if it ...

11

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 M$. Define the congruence relation $\equiv_Y$ over $M$ by $x \equiv_Y y$ iff $\big[\forall w, z \in M$, $wxz \in Y \Leftrightarrow wyz \in Y\big]$. Definition:...

11

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 paywall it would be great. I requested the full-text on ResearchGate. Title: Which Finite Monoids are Syntactic Monoids of Rational omega-Languages. Authors: ...

9

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 there exists a path in this graph from the vertex $(1,1)$ to any vertex of the form $(t,t)$. This can be answered using standard reachability algorithms (e.g.,...

9

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 there exists $a \in \Gamma$ such that $h = f_a \circ g$. Then, testing whether a function $g$ is in $G$ reduces to testing whether $g$ is reachable in the ...

7

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^*a_3\right)^*\\ e_3 &= \left(\left(a_1^*a_2^*a_3\right)^*\left(a_4^*a_5^*a_6\right)^*a_7\right)^*\\ e_4 &= \left( \left(\left(a_1^*a_2^*a_3\right)^*\left(...

5

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 \to R$ is a monoid morphism and $h:T \to R$ is a surjective morphism, then there exists a morphism $g:N \to T$ such that $f = h \circ g$. You can find a long ...

2

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 of semilinear set (it contains for instance the set $\{ (i,i) \mid i\in\mathbb{N}\}$, which is not recognizable). For more examples, you can look at the ...

2

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 special case, this holds if $M$ is any infinite simple group. (Monoid morphisms map inverse elements to inverse elements: $f(x)f(x^{-1})=f(x^{-1})f(x)=f(1)=1$. ...

1

The simplest example is probably $\mathbb{Z}$. The set $\{0\}$ is rational in $\mathbb{Z}$ but is not recognizable.

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