Improved heuristics for W-set and K-tree generation on finite state machines

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.