Аутомат бесконачног стабла

У информатици и математичкој логици, аутомат бесконачног стабла је коначна машина која се бави структуром бесконачног стабла. Може се посматрати као продужетак коначног аутомата стабла, која прихвата само коначне структуре стабла. Такође се може посматрати као проширење неких бесконачних аутомата речи, као што су Büchi и Muller аутомат.

Коначни аутомат који ради на бесконачном стаблу је први пут користио Рабин за доказивање одлучивости монадне логике другог реда. Касније је примећено да су аутомат стабла и логичке теорије уско повезани и омогућавају да проблем одлучивања у логици буде смањен на проблем одлучивања аутомата.

Дефиниција

Аутомат бесконачног стабла ради преко $\Sigma$-обележеног стабла. Постоји много благо различитих формулација аутомата стабла. Овде је једна од формулација описана. Аутомат бесконачног стабла је коначан низ $A=(\Sigma ,D,Q,\delta ,q_{0},F)$ у коме,

• $\Sigma$ је писмо.
• $D\subset \mathbb {N}$ је коначан скуп. Сваки елемент $D$ је дозвољен степен у улазном стаблу.
• $Q$ је коначан скуп стања.
• $\delta :Q\times \Sigma \times D\rightarrow 2^{Q^{*}}$ је транзитна веза која пресликава стање аутомата $q\in Q$, улазно слово $\sigma \in \Sigma$, и степен $d\in D$ у скуп d-торке стања.
• $q_{0}\in Q$ је почетно стање аутомата.
• $F\subseteq \Sigma ^{\omega }$ је прихватање услова.

Покретање

Покретање аутомата стабла $A$ преко $\Sigma$-означеног стабла $(T,V)$ је $Q$-означено стабло $(T_{r},r)$. Претпоставимо да је аутомат стабла у стању $q$ и да је достигао до чвора t означеног са $\sigma \in \Sigma$ улазног стабла. $d(t)$ је степен чвора t. Затим, аутомат наставља селектујући коначан низ $(q_{1},...,q_{d(t)})$ из скупа $\delta (q,\sigma ,d(t))$ и цепању у $d(t)$ копије себе. За сваки $0<i\leq d(t)$, једна копија улази у $q_{i}$ стање и наставља до чвора $t.i$. Овај процес производи прегажено стабло.

Формално, покретање $(T_{r},r)$ на улазном стаблу задовољава следећа два услова:

1. $r(\epsilon )=q_{0}$
2. За свако $t\in T_{r}$ и $r(t)=q$, постоји $(q_{1},...,q_{d(t)})\in \delta (q,V(t),d(t))$ као и за свако $0<i\leq d(t)$, имамо $t.i\in T_{r}$ и $r(t.i)=q_{i}$

Прихватање услова

У покретању $(T_{r},r)$, бесконачни пут је обележен као низ стања. Овај низ стања формира бесконачну реч преко стања. Ако све ове бесконачне речи припадају прихватајућем услову $F$, тада је покретање прихватајуће. Занимљиви услови прихватања су Büchi, Rabin и Muller. Ако за улаз $\Sigma$-означеног стабла $(T,V)$ постоји прихваћено покретање тада је улазно стабло прихваћено од стране аутомата. Скуп свих прихваћених $\Sigma$-означених стабала се назива језик стабала ${\mathcal {L}}(A)$ који је препознат од стране аутомата стабла $A$.

Напомене

Скуп D може изгледати необично неким људима. Понекад D је изостављен из дефиниције када је низ са једним елементом, што значи да улазно стабло има фиксирано гранање у сваком чвору. На пример, ако је D = {2} онда улазно стабло мора да буде потпуно бинарно стабло.

Аутомат бесконачног стабла је детерминистички, ако за неке $q\in Q$, $\sigma \in \Sigma$, и $d\in D$ транзитни однос $\delta (q,\sigma ,d)$ има тачно један елемент. Иначе, аутомат је не-детерминистички.

Прихватање језика стабла

Muller, parity, Rabin, и Streett прихватање услова у аутомату бесконачног стабла препознају исти језик стабла.

Али, Büchi прихватање услова је строго слабије од осталих прихватања услова, односно, постоји језик стабла који може бити препознат по Muller прихватању услова у аутомату бесконачног стабла, али не може бити призната од стране било ког Büchi прихватања услова у неким аутоматима бесконачног стабла.

Језици стабала који су препознати од стране Muller прихватања услова су затворени у унији, пресеку, пројекцији и комплементарности.