Automat beskonačnog stabla

U informatici i matematičkoj logici, automat beskonačnog stabla je konačna mašina koja se bavi strukturom beskonačnog stabla. Može se posmatrati kao produžetak konačnog automata stabla, koja prihvata samo konačne strukture stabla. Takođe se može posmatrati kao proširenje nekih beskonačnih automata reči, kao što su Büchi i Muller automat.

Konačni automat koji radi na beskonačnom stablu je prvi put koristio Rabin za dokazivanje odlučivosti monadne logike drugog reda. Kasnije je primećeno da su automat stabla i logičke teorije usko povezani i omogućavaju da problem odlučivanja u logici bude smanjen na problem odlučivanja automata.

Definicija

Automat beskonačnog stabla radi preko $\Sigma$-obeleženog stabla. Postoji mnogo blago različitih formulacija automata stabla. Ovde je jedna od formulacija opisana. Automat beskonačnog stabla je konačan niz $A=(\Sigma ,D,Q,\delta ,q_{0},F)$ u kome,

• $\Sigma$ je pismo.
• $D\subset \mathbb {N}$ je konačan skup. Svaki element $D$ je dozvoljen stepen u ulaznom stablu.
• $Q$ je konačan skup stanja.
• $\delta :Q\times \Sigma \times D\rightarrow 2^{Q^{*}}$ je tranzitna veza koja preslikava stanje automata $q\in Q$, ulazno slovo $\sigma \in \Sigma$, i stepen $d\in D$ u skup d-torke stanja.
• $q_{0}\in Q$ je početno stanje automata.
• $F\subseteq \Sigma ^{\omega }$ je prihvatanje uslova.

Pokretanje

Pokretanje automata stabla $A$ preko $\Sigma$-označenog stabla $(T,V)$ je $Q$-označeno stablo $(T_{r},r)$. Pretpostavimo da je automat stabla u stanju $q$ i da je dostigao do čvora t označenog sa $\sigma \in \Sigma$ ulaznog stabla. $d(t)$ je stepen čvora t. Zatim, automat nastavlja selektujući konačan niz $(q_{1},...,q_{d(t)})$ iz skupa $\delta (q,\sigma ,d(t))$ i cepanju u $d(t)$ kopije sebe. Za svaki $0<i\leq d(t)$, jedna kopija ulazi u $q_{i}$ stanje i nastavlja do čvora $t.i$. Ovaj proces proizvodi pregaženo stablo.

Formalno, pokretanje $(T_{r},r)$ na ulaznom stablu zadovoljava sledeća dva uslova:

1. $r(\epsilon )=q_{0}$
2. Za svako $t\in T_{r}$ i $r(t)=q$, postoji $(q_{1},...,q_{d(t)})\in \delta (q,V(t),d(t))$ kao i za svako $0<i\leq d(t)$, imamo $t.i\in T_{r}$ i $r(t.i)=q_{i}$

Prihvatanje uslova

U pokretanju $(T_{r},r)$, beskonačni put je obeležen kao niz stanja. Ovaj niz stanja formira beskonačnu reč preko stanja. Ako sve ove beskonačne reči pripadaju prihvatajućem uslovu $F$, tada je pokretanje prihvatajuće. Zanimljivi uslovi prihvatanja su Büchi, Rabin i Muller. Ako za ulaz $\Sigma$-označenog stabla $(T,V)$ postoji prihvaćeno pokretanje tada je ulazno stablo prihvaćeno od strane automata. Skup svih prihvaćenih $\Sigma$-označenih stabala se naziva jezik stabala ${\mathcal {L}}(A)$ koji je prepoznat od strane automata stabla $A$.

Napomene

Skup D može izgledati neobično nekim ljudima. Ponekad D je izostavljen iz definicije kada je niz sa jednim elementom, što znači da ulazno stablo ima fiksirano grananje u svakom čvoru. Na primer, ako je D = {2} onda ulazno stablo mora da bude potpuno binarno stablo.

Automat beskonačnog stabla je deterministički, ako za neke $q\in Q$, $\sigma \in \Sigma$, i $d\in D$ tranzitni odnos $\delta (q,\sigma ,d)$ ima tačno jedan element. Inače, automat je ne-deterministički.

Prihvatanje jezika stabla

Muller, parity, Rabin, i Streett prihvatanje uslova u automatu beskonačnog stabla prepoznaju isti jezik stabla.

Ali, Büchi prihvatanje uslova je strogo slabije od ostalih prihvatanja uslova, odnosno, postoji jezik stabla koji može biti prepoznat po Muller prihvatanju uslova u automatu beskonačnog stabla, ali ne može biti priznata od strane bilo kog Büchi prihvatanja uslova u nekim automatima beskonačnog stabla.

Jezici stabala koji su prepoznati od strane Muller prihvatanja uslova su zatvoreni u uniji, preseku, projekciji i komplementarnosti.