Please use this identifier to cite or link to this item:
http://bura.brunel.ac.uk/handle/2438/6002
Full metadata record
DC Field | Value | Language |
---|---|---|
dc.contributor.author | Hierons, RM | - |
dc.contributor.author | Ural, H | - |
dc.date.accessioned | 2011-11-22T09:49:56Z | - |
dc.date.available | 2011-11-22T09:49:56Z | - |
dc.date.issued | 2008 | - |
dc.identifier.citation | Computer Journal, 51(4): 497 - 510, Jul 2008 | en_US |
dc.identifier.issn | 0010-4620 | - |
dc.identifier.uri | http://bura.brunel.ac.uk/handle/2438/6002 | - |
dc.description | Copyright @ 2008 Oxford University Press | en_US |
dc.description.abstract | There has been much interest in testing from finite-state machines (FSMs). If the system under test can be modelled by the (minimal) FSM N then testing from an (minimal) FSM M is testing to check that N is isomorphic to M. In the distributed test architecture, there are multiple interfaces/ports and there is a tester at each port. This can introduce controllability/synchronization and observability problems. This paper shows that the restriction to test sequences that do not cause controllability problems and the inability to observe the global behaviour in the distributed test architecture, and thus relying only on the local behaviour at remote testers, introduces fundamental limitations into testing. There exist minimal FSMs that are not equivalent, and so are not isomorphic, and yet cannot be distinguished by testing in this architecture without introducing controllability problems. Similarly, an FSM may have non-equivalent states that cannot be distinguished in the distributed test architecture without causing controllability problems: these are said to be locally s-equivalent and otherwise they are locally s-distinguishable. This paper introduces the notion of two states or FSMs being locally s-equivalent and formalizes the power of testing in the distributed test architecture in terms of local s-equivalence. It introduces a polynomial time algorithm that, given an FSM M, determines which states of M are locally s-equivalent and produces minimal length input sequences that locally s-distinguish states that are not locally s-equivalent. An FSM is locally s-minimal if it has no pair of locally s-equivalent states. This paper gives an algorithm that takes an FSM M and returns a locally s-minimal FSM M′ that is locally s-equivalent to M. | en_US |
dc.description.sponsorship | This work was supported in part by Leverhulme Trust grant number F/00275/D, Testing State Based Systems, Natural Sciences and Engineering Research Council (NSERC) of Canada grant number RGPIN 976, and Engineering and Physical Sciences Research Council grant number GR/R43150, Formal Methods and Testing (FORTEST). | en_US |
dc.language.iso | en | en_US |
dc.publisher | Oxford University Press | en_US |
dc.subject | Testing | en_US |
dc.subject | Finite state machine | en_US |
dc.subject | Distributed test architecture | en_US |
dc.subject | Equivalence | en_US |
dc.title | The effect of the distributed test architecture on the power of testing | en_US |
dc.type | Article | en_US |
dc.identifier.doi | http://dx.doi.org/10.1093/comjnl/bxm096 | - |
pubs.organisational-data | /Brunel | - |
pubs.organisational-data | /Brunel/Brunel (Active) | - |
pubs.organisational-data | /Brunel/Brunel (Active)/School of Info. Systems, Comp & Maths | - |
pubs.organisational-data | /Brunel/Research Centres (RG) | - |
pubs.organisational-data | /Brunel/Research Centres (RG)/CIKM | - |
pubs.organisational-data | /Brunel/School of Information Systems, Computing and Mathematics (RG) | - |
pubs.organisational-data | /Brunel/School of Information Systems, Computing and Mathematics (RG)/CIKM | - |
Appears in Collections: | Publications Computer Science Dept of Computer Science Research Papers |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
local_cj_final.pdf | 240.7 kB | Adobe PDF | View/Open |
Items in BURA are protected by copyright, with all rights reserved, unless otherwise indicated.