License:
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CSL.2022.30
URN: urn:nbn:de:0030-drops-157504
URL: https://drops.dagstuhl.de/opus/volltexte/2022/15750/
Nakamura, Yoshiki
Spatial Existential Positive Logics for Hyperedge Replacement Grammars
Abstract
We study a (first-order) spatial logic based on graphs of conjunctive queries for expressing (hyper-)graph languages. In this logic, each primitive positive (resp. existential positive) formula plays a role of an expression of a graph (resp. a finite language of graphs) modulo graph isomorphism. First, this paper presents a sound- and complete axiomatization for the equational theory of primitive/existential positive formulas under this spatial semantics. Second, we show Kleene theorems between this logic and hyperedge replacement grammars (HRGs), namely that over graphs, the class of existential positive first-order (resp. least fixpoint, transitive closure) formulas has the same expressive power as that of non-recursive (resp. all, linear) HRGs.
BibTeX - Entry
@InProceedings{nakamura:LIPIcs.CSL.2022.30,
author = {Nakamura, Yoshiki},
title = {{Spatial Existential Positive Logics for Hyperedge Replacement Grammars}},
booktitle = {30th EACSL Annual Conference on Computer Science Logic (CSL 2022)},
pages = {30:1--30:17},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-218-1},
ISSN = {1868-8969},
year = {2022},
volume = {216},
editor = {Manea, Florin and Simpson, Alex},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/15750},
URN = {urn:nbn:de:0030-drops-157504},
doi = {10.4230/LIPIcs.CSL.2022.30},
annote = {Keywords: Existential positive logic, spatial logic, Kleene theorem}
}
Keywords: |
|
Existential positive logic, spatial logic, Kleene theorem |
Collection: |
|
30th EACSL Annual Conference on Computer Science Logic (CSL 2022) |
Issue Date: |
|
2022 |
Date of publication: |
|
27.01.2022 |