rdf-syntax-grammar
mods:
  schema location: http://www.loc.gov/mods/v3 http://www.loc.gov/standards/mods/v3/mods-3-2.xsd
  title info:
    title: Algorithms and techniques for unique input/output sequence generation
  name:
    name part: Schin, Dongjean.
    role:
      role term: creator
  type of resource: text
  genre: bibliography
  origin info:
    place:
      place term: xx
    date issued: 1998
    issuance: monographic
  language:
    language term: eng
  physical description:
    form: print
    extent: xv, 196 leaves : illustrations ; 28 cm.
  abstract: Communication protocols are the mechanisms for establishing communication patterns between different processes within a distributed computer system. A protocol must be checked to ensure conformance to a specified standard. Conformance testing is based on modeling the protocol as a finite state ma-chine(FSM), and it is usually carried out by applying a test sequence to the FSM. The FSM is tested by verifying each transition using a test subsequence. A test sequence uses a characterizing sequence (i.e. distinguishing sequence (DS), W-set and Unique input/output (UIO) sequence) for each state. A characterizing sequence is used to identify the arrival state of the transition under test. It has been proved that the problem of finding a characterizing sequence is NP-complete. This represents a limitation for the practical applicability of FSM-based methods to protocol testing. In this dissertation, we address the U1O sequence generation problem. UIO sequences check distinctive I/0 behaviors for the states in an FSM. This problem consists of finding the minimum length U1O sequences of the states in a protocol. We introduce new, efficient and practical approaches for finding U1O sequences in communication protocols. These approaches differ from previous approaches based on exhaustive approach, (such as a breadth-first search, BFS), because appropriate heuristic information is used to speed up the process of UIO generation to find suboptimal solutions. Proposed approaches include a Rule-Based Search (RBS) approach, variations of the A* Algorithms, a Genetic Algorithm, and a Simulated Annealing algorithm. These approaches assume that the FSM is deterministic, strongly connected, reduced and completely speckled. Finally, we compare all methods with the BFS algorithms, and compare the length of the UIO sequence with those of the Distinguishing Sequence and the W-set. For experiments, MCNC FSM benchmarks, randomly generated FSMS, and some commercial protocols are considered.
  note: by Dongjean Schin.
  note: Vita.
  note: Issued also on microfiche from University Microfilm Inc.
  note: Ph. D. Texas A&M University 1998.
  note: Includes bibliographical references: pages 150-155.
  subject:
    topic: Major computer science
  identifier: 99-03197 UMI
  identifier: http://proxy.library.tamu.edu/login
  related item:
    location:
      url: http://proxy.library.tamu.edu/login
  record info:
    record content source: TXA
    record creation date: 990402
    record change date: 20190325093418.0
    record identifier: in00001463450