Grigore Rosu - Matching Logic

lmcs:4153 - Logical Methods in Computer Science, December 20, 2017, Volume 13, Issue 4 - https://doi.org/10.23638/LMCS-13(4:28)2017
Matching Logic

Authors: Grigore Rosu

    This paper presents matching logic, a first-order logic (FOL) variant for specifying and reasoning about structure by means of patterns and pattern matching. Its sentences, the patterns, are constructed using variables, symbols, connectives and quantifiers, but no difference is made between function and predicate symbols. In models, a pattern evaluates into a power-set domain (the set of values that match it), in contrast to FOL where functions and predicates map into a regular domain. Matching logic uniformly generalizes several logical frameworks important for program analysis, such as: propositional logic, algebraic specification, FOL with equality, modal logic, and separation logic. Patterns can specify separation requirements at any level in any program configuration, not only in the heaps or stores, without any special logical constructs for that: the very nature of pattern matching is that if two structures are matched as part of a pattern, then they can only be spatially separated. Like FOL, matching logic can also be translated into pure predicate logic with equality, at the same time admitting its own sound and complete proof system. A practical aspect of matching logic is that FOL reasoning with equality remains sound, so off-the-shelf provers and SMT solvers can be used for matching logic reasoning. Matching logic is particularly well-suited for reasoning about programs in programming languages that have an operational semantics, but it is not limited to this.


    Volume: Volume 13, Issue 4
    Published on: December 20, 2017
    Accepted on: December 20, 2017
    Submitted on: December 20, 2017
    Keywords: Computer Science - Logic in Computer Science,D.2.4,D.3.1,F.3,F.4
    Fundings :
      Source : OpenAIRE Research Graph
    • SHF: Small: Scalable and Maximal Predictive Runtime Verification for Concurrent Software; Funder: National Science Foundation; Code: 1421575
    • SHF: Small: Usable Verification using Rewriting and Matching Logic; Funder: National Science Foundation; Code: 1218605
    • SHF: Small: VeriF-OPT, a Verification Framework for Optimizations and Program Transformations; Funder: National Science Foundation; Code: 1318191

    2 Documents citing this article

    Share

    Consultation statistics

    This page has been seen 1139 times.
    This article's PDF has been downloaded 461 times.