השערת צ'רני

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

את החסם שההשערה מציעה אי-אפשר לשפר. לדוגמה, מן התמורה  והפונקציה b המעבירה כל נקודה לעצמה, פרט לכך ש- , אפשר להגיע לערך קבוע באמצעות הסדרה , ולא בשום דרך קצרה יותר. 

ידוע שההשערה נכונה אם הקבוצה X כוללת מחזור באורך n. החסם העליון הטוב ביותר הידוע כיום הוא .

ראו גם
 בעיית צביעת המסלולים

הערות שוליים

קטגוריה:אוטומטים
קטגוריה:בעיות פתוחות במדעי המחשב