Graph Logics with Rational Relations and the Generalized Intersection Problem

DOI10.1109/LICS.2012.23zbMath1362.68063MaRDI QIDQ2986787

Diego Figueira, Pablo Barceló, Leonid O. Libkin

Publication date: 16 May 2017

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

zbMATH Keywords

complexitydecidabilityexpressive powersubwordsubsequenceregular path queriesregular relationsrational relationsrecognizable relationslogics for graphs

Mathematics Subject Classification ID

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

Related Items (4)

On Boolean closed full trios and rational Kripke frames ⋮ Closure properties and complexity of rational sets of regular languages ⋮ Synchronizing relations on words ⋮ Document Spanners

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