6 citations
- Laboratoire d'Informatique Fondamentale de LilleFR2 papers
- Centre Inria de l'Université de LilleFR1 paper
- Centre Inria de l'Université de LorraineFR1 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
- Laboratoire Lorrain de Recherche en Informatique et ses ApplicationsFR1 paper
- Technische Universität DresdenDE1 paper
2 papers
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…