Open AccessWeighted Automaton and Varieties of Formal Power Series
Author(s) -
Wang Yongbing,
Li Yongming
Publication year - 2017
Publication title -
chinese journal of electronics
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.267
H-Index - 25
eISSN - 2075-5597
pISSN - 1022-4653
DOI - 10.1049/cje.2017.01.021
Subject(s) - series (stratigraphy) , automaton , formal power series , computer science , mathematics , power (physics) , power series , algorithm , theoretical computer science , geology , physics , mathematical analysis , paleontology , quantum mechanics
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.