کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
436308 | 689987 | 2014 | 30 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
The per-character cost of repairing word languages
ترجمه فارسی عنوان
هزینه هر شخصیت برای اصلاح زبان های کلمه
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
تعمیر، هزینه عادی همبستگی، ویرایش فاصله، اتوماتای فاصله، زبان های منظم
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
• We formalize the notion of asymptotic repair cost.
• We show how to compute the asymptotic repair cost between two regular languages.
• We give similar results in the streaming setting.
We show how to calculate the maximum number of edits per character needed to convert any string in one regular language to a string in another language. Our algorithm makes use of a local determinization procedure applicable to a subclass of distance automata. We then show how to calculate the same property when the editing needs to be done in streaming fashion, by a finite state transducer, using a reduction to mean-payoff games. In this case, we show that the optimal streaming editor can be produced in P.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 539, 19 June 2014, Pages 38–67
Journal: Theoretical Computer Science - Volume 539, 19 June 2014, Pages 38–67
نویسندگان
Michael Benedikt, Gabriele Puppis, Cristian Riveros,