Efficient Algorithms for Constructing Preset Distinguishing Sequences for Nondeterministic Finite State Machines
A Master of Science thesis in Computer Engineering by Abdul Rahim Haddad entitled, "Efficient Algorithms for Constructing Preset Distinguishing Sequences for Nondeterministic Finite State Machines," submitted in June 2016. Thesis advisor is Dr. Khaled El-Fakih and thesis co-advisor is Dr....
محفوظ في:
| المؤلف الرئيسي: | |
|---|---|
| التنسيق: | doctoralThesis |
| منشور في: |
2016
|
| الموضوعات: | |
| الوصول للمادة أونلاين: | http://hdl.handle.net/11073/8471 |
| الوسوم: |
إضافة وسم
لا توجد وسوم, كن أول من يضع وسما على هذه التسجيلة!
|
| _version_ | 1864513444832608256 |
|---|---|
| author | Haddad, Abdul Rahim |
| author_facet | Haddad, Abdul Rahim |
| author_role | author |
| dc.contributor.none.fl_str_mv | El Fakih, Khaled Barlas, Gerassimos |
| dc.creator.none.fl_str_mv | Haddad, Abdul Rahim |
| dc.date.none.fl_str_mv | 2016-09-20T04:51:49Z 2016-09-20T04:51:49Z 2016-06 |
| dc.format.none.fl_str_mv | application/pdf |
| dc.identifier.none.fl_str_mv | 35.232-2016.37 http://hdl.handle.net/11073/8471 |
| dc.language.none.fl_str_mv | en_US |
| dc.subject.none.fl_str_mv | Software Engineering Functional Testing Conformance Testing Distinguishing Experiments Nondeterministic Finite State Machines Heuristics Genetic Algorithms Sequential machine theory Computer algorithms Sequences (Mathematics) |
| dc.title.none.fl_str_mv | Efficient Algorithms for Constructing Preset Distinguishing Sequences for Nondeterministic Finite State Machines Efficient algortihms for constructing preset distinguishing sequences for nondeterministic finite state machines |
| dc.type.none.fl_str_mv | info:eu-repo/semantics/publishedVersion info:eu-repo/semantics/doctoralThesis |
| description | A Master of Science thesis in Computer Engineering by Abdul Rahim Haddad entitled, "Efficient Algorithms for Constructing Preset Distinguishing Sequences for Nondeterministic Finite State Machines," submitted in June 2016. Thesis advisor is Dr. Khaled El-Fakih and thesis co-advisor is Dr. Gerassimos Barlas. Soft and hard copy available. |
| format | doctoralThesis |
| id | aus_6e61daadcecc60fb3ceaebe6f694194a |
| identifier_str_mv | 35.232-2016.37 |
| language_invalid_str_mv | en_US |
| network_acronym_str | aus |
| network_name_str | aus |
| oai_identifier_str | oai:repository.aus.edu:11073/8471 |
| publishDate | 2016 |
| repository.mail.fl_str_mv | |
| repository.name.fl_str_mv | |
| repository_id_str | |
| spelling | Efficient Algorithms for Constructing Preset Distinguishing Sequences for Nondeterministic Finite State MachinesEfficient algortihms for constructing preset distinguishing sequences for nondeterministic finite state machinesHaddad, Abdul RahimSoftware EngineeringFunctional TestingConformance TestingDistinguishing ExperimentsNondeterministic Finite State MachinesHeuristicsGenetic AlgorithmsSequential machine theoryComputer algorithmsSequences (Mathematics)A Master of Science thesis in Computer Engineering by Abdul Rahim Haddad entitled, "Efficient Algorithms for Constructing Preset Distinguishing Sequences for Nondeterministic Finite State Machines," submitted in June 2016. Thesis advisor is Dr. Khaled El-Fakih and thesis co-advisor is Dr. Gerassimos Barlas. Soft and hard copy available.Derivation of input sequences for distinguishing states of a finite state machine (FSM) specification is well studied in the context of FSM-based functional testing. We present three heuristics for the derivation of distinguishing sequences for nondeterministic FSM specifications. The first is based on a cost function that guides the derivation process, and the second is a genetic algorithm that evolves a population of individuals of possible solutions (or input sequences) using a fitness function and a crossover operator specifically tailored for the considered problem. The third heuristic is a mutation based algorithm that considers a candidate distinguishing sequence, and if the candidate is not a distinguishing sequence, then the algorithm tries to find a solution by appropriately mutating the candidate. Experiments are conducted to assess the performance of the proposed heuristics in addition to an existing algorithm, called exact algorithm, that derives distinguishing sequences of optimal length. Performance is assessed with respect to execution time, virtual memory consumption, and quality (length) of obtained sequences. Experiments are conducted using randomly generated machines with various numbers of states, inputs, outputs, and degrees of nondeterminism. Further, we assess the impact of varying the number of states, inputs, outputs, and degree of nondeterminism. Finally, in addition to the three proposed heuristics, we present a parallel multithreaded implementation of the exact algorithm using Open Multi-Processing. Experiments are conducted to assess the performance of the parallel implementation as compared to the sequential using both execution time speedup and efficiency.College of EngineeringDepartment of Computer Science and EngineeringMaster of Science in Computer Engineering (MSCoE)El Fakih, KhaledBarlas, Gerassimos2016-09-20T04:51:49Z2016-09-20T04:51:49Z2016-06info:eu-repo/semantics/publishedVersioninfo:eu-repo/semantics/doctoralThesisapplication/pdf35.232-2016.37http://hdl.handle.net/11073/8471en_USoai:repository.aus.edu:11073/84712025-06-26T12:36:50Z |
| spellingShingle | Efficient Algorithms for Constructing Preset Distinguishing Sequences for Nondeterministic Finite State Machines Haddad, Abdul Rahim Software Engineering Functional Testing Conformance Testing Distinguishing Experiments Nondeterministic Finite State Machines Heuristics Genetic Algorithms Sequential machine theory Computer algorithms Sequences (Mathematics) |
| status_str | publishedVersion |
| title | Efficient Algorithms for Constructing Preset Distinguishing Sequences for Nondeterministic Finite State Machines |
| title_full | Efficient Algorithms for Constructing Preset Distinguishing Sequences for Nondeterministic Finite State Machines |
| title_fullStr | Efficient Algorithms for Constructing Preset Distinguishing Sequences for Nondeterministic Finite State Machines |
| title_full_unstemmed | Efficient Algorithms for Constructing Preset Distinguishing Sequences for Nondeterministic Finite State Machines |
| title_short | Efficient Algorithms for Constructing Preset Distinguishing Sequences for Nondeterministic Finite State Machines |
| title_sort | Efficient Algorithms for Constructing Preset Distinguishing Sequences for Nondeterministic Finite State Machines |
| topic | Software Engineering Functional Testing Conformance Testing Distinguishing Experiments Nondeterministic Finite State Machines Heuristics Genetic Algorithms Sequential machine theory Computer algorithms Sequences (Mathematics) |
| url | http://hdl.handle.net/11073/8471 |