A navigational logic for reasoning about graph properties

Graphs play an important role in many areas of Computer Science. In particular, our work is motivated by model-driven software development and by graph databases. For this reason, it is very important to have the means to express and to reason about the properties that a given graph may satisfy. With this aim, in this paper we present a visual logic that allows us to describe graph properties, including navigational properties, i.e., properties about the paths in a graph. The logic is equipped with a deductive tableau method that we have proved to be sound and complete.

Metadaten
Author details:	Marisa Navarro ORCiD, Fernando Orejas ORCiD, Elvira Pino ORCiD, Leen Lambers ORCiD GND
DOI:	https://doi.org/10.1016/j.jlamp.2020.100616
ISSN:	2352-2208
ISSN:	2352-2216
Title of parent work (English):	Journal of logical and algebraic methods in programming
Publisher:	Elsevier Science
Place of publishing:	Amsterdam [u.a.]
Publication type:	Article
Language:	English
Date of first publication:	2021/01/01
Publication year:	2021
Release date:	2024/03/15
Tag:	Algebraic methods; Formal modelling; Graph logic; Specification
Volume:	118
Article number:	100616
Number of pages:	33
Funding institution:	Spanish Ministry of Economy and Competitiveness under grant GRAMM [TIN2017-86727-C2-1-R, TIN2017-86727-C2-2-R]; European Union (FEDER funds) under grant GRAMM [TIN2017-86727-C2-1-R, TIN2017-86727-C2-2-R]; Basque Project [GIU15/30, UFI11/45]
Organizational units:	Digital Engineering Fakultät / Hasso-Plattner-Institut für Digital Engineering GmbH
DDC classification:	0 Informatik, Informationswissenschaft, allgemeine Werke / 00 Informatik, Wissen, Systeme / 004 Datenverarbeitung; Informatik
Peer review:	Referiert