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, 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.
Type de document :
Rapport
[Research Report] FEMTO-ST. 2014
Liste complète des métadonnées

Littérature citée [13 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01089711
Contributeur : Pierre-Cyrille Heam <>
Soumis le : mardi 2 décembre 2014 - 11:09:24
Dernière modification le : jeudi 15 février 2018 - 08:48:14
Document(s) archivé(s) le : mardi 3 mars 2015 - 13:11:15

Fichiers

tagednk.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • 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〉

Partager

Métriques

Consultations de la notice

461

Téléchargements de fichiers

111