Heuristic Approaches for Efficient Computation of Synchronizing Sequences in Deterministic Finite Automata
Deterministik Sonlu Otomatlarda Senkronizasyon Dizilerinin Etkin Hesaplanması için Sezgisel Yaklaşımlar
- Tez No: 1005800
- Danışmanlar: PROF. DR. HÜSNÜ YENİGÜN
- Tez Türü: Yüksek Lisans
- Konular: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol, Computer Engineering and Computer Science and Control
- Anahtar Kelimeler: Belirtilmemiş.
- Yıl: 2026
- Dil: İngilizce
- Üniversite: Sabancı Üniversitesi
- Enstitü: Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Bilgisayar Bilimleri ve Mühendisliği Ana Bilim Dalı
- Bilim Dalı: Bilgisayar Bilimi ve Mühendisliği Bilim Dalı
- Sayfa Sayısı: Belirtilmemiş.
Özet
Deterministik sonlu otomatlarda (DFA) en kısa senkronizasyon dizisinin bulunması, otomata teorisinin temel problemlerinden biridir ve model tabanlı test, protokol doğrulama ile hata teşhisi gibi alanlarda önemli uygulamalara sahiptir. Çözümün NP-hard olması nedeniyle, pratikte Greedy ve SynchroP gibi sezgisel yöntemler kullanılmaktadır. Ancak bu yöntemler çalışma süresi ile çözüm kalitesi arasında bir denge gerektirir. Bu tezde, DFA senkronizasyonunun yapısal özellikleri incelenmiş ve hem performansı hem de çözüm kalitesini artırmayı amaçlayan yeni sezgisel strate- jiler önerilmiştir. İlk olarak, klasik Greedy algoritmasının bir uzantısı olan Fast- Greedy sunulmuştur. Bu yöntem, durum çiftlerin tamamen değerlendirmesinden önce kısa ve sınırlı birleştirme dizilerini araştırmaktadır. Deneysel sonuçlarda, Fast- Greedy çözüm kalitesini korurken çalışma süresini önemli ölçüde iyileştirmekte ve 6.28 kata kadar hızlanma sağlamaktadır. Ayrıca, DFA altkümelerindeki senkro- nizasyon maliyetleri üzerine gerçekleştirilen kapsamlı analiz, büyük altkümelerde maliyetlerin daha homojen, küçük altkümelerde ise yapısal farklılıkların daha belir- gin olduğunu ortaya koymuştur. Bu bulgular doğrultusunda, Greedy ve Syn- chroP yöntemlerini adaptif biçimde birleştiren hibrit senkronizasyon yaklaşımı önerilmiştir. Bu yöntem, erken aşamalarda Greedy, ilerleyen aşamalarda ise Syn- chroP kullanmaktadır. Deneysel sonuçlar, hibrit yaklaşımın çalışma süresi ve dizi uzunluğu açısından rakiplerinden daha dengeli sonuçlar verdiğini göstermektedir. Bu tez, DFA senkronizasyonuna dair yeni yapısal içgörüler sunmakta ve büyük ölçekli problemler için ölçeklenebilir sezgisel yöntemler önermektedir.
Özet (Çeviri)
The problem of finding shortest synchronizing sequences in deterministic finite au- tomata (DFAs) is fundamental in automata theory, with applications in model-based testing, protocol verification, and fault diagnosis. Since exact computation is NP- hard, heuristics such as Greedy and SynchroP are used, though they involve trade-offs between runtime efficiency and solution quality. This thesis investigates structural properties of DFA synchronization and proposes new heuristic strate- gies to improve both performance and sequence quality. First, we introduce Fast- Greedy, an extension of classical Greedy that explores short bounded merging sequences before full pairwise evaluations. Experimental results show that Fast- Greedy significantly reduces computational cost while preserving synchronization quality, achieving speedups of up to 6.28×. We also conduct a large-scale empirical analysis of synchronization costs across DFA subsets, revealing that larger subsets exhibit more homogeneous merging costs, while smaller subsets show greater struc- tural sensitivity. Based on these findings, we propose a hybrid synchronization approach that adaptively combines Greedy and SynchroP. The method applies Greedy in early stages and switches to SynchroP as subset size decreases. Ex- perimental evaluation demonstrates that this hybrid strategy effectively balances runtime and sequence minimality, outperforming standalone heuristics. Overall, this thesis provides new structural insights and scalable heuristic techniques for efficiently computing high-quality synchronizing sequences in large DFAs.
Benzer Tezler
- Grup teknolojisi imalat sistemi ve bu sistemin tasarımına yönelik yeni bir metot
Group technology manufacturing systems and a new method oriented to the design of these systems
M. BÜLENT DURMUŞOĞLU
