Heuristics for unique input output sequence computation

Abstract

Bu tez çalışmasında, sonlu durum makinalarında Benzersiz Girdi Çıktı (BGÇ) Dizileri bulunması için bazı sezgisel yöntemler önerilmektedir. BGÇ dizilerinin hesaplanmasının zor bir problem olduğu bilinmektedir. Bu çalışmada önerilen yöntemler de, literatürde bulunan diğer yöntemler gibi üstel büyüklükte bir ağaç yapısına dayanmaktadır. Fakat, bu çalışmada önerilen yöntemler bu ağacı oluşturması sırasında yapılan aramayı bazı sezgisel yöntemlerle yönlendirilmektedir. Bu yönlendirilmiş aramanın dışında çıkarım kullanarak BGÇ dizisi bulan yöntemlere de değinilmiş ve bu yöntemlerin bir dezavantajı olan uzun diziler çıkarma sorununa bir çare olarak, sınırlı çıkarım yapma önerilmiştir. Rasgele üretilen sonlu durum makinaları kullanılarak, bu çalışmada önerilen yöntemlerin birbirleri ve literatürde bulunan diğer yöntemler ile karşılaştırılması yapılmıştır.

In this thesis, several heuristic methods are proposed for the computation of Unique Input Output (UIO) Sequences for the states of a given finite state machine. UIO computation problem is known to be a hard problem. The methods suggested in this work are based on unfolding an exponential tree as the other methods existing in the literature. However, our methods perform a search guided by some heuristic information. We also introduce a parameter for inference based UIO sequence computation for a trade off between the memory used for the computation and the UIO sequence length. Based on a randomly generated set of finite state machines, an extensive experimental study is also provided to compare the performance of our methods between each other and to those already exist in the literature.