کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4951235 | 1441198 | 2017 | 31 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Determinacy and rewriting of functional top-down and MSO tree transformations
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله

چکیده انگلیسی
A query is determined by a view, if the result of the query can be reconstructed from the result of the view. We consider the problem of deciding for two given (functional) tree transformations, whether one is determined by the other. If the view transformation is induced by a tree transducer that may copy, then determinacy is undecidable. For a large class of noncopying views, namely compositions of extended linear top-down tree transducers, we show that determinacy is decidable, where queries are either deterministic top-down tree transducers (with regular look-ahead) or deterministic MSO tree transducers. We also show that if a query is determined by a view, then it can be rewritten into a query that works over the view and is in the same class of transducers as the query. The proof relies on the decidability of equivalence for the considered classes of queries, and on their composition closure.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Computer and System Sciences - Volume 85, May 2017, Pages 57-73
Journal: Journal of Computer and System Sciences - Volume 85, May 2017, Pages 57-73
نویسندگان
M. Benedikt, J. Engelfriet, S. Maneth,