2012/03/10 by Yongming Li, Qian Wang, Li, Yongming +3
Computer Science · #68Q45 #FOS: Computer and information sciences #Formal Languages and Automata Theory (cs.FL) #Logic, programming, and type systems #Natural Language Processing Techniques #cs.FL #msc:68Q45 #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.1203.2236
48 pages, 3 figures, 30 conferences
arxiv created 2012/03/10 · openalex publication_date 2012/03/10 · arxiv updated 2012/03/13 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Quotient is a basic operation of formal languages, which plays a key role in the construction of minimal deterministic finite automata (DFA) and the universal automata. In this paper, we extend this operation to formal power series and systemically investigate its implications in the study of weighted automata. In particular, we define two quotient operations for formal power series that coincide when calculated by a word. We term the first operation as (left or right) quotient, and the second as (left or right) residual. To support the definitions of quotients and residuals, the underlying semiring is restricted to complete semirings or complete c-semirings. Algebraical properties that are similar to the classical case are obtained in the formal power series case. Moreover, we show closure properties, under quotients and residuals, of regular series and weighted context-free series are similar as in formal languages. Using these operations, we define for each formal power series A two weighted automata \cal MA and \cal UA. Both weighted automata accepts A, and \cal MA is the minimal deterministic weighted automaton of A. The universality of \cal UA is justified and, in particular, we show that \cal MA is a sub-automaton of \cal UA. Last but not least, an effective method to construct the universal automaton is also presented in this paper.