---
tags: FYP
---

# Ochmanski's Theorem

## Preliminary

***Definition 1.1***

Let $M$ be a monoid and $X \subseteq M$. The ***left quotient*** of $X$ by an element $u \in M$ is denoted as $X/u := \{m \in M : um \in X\}$.

Let $\equiv_X$ be an equivalence class where $u \equiv_X v$ iff $X/u = X/v$. We call $\equiv_X$ as ***left syntactic relation*** of $X$

Alternatively, $u \equiv_X v$ iff $um \in X$ if and only if $vm \in X$ for all $m$.

The number of distinct left quotients of $X$ is the same as the size of the set of equivalence classes $\equiv_X$.

***Definition 1.2***

Let $M$ be a monoid and $X \subseteq M$. The ***$k$-syntactic quotient*** of $X$ by $P = (p_1, \dots, p_k) \subseteq M^k$ is $X // P = \{(q_0, \dots, q_k) : q_0p_1q_1 \dots p_kq_k \in X, q_i \in M\}$.

We can form an equivalence relation $(x_1, \dots, x_k) \equiv_{X,k} (y_1, \dots, y_k)$ if $X // (x_1, \dots, x_k) = Y // (y_1, \dots, y_k)$

***Definition 2***

Let $M = M(\Sigma, I)$ be a trace monoid. Let $L \subseteq \Sigma^*$ be a language. Denote the ***closure*** of the language $L$ with respect to $I$ as $f_I(L) = \bigcup [L]_I$.

***Definition 3***

Let $M = M(\Sigma, I)$ be a trace monoid. Let $T \subseteq M$ be a trace language. Denote $Lex(T)$ as a set of strings over $\Sigma^*$, where each string is used to denote each trace in $T$, and the string is lexicographically the smallest. Formally, $Lex(T) = \{ w \in \bigcup T : \forall w' \in [w], w \leq w'\}$

***Definition 4***

Let $(\Sigma, I)$ be a concurrent alphabet. For any string $w \in \Sigma^*$, denote $I(w) := \{w' : (w, w') \in I\}$, i.e. set of strings that are independent from $w$.

***Definition 5***

Let $(\Sigma, I)$ be a concurrent alphabet, and $L \subseteq \Sigma^*$. For any $[uv] \in [L]$, we say $rank_{L, I}(u, v) \leq n$ if there exists $w \in L$ such that:

1. $w = v_0 u_1 v_1 \dots u_n v_n$
2. $[v_0 \dots v_n] = [v]$ and $[u_1 \dots u_n] = [u]$
3. $(v_i, u_j) \in I$ for all $i < j$

Define $rank_{L, I}(u, v) = \min \{ n : rank_{L, I}(u, v) \leq n\}$ and $Rank_I(L) = \max \{rank_{L, I}(u, v) : [uv] \in [L]\}$.

One interpretation of $rank_{L, I}(u, v)$ is what is the minimum components needed to break down $[uv] \in [L]$ such that it forms a word $w \in L$.

***Definition 6***

A rational expression $R \in \text{REX}(\Sigma^*)$ is star-connected if it only have star operation over connected languages. Formally,

1. For any $w \in \Sigma^*$, the expression $w$ is star-connected
2. For any star-connected rational expression $R_1$ and $R_2$, $R_1 \cup R_2$ and $R_1 \cdot R_2$ are also star-connected.
3. For any star-connected rational expression $R$, $R^*$ is also rational expression if and only if $L(R)$ is connected.

---

# Plan

We will prove the following three statements are equivalent. Let $M = M(\Sigma, I)$ be a trace monoid, and $T \subseteq M$ be a trace language.

1. $T \in \text{REC}(M)$
2. $Lex(T) \in \text{REG}(\Sigma^*)$
3. There exists $R \in REX(\Sigma^*)$ such that $R$ is star connected and $[L(R)] = T$.

