All-Path reachability logic

Andrei Ştefanescu, Stefan Ciobâcă, Radu Mereuta, Brandon M. Moore, Grigore Rosu, Traian Florin şerbănuţă

Research output: Contribution to journalArticle

Abstract

This paper presents a language-independent proof system for reachability properties of programs written in non-deterministic (e.g., concurrent) languageş referred to as all-path reachability logic. It derives partial-correctness properties with all-path semantics (a state satisfying a given precondition reaches states satisfying a given postcondition on all terminating execution paths). The proof system takes as axioms any unconditional operational semanticş and is sound (partially correct) and (relatively) complete, independent of the object language. The soundness has also been mechanized in Coq. This approach is implemented in a tool for semantics-based verification as part of the K framework (http://kframework.org).

Original languageEnglish (US)
Pages (from-to)5:1-5:23
JournalLogical Methods in Computer Science
Volume15
Issue number2
DOIs
StatePublished - Jan 1 2019

Fingerprint

Reachability
Proof System
Semantics
Logic
Path
Precondition
Operational Semantics
Soundness
Axioms
Concurrent
Correctness
Acoustic waves
Partial
Language

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Cite this

Ştefanescu, A., Ciobâcă, S., Mereuta, R., Moore, B. M., Rosu, G., & şerbănuţă, T. F. (2019). All-Path reachability logic. Logical Methods in Computer Science, 15(2), 5:1-5:23. https://doi.org/10.23638/LMCS-15(2:5)2019

All-Path reachability logic. / Ştefanescu, Andrei; Ciobâcă, Stefan; Mereuta, Radu; Moore, Brandon M.; Rosu, Grigore; şerbănuţă, Traian Florin.

In: Logical Methods in Computer Science, Vol. 15, No. 2, 01.01.2019, p. 5:1-5:23.

Research output: Contribution to journalArticle

Ştefanescu, A, Ciobâcă, S, Mereuta, R, Moore, BM, Rosu, G & şerbănuţă, TF 2019, 'All-Path reachability logic', Logical Methods in Computer Science, vol. 15, no. 2, pp. 5:1-5:23. https://doi.org/10.23638/LMCS-15(2:5)2019
Ştefanescu A, Ciobâcă S, Mereuta R, Moore BM, Rosu G, şerbănuţă TF. All-Path reachability logic. Logical Methods in Computer Science. 2019 Jan 1;15(2):5:1-5:23. https://doi.org/10.23638/LMCS-15(2:5)2019
Ştefanescu, Andrei ; Ciobâcă, Stefan ; Mereuta, Radu ; Moore, Brandon M. ; Rosu, Grigore ; şerbănuţă, Traian Florin. / All-Path reachability logic. In: Logical Methods in Computer Science. 2019 ; Vol. 15, No. 2. pp. 5:1-5:23.
@article{0af2d8d859f243edb37cc0ac0e6ce30d,
title = "All-Path reachability logic",
abstract = "This paper presents a language-independent proof system for reachability properties of programs written in non-deterministic (e.g., concurrent) languageş referred to as all-path reachability logic. It derives partial-correctness properties with all-path semantics (a state satisfying a given precondition reaches states satisfying a given postcondition on all terminating execution paths). The proof system takes as axioms any unconditional operational semanticş and is sound (partially correct) and (relatively) complete, independent of the object language. The soundness has also been mechanized in Coq. This approach is implemented in a tool for semantics-based verification as part of the K framework (http://kframework.org).",
author = "Andrei Ştefanescu and Stefan Ciob{\^a}că and Radu Mereuta and Moore, {Brandon M.} and Grigore Rosu and şerbănuţă, {Traian Florin}",
year = "2019",
month = "1",
day = "1",
doi = "10.23638/LMCS-15(2:5)2019",
language = "English (US)",
volume = "15",
pages = "5:1--5:23",
journal = "Logical Methods in Computer Science",
issn = "1860-5974",
publisher = "Technischen Universitat Braunschweig",
number = "2",

}

TY - JOUR

T1 - All-Path reachability logic

AU - Ştefanescu, Andrei

AU - Ciobâcă, Stefan

AU - Mereuta, Radu

AU - Moore, Brandon M.

AU - Rosu, Grigore

AU - şerbănuţă, Traian Florin

PY - 2019/1/1

Y1 - 2019/1/1

N2 - This paper presents a language-independent proof system for reachability properties of programs written in non-deterministic (e.g., concurrent) languageş referred to as all-path reachability logic. It derives partial-correctness properties with all-path semantics (a state satisfying a given precondition reaches states satisfying a given postcondition on all terminating execution paths). The proof system takes as axioms any unconditional operational semanticş and is sound (partially correct) and (relatively) complete, independent of the object language. The soundness has also been mechanized in Coq. This approach is implemented in a tool for semantics-based verification as part of the K framework (http://kframework.org).

AB - This paper presents a language-independent proof system for reachability properties of programs written in non-deterministic (e.g., concurrent) languageş referred to as all-path reachability logic. It derives partial-correctness properties with all-path semantics (a state satisfying a given precondition reaches states satisfying a given postcondition on all terminating execution paths). The proof system takes as axioms any unconditional operational semanticş and is sound (partially correct) and (relatively) complete, independent of the object language. The soundness has also been mechanized in Coq. This approach is implemented in a tool for semantics-based verification as part of the K framework (http://kframework.org).

UR - http://www.scopus.com/inward/record.url?scp=85070399992&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85070399992&partnerID=8YFLogxK

U2 - 10.23638/LMCS-15(2:5)2019

DO - 10.23638/LMCS-15(2:5)2019

M3 - Article

AN - SCOPUS:85070399992

VL - 15

SP - 5:1-5:23

JO - Logical Methods in Computer Science

JF - Logical Methods in Computer Science

SN - 1860-5974

IS - 2

ER -