کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4950722 | 1364302 | 2017 | 20 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Visibly pushdown modular games,
ترجمه فارسی عنوان
بازی های مدولار ظاهری پایدار
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
Recursive game graphs can be used to reason about the control flow of sequential programs with recursion. Here, the most natural notion of strategy is the modular one, i.e., a strategy that is local to a module and is oblivious to previous module invocations. In this work, we study for the first time modular strategies with respect to winning conditions expressed as languages of pushdown automata. We show that pushdown modular games are undecidable in general, and become decidable for visibly pushdown automata specifications. Our solution relies on a reduction to modular games with finite-state winning conditions. We carefully characterize the computational complexity of this decision problem by also considering as winning conditions nondeterministic and universal Büchi or co-Büchi visibly pushdown automata, and CaRet or Nwtl temporal logic formulas. As a further contribution, we present a different synthesis algorithm that improves on known solutions for large specifications and many exits.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Information and Computation - Volume 253, Part 2, April 2017, Pages 204-223
Journal: Information and Computation - Volume 253, Part 2, April 2017, Pages 204-223
نویسندگان
I. De Crescenzo, S. La Torre, Y. Velner,