- (1) implies (2) is proven in ***Theorem 2***.
- (2) implies (3) is shown by ***Corollary 3.1***.
- (3) implies (1) is shown by ***???***

Note: I think it should be equivalent to what we have proven during the meeting, i.e. suppose $L \subseteq M$ such that $L$ is recognizable, then the three statements are equivalent:

1. $[L] \in REC(M)$
2. $Lex([L]) \in REG(\Sigma^*)$
3. There exists $R \in REX(\Sigma^*)$ such that $R$ is star connected and $[L(R)] = [L]$.

## Theorem 1

Let $M$ be a monoid and $\approx$ be a congruence on $M$. Let $X \subseteq M_\approx$ be a subset of equivalence classes.

$$ X \in \text{REC}(M_\approx) \iff \bigcup X \in \text{REC}(M) $$

*Proof*. It is sufficient to prove that the number of left quotient of $X$ is equal to $\bigcup X$.

Denote $\equiv_{\bigcup X}$ and $\equiv_X$ as the left syntactic relation of $\bigcup X$ w.r.t. the monoid $M$ and $X$ w.r.t. the monoid $M_\approx$ respectively.

We shall prove the following:

$$ [w_1] \equiv_X [w_2] \iff w_1 \equiv_{\bigcup X} w_2 $$

($\Rightarrow$)

- Given $[w_1], [w_2] \in X$ such that $[w_1] \equiv_X [w_2]$
- Take any $z \in (\bigcup X)/w_1$
- $w_1 z \in \bigcup X$ by definition
- $[w_1z] \in X$
- $[w_1][z] \in X$
- $[z] \in X/[w_1]$
- $[z] \in X/[w_2]$ as $[w_1] \equiv_X [w_2]$
- $[w_2][z] \in X$
- $[w_2 z] \in X$
- $w_2 z \in \bigcup X$
- $z \in (\bigcup X) / w_2$
- Therefore $(\bigcup X)/w_1 = (\bigcup X)/w_2$, hence $w_1 \equiv_{\bigcup X} w_2$

($\Leftarrow$)

- Given $w_1, w_2 \in \bigcup X$ such that $w_1 \equiv_{\bigcup X} w_2$
- Take any $[z] \in X/[w_1]$
- $[w_1][z] \in X$
- $[w_1 z] \in X$
- $w_1 z \in \bigcup X$
- $w_2 z \in \bigcup X$ as $w_1 \equiv_{\bigcup X} w_2$
- $[w_2 z] \in X$
- $[w_2][z] \in X$
- $[z] \in X/[w_2]$
- Therefore, $X/[w_1] = X/[w_2]$, hence $[w_1] \equiv_X [w_2]$

As there is one-to-one correspondence from an element in classes of $\equiv_X$ to classes of $\equiv_{\bigcup X}$, both have the same number of left quotient.

If a subset of a monoid is recognizable, then the number of left quotient is finite. This completes the proof.

***Corollary***

Let $M = M(\Sigma, I)$ be a trace monoid, and $L \subseteq \Sigma^*$ be a language. Then

$$ [L] \in \text{REC}(M) \iff f_I(L) = \bigcup [L] \in \text{REC}(\Sigma^*) $$

## Theorem 2

Let $M = M(\Sigma, I)$ be a trace monoid and $T \subseteq M$ be a trace language.

$$ T \in \text{REC}(M) \implies Lex(T) \in \text{REG}(\Sigma^*) $$

*Proof*. Note that $Lex(T) = Lex(M) \cap \bigcup T$. We know that $\bigcup T$ is regular by Theorem 1. Now we need to prove that $Lex(M)$ is also regular.

$$Lex(M) = \Sigma^* - \{\Sigma^*bI(a)a\Sigma^* : (a, b) \not\in I \text{ and } a < b\}$$

We can see that $I(a) = \{ w \in \Sigma^* : (w, a) \in I \} = \{ c \in \Sigma : (c, a) \in I \}^*$ is regular. Therefore, $Lex(M)$ is regular.

