کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
6876342 | 689759 | 2013 | 14 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Rigorous approximated determinization of weighted automata
ترجمه فارسی عنوان
تعیین دقیق تقریبی ماشین آلات با وزن
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
اتوماتای وزنی، تعیین کننده، نزدیک شدن
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
In this paper we study approximated determinization of WFAs. We describe an algorithm that, given a WFA A and an approximation factor tâ¥1, constructs a DWFA Aâ² that t-determinizesA. Formally, for all words wâΣâ, the value of w in Aâ² is at least its value in A and at most t times its value in A. Our construction involves two new ideas: attributing states in the subset construction by both upper and lower residues, and collapsing attributed subsets whose residues can be tightened. The larger the approximation factor is, the more attributed subsets we can collapse. Thus, t-determinization is helpful not only for WFAs that cannot be determinized, but also in cases determinization is possible but results in automata that are too big to handle. We also describe a property (the t-twins property) and use it in order to characterize t-determinizable WFAs. Finally, we describe a polynomial algorithm for deciding whether a given WFA has the t-twins property.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 480, 8 April 2013, Pages 104-117
Journal: Theoretical Computer Science - Volume 480, 8 April 2013, Pages 104-117
نویسندگان
Benjamin Aminof, Orna Kupferman, Robby Lampert,