3 papers
cs.AI2020
Containment of Simple Regular Path Queries
Diego Figueira, Adwait Godbole, S. Krishna +3
Testing containment of queries is a fundamental reasoning task in knowledge representation. We study here the containment problem for Conjunctive Regular Path Queries (CRPQs), a na…
cs.DB2018
Enumeration on Trees with Tractable Combined Complexity and Efficient Updates
Antoine Amarilli, Pierre Bourhis, Stefan Mengel +1
We give an algorithm to enumerate the results on trees of monadic second-order (MSO) queries represented by nondeterministic tree automata. After linear time preprocessing (in the…
cs.DB2018
Constant-Delay Enumeration for Nondeterministic Document Spanners
Antoine Amarilli, Pierre Bourhis, Stefan Mengel +1
We consider the information extraction framework known as document spanners, and study the problem of efficiently computing the results of the extraction from an input document, wh…