Weighted Automaton and Varieties of Formal Power Series

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.