Post processing for checking sequences

Abstract

Verilen bir Sonlu Durumlu Makina (SDM) M için bir çok kontrol dizisi (KD) üretme metodu bulunmuştur. Bu metodlar KD üretimini, KD M üzerinden gezilirken yapılmaktadır. Bu gezme sırasında ziyaret edilen tüm düğümler, M'de bulunan bazı durumlar tarafından tanımlanır ve M'de bulunan her bir bağlantı üzerinden geçilmiş olur. Düğümlerin tanımlanması incelendiğinde, bazı düğümlerin birden fazla kez gereksiz yere tanımlanmış oldukları gözlemlenebilmektedir. Bu gözlem şu soruyu ortaya çıkarmaktadır: KD'nin uzunluğununu gereksiz tanımlamaları ortadan kaldırarak azaltmak mümkün müdür? Bu çalışmada bu soru üzerinde durulmaktadır. Verilen bir KD uzunluğunu kısaltabilmek için, tanımlamalar somutlaştırılmış, birden fazla kez tanımlanan gereksiz düğümler bulunmuş ve bu düğümleri ortadan kaldırmak için bir çözüm sunulmuştur. Ayrıca bu yaklaşımın deneysel bir çalışması da bu tez içerisinde sunulmaktadır.

There are several methods to generate a checking sequence (CS) from a given Finite State Machine M. These methods generate a CS in such a way that when the CS is traced on M, every node visited during this trace is recognized as some state of M and every transition of M is traversed. When the recognitions of the nodes in this trace are analyzed, it is observed that some of the nodes are recognized multiple times redundantly. This observation raises the following question: Is it possible to reduce the length of a given CS by eliminating redundant recognitions? In this thesis we focus on this question. We formalize the recognitions, detect multiple redundant recognitions and suggest a way to eliminate them to reduce the length of a given CS. An experimental study of our approach is also presented.