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/
Go to the corresponding LIPIcs Volume Portal

Nakamura, Yoshiki

Spatial Existential Positive Logics for Hyperedge Replacement Grammars

pdf-format:
LIPIcs-CSL-2022-30.pdf (0.9 MB)

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

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI