Computer Science – Formal Languages and Automata Theory
Scientific paper
2012-03-10
Computer Science
Formal Languages and Automata Theory
48 pages, 3 figures, 30 conferences
Scientific paper
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) \emph{quotient}, and the second as (left or right) \emph{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 M}_A$ and ${\cal U}_A$. Both weighted automata accepts $A$, and ${\cal M}_A$ is the minimal deterministic weighted automaton of $A$. The universality of ${\cal U}_A$ is justified and, in particular, we show that ${\cal M}_A$ is a sub-automaton of ${\cal U}_A$. Last but not least, an effective method to construct the universal automaton is also presented in this paper.
Li Sanjiang
Li Yongming
Wang Qiangguo
No associations
LandOfFree
On Quotients of Formal Power Series does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with On Quotients of Formal Power Series, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On Quotients of Formal Power Series will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-488368