درخت اتومات نامتناهی

در علوم کامپیوتر و منطق ریاضی‌, یک درخت اتومات نا متناهی ماشینی از وضعیت ها است که با یک ساختار درختی نا متناهی کار می‌کند. می‌توان به آن به عنوان بسط ای از یک درخت اتومات متناهی که فقط ساختار درختی متناهی را قبول می‌کند نگاه کرد. همچنین می‌توان مانند مانند گسترش برخی اتومات های نامتناهی کلمه ،مانند اتومات بوچی (به انگلیسی: Büchi automaton) و اتومات مولر (به انگلیسی: Muller automaton) نگاه کرد.

یک اتومات متناهی که روی یک درخت نامتناهی اجرا میشود اولین بار توسط رابین برای اثبات تصمیم پذیری منطق مرتبه دوم استفاده شد. علاوه بر این مشاهده شده درخت اتومات و نظریه ها در منطق با همدیگر رابطهٔ نزدیکی دارند که اجازه میدهد مسائل تصمیم در منطق به اتومات های ساده کاهش شوند.

تعریف

درخت اتومات نامتناهی روی $\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$ تایی از وضعیت ها است.
• $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)$ یک اجرا روی درخت ورودی ۲ شرط زیر را برآورده می‌کند:

۱.$r(\epsilon )=q_{0}$

۲.برای هر $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$ باشدآنگاه اجرا پذیرفته میشود. به بوچی‌‌, رابین‌ (به انگلیسی: Rabin) , ستریت (به انگلیسی: Streett) و مولر می‌توان به عنوان چند تا از شرایط های پذیرش جالب توجه اشاره کرد . اگر برای $\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)$ دارای دقیقاً یک عنصر باشد. در غیر این صورت اتومات غیر قطعی است.

زبان های مورد پذیرش درخت

شرایط پذیرش مولر‌, پریتی‌ (به انگلیسی: parity) , رابین و ستریت در درخت اتوماتون نامتناهی زبان های درخت های یکسانی را شناسایی میکنند.

اما بوچی شرط های ضعیف تری رو نسبت به بقیه شرط ها می‌پذیرد، یعنی وجود داره یک زبان درخت که با شرط پذیرش مولر شناخته شود در درخت نامتناهی اما نمی‌تواند توسط بوچی شرط پذیرش به ازای تمامی درخت های نامتناهی شناخته شود .

زبان های درختی که با شرط پذیرش مولر شناخته میشوند نسبت به اجتماع،اشتراک،متمم گیری و تحدید بسته است.