Graph logics with rational relations: the role of word combinatorics

DOI10.1145/3070822MaRDI QIDQ5278208zbMATH OpenOpenAlexWikidataFDO

Authors Pablo Barceló, Pablo R. Muñoz

Publication date 13 July 2017

Published in ACM Transactions on Computational Logic (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/3070822

zbMATH Keywords

complexity of evaluationlogics for graphsrational relationsregular path queriesshuffleword equations

Mathematics Subject Classification ID

Logic in computer science (03B70) Database theory (68P15) Analysis of algorithms and problem complexity (68Q25) Combinatorics on words (68R15)

Recommendations

• Graph logics with rational relations: the role of word combinatorics
• Graph logics with rational relations
• Graph Logics with Rational Relations and the Generalized Intersection Problem
• Path logics for querying graphs: combining expressiveness and efficiency
• Expressive path queries on graph with data

Cites work

• Algorithmic metatheorems for decidable LTL model checking over infinite systems
• Algorithms on Strings, Trees and Sequences
• Computer Aided Verification
• Definable relations and first-order query languages over strings
• Elements of automata theory. Translated from the French by Reuben Thomas
• Graph logics with rational relations
• Hardness of longest common subsequence for sequences with bounded run-lengths
• scientific article; zbMATH DE number 3660804 (Why is no real title available?)
• scientific article; zbMATH DE number 1339964 (Why is no real title available?)
• scientific article; zbMATH DE number 1024080 (Why is no real title available?)
• Path logics for querying graphs: combining expressiveness and efficiency
• Relational string verification using multi-track automata
• Rewriting of regular expressions and regular path queries
• Satisfiability of word equations with constants is in PSPACE
• Sets recognized by n-tape automata
• Solving word equations
• Synchronized rational relations of finite and infinite words
• The Complexity of Some Problems on Subsequences and Supersequences
• The existential theory of equations with rational constraints in free groups is PSPACE-complete
• The expressibility of languages and relations by word equations
• THE PROBLEM OF SOLVABILITY OF EQUATIONS IN A FREE SEMIGROUP

Cited in

(18)

• Subsequence versus substring constraints in sequence pattern languages
• Word equations in the context of string solving
• A logic for document spanners
• Graph logics with rational relations
• Graph Logics with Rational Relations and the Generalized Intersection Problem
• A term-graph clausal logic: completeness and incompleteness results ★
• Graph logics with rational relations: the role of word combinatorics
• Pattern logics and auxiliary relations
• Path logics for querying graphs: combining expressiveness and efficiency
• Closure properties of synchronized relations
• scientific article; zbMATH DE number 6747949 (Why is no real title available?)
• Positive First-order Logic on Words and Graphs
• Evaluation diversity for graph conditions
• Foundations of graph path query languages. Course notes for the reasoning web summer school 2021
• Using Multigraphs to Study the Interaction Between Opposition, Implication and Duality Relations in Logical Squares
• A closer look at the expressive power of logics based on word equations
• Institutions for navigational logics for graphical structures
• FC-Datalog as a framework for efficient string querying

Describes a project that uses

Uses Software

• SPARQ2L

This page was built for publication: Graph logics with rational relations: the role of word combinatorics

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