The upper bound for the length of the shortest homing sequences
En kısa özgüdüm dizilerinin uzunluğunun üst sınırı
- Tez No: 556769
- Danışmanlar: DOÇ. 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: 2019
- Dil: İngilizce
- Üniversite: Sabancı Üniversitesi
- Enstitü: Mühendislik ve Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Belirtilmemiş.
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: 50
Özet
Ö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.
Özet (Çeviri)
Homing sequences are special input sequences that are used by various techniques of finite state machine based testing. Using a shorter homing sequence is typically preferred since it would yield a shorter test sequence. Finding a shortest homing sequence is known to be an NP–hard problem. The upper bound of shortest homing sequences is also a problem studied in the literature. A tight upper bound for the length of shortest homing sequence for a finite state machine with n states is known to be n(n−1)/2 . However, the known examples of finite state machines hitting to this upper bound also use n−1 input symbols, i.e. the size of the input alphabet also grows with the number of states. Is this upper bound reachable for a finite state machine with a constant number of inputs? In this work, we use an experimental analysis and we answer this question negatively. By exhaustively enumerating all finite state machines with two input symbols and two output symbols, we experimentally compute the upper bound for the length of the shortest homing sequence for finite state machines with 10 or less states. In order to make this computation feasible in practice, we apply several techniques to eliminate from our search those finite state machines which would not affect the result of the computation.
Benzer Tezler
- Sönümlemeli kanallarda kafes kodlamalı sistemler için birleşik serpiştirme tekniği
Combined interleaving technique for trellis coded systems in feding channels
ERSİN ÖZTÜRK
Yüksek Lisans
Türkçe
1998
Elektrik ve Elektronik Mühendisliğiİstanbul Teknik ÜniversitesiElektronik ve Haberleşme Mühendisliği Ana Bilim Dalı
DOÇ. DR. ÜMİT AYGÖLÜ
- Çok-düzeyli kodlama/çok-aşamalı kod çözme tekniğinin incelenmesi ve frekans/faz kaydırmalı anahtarlama modülasyonuna uygulanması
Multilevel coding/multistage decoding and its application to frequency/phase shift keying modulation
İBRAHİM ALTUNBAŞ
Yüksek Lisans
Türkçe
1992
Elektrik ve Elektronik Mühendisliğiİstanbul Teknik ÜniversitesiYRD. DOÇ. DR. ÜMİT AYGÖLÜ
- Sürekli faz modülasyonunun çok düzeyli kodlanması
Multilevel coding of continuous phase modulation
İBRAHİM ALTUNBAŞ
Doktora
Türkçe
1999
Elektrik ve Elektronik Mühendisliğiİstanbul Teknik ÜniversitesiPROF.DR. ÜMİT AYGÖLÜ
- Dizi şifreleme sistemleri ve doğrusal karmaşıklık
Başlık çevirisi yok
ERKAY SAVAŞ
Yüksek Lisans
Türkçe
1994
Elektrik ve Elektronik Mühendisliğiİstanbul Teknik ÜniversitesiPROF.DR. İ. CEM GÖKNAR
- A new offline path search algorithm for computer games that considers damage as a feasibility criterion
Tehditleri dikkate alan yeni bir çevrim dışı yol bulma algoritması
SERHAT BAYILI
Yüksek Lisans
İngilizce
2008
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolOrta Doğu Teknik ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
PROF. DR. FARUK POLAT