Hence, we conclude that $Lex(T)$ is also a regular language.

## Theorem 3

Let $M = M(\Sigma, I)$ be a trace monoid and $T \subseteq M$ be a trace language.

$$ Lex(T) \in \text{REG}(\Sigma^*) \implies \exists R \in \text{REX}(\Sigma^*), R \text{ is star-connected and } L(R) = Lex(T) $$

*Proof*. Suppose not, there exists a word $w$ and $ww$ in $L(R)$ such that $w$ is a disconnected word. However, $ww$ cannot be lexicographically smallest, as we can swap some smallest letter from second $w$ to the first $w$.

### Corollary 3.1

$$ Lex(T) \in \text{REG}(\Sigma^*) \implies \exists R \in \text{REX}(\Sigma^*), R \text{ is star-connected and } [L(R)] = T $$

## Lemma 3

Let $(\Sigma^*, I)$ be a concurrent alphabet. Let $u, v, w \in \Sigma^*$. $[w] = [uv]$ if and only if $w = v_0 u_1 v_1 \dots u_n v_n$, where $[u] = [u_1 \dots u_n]$, $[v] = [v_0 \dots v_n]$, and $(v_i, u_j) \in I$ for $i < j$.

## Theorem 4 (Hachiguchi)

Let $(\Sigma, I)$ be a concurrent alphabet. Suppose $L \subseteq \Sigma^*$ and $L \in \text{REG}(\Sigma^*)$.

If $Rank_I(L)$ is finite, then $f_I(L) \in \text{REG}(\Sigma^*)$.

*Proof*. It is sufficient to prove that the number of left quotient of $f_I(L)$ is finite.

We will try to find a way to represent $f_I(L)/u$, for some $u \in \Sigma^*$.

Let $v \in f_I(L) / u$, then $uv \in f_I(L)$. From ***Lemma 3***, we know that there exists $w \in L$ such that:

1. $w = v_0 u_1 v_1 \dots u_n v_n$
2. $[u] = [u_1 \dots u_n]$, $[v] = [v_0 \dots v_n]$
3. $(v_i, u_j) \in I$ for $i < j$

