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

PDF

10282726_BerkCirisci.pdf

Download (662kB)

10282726_BerkCirisci.pdf

Download (662kB)

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

Divisions: | Faculty of Engineering and Natural Sciences > Academic programs > Computer Science & Eng. Faculty of Engineering and Natural Sciences |

Depositing User: | IC-Cataloging |

Date Deposited: | 25 Sep 2019 13:48 |

Last Modified: | 26 Apr 2022 10:31 |

URI: | https://research.sabanciuniv.edu/id/eprint/39257 |