کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4952134 | 1442010 | 2017 | 16 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
A disambiguation algorithm for weighted automata
ترجمه فارسی عنوان
یک الگوریتم ابهام برای ماشینهای وزن
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
اتوماتای وزنی، الگوریتم های اتوماتای وزن، نظریه اتوماتیک، سری قدرت عقلانی،
ترجمه چکیده
ما یک الگوریتم ابهام برای ماشینهای وزن داریم. الگوریتم دو مرحله اصلی را پذیرفته است: یک مرحله قبل از تشخیص و به دنبال آن یک مرحله انتقال حذف شده است. ما شرح مفصلی از الگوریتم و اثبات صحت آن را ارائه می دهیم. این الگوریتم برای همه ماشینهای وزنی قابل استفاده نیست، اما ما شرایط کافی برای کاربرد آن در مورد ترمینال گرمسیری را با معرفی ویژگی ضعیف دوقلوها ثابت می کنیم. به طور خاص، الگوریتم را می توان با هر ماشین اتوماتیک وزن بیش از نیمه گرمسیری که برای آن الگوریتم تعیین وزن استفاده می شود، متوقف می کند و با هر ماشین اتوماتیک مقادیر آسیلیلی بیش از یک معادله تضعیف و تعویض تقسیم پذیری ضعیف سمت چپ دلخواه دلخواه است. درحالی که با استفاده از تعیین وزنی می توان ابهام های گوناگونی را بدست آورد، الگوریتم ابهام الگوریتم ما در برخی موارد می تواند نتیجه ای را که به صورت مؤثر کوچکتر از هر دستگاه اتوماتیک معکوس است، بازگرداند. ما همچنین شواهدی تجربی درباره مزایای فیزیکی ابهام در تعیین تعیین در تشخیص گفتار و برنامه های ترجمه ماشین را ارائه می دهیم.
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
We present a disambiguation algorithm for weighted automata. The algorithm admits two main stages: a pre-disambiguation stage followed by a transition removal stage. We give a detailed description of the algorithm and the proof of its correctness. The algorithm is not applicable to all weighted automata but we prove sufficient conditions for its applicability in the case of the tropical semiring by introducing the weak twins property. In particular, the algorithm can be used with any weighted automaton over the tropical semiring for which the weighted determinization algorithm terminates and with any acyclic weighted automaton over an arbitrary weakly left divisible cancellative and commutative semiring. While disambiguation can sometimes be achieved using weighted determinization, our disambiguation algorithm in some cases can return a result that is exponentially smaller than any equivalent deterministic automaton. We also present some empirical evidence of the space benefits of disambiguation over determinization in speech recognition and machine translation applications.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 679, 30 May 2017, Pages 53-68
Journal: Theoretical Computer Science - Volume 679, 30 May 2017, Pages 53-68
نویسندگان
Mehryar Mohri, Michael D. Riley,