مسئله ارتفاع ستاره

مسئلهٔ ارتفاع ستاره که توسط Eggan Lawrence C مطرح شده‌است، مسئله‌ای در تئوری زبان صوری است که سعی در پاسخ به این پرسش دارد که آیا می‌توان همهٔ زبان منظم را به کمک عبارات منظمی که ارتفاع ستارهٔ محدودی دارند بیان کرد؟ ارتفاع ستارهٔ یک عبارت منظم، بیشینهٔ عمق ستاره‌های تو در تویی است که در آن عبارت وجود دارد. به‌طور مشخص‌تر، این مسئله بیان می‌کند که آیا همیشه عمق تو در توی یک کافی است و امکان‌پذیر است که همهٔ زبان‌های منظم را با عبارات منظم به عمق یک نشان داد؟ اگر پاسخ این سؤال منفی است، آیا الگوریتمی وجود دارد که عمق مورد نیاز را مشخص کند؟

مسئلهٔ اولیه، نخستین بار توسط Eggan پاسخ داده شد [۱]. او با ارائه مثالی نشان داد که پاسخ این پرسش منفی است. او برای هر عدد طبیعی مانند n، یک زبان منظم با ارتفاع ستارهٔ n ارائه داد. ساخت این عبارات به صورت بازگشتی است و به این ترتیب صورت می‌گیرد که عبارت $e_{n+1}$ ، از کنار هم قرار دادن دو نسخهٔ $e_{n}$ و تغییر نام نسخهٔ دوم با نام‌های جدید و پس از آن اضافه کردن یک نشانهٔ جدید در انتها و اضافه کردن پرانتز و ستاره در اطراف عبارت ساخته شده تا اینجا، صورت می‌گیرد.

با به‌کارگیری تنظیم «چپ» تصویر در سمت چپ متن ظاهر می‌شود. Eggan ثابت کرد که هیچ عبارت منظمی با ارتفاع ستارهٔ کمتر از n وجود ندارد که معادل با $e_{n}$ باشد [۱]. هرچند مثال ارائه شده توسط او از الفبای بزرگی استفاده می‌کند که برای زبانی با ارتفاع ستارهٔ n، اندازهٔ آن 2ⁿ-۱ است. به همین دلیل، سؤال دیگری که مطرح کرد این بود که آیا مثال‌هایی روی الفبای دودویی وجود دارد که به این شکل باشند؟ این سؤال به سرعت توسط Dejean و Schützenberger پاسخ داده شد [۳]. آن‌ها مثالی بازگشتی از چنین عباراتی به ازای هر n ارائه دادند. $e_{n}$ در هر گام به این صورت ساخته می‌شود که ابتدا به تعداد 2ⁿ نشانهٔ اول و سپس $e_{n}$ و پس از آن به تعداد 2ⁿ نشانهٔ دوم و در انتها نیز $e_{n}$ قرار می‌گیرد. در نهایت پرانتز دور این عبارت قرار گرفته و ستاره اضافه می‌شود.

Dejean و Schützenberger و Salomaa نشان دادند که هیچ عبارت منظمی با ارتفاع ستارهٔ کمتری نمی‌تواند n را توصیف کند [۳٬۴].

سؤال مطرح شدهٔ دوم، پاسخ به نسبت پیچیده‌تری نسبت به سؤال اول دارد و برای حدود دو دهه به عنوان یکی از مسائل معروف حل نشدهٔ حوزهٔ زبان‌های صوری شناخته می‌شد [2]. Hashiguchi در سال ۱۹۸۸ الگوریتمی برای تعیین ارتفاع ستارهٔ هر عبارت منظمی ارائه داد. اما این الگوریتم عملی نیست و به محاسباتی می‌انجامد که حتی برای مثال‌های کوچک نیز امکان‌پذیر نیست. الگوریتم بهینه‌تری توسط Kirsten در سال ۲۰۰۵ ارائه شد، اما حتی این الگوریتم هم فاصلهٔ زیادی با آنچه که قابل انجام است، دارد [۵]. این الگوریتم توسط Colcombet و Löding در سال ۲۰۰۸ کلی‌سازی و بهینه‌سازی شده‌است [۶] و در سال ۲۰۱۷ در ابزار Stamina پیاده‌سازی شده‌است [۷].^[۱]^[۲]^[۳]^[۴]^[۵]^[۶]^[۷]

منابع

↑ Eggan, Lawrence C. (1963). "Transition graphs and the star-height of regular events". Michigan Mathematical Journal. 10 (4): 385–397.
↑ Brzozowski, Janusz A. (1980). "Open problems about regular languages". In Book, Ronald V. Formal language theory—Perspectives and open problems. New York: Academic Press. pp. 23–47.
↑ Dejean, Françoise; Schützenberger, Marcel-Paul (1966). "On a Question of Eggan". Information and Control. 9 (1): 23–25.
↑ Salomaa, Arto (1981). Jewels of Formal Language Theory. Melbourne: Pitman Publishing.
↑ Kirsten, Daniel (2005). "Distance desert automata and the star height problem". RAIRO Theoretical Informatics and Applications. 39 (3): 455–509.
↑ Thomas Colcombet, Christof Löding: "The Nesting-Depth of Disjunctive µ-Calculus for Tree Languages and the Limitedness Problem". CSL 2008: 416-430
↑ Nathanaël Fijalkow, Hugo Gimbert, Edon Kelmendi, Denis Kuperberg: "Stamina: Stabilisation Monoids in Automata Theory". CIAA 2017: 101-112

[1] Eggan, Lawrence C. (1963). "Transition graphs and the star-height of regular events". Michigan Mathematical Journal. 10 (4): 385–397.

[2] Brzozowski, Janusz A. (1980). "Open problems about regular languages". In Book, Ronald V. Formal language theory—Perspectives and open problems. New York: Academic Press. pp. 23–47.

[3] Dejean, Françoise; Schützenberger, Marcel-Paul (1966). "On a Question of Eggan". Information and Control. 9 (1): 23–25.

[4] Salomaa, Arto (1981). Jewels of Formal Language Theory. Melbourne: Pitman Publishing.

[5] Kirsten, Daniel (2005). "Distance desert automata and the star height problem". RAIRO Theoretical Informatics and Applications. 39 (3): 455–509.

[6] Thomas Colcombet, Christof Löding: "The Nesting-Depth of Disjunctive µ-Calculus for Tree Languages and the Limitedness Problem". CSL 2008: 416-430

[7] Nathanaël Fijalkow, Hugo Gimbert, Edon Kelmendi, Denis Kuperberg: "Stamina: Stabilisation Monoids in Automata Theory". CIAA 2017: 101-112

[۱]

[۲]

[۳]

[۴]

[۵]

[۶]

[۷]