We can represent $v$ as $n$-syntactic quotient of $(u_1 \dots u_n)$. Let $\text{CON}$ be a concatenation function of tuples, i.e. $\text{CON}((w_1, w_2, \dots, w_n)) = w_1 \dots w_n$. Then for any $v \in f_I(L) / u$, surely $v \in f_I[\text{CON}(L // (u_1, \dots, u_n))]$, where $[u] = [u_1 \dots u_n]$. However, we need to ensure that all elements $(v_0, \dots, v_n) \in L // (u_1, \dots, u_n)$ must satisfy (3).

Hence, we intersect it with $I(x_1, \dots, x_k) = I(x_1 \dots x_k) \times I(x_2 \dots x_k) \dots \times I(x_k) \times \Sigma^*$, i.e. a tuple whose first element is independent with all, the second element is independent with second word onwards, etc.

Therefore, $f_I(L) / u = \bigcup \{f_I[\text{CON}(L // (u_1, \dots, u_n) \cap I(u_1, \dots, u_n))] : [u_1 \dots u_n] = [u]\}$.

Since the family $\{I(x) : x \in \Sigma^*\}$ is finite, so does $\{I(x_1, \dots, x_n) : x_i \in \Sigma^*\}$.

Since $L$ is regular, $\equiv_{L, k}$ has finite equivalence classes. Therefore, the family $\{L//(u_1, \dots, u_n)\}$ is finite as $Rank_I(L)$ is finite. Therefore, the family $\{f_I(L) / u\}$ is finite.

Hence, $f_I(L)$ is recognizable.

## Theorem 5

Let $M = M(\Sigma, I)$ be a trace monoid, and $T \subseteq M$ be a trace language.

$$ \exists R \in \text{REX}(\Sigma^*), R \text{ is star-connected and } [L(R)] = T \implies T \in \text{REC}(M) $$

*Proof.* We will prove this by using structural induction over definition of star-connected rational expression.

**Base Case**: For every word $w \in \Sigma^*$, suppose $R = w$. Therefore $[L(R)] \in \text{REC}(M)$, as the size of $[L(R)]$ is finite.

**Inductive Case**.

(Union) Suppose $R_1$ and $R_2$ are star-connected. By inductive step, both $[L(R_1)]$ and $[L(R_2)]$ are recognizable. Note that $[L(R_1 \cup R_2)] = [L(R_1)] \cup [L(R_2)]$. As recognizability is closed under union, we conclude that $[L(R_1 \cup R_2)] \in \text{REC}(M)$

(Concatenation) Suppose $R_1$ and $R_2$ are star-connected. By inductive step, both $[L(R_1)]$ and $[L(R_2)]$ are recognizable.

Denote $L_1 = \bigcup [L(R_1)]$ and $L_2 = \bigcup [L(R_2)]$. Both $L_1$ and $L_2$ are regular languages. As regular languages are closed under concatenation, therefore $L_1 \cdot L_2$ is a regular language.

Take any $[uv] \in [L_1L_2]$. We can find $w \in L_1L_2$ such that $w$ is factorization of $u$ and $v$. As $w \in L_1L_2$, we can break down $w$ as $w_1w_2$, where $w_1 \in L_1$ and $w_2 \in L_2$.

Note that $[uv] = [w_1w_2]$. By Levi's lemma, there exists $x_1, x_2, x_3, x_4$ such that $(x_2, x_3) \in I$ and $u = x_1 x_2, v = x_3 x_4, w_1 = x_1 x_3, w_2 = x_2 x_4$. Hence, $Rank_I(L_1L_2) \leq 2$. By Hachiguchi, $f_I(L_1 L_2) = \bigcup (L(R_1) L(R_2))$ is regular. Therefore, $[L(R_1)L(R_2)]$ is recognizable.

(Star) ???

---

## Appendix

We will prove that $Lex(M) = \Sigma^* - \{\Sigma^*bI(a)a \Sigma^* : (a, b) \not\in I \text { and } a < b\}$ is true.

It is sufficient to prove that all strings that are not minimal (lexicographically smallest) can be represented as $\Sigma^*bI(a)a\Sigma^*$ for some $(a, b) \not\in I$ and $a < b$, and that representation is sufficient to contain all minimal string.

Equivalently, we can prove the following:

Let $w$ be a word. $w$ is minimal if and only if for all factorizations $w = xbyaz$, where $x, y, z \in \Sigma^*$, $a, b \in \Sigma$, $(a, b) \in I$ and $a < b$, there is a letter of $y$ that does not commute with $a$.

*Proof*. If $w$ is minimal, then the consequent is true. Otherwise, we can swap $a$ and $b$ to get smaller string.

Let $w$ be a word such that for all factorizations $w = xbyaz$ where $x, y, z \in \Sigma^*$, $a, b \in \Sigma$, $a < b$, and $(a, b) \in I$, there is a letter in $y$ that does not commute with $a$.

Suppose $w$ is not minimal, i.e. there is an equivalent word $v$ such that $v < w$. Hence, there must be some symbols $a$ and $b$ such that $a < b$ and $v = x'av'$ and $w = x'bw'$, where $x', v', w' \in \Sigma^*$. We know that there must be symbol $a$ in $w'$, and $(a, b) \in I$.

We can rewrite $w$ as $w = x'byaz$ where $|y|_a = 0$, i.e. $a$ does not appear in $y$. This violates the assumption that all factorizations of $w$ satisfies the condition.

## References

- The Book of Traces Chapter 6
- Partial Commutation and Traces, Theorem 7