اتوماتای سنگ‌ریزه

اتوماتای سنگ‌ریزه (به انگلیسی: pebble automaton)، یک درخت را به عنوان ورودی می‌گیرد و روی گره‌های درخت از طریق یال‌ها حرکت می‌کند. به علاوه، این اتوماتا یک مجموعه‌ی متناهی با اندازه‌ی ثابت از «سنگ‌ریزه‌ها» دارد که از 1 تا k شماره‌گذاری شده‌اند و می‌تواند آن‌ها را روی گره‌های درخت بگذارد. در یک گام اتوماتا می‌تواند روی گره فعلی بماند، به گره پدر برود، به گره فرزند چپ یا راست برود. همین‌طور می‌تواند سنگ‌ریزه‌ی iم را بردارد، یا سنگ‌ریزه‌ی i-1م را رو گره فعلی قرار دهد. این که در هر گام اتوماتا چه تصمیمی می‌گیرد، بستگی به حالت فعلی اتوماتا، مجموعه‌ی سنگ‌ریزه‌هایی که روی گره فعلی قرار دارد، برچسب گره فعلی، و نوع گره فعلی (ریشه، فرزند چپ یا راست، برگ یا گره داخلی) دارد.

تعریف دقیق

مجموعه‌ی {TYPE = {r, 0, 1} × {l, i، انواع ممکن برای یک گره را دربردارد. در این‌جا r برای ریشه، 0 فرزند برای فرزند چپ، 1 برای فرزند راست، l برای برگ، و i برای گره درونی در نظر گرفته شده است. مجموعه‌ی {MOVES = {ε, ←, →, ↑, lift, drop، انواع حرکت‌های ممکن را برای اتوماتا دربرمی‌گیرد. در این‌جا ↑ برای رفتن به گره پدر، ← برای رفتن به فرزند چپ، → برای رفتن به فرزند راست، drop برای گذاشتن سنگ‌ریزه، و lift برای برداشتن سنگ‌ریزه در نظر گرفته شده است. همین‌طور مجموعه‌ی توانی یک مجموعه مانند S را با (P(S نشان می‌دهیم.

یک اتوماتای سنگ‌ریزه که k سنگ‌ریزه دارد، یک چندتاییِ (A = (Σ,Q, I, F, δ است، که Q مجموعه‌ای متناهی از حالت‌هاست، I ⊆ Q مجموعه‌ی حالات اولیه، F ⊆ Q مجموعه‌ی حالات پایانی، و δ رابطه‌ی گذر (به انگلیسی: transition relation) است.

(δ ⊆ (Q × TYPES × {1, . . . , k + 1} × P({1, · · · , k}) × Σ) × (Q × MOVES

چندتاییِ q, β, i, S, σ, q′,m) ∈ δ) بیان می‌کند که اگر A در حالت q باشد، سنگ‌ریزه‌های i تا k در درخت باشند، مجموعه‌ی S سنگ‌ریزه‌های گره فعلی را دربرداشته باشد، گره از نوع β باشد و برچسب σ داشته باشد، آن‌گاه A به حالت ′q می‌رود و باتوجه به m حرکت می‌کند.

انواع

اتوماتای سنگ‌ریزه بسته به نحوه‌ی برداشتن سنگ‌ریزه‌ها، در دو نوع بررسی می‌شود:

• ضعیف: در اتوماتای سنگ‌ریزه‌ی ضعیف، سنگ‌ریزه‌ها را در صورتی می‌توان برداشت که روی گره فعلی باشند.
• قوی: در اتوماتای سنگ‌ریزه‌ی قوی محدودیت گره فعلی وجود ندارد و سنگ‌ریزه‌ها را می‌توان از هر گرهی برداشت.

به صورت پیش‌فرض اتوماتا قوی در نظر گرفته می‌شود.

قطعیت و عدم قطعیت

یک اتوماتای سنگ‌ریزه قطعی است، اگر δ یک تابع جزیی (به انگلیسی: partial function) از Q × types × {1, · · · , k + 1} × P({1, · · · , k}) × Σ به Q × moves باشد.

نمادگذاری

مجموعه‌ی زبان‌های تشخیص‌پذیر توسط اتوماتای سنگ‌ریزه‌ی قطعیِ قوی با n سنگ‌ریزه با sDPA_n نشان داده می‌شود. همین طور مجموعه‌ی زبان‌های تشخیص‌پذیر توسط اتوماتای درخت‌پیما (به انگلیسی: tree walking automaton) با TWA و مجموعه‌ی زبان‌های تشخیص‌پذیر توسط اتوماتای پایین‌به‌بالا (به انگلیسی: bottom-up tree automaton) با REG نشان داده می‌شود.

ویژگی‌ها

• $PA\subsetneq REG$
• برای هر $n\geqslant 0$:
  • $PA_{n}\subsetneq PA_{n+1}$و $DPA_{n}\subsetneq DPA_{n+1}$
  • $TWA\nsubseteq DPA_{n}$
  • $sPA_{n}=PA_{n}$و $sDPA_{n}=DPA_{n}$
  • $sDPA_{n}$تحت مکمل‌گیری بسته است.

یک نتیجه در منطق

اگر $FO+TC$، مجموعه‌ی ویژگی‌های قابل توصیف درخت در منطق مرتبه‌ی اول بستار تعدی (به انگلیسی: transitive closure first-order logic) باشد، و $FO+posTC$همان مجموعه در منطق بستار تعدی مثبت باشد، ثابت می‌شود که $PA\subsetneq FO+TC$، و در واقع $PA=FO+posTC$. یعنی مجموعه‌ی زبان‌های تشخیص‌پذیر توسط اتوماتای سنگ‌ریزه با مجموعه‌ی زبان‎های قابل‌توصیف در منطق بستار تعدی مثبت برابر است.