The Emptiness Problem for Tree Automata with at Least One Disequality Constraint is NP-hard

Pierre-Cyrille Héam 1, 2 Vincent Hugot 3, 4 Olga Kouchnarenko 2, 1
1 CASSIS - Combination of approaches to the security of infinite states systems
FEMTO-ST - Franche-Comté Électronique Mécanique, Thermique et Optique - Sciences et Technologies (UMR 6174), Inria Nancy - Grand Est, LORIA - FM - Department of Formal Methods
3 LINKS - Linking Dynamic Data
LIFL - Laboratoire d'Informatique Fondamentale de Lille, Inria Lille - Nord Europe
Abstract : 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 disequality constraint, the emptiness problem is NP-hard.
Document type :
Reports
Complete list of metadatas

Cited literature [13 references]  Display  Hide  Download

https://hal.inria.fr/hal-01089711
Contributor : Pierre-Cyrille Heam <>
Submitted on : Tuesday, December 2, 2014 - 11:09:24 AM
Last modification on : Thursday, February 21, 2019 - 10:52:55 AM
Long-term archiving on : Tuesday, March 3, 2015 - 1:11:15 PM

Files

tagednk.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-01089711, version 1
  • ARXIV : 1412.0839

Citation

Pierre-Cyrille Héam, Vincent Hugot, Olga Kouchnarenko. The Emptiness Problem for Tree Automata with at Least One Disequality Constraint is NP-hard. [Research Report] FEMTO-ST. 2014. ⟨hal-01089711⟩

Share

Metrics

Record views

526

Files downloads

128