Graph logics with rational relations

DOI10.2168/LMCS-9(3:1)2013zbMATH Open1272.03147arXiv1304.4150MaRDI QIDQ2846573FDOQ2846573

Authors: Pablo Barceló, Diego Figueira, Leonid Libkin 

Publication date: 6 September 2013

Published in: Logical Methods in Computer Science (Search for Journal in Brave)

Abstract: We investigate some basic questions about the interaction of regular and rational relations on words. The primary motivation comes from the study of logics for querying graph topology, which have recently found numerous applications. Such logics use conditions on paths expressed by regular languages and relations, but they often need to be extended by rational relations such as subword or subsequence. Evaluating formulae in such extended graph logics boils down to checking nonemptiness of the intersection of rational relations with regular or recognizable relations (or, more generally, to the generalized intersection problem, asking whether some projections of a regular relation have a nonempty intersection with a given rational relation). We prove that for several basic and commonly used rational relations, the intersection problem with regular relations is either undecidable (e.g., for subword or suffix, and some generalizations), or decidable with non-primitive-recursive complexity (e.g., for subsequence and its generalizations). These results are used to rule out many classes of graph logics that freely combine regular and rational relations, as well as to provide the simplest problem related to verifying lossy channel systems that has non-primitive-recursive complexity. We then prove a dichotomy result for logics combining regular conditions on individual paths and rational relations on paths, by showing that the syntactic form of formulae classifies them into either efficiently checkable or undecidable cases. We also give examples of rational relations for which such logics are decidable even without syntactic restrictions.

Full work available at URL: https://arxiv.org/abs/1304.4150

Recommendations

• Graph Logics with Rational Relations and the Generalized Intersection Problem
• Graph logics with rational relations: the role of word combinatorics
• Graph logics with rational relations: the role of word combinatorics
• A graph calculus for predicate logic
• On the Expressive Power of Graph Logic
• A graph-theoretic account of logics
• Expressiveness and complexity of graph logic
• The Equational Logic For Graph Algebras
• Graph theoretical structures in logic programs and default theories
• Graphs and plausibility logic

zbMATH Keywords

graph databasesintersection problemregular relationsrational relationsnon-primitive recursiverecognizable relationsRPQ

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Automata and formal grammars in connection with logical questions (03D05) Database theory (68P15) Combinatorics on words (68R15) Logic in computer science (03B70)

Cited In (12)

• Closure properties of synchronized relations
• Foundations of graph path query languages. Course notes for the reasoning web summer school 2021
• Fregean Logical Graphs
• Conjunctive visibly-pushdown path queries
• Graph logics with rational relations: the role of word combinatorics
• Graph logics with rational relations: the role of word combinatorics
• Generalized rational relations and their logical definability
• On the Expressive Power of Graph Logic
• Chain-free string constraints
• Complexity hierarchies beyond elementary
• Decision procedures for sequence theories
• Graph Logics with Rational Relations and the Generalized Intersection Problem

Uses Software

• GraphLog

This page was built for publication: Graph logics with rational relations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2846573)