مسئله کلمات جداکننده

"این مقاله در حال ترجمه از ویکی انگلیسی است

لطفا حذف نشود."

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

مثال

دو رشته 0010 و 1000 می‌توانند توسط یک ماشین سه حالته از یکدیگر متمایز شوند که در آن انتقال از حالت شروع به دو حالت مختلف می رود، که هر دو پایانی هستند به این معنا که انتقال های بعدی از این دو حالت همیشه به همان حالت اولیه بازمی‌گردد. حالت این ماشین اولین نماد رشته ورودی را ثبت می کند. اگر یکی از دو حالت پایانی در حال قبول و دیگری رد باشد، ماشین تنها یکی از رشته های 0010 و 1000 را می پذیرد. با این حال، این دو رشته را نمی توان با هیچ ماشینی با کمتر از سه حالت متمایز کرد.

ساده‌سازی مفروضات

برای اثبات کرانه‌های این مسئله، بدون از دست دادن کلیت فرض می‌شود که ورودی‌ها، رشته‌هایی روی یک الفبای دو حرفی هستند. زیرا، اگر دو رشته در یک الفبای بزرگ‌تر با هم متفاوت باشند، یک هم‌‌ریختی رشته‌ای وجود دارد که آنها را به رشته‌هایی باینری با طول یکسان، نگاشت می‌کند که در این نگاشت، هر دو رشته همچنان با هم متفاوت هستند. هر ماشینی که این دو رشته‌ باینری را متمایز می‌کند، می‌تواند به ماشینی تبدیل شود که رشته‌های اصلی را بدون هیچ افزایشی در تعداد حالت‌ها متمایز کند.

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

تاریخچه و کرانه‌ها

مسئله محدود کردن اندازه ماشینی که دو رشته داده شده را از هم متمایز می کند، برای اولین بار توسط (Goralčík و Koubek 1986) فرموله شد، که نشان دادند اندازه ماشین همیشه زیرخطی است. بعدها، (Robson 1989) بهترین کران بالایی شناخته شده، O(n^2/5(log n)^3/5) ، در اندازه ماشینی که ممکن است مورد نیاز باشد اثبات کرد. این مقدار توسط (Chase 2020) به O(n^1/3(log n)⁷) بهبود یافت.

جفت ورودی‌هایی وجود دارند که هر دو رشته‌های باینری به طول n هستند و هر ماشینی که ورودی‌ها را متمایز می‌کند باید اندازه Ω(log n) باشد. بستن شکاف بین این کران پایین و کران بالایی رابسون همچنان یک مسئله باز است. جفری شالیت جایزه 100 پوندی بریتانیا را برای هر بهبودی در حد بالایی رابسون در نظر گرفته است.

موارد خاص

چندین مورد خاص از مسئله جداکننده کلمات با استفاده از چند حالت قابل حل شناخته شده‌است:

• اگر دو کلمه باینری دارای اعداد متفاوتی از صفر یا یک باشند، آنگاه می‌توان آنها را با شمارش مدول وزن‌های همینگ آن‌ها با اندازه لگاریتمی اول، با استفاده از تعداد لگاریتمی حالت‌ها از یکدیگر متمایز کرد. به طور کلی، اگر یک الگوی طول 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) حالت از هم دیگر تمایز داد.