Graph Logics with Rational Relations

DOI10.1145/3070822zbMath1367.68082OpenAlexW2613188923MaRDI QIDQ5278208

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

shuffleword equationsregular path queriesrational relationslogics for graphscomplexity of evaluation

Mathematics Subject Classification ID

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

Related Items

Word equations in the context of string solving, Foundations of graph path query languages. Course notes for the reasoning web summer school 2021, Institutions for navigational logics for graphical structures, Closure properties of synchronized relations, A logic for document spanners

Uses Software

• SPARQ2L

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Synchronized rational relations of finite and infinite words
• Rewriting of regular expressions and regular path queries
• Sets recognized by n-tape automata
• The existential theory of equations with rational constraints in free groups is PSPACE-complete
• Graph Logics with Rational Relations
• Hardness of Longest Common Subsequence for Sequences with Bounded Run-Lengths
• RELATIONAL STRING VERIFICATION USING MULTI-TRACK AUTOMATA
• Definable relations and first-order query languages over strings
• Algorithmic Metatheorems for Decidable LTL Model Checking over Infinite Systems
• Satisfiability of word equations with constants is in PSPACE
• The Complexity of Some Problems on Subsequences and Supersequences
• THE PROBLEM OF SOLVABILITY OF EQUATIONS IN A FREE SEMIGROUP
• Algorithms on Strings, Trees and Sequences
• The expressibility of languages and relations by word equations
• Path Logics for Querying Graphs: Combining Expressiveness and Efficiency
• Computer Aided Verification
• Solving word equations