مسألة فصل الكلمات

في علم الحاسوب النظري ، تُعرف مشكلة فصل الكلمات بأنها إيجاد أصغر آلة حتمية محدودة تتصرف بشكل مختلف مع سلسلتين نصيتين معطيتين ، أي أنها تقبل إحدى السلسلتين وترفض الأخرى. ولا يزال حجم هذه الآلة، في أسوأ الحالات، مسألة مفتوحة ، وذلك كدالة لطول السلسلتين المدخلتين.

يمكن التمييز بين السلسلتين 0010 و1000 باستخدام آلة حالة ثلاثية، حيث تنتقل الحالة الابتدائية إلى حالتين مختلفتين، كلتاهما نهائيتان بمعنى أن الانتقالات اللاحقة من هاتين الحالتين تعود دائمًا إلى الحالة نفسها. تسجل حالة هذه الآلة الرمز الأول من سلسلة الإدخال. إذا كانت إحدى الحالتين النهائيتين تقبل والأخرى ترفض، فإن الآلة ستقبل إحدى السلسلتين 0010 أو 1000 فقط. مع ذلك، لا يمكن التمييز بين هاتين السلسلتين باستخدام أي آلة حالة أقل من ثلاث حالات. ^{[ 1 ]}

لإثبات حدود هذه المسألة، يمكن افتراض، دون فقدان للعمومية، أن المدخلات عبارة عن سلاسل نصية على أبجدية ثنائية الأحرف. فإذا اختلفت سلسلتان نصيتان على أبجدية أكبر، فإنه يوجد تماثل سلاسل نصية يحولهما إلى سلسلتين ثنائيتين متساويتين في الطول ومختلفتين أيضًا. ويمكن ترجمة أي آلة ذاتية التمييز بين السلسلتين الثنائيتين إلى آلة ذاتية التمييز بين السلسلتين الأصليتين، دون أي زيادة في عدد الحالات. ^{[ 1 ]}

يمكن أيضًا افتراض أن السلسلتين متساويتان في الطول. أما بالنسبة للسلاسل غير المتساوية في الطول، فيوجد دائمًا عدد أولي p تكون قيمته لوغاريتمية بالنسبة لأصغر طول من طولي المدخلات، بحيث يكون الطولان مختلفين بتردد p . في هذه الحالة، يمكن استخدام آلة تحسب طول مدخلاتها بتردد p لتمييز السلسلتين عن بعضهما. لذلك، يمكن دائمًا تمييز السلاسل غير المتساوية في الطول عن بعضها بواسطة آلات ذات عدد قليل من الحالات. ^{[ 1 ]}

صاغ غورالتشيك وكوبيك (1986) لأول مرة مسألة تحديد حجم آلة الأوتوماتون التي تميز بين سلسلتين معطيتين، حيث أثبتا أن حجم الأوتوماتون يكون دائمًا دون الخطي. ^{[ 2 ]} لاحقًا، أثبت روبسون (1989) الحد الأعلى O ( n² ^/5 (log n ) ^³/5 )  لحجم الأوتوماتون المطلوب. ^{[ 3 ]} وقد حسّن تشيس (2020) هذا الحد إلى O ( n¹ ^/³ (log n ) ^⁷ )  . ^{[ 4 ] [ 5 ]}

توجد أزواج من المدخلات، كل منها عبارة عن سلسلة ثنائية بطول n، بحيث يكون حجم أي آلة قادرة على التمييز بين هذه المدخلات Ω(log n ) . ولا يزال سد الفجوة بين هذا الحد الأدنى والحد الأعلى الذي حدده تشيس مشكلة مفتوحة. وقد عرض جيفري شاليت جائزة قدرها 100 جنيه إسترليني لأي تحسين للحد الأعلى الذي حدده روبسون. ^{[ 6 ]}

من المعروف أن العديد من الحالات الخاصة لمشكلة فصل الكلمات قابلة للحل باستخدام عدد قليل من الحالات:

• إذا احتوت كلمتان ثنائيتان على عدد مختلف من الأصفار أو الآحاد، فيمكن التمييز بينهما بحساب أوزان هامينغ لكل منهما بتردد عدد أولي ذي حجم لوغاريتمي، باستخدام عدد لوغاريتمي من الحالات. وبشكل أعم، إذا ظهر نمط بطول k عددًا مختلفًا من المرات في الكلمتين، فيمكن التمييز بينهما باستخدام O ( k log n ) حالة. ^{[ 1 ]}
• إذا اختلفت كلمتان ثنائيتان عن بعضهما البعض في أول أو آخر k موضع، فيمكن التمييز بينهما باستخدام k + O (1) حالة. وهذا يعني أنه يمكن التمييز بين جميع أزواج الكلمات الثنائية تقريبًا باستخدام عدد لوغاريتمي من الحالات، لأن نسبة صغيرة جدًا من الأزواج لا يوجد فرق بينها في أول O (log n ) موضع. ^{[ 1 ]}
• إذا كانت المسافة بين كلمتين ثنائيتين هي d ، فإنه يوجد عدد أولي p بحيث يكون p = O ( d log n ) وموضع i يختلف فيه النصان، بحيث لا يكون i مساويًا بتردد p لموضع أي اختلاف آخر. بحساب زوجية رموز الإدخال في المواضع المطابقة لـ i بتردد p ، يمكن تمييز الكلمات باستخدام آلة ذات O ( d log n ) حالة. ^{[ 1 ]}