Determinization of weighted finite automata over strong bimonoids

被引：47

作者：

Ciric, Miroslav ^{[1
]}

Droste, Manfred ^{[2
]}

Ignjatovic, Jelena ^{[1
]}

Vogler, Heiko ^{[3
]}

机构：

[1] Univ Nis, Fac Sci & Math, Nish 18000, Serbia

[2] Univ Leipzig, Inst Informat, D-04009 Leipzig, Germany

[3] Tech Univ Dresden, Fac Comp Sci, D-01062 Dresden, Germany

来源：

INFORMATION SCIENCES | 2010年 / 180卷 / 18期

关键词：

Weighted automaton; Strong bimonoid; Formal power series; Determinization; Nerode automaton; Myhill automaton; Run automaton; QUANTUM LOGIC; MEMBERSHIP VALUES; RECOGNIZABILITY;

D O I：

10.1016/j.ins.2010.05.020

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

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. (C) 2010 Elsevier Inc. All rights reserved.

引用

页码：3497 / 3520

页数：24

共 40 条

[31]

SAKAROVITCH J, 2003, ELEMENTS THEORIE AUT

[32]

Salomaa A., 1978, Automata-theoretic aspects of formal power series

[33] FINITE TREE AUTOMATA WITH COST-FUNCTIONS [J].