2026-07-27T04:03:19Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:15750 2024-03-06T10:56:06Z ddc:004 open_access

Spatial Existential Positive Logics for Hyperedge Replacement Grammars Nakamura, Yoshiki Existential positive logic spatial logic Kleene theorem 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Yoshiki Nakamura 2022 Is Part Of LIPIcs, Volume 216, 30th EACSL Annual Conference on Computer Science Logic (CSL 2022) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CSL.2022.30 urn:nbn:de:0030-drops-157504 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2022.30 eng https://creativecommons.org/licenses/by/4.0/legalcode