کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4950911 | 1441044 | 2017 | 4 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
The emptiness problem for tree automata with at least one global disequality constraint is NP-hard
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
![عکس صفحه اول مقاله: The emptiness problem for tree automata with at least one global disequality constraint is NP-hard The emptiness problem for tree automata with at least one global disequality constraint is NP-hard](/preview/png/4950911.png)
چکیده انگلیسی
- Tree Automata with constraints are a relevant for modeling programs, protocols and XML-like documents.
- The Emptiness problem for TAG⧠is decidable but the only known algorithm is non elementary.
- Studying the complexity of sub-classes of TAG⧠is therefore a challenging problem.
- We prove that the emptiness problem for TAG⧠with at least one disequality constraint is NP-hard.
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.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Information Processing Letters - Volume 118, February 2017, Pages 6-9
Journal: Information Processing Letters - Volume 118, February 2017, Pages 6-9
نویسندگان
P.-C. Héam, V. Hugot, O. Kouchnarenko,