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
- Efficient procedures for multi-item lot sizing problems based on tight formulations
Başlık çevirisi yok
MELİH KÖKTEN
Yüksek Lisans
İngilizce
1990
Endüstri ve Endüstri MühendisliğiOrta Doğu Teknik ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
DOÇ. DR. ÖMER KIRCA
- Telegram scheduling for the periodic phase of the multifunction vehicle bus
Çok fonksiyonlu araç veriyolu'nun periyodik fazı için telegram çizelgelemesi
MUSTAFA ÇAĞLAR GÜLDİKEN
Yüksek Lisans
İngilizce
2020
Elektrik ve Elektronik MühendisliğiOrta Doğu Teknik ÜniversitesiElektrik-Elektronik Mühendisliği Ana Bilim Dalı
PROF. DR. KLAUS VERNER SCHMİDT
PROF. DR. ŞENAN ECE SCHMİDT
- Tabu search based solution approaches for lot streaming problems in flow shops
Akış tipi sistemlerde, kafile bölme ve kaydırma problemleri için tabu arama tabanlı çözüm yaklaşımları
RAHİME SANCAR EDİS
Doktora
İngilizce
2009
Endüstri ve Endüstri MühendisliğiDokuz Eylül ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
DOÇ. DR. ARSLAN ÖRNEK
- Optıcut: Desen minimizasyonlu tek boyutlu stok kesme problemi için yeni bir sezgisel yaklaşım
Opticut: A new heuristic algorithm for the one-dimensional cutting stock problem with pattern minimisation
NAHSEN KAYHAN
Doktora
Türkçe
2025
Endüstri ve Endüstri MühendisliğiSakarya ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
DOÇ. DR. ESRA TEKEZ
- FPM based partitioning and assignment algorithm for data parallel applications on heterogeneous platforms
Heterojen platformlarda veri paralel uygulamaları için FPM tabanlı bölümleme ve atama algoritması
MAHMOUD RAFAT MAHMOUD ALASMAR
Yüksek Lisans
İngilizce
2022
Elektrik ve Elektronik MühendisliğiOrta Doğu Teknik ÜniversitesiElektrik-Elektronik Mühendisliği Ana Bilim Dalı
PROF. DR. GÖZDE AKAR
PROF. DR. CÜNEYT FEHMİ BAZLAMAÇCI