Weighted Automaton and Varieties of Formal Power Series  

作　　者：WANG Yongbing LI Yongming 

机构地区：[1]College of Computer Science,Shaanxi Normal University [2]College of Mathematics and Computation,Anqing Normal University

出　　处：《Chinese Journal of Electronics》2017年第2期299-305,共7页电子学报（英文版）

基　　金：supported by the National Natural Science Foundation of China(No.11271237,No.11301316,No.11301321)

摘　　要：We introduce the concepts of syntactic monoids of formal power series through syntactic congruences on a free monoid,and we study recognition of formal power series by monoids,as well as the basic properties of syntactic congruences and syntactic monoids.We also prove that syntactic monoids of formal power series are sub-direct products of syntactic monoids of crisp cut series.We present the Myhill-Nerode theorem for formal power series and provide some precise characterizations for regular series and its syntactic monoid.We show an Eilenbergtype theorem for formal power series,we establish a bijective correspondence among varieties of regular series,varieties of regular languages and varieties of monoids.We introduce the concepts of syntactic monoids of formal power series through syntactic congruences on a free monoid,and we study recognition of formal power series by monoids,as well as the basic properties of syntactic congruences and syntactic monoids.We also prove that syntactic monoids of formal power series are sub-direct products of syntactic monoids of crisp cut series.We present the Myhill-Nerode theorem for formal power series and provide some precise characterizations for regular series and its syntactic monoid.We show an Eilenbergtype theorem for formal power series,we establish a bijective correspondence among varieties of regular series,varieties of regular languages and varieties of monoids.

关 键 词：Formal power series Weighted automaton Regular series Quotient Syntactic monoids Variety theorem 

分 类 号：O152.7[理学—数学]