The Emptiness Problem for Tree Automata with at Least One Disequality Constraint is NP-hard - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Rapport (Rapport De Recherche) Année : 2014

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

Résumé

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.

Domaines

Informatique et langage [cs.CL]
Fichier principal
Vignette du fichier
tagednk.pdf (142.49 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)

Pierre-Cyrille Heam  : Connectez-vous pour contacter le contributeur

https://inria.hal.science/hal-01089711

Soumis le : mardi 2 décembre 2014-11:09:24

Dernière modification le : lundi 11 septembre 2023-17:41:18

Archivage à long terme le : mardi 3 mars 2015-13:11:15

Télécharger pour visualiser

Dates et versions

hal-01089711 , version 1 (02-12-2014)

Identifiants

Citer

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⟩

Exporter

BibTeX XML-TEI Dublin Core DC Terms EndNote DataCite

Collections

UNIV-LILLE3 CNRS INRIA UNIV-FCOMTE UNIV-BM FEMTO-ST UNIV-BM-THESE CRISTAL UNIV-LORRAINE INRIA2 CRISTAL-LINKS LORIA LORIA-FM LARA ANR
232 Consultations
51 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More