Exercises 2 : Non-Recognizable Languages and Commutative closure

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

⟹ contradiction

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

Leave a comment