کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
10331366 | 686682 | 2005 | 10 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Closure properties and decision problems of dag automata
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
![عکس صفحه اول مقاله: Closure properties and decision problems of dag automata Closure properties and decision problems of dag automata](/preview/png/10331366.png)
چکیده انگلیسی
Tree automata are widely used in various contexts. They are closed under boolean operations and their emptiness problem is decidable in polynomial time. Dag automata are natural extensions of tree automata, operating on dags instead of on trees; they can also be used for solving problems. Our purpose in this paper is to show that algebraically they behave differently: the class of dag automata is not closed under complementation, dag automata are not determinizable, their membership problem is NP-complete, the universality problem is undecidable, and the emptiness problem is NP-complete even for deterministic labeled dag automata.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Information Processing Letters - Volume 94, Issue 5, 15 June 2005, Pages 231-240
Journal: Information Processing Letters - Volume 94, Issue 5, 15 June 2005, Pages 231-240
نویسندگان
Siva Anantharaman, Paliath Narendran, Michael Rusinowitch,