Graph Logics with Rational Relations and the Generalized Intersection Problem

DOI10.1109/LICS.2012.23MaRDI QIDQ2986787zbMATH OpenFDO

Authors Pablo Barceló, Diego Figueira, Leonid Libkin

Publication date 16 May 2017

Published in 2012 27th Annual IEEE Symposium on Logic in Computer Science (Search for Journal in Brave)

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

zbMATH Keywords

complexitydecidabilityexpressive powerlogics for graphsrational relationsrecognizable relationsregular path queriesregular relationssubsequencesubword

Mathematics Subject Classification ID

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

Recommendations

• Graph logics with rational relations
• Graph logics with rational relations: the role of word combinatorics
• Graph logics with rational relations: the role of word combinatorics
• On graphs for intuitionistic modal logics
• The Equational Logic For Graph Algebras
• On the Expressive Power of Graph Logic
• Graph theoretical structures in logic programs and default theories
• A graph-theoretic account of logics
• A graph calculus for predicate logic
• scientific article; zbMATH DE number 6970800

Cited in

(10)

• On Boolean closed full trios and rational Kripke frames
• Document spanners: a formal approach to information extraction
• Graph logics with rational relations
• Graph logics with rational relations: the role of word combinatorics
• Graph logics with rational relations: the role of word combinatorics
• Using Multigraphs to Study the Interaction Between Opposition, Implication and Duality Relations in Logical Squares
• A class of rational trace relations closed under composition
• Efficient iterative programs with distributed data collections
• Closure properties and complexity of rational sets of regular languages
• Synchronizing relations on words

This page was built for publication: Graph Logics with Rational Relations and the Generalized Intersection Problem

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