Weighted Automaton and Varieties of Formal Power Series. Issue 2 (1st March 2017)

• Record Type: Journal Article
• Authors: Wang, Yongbing; Li, Yongming
• Is Part Of: Chinese journal of electronics. Volume 26:Issue 2(2017)
• Page Start: 299
• Page End: 305
• Publication Date: 2017-03-01
• Subjects: Formal power series -- Weighted automaton -- Regular series -- Quotient -- Syntactic monoids -- Variety theorem; automata theory -- formal languages -- polynomials; weighted automaton -- formal power series -- syntactic congruences -- syntactic monoids -- crisp cut series -- Myhill‐Nerode theorem; Electronics -- Periodicals; Electronics -- China -- Periodicals; Electronics; China; Periodicals; 621.38105
• DOI: 10.1049/cje.2017.01.021
• Languages: English
• ISSNs: 1022-4653

Abstract

Abstract : 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 Eilenberg‐type theorem for formal power series, we establish a bijective correspondence among varieties of regular series, varieties of regular languages and varieties of monoids.