Testing theory for probabilistic systems. Wolf, V. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 3472 LNCS:233-275, 2005.
Testing theory for probabilistic systems [link]Website  abstract   bibtex   
We have given an extensive survey of the testing theory for probabilistic systems and presented the definitions of different preorders in a uniform style to ease the task of establishing relationships between them. Moreover we saw that in most cases the relations are closely connected with the classical testing relation of De Nicola and Hennessy (see Figure 9.14, page 265) and we discussed characterizations to better reflect the nature of the relations (see Figure 9.15, page 270). Table 9.1 summarizes the main contents of this chapter. Computational issues: Most authors do not not address computational issues, but from the summary table we can see that some of the relations are decidable. First, consider the characterization by extended traces. If the process is finite, we can determine the (finite) set of extended traces with a non-zero probability and compute the probability of each extended trace with the inductive definitions of section 9.11.1. Christoff presents algorithms for verification of his testing relations in [CC91]. Furthermore, we have a characterization by probabilistic bisimulation that can be computed in polynomial time and space by a partitioning technique [HT92]. To the best of our knowledge, for all other relations no algorithms computing them exist. Open problems: • We have only pointed out the most obvious connections between the different preorders presented here. Clarifying which relations are incomparable and which are finer/coarser than others would be helpful to obtain a more complete picture on probabilistic testing relations. For example, the relationship between the following pairs of relations has not been considered yet: (⊆CL, ⊆CL), (⊆CL, ⊆JY), (⊆CHwte, ⊆BC) and the ⊆LS with any of the "compositional testing relations". • Many relations are not computable because infinite sets of test processes have to be applied, so an interesting problem would be finding the set of "essential" test processes that decide whether two processes are related or not. A good starting point would be defining the "informativeness" of a test process with regard to the tested process. Of course, test processes should be as compact as possible avoiding unnecessary computations. © Springer-Verlag Berlin Heidelberg 2005.
@article{
 title = {Testing theory for probabilistic systems},
 type = {article},
 year = {2005},
 keywords = {Algorithms,Automata theory,Polynomial time,Probabilistic bisimulation,Probabilistic logics,Probabilistic systems,Problem solving,Software testing,Testing theory},
 pages = {233-275},
 volume = {3472 LNCS},
 websites = {http://www.scopus.com/inward/record.url?eid=2-s2.0-36849044726&partnerID=40&md5=b9cb99864d2adcf9d4d092a715a269b2},
 id = {cb486db4-1972-3c4f-b3df-c3d73b330caa},
 created = {2016-02-15T08:58:11.000Z},
 file_attached = {false},
 profile_id = {bbb99b2d-2278-3254-820f-2de6d915ce63},
 last_modified = {2017-03-22T13:51:34.979Z},
 read = {false},
 starred = {false},
 authored = {true},
 confirmed = {true},
 hidden = {false},
 private_publication = {false},
 abstract = {We have given an extensive survey of the testing theory for probabilistic systems and presented the definitions of different preorders in a uniform style to ease the task of establishing relationships between them. Moreover we saw that in most cases the relations are closely connected with the classical testing relation of De Nicola and Hennessy (see Figure 9.14, page 265) and we discussed characterizations to better reflect the nature of the relations (see Figure 9.15, page 270). Table 9.1 summarizes the main contents of this chapter. Computational issues: Most authors do not not address computational issues, but from the summary table we can see that some of the relations are decidable. First, consider the characterization by extended traces. If the process is finite, we can determine the (finite) set of extended traces with a non-zero probability and compute the probability of each extended trace with the inductive definitions of section 9.11.1. Christoff presents algorithms for verification of his testing relations in [CC91]. Furthermore, we have a characterization by probabilistic bisimulation that can be computed in polynomial time and space by a partitioning technique [HT92]. To the best of our knowledge, for all other relations no algorithms computing them exist. Open problems: • We have only pointed out the most obvious connections between the different preorders presented here. Clarifying which relations are incomparable and which are finer/coarser than others would be helpful to obtain a more complete picture on probabilistic testing relations. For example, the relationship between the following pairs of relations has not been considered yet: (⊆CL, ⊆CL), (⊆CL, ⊆JY), (⊆CHwte, ⊆BC) and the ⊆LS with any of the "compositional testing relations". • Many relations are not computable because infinite sets of test processes have to be applied, so an interesting problem would be finding the set of "essential" test processes that decide whether two processes are related or not. A good starting point would be defining the "informativeness" of a test process with regard to the tested process. Of course, test processes should be as compact as possible avoiding unnecessary computations. © Springer-Verlag Berlin Heidelberg 2005.},
 bibtype = {article},
 author = {Wolf, V},
 journal = {Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)}
}
Downloads: 0
About
Documentation
Keywords
Search
Users
Terms and Conditions of Use
Privacy Policy
Sitemap
© BibBase.org 2021