مسئله کلمات جداکننده
در علوم نظری رایانه، مسئله کلمات جداکننده، مسئله یافتن کوچک‌ترین ماشین متناهی قطعی است که در دو رشته داده شده رفتار متفاوتی دارد، به این معنی که یکی از دو رشته را می‌پذیرد و رشته دیگر را رد می‌کند. یافتن تعداد حالات این ماشین، یک مسئله باز است و در بدترین حالت، تابعی از طول رشته‌های ورودی است.
مثال[ویرایش]
دو رشته ۰۰۱۰ و ۱۰۰۰ می‌توانند توسط یک ماشین سه حالته از یکدیگر متمایز شوند که در آن انتقال از حالت شروع به دو حالت مختلف می‌رود، که هر دو پایانی هستند به این معنا که انتقال‌های بعدی از این دو حالت همیشه به همان حالت اولیه بازمی‌گردد. حالت این ماشین اولین نماد رشته ورودی را ثبت می‌کند. اگر یکی از دو حالت پایانی قبول و دیگری رد باشد، ماشین تنها یکی از رشته‌های ۰۰۱۰ و ۱۰۰۰ را می‌پذیرد. با این حال، این دو رشته را نمی‌توان با هیچ ماشینی با کمتر از سه حالت متمایز کرد.[۱]
ساده‌سازی مفروضات[ویرایش]
برای اثبات کرانه‌های این مسئله، بدون از دست دادن کلیت، فرض می‌شود که ورودی‌ها، رشته‌هایی روی یک الفبای دو حرفی هستند؛ زیرا، اگر دو رشته در یک الفبای بزرگ‌تر با هم متفاوت باشند، یک هم‌ریختی رشته‌ای وجود دارد که آنها را به رشته‌هایی باینری با طول یکسان، نگاشت می‌کند که در این نگاشت، هر دو رشته همچنان با هم متفاوت هستند. هر ماشینی که این دو رشته باینری را متمایز می‌کند، می‌تواند به ماشینی تبدیل شود که رشته‌های اصلی را بدون هیچ افزایشی در تعداد حالت‌ها متمایز کند.[۱]
همچنین ممکن است فرض شود که طول دو رشته برابر است. برای رشته‌هایی با طول نامساوی، همیشه یک عدد اول p وجود دارد که مقدار آن تابع لگاریتمیکی از طول کوچک‌تر است، به طوری که دو طول، دو هم‌نهشتی p متفاوت هستند. در این مورد می‌توان از ماشینی که طول مدول ورودی p را شمارش می‌کند برای تشخیص دو رشته از یکدیگر استفاده کرد؛ بنابراین، رشته‌هایی با طول‌های نابرابر همیشه می‌توانند توسط ماشینی با حالت‌های کم از یکدیگر متمایز شوند.[۱]
تاریخچه و کرانه‌ها[ویرایش]
مسئله محدود کردن اندازه ماشینی که دو رشته داده شده را از هم متمایز می‌کند، برای اولین بار توسط (Goralčík و Koubek 1986) فرموله شد، که نشان دادند اندازه ماشین همیشه زیرخطی است.[۲] بعدها، (Robson 1989) بهترین کران بالایی شناخته شده، O(n2/5(log n)3/5)، در اندازه ماشینی که ممکن است مورد نیاز باشد را اثبات کرد.[۳] این مقدار توسط (Chase 2020) به O(n1/3(log n)7) بهبود یافت.
جفت ورودی‌هایی وجود دارند که هر دو رشته‌های باینری به طول n هستند و هر ماشینی که ورودی‌ها را متمایز می‌کند باید اندازه Ω(log n) باشد. بستن شکاف بین این کران پایین و کران بالایی رابسون همچنان یک مسئله باز است.[۱] جفری شالیت جایزه ۱۰۰ پوندی بریتانیا را برای هر بهبودی در حد بالایی رابسون در نظر گرفته‌است.[۴]
حالت‌های خاص[ویرایش]
چندین مورد خاص از مسئله جداکننده کلمات، با استفاده از چند حالت مشخص، قابل حل شناخته شده‌است:
- اگر دو کلمه باینری دارای تعداد متفاوتی صفر یا یک باشند، آنگاه می‌توان آنها را با شمارش مدول وزن‌های همینگ آنها با اندازه لگاریتمی عددی اول، با استفاده از تعداد لگاریتمی حالت‌ها از یکدیگر متمایز کرد. به‌طور کلی، اگر یک الگوی طول k، متفاوت بار در دو کلمه ظاهر شود، می‌توان‌آنها را با استفاده از تعداد O(k log n) حالت از یکدیگر متمایز کرد.[۱]
- اگر دو کلمه باینری در اولین یا آخرین k با یکدیگر متفاوت باشند، می‌توان آنها را با استفاده از k + O(1) حالت از یکدیگر متمایز کرد. این نشان می‌دهد که تقریباً همه جفت‌های کلمات باینری را می‌توان با تعداد لگاریتمی از حالت‌ها از یکدیگر متمایز کرد، زیرا تنها درصد کمی از جفت‌ها در موقعیت‌های O(log n) اولیه خود با هم تفاوتی ندارند.[۱]
- اگر دو کلمه باینری فاصله همینگ d را داشته باشند، عدد اول p با p = O(d log n) و یک موقعیت i که در آن دو رشته متفاوت هستند، به طوری که i برابر مدول p با موقعیت هیچ تفاوت دیگری نیست وجود دارد. با محاسبه زوج و فردی نمادهای ورودی در موقعیت‌های همخوان با i modulo p، می‌توان کلمات را با استفاده از ماشینی با O(d log n) حالت از هم دیگر تمایز داد.[۱]
منابع[ویرایش]
- ↑ ۱٫۰ ۱٫۱ ۱٫۲ ۱٫۳ ۱٫۴ ۱٫۵ ۱٫۶ Demaine, Erik D.; Eisenstat, Sarah; Shallit, Jeffrey; Wilson, David A. (2011), "Remarks on separating words", Descriptional Complexity of Formal Systems: 13th International Workshop, DCFS 2011, Gießen/Limburg, Germany, July 25-27, 2011, Proceedings, Lecture Notes in Computer Science, vol. 6808, Heidelberg: Springer-Verlag, pp. 147–157, arXiv:1103.4513, doi:10.1007/978-3-642-22600-7_12, MR 2910373.
- ↑ Goralčík, P.; Koubek, V. (1986), "On discerning words by automata", Automata, Languages and Programming: 13th International Colloquium, Rennes, France, July 15–19, 1986, Proceedings, Lecture Notes in Computer Science, vol. 226, Berlin: Springer-Verlag, pp. 116–122, doi:10.1007/3-540-16761-7_61, MR 0864674.
- ↑ Robson, J. M. (1989), "Separating strings with small automata", Information Processing Letters, 30 (4): 209–214, doi:10.1016/0020-0190(89)90215-9, MR 0986823.
- ↑ Shallit, Jeffrey (2014), "Open Problems in Automata Theory: An Idiosyncratic View", British Colloquium for Theoretical Computer Science (BCTCS 2014), Loughborough University (PDF).