# EX 1 : an abstract language

• $t$ linear ⟺ one occurrence of $x_i$ at most

• $C ∈ 𝒞(𝔉) ⟺ C = \text{ a term wth a hole }$
• $σ \text{ ground substitution} ⟺ tσ \text{ without variables}$

## 1.

Show that

$Red({\cal E}) ≝ \lbrace C[tσ] \mid C ∈ C(𝔉), t ∈ {\cal E}, σ \text{ ground substitution} \rbrace$

is recognizable (sufficient since recognized languages are closed under union):

Ex:

$t = f(f(x_1, x_2), x_3)$

$C(f(f(t_1, t_2), t_3), t’) ∈ Red(\lbrace t \rbrace)$

• $Q ≝ \lbrace q_\bot \rbrace ∪ \underbrace{Pos(t)}_{\ni ε}$

• $F = \lbrace ε \rbrace$

• $Δ ≝$

• $f(w0, \ldots, w(n-1)) ⟶ w \quad \text{ if } t_w = f$
• $f(q_1, \ldots, q_n) ⟶ ε \quad \text{ if } ∃i, q_i = ε$
• for all $f$ and $q_i$:
• $f(q_1, \ldots, q_n) ⟶ w ∈ Pos(t) \quad \text{ s.t. } t_w \text{ is a variable}$
• $f(q_1, \ldots, q_n) ⟶ q_\bot$
• for all $a^{(0)} ∈ 𝔉$, for all $w ∈ Pos(t)$ s.t. $t_w = a$:
• $a ⟶ w ∈ Pos(t)$

## 2.

Ground terms ⟺ no variables

$Red(\lbrace t \rbrace) ≝ \lbrace C[t] \mid C ∈ C(𝔉) \rbrace$

$n ≝ \text{ number of nodes of } {\cal E}$

We can’t consider just one term as before, before we lose the determinism when doing the union.

Ex:

• $n=8$: $t_1 = f(a, a), \; t_2 = f(f(a, a), a)$

• as $t_1 ⊆ t_2$: one can just ignore $t_2$ (by propagating the accepting state for $t_1$)
$Q ≝ \lbrace q_t \mid \underbrace{t \text{ is a subtree of a tree of } {\cal E}}_{t ∈ Sub({\cal E})} \rbrace ∪ \lbrace q_\bot, q_\top \rbrace$
• $Δ ≝$

• $f(q_{t_1}, \ldots, q_{t_n}) ⟶ q_{f({t_1}, \ldots, {t_n})} \quad \text{ if } f({t_1}, \ldots, {t_n}) ∈ Sub({\cal E})\backslash {\cal E}$
• $f(q_{t_1}, \ldots, q_{t_n}) ⟶ q_\top \quad \text{ if } f({t_1}, \ldots, {t_n}) ∈ {\cal E}$
• $f(q_{t_1}, \ldots, q_{t_n}) ⟶ q_\top \quad \text{ if } ∃i; q_i = q_\top$
• else (the other cases don’t apply): $f(q_{t_1}, \ldots, q_{t_n}) ⟶ q_\bot$

# EX 2 : Commutative closure

$𝔉 ≝ \lbrace f(2), a(0), b(0) \rbrace$

## 1.

$L_1$, defined as follows:

1. $f(a,b) ∈ L_1$
2. $t∈ L_1 ⟹ f(a, f(t, b)) ∈ L_1$

is recognizable.

• $Q ≝ \lbrace q_a, q_b, q_f, q_\top \rbrace$

• $F ≝ \lbrace q_\top \rbrace$

• $Δ ≝$

• $a ⟶ q_a$
• $b ⟶ q_b$
• $f(q_a, q_b) ⟶ q_\top$
• $f(q_\top, q_b) ⟶ q_f$
• $f(q_a, q_b) ⟶ q_\top$

## 2.

$L_2 ≝ \lbrace t ∈ T({\cal F}) \mid \vert t \vert_a = \vert t \vert_b \rbrace$

is not recognizable.

Proof: By contradiction, assume it’s the case.

Then, by the pumping lemma, there exists $k$ s.t.

$∀t∈ L, \; Height(t) ≥ k$

There exists $C ∈ C(T)$ s.t. there exists $C’ ∈ C(T) \backslash \lbrace ε \rbrace$ s.t.

$\begin{cases} ∃ u; \; t = C[C'(u)] \\ ∀n, C[C'^n (u)] ∈ L \end{cases}$

Let

$t ≝ f\Big(\,f(f(f(⋯f(b, b), ⋯ b), b), b), \; f(a, f(a, f(⋯ f(a, a) ⋯ )))) \, \Big)$

$height(t) ≥ k$ so we have $C, C’, u$ s.t. $t = C[C’(u)]$ and:

• $C[C’^2 (u)] ∈ L$ by the pumping lemma
• $C[C’^2 (u)] ∉ L$ because

## 3.

$C(L)$: commutative closure

If $f(q,q’) ⟶ q’’$, then we add $f(q’, q) ⟶ q’’$

## 4.

$\underbrace{L_2}_{\text{not recognizable}} = AC(\underbrace{L_1}_{\text{recognizable}}))$

# EX 3 : Decision problems

## 1.

$t$ linear: GTT P-complete ?

• $GII ∈ P$ ?
• $∃ A ∈ P-complete; A ≼ GII$ ?

Reminder:

• emptiness of language ⟶ P-complete

• intersection non emptiness ⟶ EXPTIME-complete

1. With EX1.1), we can construct $𝔅$ such that $L(𝔅) = \lbrace t σ \mid σ \text{ ground substitution} \rbrace$

Then: $L(𝒜) ∩ L(𝔅) ≠ ∅ ⟺ GII$

1. Let $𝒜$ be a tree automaton: $L(𝒜) ≠ ∅ ⟺ \underbrace{GII \text{ of } x \text{ and } 𝒜}_{L(𝒜) ∩ Σ^\ast ≠ ∅}$

## 2.

$𝒜$ is now assumed to be deterministic.

• $GII ∈ NP$ ?
• $∃ A ∈ NP-complete; A ≼ GII$ ?
1. We just guess an accessible state where is the variable $x$, then we run the automaton on this

2. reduction to SAT

Tags:

Updated: