THE UPPER BOUND FOR THE LENGTH OF THE SHORTEST HOMING SEQUENCES

Berk Çirişci
Computer Science and Engineering, MSc. Thesis, 2019

Thesis Jury

Assoc. Prof. Dr. Hüsnü Yenigün (Thesis Advisor),

Asst. Prof. Dr. Kamer Kaya,

Asst. Prof. Dr. Uraz Cengiz Türker

Date & Time: July 19, 2019 14:40

Place: FENS L058

Keywords: Finite State Machines, Homing Sequences, Isomorphic FSM, Hibbard’s Upper Bound

Abstract

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