WANG Yongbing, LI Yongming. Weighted Automaton and Varieties of Formal Power Series[J]. Chinese Journal of Electronics, 2017, 26(2): 299-305. doi: 10.1049/cje.2017.01.021
Citation: WANG Yongbing, LI Yongming. Weighted Automaton and Varieties of Formal Power Series[J]. Chinese Journal of Electronics, 2017, 26(2): 299-305. doi: 10.1049/cje.2017.01.021

Weighted Automaton and Varieties of Formal Power Series

doi: 10.1049/cje.2017.01.021
Funds:  This work is supported by the National Natural Science Foundation of China (No.11271237, No.11301316, No.11301321).
  • Received Date: 2016-03-10
  • Rev Recd Date: 2016-08-05
  • Publish Date: 2017-03-10
  • 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.
  • loading
  • S. Eilenberg, Automata, Languages and Machines, Academic Press, New York, 1974.
    J.E. Pin, Varieties of Formal Languages, North Oxford Academic, London, 1986.
    T. Petković, "Varieties of fuzzy languages", Proc. of 1st Internat. Conf. on Algebraic Informatics, Aristotle University of Thessaloniki, Thessaloniki, pp.197-205, 2005,
    Z. Fülöp and M. Steinby, "Varieties of recognizable tree series over fields", Theoretical Computer Science, Vol.412, Nos.8-10, pp.736-752, 2011.
    M.P. Schützenberger, "On the definition of a family of automata", Information and Control, Vol.4, Nos.2-3, pp.245-270, 1961.
    M. Droste, W. Kuich and H. Vogler (Eds.), Handbook of Weighted Automata, Springer-Verlag, Berlin-Heidelberg, 2009.
    A. Salomaa and M. Soittola, Automata-Theoretic Aspects of Formal Power Series, Springer, Berlin, 1978.
    M. Droste and G.Q. Zhang, "On transformations of formal power series", Information and Computation, Vol.184, No.2, pp.369-383, 2003.
    J. Shen, "Fuzzy language on free monoid", Information Sciences, Vol.88, Nos.1-4, pp.149-168, 1996.
    J.N. Mordeson and D.S. Malik, Fuzzy Automata and Languages:Theory and Applications, Chapman & Hall, CRC, Boca Raton, London, 2002.
    D.W. Qiu, "Characterizations of fuzzy finite automata", Fuzzy Sets and Systems, Vol.141, No.3, pp.391-414, 2004.
    Y.M. Li and W. "Pedrycz,Fuzzy finite automata and fuzzy regular expressions with membership values in lattice-ordered monoids", Fuzzy Sets and Systems, Vol.156, No.1, pp.68-92, 2005.
    Y.Z. Cao and Y. "Ezawa, Nondeterministic fuzzy automata", Information Sciences, Vol.191, No.15, pp.86-97, 2012.
    M. Droste, T. Stüber and H. Vogler, "Weighted finite automata over strong bimonoids", Information Sciences, Vol.180, No.1, pp.156-166, 2010.
    J. Ignjatović, M. Ćirić, S. Bogdanović, et al., "Myhill-Nerode type theory for fuzzy languages and automata", Fuzzy Sets and Systems, Vol.161, No.9, pp.1288-1324, 2010.
    J. Almeida, "On pseudovarieties, varieties of languages", filters of congruences, pseudoidentities and related topics, Algebra Universalis, Vol.27, No.3, pp.333-350, 1990.
  • 加载中

Catalog

    通讯作者: 陈斌, bchen63@163.com
    • 1. 

      沈阳化工大学材料科学与工程学院 沈阳 110142

    1. 本站搜索
    2. 百度学术搜索
    3. 万方数据库搜索
    4. CNKI搜索

    Article Metrics

    Article views (126) PDF downloads(436) Cited by()
    Proportional views
    Related

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return