Publikation: An Efficient Algorithm for Computing Causal Trace Sets in Causality Checking
Lade...
Dateien
Zu diesem Dokument gibt es keine Dateien.
Datum
2019
Autor:innen
Herausgeber:innen
ISSN der Zeitschrift
Electronic ISSN
ISBN
Bibliografische Daten
Verlag
Schriftenreihe
Auflagebezeichnung
URI (zitierfähiger Link)
DOI (zitierfähiger Link)
Internationale Patentnummer
Link zur Lizenz
Angaben zur Forschungsförderung
Projekt
Open Access-Veröffentlichung
Open Access Green
Core Facility der Universität Konstanz
Titel in einer weiteren Sprache
Publikationstyp
Beitrag zu einem Konferenzband
Publikationsstatus
Published
Erschienen 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, 2019, pp. 171-186. Lecture Notes in Computer Science. 11781. ISSN 0302-9743. eISSN 1611-3349. ISBN 978-3-030-31783-6. Available under: doi: 10.1007/978-3-030-31784-3_10
Zusammenfassung
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.
Zusammenfassung in einer weiteren Sprache
Fachgebiet (DDC)
004 Informatik
Schlagwörter
Konferenz
International Symposium on Automated Technology for Verification and Analysis : 17th International Symposium, ATVA 2019, 28. Okt. 2019 - 31. Okt. 2019, Taipei
Rezension
undefined / . - undefined, undefined
Zitieren
ISO 690
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, 28. Okt. 2019 - 31. Okt. 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, 2019, pp. 171-186. Lecture Notes in Computer Science. 11781. ISSN 0302-9743. eISSN 1611-3349. ISBN 978-3-030-31783-6. Available under: doi: 10.1007/978-3-030-31784-3_10BibTex
@inproceedings{Kolbl2019Effic-53474,
year={2019},
doi={10.1007/978-3-030-31784-3_10},
title={An Efficient Algorithm for Computing Causal Trace Sets in Causality Checking},
number={11781},
isbn={978-3-030-31783-6},
issn={0302-9743},
publisher={Springer Nature},
address={Cham},
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: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/server/rdf/resource/123456789/53474">
<dc:contributor>Leue, Stefan</dc:contributor>
<dcterms:available rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2021-04-23T11:44:58Z</dcterms:available>
<dc:creator>Kölbl, Martin</dc:creator>
<dc:creator>Leue, Stefan</dc:creator>
<dcterms:rights rdf:resource="https://rightsstatements.org/page/InC/1.0/"/>
<dcterms:issued>2019</dcterms:issued>
<dc:rights>terms-of-use</dc:rights>
<void:sparqlEndpoint rdf:resource="http://localhost/fuseki/dspace/sparql"/>
<dspace:isPartOfCollection rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/36"/>
<bibo:uri rdf:resource="https://kops.uni-konstanz.de/handle/123456789/53474"/>
<dcterms:hasPart rdf:resource="https://kops.uni-konstanz.de/bitstream/123456789/53474/1/Koelbl_2-1u56ubk3dc5085.pdf"/>
<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>
<foaf:homepage rdf:resource="http://localhost:8080/"/>
<dc:date rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2021-04-23T11:44:58Z</dc:date>
<dcterms:title>An Efficient Algorithm for Computing Causal Trace Sets in Causality Checking</dcterms:title>
<dspace:hasBitstream rdf:resource="https://kops.uni-konstanz.de/bitstream/123456789/53474/1/Koelbl_2-1u56ubk3dc5085.pdf"/>
<dcterms:isPartOf rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/36"/>
<dc:contributor>Kölbl, Martin</dc:contributor>
<dc:language>eng</dc:language>
</rdf:Description>
</rdf:RDF>Interner Vermerk
xmlui.Submission.submit.DescribeStep.inputForms.label.kops_note_fromSubmitter
Prüfungsdatum der Dissertation
Finanzierungsart
Kommentar zur Publikation
Allianzlizenz
Corresponding Authors der Uni Konstanz vorhanden
Internationale Co-Autor:innen
Universitätsbibliographie
Ja
