کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
9657926 | 690117 | 2005 | 18 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Weak Muller acceptance conditions for tree automata
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
![عکس صفحه اول مقاله: Weak Muller acceptance conditions for tree automata Weak Muller acceptance conditions for tree automata](/preview/png/9657926.png)
چکیده انگلیسی
Over the last decades the theory of automata on infinite objects has been an important source of tools for the specification and the verification of computer programs. Trees are more suitable than words to model nondeterminism and concurrency. In the literature, there are several examples of acceptance conditions that have been proposed for automata on infinite words and then have been fruitfully extended to infinite trees. The type of acceptance condition can influence both the succinctness of the language acceptors and the computational complexity of the decision problems. Here we consider, relatively to automata on infinite trees, two acceptance conditions that are obtained by a relaxation of the Muller acceptance condition: the Landweber and the Muller-Superset conditions. We prove that Muller-Superset tree automata accept the same class of languages as Büchi tree automata. Also, we show that for such languages the minimal Muller-Superset acceptor is at least as succinct as the minimal Büchi acceptor and, in some cases, it can be exponentially more succinct. Landweber tree automata, instead, define a class of languages that is not comparable with that defined by Büchi tree automata. The main result we prove is that the emptiness problem for this class of automata is decidable in polynomial time, and thus we extend the class of automata with a tractable emptiness problem.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 332, Issues 1â3, 28 February 2005, Pages 233-250
Journal: Theoretical Computer Science - Volume 332, Issues 1â3, 28 February 2005, Pages 233-250
نویسندگان
Salvatore La Torre, Aniello Murano, Margherita Napoli,