Geri Dön

The upper bound for the length of the shortest homing sequences

En kısa özgüdüm dizilerinin uzunluğunun üst sınırı

  1. Tez No: 556769
  2. Yazar: BERK ÇİRİŞCİ
  3. Danışmanlar: DOÇ. DR. HÜSNÜ YENİGÜN
  4. Tez Türü: Yüksek Lisans
  5. Konular: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol, Computer Engineering and Computer Science and Control
  6. Anahtar Kelimeler: Belirtilmemiş.
  7. Yıl: 2019
  8. Dil: İngilizce
  9. Üniversite: Sabancı Üniversitesi
  10. Enstitü: Mühendislik ve Fen Bilimleri Enstitüsü
  11. Ana Bilim Dalı: Belirtilmemiş.
  12. Bilim Dalı: Belirtilmemiş.
  13. 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

  1. 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

    Türkçe

    1998

    Elektrik ve Elektronik Mühendisliğiİstanbul Teknik Üniversitesi

    Elektronik ve Haberleşme Mühendisliği Ana Bilim Dalı

    DOÇ. DR. ÜMİT AYGÖLÜ

  2. Ç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

    Türkçe

    1992

    Elektrik ve Elektronik Mühendisliğiİstanbul Teknik Üniversitesi

    YRD. DOÇ. DR. ÜMİT AYGÖLÜ

  3. Sürekli faz modülasyonunun çok düzeyli kodlanması

    Multilevel coding of continuous phase modulation

    İBRAHİM ALTUNBAŞ

  4. Dizi şifreleme sistemleri ve doğrusal karmaşıklık

    Başlık çevirisi yok

    ERKAY SAVAŞ

    Yüksek Lisans

    Türkçe

    Türkçe

    1994

    Elektrik ve Elektronik Mühendisliğiİstanbul Teknik Üniversitesi

    PROF.DR. İ. CEM GÖKNAR

  5. 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

    İngilizce

    2008

    Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolOrta Doğu Teknik Üniversitesi

    Bilgisayar Mühendisliği Ana Bilim Dalı

    PROF. DR. FARUK POLAT