📝

1 Monoids and MSO

1.1 Monoids and Regularity

We say that a language is recognized by a finite monoid \(M\) if there exists a morphism \(\mu \colon A^* \to M\) and a subset \(P \subseteq M\) such that \(L = \mu^{-1}(P)\).

  1. Prove that a language is regular if and only if it is recognized by a finite monoid.
  2. Use the above result to conclude that regular languages are closed under the following operations:
    • union,
    • intersection,
    • complement,
    • reversal,
    • concatenation
  3. Prove that the class of regular languages is closed under radicals \(\sqrt{L} :=\left\{ w \in A^* \mid ww \in L \right\}\).
  4. Prove that the class of regular language is closed under Kleene star.

1.2 From MSO to Monoids

Let \(\varphi\) be an \(\mathbb{MSO}\) sentence over finite words. Prove that there exists a monoid \(M\) and a function \(f : A^* \to M\) and a subset \(P \subseteq M\) such that \(w \models \varphi\) if and only if \(f(w) \in P\).

Can you adapt the construction in the case of \(\mathbb{MSO}\) formulas?

Hint: Use automata theory

At least for the first part, you can use the fact that \(\varphi\) defines a regular language.

1.3 From Monoids to MSO

Let \(M\) be a finite monoid and \(m \in M\). Construct an \(\mathbb{MSO}\) formula \(\varphi_m(x,y)\) over \(M^*\) that accepts all pairs \(x < y\) such that the factor \(w[x:y]\) evaluates to \(m\).

If the monoid is aperiodic, can you write this formula in \(\mathbb{FO}\)?

2 Factorisation Forests

2.1 Baby Factorisation Forest

Let \(M\) be a finite monoid. Prove that there exists a constant \(N\) such that for every \(w \in M^*\) with \(|w| \geq N\), there exist \(v_0, v_1 \in M^*\), and \(u \in M^+\) such that \(w = v_0 u v_1\) and \(u\) is an idempotent element of \(M\).

2.2 First-order Factorisation Forests

Let \(M\) be a finite aperiodic monoid. Prove that there exists a constant \(N\) such that for every \(w \in M^*\), one can build a factorisation of \(w\) of depth at most \(N\), where idempotent products are replaced by constant products.

2.3 Pumping lemma for regular functions

Let \(f\) be a regular function. Prove that there exists \(N \geq 0\) such that for all \(w \in A^*\) with \(|w| \geq N\), there exist \(v_0, v_1 \in A^*\), \(u \in A^+\), \(n \geq 0\), \(\alpha_0, \dots, \alpha_n \in B^*\), \(\beta_1, \dots, \beta_n \in B^+\) such that \(w = v_0 u v_1\) and

\[ f(v_0 u^{X + 1} v_1) = \alpha_0 \beta_1^X \alpha_1 \dots \beta_n^X \alpha_n \quad ,\quad \text{for all } X \geq 0 \quad . \]

Solution: Solution

Without loss of generality, we assume that \(Q = Q^\leftarrow \cup Q^\rightarrow\), where states in \(Q^\leftarrow\) are always doing left transitions, while states in \(Q^\rightarrow\) are always doing right transitions. We define the transition monoid of \(f\) as follows: \(M := Q \to Q\). The intended semantics is that given a state \(q \in Q\), and a word \(u\), the transition performed by \(u\) is given by the first state reached by \(f\) outside of the word \(u\).

2.4 Efficient Query Evaluation

Let \(q \in \mathbb{N}\). Provide a linear-time computation of a data-structure over a word \(w\) allowing for constant-time answer to \(\mathbb{MSO}\) queries of quantifier depth at most \(q\).

Hint: Use factorisation forests

Construct a factorisation forest of the monoid of \(\mathbb{MSO}^q\) types.

References