Please use this identifier to cite or link to this item:
http://bura.brunel.ac.uk/handle/2438/16391
Full metadata record
DC Field | Value | Language |
---|---|---|
dc.contributor.author | Hierons, RM | - |
dc.date.accessioned | 2010-06-21T12:31:19Z | - |
dc.date.accessioned | 2018-06-20T11:54:49Z | - |
dc.date.available | 2010-08-19 | - |
dc.date.available | 2018-06-20T11:54:49Z | - |
dc.date.issued | 2010 | - |
dc.identifier | http://bura.brunel.ac.uk/handle/2438/4448 | - |
dc.identifier.citation | SIAM Journal of Computing, 2010, 39 (8), pp. 3480 - 3500 | en_US |
dc.identifier.issn | http://bura.brunel.ac.uk/handle/2438/4448 | - |
dc.identifier.issn | 0097-5397 | - |
dc.identifier.issn | http://dx.doi.org/10.1137/090771296 | - |
dc.identifier.uri | http://bura.brunel.ac.uk/handle/2438/16391 | - |
dc.description.abstract | Some systems interact with their environment at physically distributed interfaces, called ports, and in testing such a system it is normal to place a tester at each port. Each tester observes only the events at its port and it is known that this limited observational power introduces additional controllability and observability problems into testing. Given a multiport finite state machine (FSM) $M$, we consider the problems of defining strategies for the testers either to reach a given state of $M$ or to distinguish two states of $M$. These are important problems since most techniques for testing from a single-port FSM use sequences that reach and distinguish states. Both problems can be solved in low-order polynomial time for single-port FSMs but we prove that the corresponding decision problems are undecidable for multiport FSMs. However, we also show that they can be solved in low-order polynomial times for deterministic FSMs if we restrict our attention to controllable tests. These results have important ramifications for testing from a multiport FSM since they suggest that methods for testing from a single-port FSM cannot be easily adapted. In addition, two FSMs can be distinguished if and only if their initial states can be distinguished and so the results suggest that, in contrast to single-port FSMs, we cannot expect to produce general complete test generation methods for multiport FSMs. | en_US |
dc.format.extent | 3480 - 3500 | - |
dc.language.iso | en | en_US |
dc.publisher | Society for Industrial and Applied Mathematics | en_US |
dc.relation.replaces | http://bura.brunel.ac.uk/handle/2438/4448 | - |
dc.relation.replaces | 2438/4448 | - |
dc.subject | Finite state machine | en_US |
dc.subject | Testing | en_US |
dc.subject | Distributed systems | en_US |
dc.subject | Multiport systems | en_US |
dc.title | Reaching and distinguishing states of distributed systems | en_US |
dc.type | Article | en_US |
dc.identifier.doi | http://dx.doi.org/10.1137/090771296 | - |
dc.relation.isPartOf | SIAM Journal of Computing | - |
pubs.issue | 8 | - |
pubs.volume | 39 | - |
Appears in Collections: | Computer Science Dept of Computer Science Research Papers Software Engineering (B-SERC) |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
Fulltext.pdf | 249.42 kB | Adobe PDF | View/Open |
Items in BURA are protected by copyright, with all rights reserved, unless otherwise indicated.