השערת צ'רני

מתוך ויקיפדיה, האנציקלופדיה החופשית
קפיצה אל: ניווט, חיפוש

בתורת האוטומטים הסופיים, השערת צ'רניאנגלית: Černý conjecture; על שם יאן צ'רני) היא השערה על האורך המקסימלי של מילה מסנכרנת, באוטומט שיש בו מילה כזו. ההשערה קובעת שאם X היא משפחה של פונקציות מקבוצה בת n נקודות לעצמה, ואפשר להרכיב מ-X באמצעות הרכבה פונקציה קבועה, אז יש הרכבה כזו באורך שאינו עולה על \ (n-1)^2 ‏‏[1].

את החסם שההשערה מציעה אי-אפשר לשפר. לדוגמה, מן התמורה \ a=(1 2 \cdots n) והפונקציה b המעבירה כל נקודה לעצמה, פרט לכך ש- \ b(1)=2, אפשר להגיע לערך קבוע באמצעות הסדרה \ b(a^{n-1}b)^{n-2}, ולא בשום דרך קצרה יותר.

ידוע שההשערה נכונה אם הקבוצה X כוללת מחזור באורך n. החסם העליון הטוב ביותר הידוע כיום הוא \ (n^3-n)/6.

ראו גם[עריכת קוד מקור | עריכה]

הערות שוליים[עריכת קוד מקור | עריכה]

  1. ^ J. Černý, Poznámka k homogénnym eksperimentom s konecnými automatami, Mat.-Fyz. Cas. Slovensk. Akad. Vied., Vol. 14, 208--216, (1964). (בסלובקית)‏