Improved heuristics for W-set and K-tree generation on finite state machines
Sonlu durum makinelerinde W-kümesi ve K-ağacı türetimi için sezgisel algoritmaların iyileştirilmesi
- Tez No: 658424
- 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: 2020
- Dil: İngilizce
- Üniversite: Sabancı Üniversitesi
- Enstitü: Mühendislik ve Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Bilgisayar Bilimleri ve Mühendisliği Ana Bilim Dalı
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: 81
Özet
Sonlu Durum Makinesi (FSM) bazlı test yöntemleri, Durum Saptama Dizileri adı verilen, kara-kutu olarak verilen bir makinedeki durumların tasarımdaki durumlarla örtüşüp örtüşmediğini saptamaya yarayan dizileri kullanır. Bilinen farklı durum saptama dizisi çeşitleri vardır. Bu durum saptama dizilerinden bazılarının her tasarım için var olacağı kesin değildir. Ancak, bir durum saptama dizisi çeşidinin - W–kümesi bazlı durum saptama dizileri - indirgenmiş, gerekirci, ve tam belirtimlenmiş tüm sonlu durum makineleri için her zaman bulunduğu bilinmektedir. W–kümesi bazlı durum saptama dizileri uzun süredir bilinmesine karşın, literatürdeki birçok güvenli tekrar başlatma özelliği olmayan makineler için geliştirilen yöntemler tarafından tercih edilmemektedir. Bunun sebebi, W–kümesi bazlı yöntemlerin ürettiği dizilerin uzunluğunun W–kümesindeki eleman sayısına göre üstel olarak artmasıdır. Bazı güncel çalışmalar, W–kümesi bazlı durum saptama dizilerinin uzunluklarının düşürülebileceğini önermektedirler. Aslında bu yöntemler, önayarlı deneylerden oluşan W–kümeleri yerine, uyarlanabilir deneylerden oluşan K–kümelerini de kullanabilmektedirler. K–kümeleri de W–kümeleri gibi her indirgenmiş, gerekirci ve tam belirtimli tüm sonlu durum makineleri için bulunmaktadırlar. Bundan da öte, bu yeni yöntemler W–kümesinin/K–kümesinin tüm elemanları kullanılmadan da bir durum saptama dizisi üretilebileceğini öne sürmektedirler. Bu yöntemlerde, sonlu durum makinesinin bir durumu için hangi W–kümesi/K–kümesi elemanlarının kul- lanılacağını saptamak adına, uyarlanabilir bir yapı olan K–ağaçları kullanılır. Fakat, literatürde bu yeni yöntemlerle alakalı bir deneyli çalışma henüz yapılmamıştır. Buna ek olarak, K–ağaçlarının nasıl üretileceği ile alakalı bir algoritma da verilmemiştir. Bu çalışmada, öncelikle daha iyi W–kümeleri (hem eleman sayısı hem de toplam uzunluk bakımından) oluşturulması için W–kümesi oluşturma algoritmaları sunulmaktadır. Bu W–kümesi algoritmaları literatürdeki diğer algoritmalarla deneysel olarak karşılaştırılmaktadır. Aynı zamanda bu çalışmada, K–kümesi ve K–ağacı üretimi için algoritmalar da önerilmektedir. Son olarak, durum saptama dizileri ile ilgili kapsamlı bir deneysel çalışma sunulmaktadır. Bu deneysel çalışmalar, W– kümesi bazlı durum saptama dizileri tarihsel olarak pratikte kullanışsız gözükse de, K–ağacı yardımıyla oluşturulduğunda, bu durum saptama dizilerinin çok kısa ve kullanışlı sonuçlar ürettiklerini göstermektedir. Ayrıca, K–ağacı üretilirken K–kümelerinin kullanılması da W–kümelerine göre bir avantaj sağlamaktadır.
Özet (Çeviri)
Finite State Machine (FSM) based testing methods utilize State Identification Sequences which are used to identify the states of a black box implementation as corresponding to states of an FSM given as the specification. There are different types of state identification sequences. Some of these state identification sequences are not guaranteed to exist for all specifications. There is one particular type of state identification sequences, W-set based state identification sequences, which are known to exist for any minimal, deterministic, completely specified FSM. Although W-set based state identification sequences are known for a very long time, most of the works in FSM based testing literature do not prefer to use them when testing for an implementation without a reliable reset feature, since the length of W-set based state identifications sequences in this case are exponential in the cardinality of the W-sets. There are some recent works that suggest to reduce the length of the W-set based state identification sequences. In fact, instead of W-sets, which are sets of preset experiments, these new methods can make use of so called K-sets, which are set of adaptive experiments that again always exist. Furthermore, these new methods suggest to apply not all elements of W–sets/K-sets, but instead an adaptive structure, called a K-tree is used to orchestrate the application of the elements of the K-set. However, there are no extensive experimental studies for these new methods. In addition, no algorithms are given for the construction of K-trees. In this work, we first present some W-set construction algorithms to construct better W-sets, in terms of both the cardinality and the total length of the sequences. We compare our W-set algorithms experimentally to the algorithms that exist in the literature. We also present algorithms to constructs K-sets and K-trees. Finally, we present an extensive experimental study for state identification sequences. The results show that, although W-set based state identification sequences have been considered practically infeasible due to the exponentially long sequences, the usage of K-trees make state identification sequences very short and practically usable. Utilizing K–sets in the generation of K–trees also yields better results than utilizing W–sets.
Benzer Tezler
- Multiobjective relational data warehouse design for the cloud
Bulut için çok amaçlı ilişkisel veri ambarı tasarımı
TANSEL DÖKEROĞLU
Doktora
İngilizce
2014
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolOrta Doğu Teknik ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
PROF. DR. AHMET COŞAR
- Güç transformatörlerinin optimum tasarımına yönelik çalışmaların incelenmesi
Başlık çevirisi yok
LEVENT CAN
Yüksek Lisans
Türkçe
1998
Elektrik ve Elektronik Mühendisliğiİstanbul Teknik ÜniversitesiElektrik Mühendisliği Ana Bilim Dalı
PROF. DR. NURDAN GÜZELBEYOĞLU
- Sincap kafesli asenkron motorların rotor çubuk kırıklarının akustik ölçümlerle tespiti
Detection of broken rotor bar of squirrel-cage induction motors by acoustic measurements
OSMAN ZEKİ ERBAHAN
Doktora
Türkçe
2023
Elektrik ve Elektronik MühendisliğiZonguldak Bülent Ecevit ÜniversitesiElektrik-Elektronik Mühendisliği Ana Bilim Dalı
DOÇ. DR. İBRAHİM ALIŞKAN
- Optimization of surgery delivery systems
Ameliyat uygulama sistemlerinin optimizasyonu
SERHAT GÜL
Doktora
İngilizce
2010
Endüstri ve Endüstri MühendisliğiArizona State UniversityEndüstri Mühendisliği Ana Bilim Dalı
PROF. DR. JOHN W. FOWLER
PROF. DR. BRIAN T. DENTON
- Optimization of surgery delivery systems
Başlık çevirisi yok
SERHAT GÜL
Doktora
İngilizce
2010
Endüstri ve Endüstri MühendisliğiArizona State UniversityDR. JOHN W. FOWLER
DR. BRIAN T. DENTON