Exercises 3:

EX 1: Bottom-up transducers

1.

Reminder:

Tree homomorphism $h: T(𝔉) ⟶ T(𝔉’)$:

• $h(a) = t_a ∈ T(𝔉’)$
• $h(f(t_1, \ldots, t_n)) = t_f \lbrace x_i ↤ h(t_i) \rbrace_i$

Ex:

\[𝔉 ≝ \lbrace g(3), a(0), b(0) \rbrace, \; 𝔉' ≝ \lbrace f(2), a(0), b(0) \rbrace\]

• $h(g) = f(f(x_1, x_2), x_3)$
• $h(a) = a$
• $h(b) = b$

so that:

\[h(g(a, g(b,b,b), a)) = f(f(a, f(f(b,b), b)), a)\]

With only one state that we propagate: each tree homomorphism is a transducer.

2.

We disable the rewriting process

in $Δ$:

• $f(q_1(x_1), \ldots, q_n(x_n)) ⟶ q’(u_f)$
• $q(x_1) ⟶ q’(u)$

becomes

• $f(q_1(x_1), \ldots, q_n(x_n)) ⟶ q’(f(x_1, \ldots, x_n))$
• $q(x_1) ⟶ q’(x_1)$

EX 2: Minimal automaton

1 ⟹ 2

\[u ≡_𝒜 v ⟺ δ^\ast(u) = δ^\ast(v)\]

where $δ$ is the transitive closure of the transition function of the automaton:

\[L = \bigcup_{q ∈ Q_f} \overline{q}\]

and $Q_f ⊆ Q$ is finite.

2 ⟹ 3

We have a finite $\sim$ congruence relation. Let’s show that $≡_L$ is finite.

It will suffice to show that $u \sim v ⟹ u ≡_L v$:

if $u \sim v$, then $C(u) \sim C(v)$ (congruence), that is: there exists a congruence class $𝒞$ s.t.

\[C(u), C(v) ∈ 𝒞\]

Thus:

\[C(u) ∈ L = \bigcup_{𝒞' \text{ congruence class}} 𝒞' ⟺ C(v) ∈ L = \bigcup_{𝒞' \text{ congruence class}} 𝒞'\]

3 ⟹ 1

Let’s assume $≡_L$ is finite.

Let’s build

\[𝒜_{min} ≝ ⟨Q_{min} ≝ \lbrace \overline{u} \mid u ∈ Σ^\ast \rbrace, 𝔉, Q_{min, f} ≝ ≝ \lbrace \overline{u} \mid u ∈ L \rbrace, δ_{min}⟩\]

Then

\[δ_{min}(f, \overline{u_1}, \ldots, \overline{u_n}) = \overline{f(u_1, \ldots, u_n)}\]

---

Given $L$ and $𝒜$ s.t. $L(𝒜) = L$, we build $≡_𝒜$ as in 1 ⟹ 2.

We know that with 2 ⟹ 1:

\[\vert Q_𝒜 \vert = \vert \lbrace \overline{u}^𝒜 \mid u ∈ Σ^\ast \rbrace \vert ≥ \vert \lbrace \overline{u}^L \mid u ∈ Σ^\ast \rbrace \vert = \vert Q_{𝒜_{min}} \vert\]

Why is the minimal automaton useful?: given two automata $𝒜_1, 𝒜_2$, you can check if $L(𝒜_1) = L(𝒜_2)$ by comparing their minimal automata.

EX 3: MSO on finite trees

1.

$X$ is closed under predecessors:

\[closed(X) ≝ ∀x,y. (y ∈ X ∧ x \downarrow y ⟹ x∈X)\]

2.

Seen in class.

3.

\[∃x, y. (P_a(x) ∧ P_a(y) ∧ x \downarrow_\ast y ∧ x ≠ y)\]

4.

\[∃x, y. (P_a(x) ∧ P_a(y) ∧ ¬ (x \downarrow_\ast y) ∧ ¬ (y \downarrow_\ast x) ∧ x ≠ y)\]

5.

\[∃x. ∀y. (x \downarrow_\ast y) ⟹ P_a(y)\]

6.

\[x ≼ y ⟺ x \text{ is before } y \text{ in the frontier} \\ ≝ ∃z, x_0, y_0. z \downarrow_1 x_0 ∧ z \downarrow_1 x_1 ∧ x_0 \downarrow_\ast x ∧ y_0 \downarrow_\ast y \\ ∧ Fr(x) ∧ Fr(y)\]

⟶ \(∃x, y. P_a(x) ∧ P_b(y) \\ ∧ (∃z. x ≼ z ∧ z ≼ y) ∧ x ≼ y\)