Path logics for querying graphs: combining expressiveness and efficiency

DOI10.1109/LICS.2015.39MaRDI QIDQ4635815zbMATH OpenFDO

Authors Diego Figueira, Leonid Libkin

Publication date 23 April 2018

Published in 2015 30th Annual ACM/IEEE Symposium on Logic in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1109/LICS.2015.39

Mathematics Subject Classification ID

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

Recommendations

• Graph logics with rational relations: the role of word combinatorics
• Graph logics with rational relations: the role of word combinatorics
• Querying regular graph patterns
• Querying Graphs with Data
• Expressive path queries on graph with data

Cited in

(26)

• Closure properties of synchronized relations
• History-deterministic Parikh automata
• Expressiveness results for an inductive logic of separated relations
• Foundations of Software Science and Computation Structures
• An accelerated search on the graph: PROLOG representation
• ``Most of leads to undecidability: failure of adding frequencies to LTL
• The algebraic theory of Parikh automata
• Querying best paths in graph databases
• A pattern logic for automata with outputs
• Path querying on acyclic graphs using Boolean grammars
• scientific article; zbMATH DE number 1735826 (Why is no real title available?)
• scientific article; zbMATH DE number 7407799 (Why is no real title available?)
• Graph logics with rational relations: the role of word combinatorics
• Graph logics with rational relations: the role of word combinatorics
• Decidable (ac)counting with Parikh and Muller: adding Presburger arithmetic to monadic second-order logic over tree-interpretable structures
• Remarks on Parikh-recognizable omega-languages
• As soon as possible but rationally
• Using variable automata for querying data graphs
• Certified Graph View Maintenance with Regular Datalog
• Parikh one-counter automata
• Resynchronizing classes of word relations
• PDL for structured data: a graph-calculus approach
• Synchronization of Parikh automata
• On computability of data word functions defined by transducers
• History-deterministic Parikh automata
• Relative expressive power of navigational querying on graphs

This page was built for publication: Path logics for querying graphs: combining expressiveness and efficiency

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