Gry Ehrenfeucht-Fraïssé (w rzeczywistości Ajtai-Fagin) dla zwykłych języków.

Immerman (Complexity opisowa, 1999) przedstawia gry EF dla egzystencjalnej monadycznej drugiego rzędu (Gry Ajtai-Fagin) na stronie 127. Jak MSO na słowach jest odpowiednikiem zwykłych języków, gra może być napisany w sposób następujący. $\exists$

Język jest regularny tylko wtedy, gdy Delilah nie ma strategii wygranej w następującej grze: 1. Samson wybiera , 2. Delilah wybiera , 3. Samson wybiera podzbiory ze zbioru pozycji w (tj. ), 4. Delilah wybiera Podzbiory i zbioru pozycji w , 5. Samson i Delilah grają $L \subseteq \{a, b\}^*$
włącz grę EF na $c, m \in \mathbb{N}$
$w \in L$
$c$ $C_1^w, \ldots, C_c^w$ $w$ $\{0, \ldots, |w|-1\}$
$v \not\in L$ $c$ $C_1^v, \ldots, C_c^v$ $v$
$m$ i, gdziejest strukturą związaną ze słowem, tj .: $(\mathfrak{S}(w), C_1^w, \ldots, C_c^w)$ $(\mathfrak{S}(v), C_1^v, \ldots, C_c^v)$
$\mathfrak{S}(w)$ $w$

S (w) = ⟨ {0, \dots, | w | - 1}, S U C C, Q_{a}, Q_{b} ⟩

$\mathfrak{S}(w) = \langle \{0, \ldots, |w|-1\}, SUCC, Q_a, Q_b \rangle$ z

, a

jest predykatem następcy binarnej.

Q_{l} = {p | w_{p} = l}

$Q_l = \{p \;|\; w_p = l\}$

S U C C

$SUCC$

Mam dwa pytania:
- Jak pokazać, że nie jest regularne, przy użyciu takiego argumentu EF, - Czy jest łatwiej / trudniej grać w te gry (aby wykazać nieregularność), gdy ktoś ma relację uporządkowania niż następcy? (Są one równoważne w egzystencjalnym MSO). $\{a^nb^n \;|\; n \in \mathbb{N}\}$

lo.logic automata-theory descriptive-complexity

— Michaël Cadilhac
źródło

$c$ $m$ $w = a^n b^n$ $n$ $C^w_1,\ldots,C^w_c$ $w$ $2^c$ $w'$ $w'[i,\ldots,j]$ $w'$ $r$ $t$

$0 \leq i \leq j \leq n$ $w'$
$r$ $r$ $i$ $j$ $w'$
$k \in [i,\ldots,j]$ $r$ $k$ $w'$ $r$ $t$ $w'$

v^{'} = w^{'} [0, \dots, i - 1] w^{'} [i, \dots, j]^{2} w^{'} [j + 1, \dots, 2 n - 1] .

$v' = w'[0,\ldots,i-1] w'[i,\ldots,j]^2 w'[j+1,\ldots,2n-1].$

v

$v$

a, b

${a,b}$

v^{'}

$v'$

v

$v$

L

$L$

a

$a$

m

$m$

w^{'}

$w'$

v^{'}

$v'$

r

$r$

t

$t$

c

$c$

m

$m$

$n$ $c$ $m$ $r$ $t$ $w'[i,\ldots,j]$ $r$

To działało w przypadku następców. Przy liniowym porządku będzie to trochę trudniejsze, ale nie myślałem o tym zbyt wiele.

Zauważ, że nic dziwnego, że ten argument wygląda trochę jak argument „pompowania” w automatach. Jednak nie jest tak głupie, jak zwykłe przetłumaczenie formuły na automat. Myślę, że liczy się to jako argument teoretyczny.

— slimton
źródło

Czy moja odpowiedź cię nie przekonuje?

— slimton

Ups, przepraszam, oczywiście że tak. Chociaż byłbym bardzo zainteresowany, aby zobaczyć, co by to było z porządkiem liniowym (a więc bez lokalizacji Hanfa). Dziękuję za tę odpowiedź!

— Michaël Cadilhac