کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
6874212 | 1441029 | 2018 | 7 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Balancedness of MSO transductions in polynomial time
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
We show that MSO definable tree-to-string transductions with a fixed copy number, given as top-down tree-to-string transducers with fixed copying-bound, can be checked for balancedness of all output strings in polynomial time. We also present an upper bound for the copying bound for deterministic top-down transducers and show that in general, balancedness of output languages of deterministic finite-copying top-down tree-to-string transducers is DExptime-hard.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Information Processing Letters - Volume 133, May 2018, Pages 26-32
Journal: Information Processing Letters - Volume 133, May 2018, Pages 26-32
نویسندگان
S. Maneth, H. Seidl,