The upper bound for the length of the shortest homing sequences

Warning The system is temporarily closed to updates for reporting purpose.

Çirişci, Berk (2019) The upper bound for the length of the shortest homing sequences. [Thesis]

PDF - Requires a PDF viewer such as GSview, Xpdf or Adobe Acrobat Reader

Official URL: http://risc01.sabanciuniv.edu/record=b2315111_ (Table of contents)


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−1 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

Item Type:Thesis
Uncontrolled Keywords:Finite state machines. -- Homing sequences. -- Isomorphic FSM. -- Hibbard’s upper bound. -- Sonlu durum makineleri. -- Özgüdüm dizileri. -- Esbiçimli sonlu durum makinesi. -- Hibbard'ın üst sınırı.
Subjects:T Technology > TK Electrical engineering. Electronics Nuclear engineering > TK7800-8360 Electronics > TK7885-7895 Computer engineering. Computer hardware
ID Code:39257
Deposited By:IC-Cataloging
Deposited On:25 Sep 2019 13:48
Last Modified:25 Sep 2019 13:48

Repository Staff Only: item control page