اتوماتای نخی

در نظریه اتوماتا، شاخه‌ای از علوم کامپیوتر نظری، اتوماتای نخی (به انگلیسی: Thread automata) ماشینی قدرمتند است، که اولین بار در سال ۲۰۰۲ توسط اریک کلرگری (به انگلیسی: Eric Clergerie) معرفی شد. این ماشین، طیف گسترده‌ای از زبان‌های نیمه حساس به متن (به انگلیسی: Mildly context-sensitive languages) را می‌پذیرد. به‌طور خاص، اتوماتای نخی دستهٔ سیستم های بازنویسی مستقل از متن خطی (به انگلیسی: Linear Context-free Rewriting Systems) را به‌طور کامل می‌پذیرد و حتی قدرت پذیرش زبان‌هایی فراتر از این دسته را نیز دارد. اتوماتای نخی، نسخه‌ای گسترده‌تر و ساده‌تر از ماشین‌هایی است که قبل از آن برای تجزیه زبان‌های نیمه حساس به متن پیشنهاد شده بودند. از این قبیل ماشین‌ها می‌توان به اتوماتای دو پشته‌ای (به انگلیسی: Two-stack automata) که برای گرامرهای درخت مجاورت (به انگلیسی: Tree-adjoining grammars) پیشنهاد شده بود، اشاره کرد.

ایده کلی

اتوماتای نخی غیرقطعی می‌باشد، و اگر تمام حالات ممکن، مستقل از یکدیگر دنبال شوند، پیچیدگی محاسباتی آن‌ها نمایی خواهد شد. اما به همراه نمایش فشردهٔ زیراشتقاق‌ها و نیز تکنیک‌های جدول‌بندی، پیچیدگی محاسباتی آن‌ها چندجمله‌ای می‌شود. ایدهٔ کلی اتوماتای نخی بر این اساس است که در هر لحظه مجموعه‌ای از نخ‌ها وجود دارند که یکی از آن‌ها فعال است. حرکات در اتوماتا نیز به این صورت است که نخ‌ها ممکن است یک زیرنخ جدید را ایجاد کنند، تمام شوند، و یا معلق شده و کنترل را به پدر و یا یکی از فرزندان خود بازگردانند.

تعریف رسمی

اتوماتای نخی به یک نه‌تایی $M=(N\ ,T\ ,S\ ,F\ ,\kappa \ ,\mathrm {K} \ ,\delta \ ,U\ ,\Theta )\!$ گفته می‌شود، بدین صورت که:

• $N$ مجموعهٔ متناهی از نمادهای غیر-پایانه است.
• $T$ مجموعهٔ متناهی از نمادهای پایانه است.
• $S$ غیر-پایانهٔ ابتدایی است.
• $F$ غیر-پایانهٔ انتهایی است.
• $\kappa$ یک تابع راه اندازی (به انگلیسی: Triggering function) است که یک تابع جزیی (به انگلیسی: Partial function) از $N$ به یک مجموعهٔ متناهی $\mathrm {K}$ را تعریف می‌کند، که برای دریافت کردن اطلاعاتی که در یک نخ به‌دست آمده در جهت راه اندازی درخواست برای نوعی از انتقال‌ها (به انگلیسی: Transitions) استفاده می‌شود.
• $U$ مجموعهٔ متناهی از برچسب‌ها است که برای شناسایی نخ‌ها از آن استفاده می‌شود. علاوه بر این، مجموعهٔ متناهی $U$ توسط تابع جزیی $\delta$ نیز استفاده می‌شود.
• $\delta$ یک تابع جزیی از $N$ به $U\ \cup \ \{\perp \}$ است که برای مشخص کردن نخ‌هایی که ممکن است در زمانی ساخته شوند و یا ادامه یابند استفاده می‌شود.
• $\Theta$ مجموعه‌ای متناهی از انتقال‌ها است.

حال اگر $M=(N\ ,T\ ,S\ ,F\ ,\kappa \ ,\mathrm {K} \ ,\delta \ ,U\ ,\Theta )\!$ یک اتوماتای نخی باشد:

• یک نخ عبارت است از یک جفت $p:A$ که در آن $p=u_{1}\ ...\ u_{n}\in U^{*}$ یک مسیر نخ (به انگلیسی: Thread path) است که می‌تواند خالی باشد، و $A$ نیز یک نماد غیر-پایانه از $N$ است که محتوای آن نخ می‌باشد.
• یک انبار نخ (به انگلیسی: Thread store)، مجموعه‌ای از نخ‌ها است که نمایان‌گر تابعی از $dom(S)$ به $N$ است که $dom(s)\subset U^{*}$ نسبت به پیشوند بسته است و یا در واقع $pu\in dom(S)\Rightarrow p\in dom(S)$.
• یک پیکربندی (به انگلیسی: Configuration) از $M$ یک سه‌تایی $(l,\ p,\ S)$ است که در آن $l$ مکان فعلی در رشتهٔ ورودی را مشخص می‌کند، $S$ یک انبار نخ است و $p$ یک مسیر نخ در $S$ است.
• عمل جابه‌جایی (به انگلیسی: SWAP) محتوای یک نخ فعال را تغییر می‌دهد.
• عمل PUSH یک زیرنخ جدید را ایجاد کرده و پدر آن‌را معلق می‌کند.
• عمل POP نخ فعال را پایان داده و کنترل را به پدر آن نخ بازمی‌گرداند.
• عمل SPUSH یک زیرنخ معلق شده از نخ فعال فعلی را، دوباره فعال می‌کند.
• عمل SPOP پدر نخ فعال فعلی را، دوباره فعال می‌کند.

زبان یک اتوماتای نخی، مجموعه‌ای از کلمات است که می‌توان با شروع از مجموعه نخ $\{\epsilon :S\}$ و بعد از خواندن تمام ورودی به مجموعه نخ $\{\epsilon :S,\ \delta (S):F\}$ رسید.

جستارهای وابسته

• نظریه اتوماتا
• زبان‌های نیمه حساس به متن
• گرامرهای درخت مجاورت
• سیستم های بازنویسی مستقل از متن خطی