The emptiness problem for tree automata with at least one global disequality constraint is NP-hard
| Affiliation auteurs | !!!! Error affiliation !!!! |
| Titre | The emptiness problem for tree automata with at least one global disequality constraint is NP-hard |
| Type de publication | Journal Article |
| Year of Publication | 2017 |
| Auteurs | Heam P.-C, Hugot V., Kouchnarenko O. |
| Journal | INFORMATION PROCESSING LETTERS |
| Volume | 118 |
| Pagination | 6-9 |
| Date Published | FEB |
| Type of Article | Article |
| ISSN | 0020-0190 |
| Mots-clés | Algorithms, Formal languages, Tree automata |
| Résumé | The model of tree automata with global equality and disequality constraints was introduced in 2007 by Filiot, Talbot and Tison, and extended in various ways since then. In this paper we show that if there is at least one disequality constraint, the emptiness problem is NP-hard. (C) 2016 Elsevier B.V. All rights reserved. |
| DOI | 10.1016/j.ipl.2016.09.007 |