Brunel University Research Archive (BURA) >
College of Engineering, Design and Physical Sciences >
Dept of Computer Science >
Dept of Computer Science Research Papers >

Please use this identifier to cite or link to this item: http://bura.brunel.ac.uk/handle/2438/4075

Title: Canonical finite state machines for distributed systems
Authors: Hierons, RM
Keywords: Finite state machine
Equivalence
Distributed test architecture
Canonical
Publication Date: 2010
Publisher: Theoretical Computer Science. 411(2): 566-580
Abstract: There has been much interest in testing from finite state machines (FSMs) as a result of their suitability for modelling or specifying state-based systems. Where there are multiple ports/interfaces a multi-port FSM is used and in testing, a tester is placed at each port. If the testers cannot communicate with one another directly and there is no global clock then we are testing in the distributed test architecture. It is known that the use of the distributed test architecture can affect the power of testing and recent work has characterised this in terms of local s-equivalence: in the distributed test architecture we can distinguish two FSMs, such as an implementation and a specification, if and only if they are not locally s-equivalent. However, there may be many FSMs that are locally s-equivalent to a given FSM and the nature of these FSMs has not been explored. This paper examines the set of FSMs that are locally s-equivalent to a given FSM M. It shows that there is a unique smallest FSM χmin(M) and a unique largest FSM χmax(M) that are locally s-equivalent to M. Here smallest and largest refer to the set of traces defined by an FSM and thus to its semantics. We also show that for a given FSM M the set of FSMs that are locally s-equivalent to M defines a bounded lattice. Finally, we define an FSM that, amongst all FSMs locally s-equivalent to M, has fewest states. We thus give three alternative canonical FSMs that are locally s-equivalent to an FSM M: one that defines the smallest set of traces, one that defines the largest set of traces, and one with fewest states. All three provide valuable information and the first two can be produced in time that is polynomial in terms of the number of states of M. We prove that the problem of finding an s-equivalent FSM with fewest states is NP-hard in general but can be solved in polynomial time for the special case where there are two ports.
URI: http://bura.brunel.ac.uk/handle/2438/4075
DOI: http://dx.doi.org/10.1016/j.tcs.2009.09.039
ISSN: 0304-3975
Appears in Collections:Computer Science
Software Engineering (B-SERC)
Dept of Computer Science Research Papers

Files in This Item:

File Description SizeFormat
Fulltext.pdf244.84 kBAdobe PDFView/Open

Items in BURA are protected by copyright, with all rights reserved, unless otherwise indicated.