• search hit 5 of 23
Back to Result List

Evaluation diversity for graph conditions

  • Graphs are used as a universal data structure in various domains. Sets of graphs (and likewise graph morphisms) can be specified using, e.g., the graph logic Image 1 of Graph Conditions (GCs). The evaluation of a graph against such a GC results in a Boolean satisfaction judgement on whether the graph is specified by the GC. The graph logic Image 1 is known to be as expressive as first-order logic on graphs. However, since infinitely many graphs exist, there are also infinitely many evaluations for each given GC. To support GC validation, testing, debugging, and repair, a suitable synthesis procedure generating a complete compact overview of how a given GC may be evaluated for possibly varying graphs is called for. In a previous paper, we generated such an overview for a given GC in the form of a complete finite set of diverse evaluations for varying associated graphs formally given by so called Evaluation Trees (ETs). Each of these ETs concretely describes how its associated graph is evaluated against the given GC by recording theGraphs are used as a universal data structure in various domains. Sets of graphs (and likewise graph morphisms) can be specified using, e.g., the graph logic Image 1 of Graph Conditions (GCs). The evaluation of a graph against such a GC results in a Boolean satisfaction judgement on whether the graph is specified by the GC. The graph logic Image 1 is known to be as expressive as first-order logic on graphs. However, since infinitely many graphs exist, there are also infinitely many evaluations for each given GC. To support GC validation, testing, debugging, and repair, a suitable synthesis procedure generating a complete compact overview of how a given GC may be evaluated for possibly varying graphs is called for. In a previous paper, we generated such an overview for a given GC in the form of a complete finite set of diverse evaluations for varying associated graphs formally given by so called Evaluation Trees (ETs). Each of these ETs concretely describes how its associated graph is evaluated against the given GC by recording the executed evaluation steps. Moreover, these generated ETs and the given GC for which they are generated have the same underlying structure easing comprehensibility of the represented evaluation steps. The returned ETs are complete since each possible ET subsumes one of the returned ETs and diverse by not containing superfluous ETs subsuming smaller ETs. We now extend and refine this approach still solving the ET synthesis problem by (a) extending the graph logic GL allowing for the specification of a minimal number of graph patterns to be contained in specified graphs, (b) provide means to scale the size of the generated ETs up to a user-provided bound allowing for the generation of not just minimal ETs, (c) record the order of evaluations steps also for operators where the evaluation but not the operator itself defines such an order, and (d) generate ETs recording combinations of reasons for (non-)satisfaction of GCs where only single reasons were recorded before.show moreshow less

Export metadata

Additional Services

Search Google Scholar
Metadaten
Author: Sven Schneider, Leen Lambers
URL:https://www.sciencedirect.com/science/article/pii/S2352220823000160?via%3Dihub
DOI:https://doi.org/10.1016/j.jlamp.2023.100862
ISSN:2352-2216
ISSN:2352-2208
Title of the source (English):Journal of Logical and Algebraic Methods in Programming
Document Type:Scientific journal article peer-reviewed
Language:English
Year of publication:2023
Tag:Coverage criteria; Debugging; Graph logic; Logic coverage; Model generation; Validation
Volume/Year:133
Article number:100862
Faculty/Chair:Fakultät 1 MINT - Mathematik, Informatik, Physik, Elektro- und Informationstechnik / FG Praktische Informatik / Softwaresystemtechnik
Einverstanden ✔
Diese Webseite verwendet technisch erforderliche Session-Cookies. Durch die weitere Nutzung der Webseite stimmen Sie diesem zu. Unsere Datenschutzerklärung finden Sie hier.