The upper bound for the length of the shortest homing sequences

Özgüdüm dizileri, çeşitli sonlu durum makinesi bazlı testlerde kullanılan ilginç girdi dizilerindendir. Daha kısa özgüdüm dizileri kullanmak, daha kısa test dizileri sağlayacağı için genellikle tercih edilir. En kısa özgüdüm dizisini bulmanın NP-zor bir problem olduğu bilinmektedir. En kısa özgüdüm dizisinin üst sınırı da literatürde çalışılan bir problemdir. n durumlu bir sonlu durum makinesi için sıkı üst sınırın n(n − 1)/2 olduğu bilinmektedir. Bununla birlikte, bu sınıra ulaşan sonlu durum makinelerinin bilinen bütün örneklerinin hepsi n−1 girdi sembolu kullanmaktadır ve bu durum, girdi alfabesi durum sayısı ile birlike büyüyor demektir. Peki bu üst sınıra sabit sayıda girdili bir sonlu durum makinesi ile ulaşılabilir mi? Bu çalışmada deneysel bir analiz yaptık ve soruya negatif bir şekilde cevap verdik. Bütün 2 girdili, 2 çıktılı sonlu durum makinelerini etraflıca sayıp, deneysel olarak 10 ya daha az durumlu sonlu durum makineler için en kısa özgüdüm dizisinin üst sınırını hesapladık. Bu hesaplamayı pratikte uygulanabilir kılmak adına sonucu etkilemeyen sonlu durum makinelerini elemek için çeşitli teknikler uyguladık.