title: The algebraic characterizations for a formal power series over complete strong bimonoids.
abstract: On the basis of run semantics and breadth-first algebraic semantics, the algebraic characterizations for a classes of formal power series over complete strong bimonoids are investigated in this paper. As recognizers, weighted pushdown automata with final states (WPDAs for short) and empty stack (WPDAs[Formula: see text]) are shown to be equivalent based on run semantics. Moreover, it is demonstrated that for every WPDA there is an equivalent crisp-simple weighted pushdown automaton with final states by run semantics if the underlying complete strong bimonoid satisfies multiplicatively local finiteness condition. As another type of generators, weighted context-free grammars over complete strong bimonoids are introduced, which are proven to be equivalent to WPDAs[Formula: see text] based on each one of both run semantics and breadth-first algebraic semantics. Finally examples are presented to illuminate the proposed methods and results.
authors.affiliation: College of Sciences, Southwest Petroleum University, Xindu District, Xindu Road, Chengdu, 610500 China ; College of Mathematics and Econometrics, Hunan University, Yuelu Mountain South Road, Changsha, 410082 China.
authors.forename: Jian Hua
authors.initials: JH
authors.lastname: Jin
authors.affiliation: College of Sciences, Southwest Petroleum University, Xindu District, Xindu Road, Chengdu, 610500 China.
authors.forename: Chun Quan
authors.initials: CQ
authors.lastname: Li
keywords: Equivalence; Formal power series; Strong bimonoids; Weighted context-free grammars; Weighted pushdown automata