38 citations
- Centre de Recherche en Informatique, Signal et Automatique de LilleFR2 papers
- Laboratoire d'Informatique Fondamentale de LilleFR2 papers
- Millennium InstituteBR2 papers
- Birkbeck, University of LondonGB1 paper
- Centre de Recherche en InformatiqueFR1 paper
- Centre Inria de l'Université de LilleFR1 paper
- Centre Inria de l'Université de LorraineFR1 paper
- Centre National de la Recherche ScientifiqueFR1 paper
- Community LinkUS1 paper
- École Centrale de LilleFR1 paper
- Franche-Comté Électronique Mécanique Thermique et Optique - Sciences et TechnologiesFR1 paper
- Institut national de recherche en sciences et technologies du numériqueFR1 paper
Showing 2014Show all
2 papers · 1 filter
cs.FL2014
The Emptiness Problem for Tree Automata with at Least One Disequality Constraint is NP-hard
P. -C Héam, V. Hugot, O. Kouchnarenko
The model of tree automata with equality and disequality constraints was introduced in 2007 by Filiot, Talbot and Tison. In this paper we show that if there is at least one disequa…
cs.DB2014★ 6 cited
Query Containment for Highly Expressive Datalog Fragments
Pierre Bourhis, Markus Krötzsch, Sebastian Rudolph
The containment problem of Datalog queries is well known to be undecidable. There are, however, several Datalog fragments for which containment is known to be decidable, most notab…