22 citations · 90 across the 29 of their papers we have counts for
4 papers · 1 filter
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…
Knowledge Compilation, Width and Quantification
Florent Capelli, Stefan Mengel
We generalize many results concerning the tractability of SAT and #SAT on bounded treewidth CNF-formula in the context of Quantified Boolean Formulas (QBF). To this end, we start b…
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…
QBF as an Alternative to Courcelle's Theorem
Michael Lampis, Stefan Mengel, Valia Mitsou
We propose reductions to quantified Boolean formulas (QBF) as a new approach to showing fixed-parameter linear algorithms for problems parameterized by treewidth. We demonstrate th…