کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
395784 666016 2010 24 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Determinization of weighted finite automata over strong bimonoids
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر هوش مصنوعی
پیش نمایش صفحه اول مقاله
Determinization of weighted finite automata over strong bimonoids
چکیده انگلیسی

We consider weighted finite automata over strong bimonoids, where these weight structures can be considered as semirings which might lack distributivity. Then, in general, the well-known run semantics, initial algebra semantics, and transition semantics of an automaton are different. We prove an algebraic characterization for the initial algebra semantics in terms of stable finitely generated submonoids. Moreover, for a given weighted finite automaton we construct the Nerode automaton and Myhill automaton, both being crisp-deterministic, which are equivalent to the original automaton with respect to the initial algebra semantics, respectively, the transition semantics. We prove necessary and sufficient conditions under which the Nerode automaton and the Myhill automaton are finite, and we provide efficient algorithms for their construction. Also, for a given weighted finite automaton, we show sufficient conditions under which a given weighted finite automaton can be determinized preserving its run semantics.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Information Sciences - Volume 180, Issue 18, 15 September 2010, Pages 3497–3520
نویسندگان
, , , ,