KOPS - The Institutional Repository of the University of Konstanz

An Efficient Algorithm for Computing Causal Trace Sets in Causality Checking

An Efficient Algorithm for Computing Causal Trace Sets in Causality Checking

Cite This

Files in this item

Checksum: MD5:0519873f207a8d454ed822642a363a03

KÖLBL, Martin, Stefan LEUE, 2019. An Efficient Algorithm for Computing Causal Trace Sets in Causality Checking. International Symposium on Automated Technology for Verification and Analysis : 17th International Symposium, ATVA 2019. Taipei, Oct 28, 2019 - Oct 31, 2019. In: CHEN, Yu-Fang, ed., Chih-Hong CHENG, ed., Javier ESPARZA, ed.. Automated Technology for Verification and Analysis 17th International Symposium, ATVA 2019, Proceedings. Cham:Springer Nature, pp. 171-186. ISSN 0302-9743. eISSN 1611-3349. ISBN 978-3-030-31783-6. Available under: doi: 10.1007/978-3-030-31784-3_10

@inproceedings{Kolbl2019Effic-53474, title={An Efficient Algorithm for Computing Causal Trace Sets in Causality Checking}, year={2019}, doi={10.1007/978-3-030-31784-3_10}, number={11781}, isbn={978-3-030-31783-6}, issn={0302-9743}, address={Cham}, publisher={Springer Nature}, series={Lecture Notes in Computer Science}, booktitle={Automated Technology for Verification and Analysis 17th International Symposium, ATVA 2019, Proceedings}, pages={171--186}, editor={Chen, Yu-Fang and Cheng, Chih-Hong and Esparza, Javier}, author={Kölbl, Martin and Leue, Stefan} }

<rdf:RDF xmlns:dcterms="http://purl.org/dc/terms/" xmlns:dc="http://purl.org/dc/elements/1.1/" xmlns:rdf="http://www.w3.org/1999/02/22-rdf-syntax-ns#" xmlns:bibo="http://purl.org/ontology/bibo/" xmlns:dspace="http://digital-repositories.org/ontologies/dspace/0.1.0#" xmlns:foaf="http://xmlns.com/foaf/0.1/" xmlns:void="http://rdfs.org/ns/void#" xmlns:xsd="http://www.w3.org/2001/XMLSchema#" > <rdf:Description rdf:about="https://kops.uni-konstanz.de/rdf/resource/123456789/53474"> <dc:rights>terms-of-use</dc:rights> <dspace:isPartOfCollection rdf:resource="https://kops.uni-konstanz.de/rdf/resource/123456789/36"/> <dcterms:rights rdf:resource="https://rightsstatements.org/page/InC/1.0/"/> <dcterms:abstract xml:lang="eng">Causality Checking [LL13a] has been proposed as a finite state space exploration technique which computes ordered sequences of events that are considered to cause the violation of a reachability property. A crucial point in the implementation of Causality Checking is the computation and storage of all minimal counterexamples found during state space exploration. We refer to the set of all minimal counterexamples as a causal trace set. However, the Duplicate State Prefix Matching (DSPM) Algorithm that is currently used in Causality Checking only under-approximates the causal trace set. As we argue, without the approximation the DSPM algorithm is inefficient. We propose the, to the best of our knowledge, first efficient algorithm that precisely computes a causal trace set, avoiding approximation, called Causal Trace Backward Search (CTBS). We compare the DSPM and CTBS algorithms with respect to their worst case complexities, and by applying them to several case studies.</dcterms:abstract> <dc:contributor>Leue, Stefan</dc:contributor> <dc:contributor>Kölbl, Martin</dc:contributor> <dcterms:hasPart rdf:resource="https://kops.uni-konstanz.de/bitstream/123456789/53474/1/Koelbl_2-1u56ubk3dc5085.pdf"/> <bibo:uri rdf:resource="https://kops.uni-konstanz.de/handle/123456789/53474"/> <void:sparqlEndpoint rdf:resource="http://localhost/fuseki/dspace/sparql"/> <dcterms:title>An Efficient Algorithm for Computing Causal Trace Sets in Causality Checking</dcterms:title> <foaf:homepage rdf:resource="http://localhost:8080/jspui"/> <dc:language>eng</dc:language> <dc:date rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2021-04-23T11:44:58Z</dc:date> <dc:creator>Kölbl, Martin</dc:creator> <dc:creator>Leue, Stefan</dc:creator> <dcterms:isPartOf rdf:resource="https://kops.uni-konstanz.de/rdf/resource/123456789/36"/> <dspace:hasBitstream rdf:resource="https://kops.uni-konstanz.de/bitstream/123456789/53474/1/Koelbl_2-1u56ubk3dc5085.pdf"/> <dcterms:issued>2019</dcterms:issued> <dcterms:available rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2021-04-23T11:44:58Z</dcterms:available> </rdf:Description> </rdf:RDF>

Downloads since Apr 23, 2021 (Information about access statistics)

Koelbl_2-1u56ubk3dc5085.pdf 18

This item appears in the following Collection(s)

Search KOPS


Browse

My Account