Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Regular grammars with truth values in lattice-ordered monoid and their languages

  • Original Paper
  • Published:
Soft Computing Aims and scope Submit manuscript

Abstract

In this study, we introduce the concept of lattice-valued regular grammars. Such grammars have become a necessary tool for the analysis of fuzzy finite automata. The relationship between lattice-valued finite automata (LA) and lattice-valued regular grammars (LRG) are discussed and we get the following results, for a given LRG, there exists an LA such that they accept the same languages, and vice versa. We also show the equivalence between deterministic lattice-valued regular grammars and deterministic lattice-valued finite automata.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

Explore related subjects

Discover the latest articles, news and stories from top researchers in related subjects.

References

  • Asveld PRJ (2003) Algebraic aspects of families of fuzzy languages. Theor Comput Sci 293:417–445

    Google Scholar 

  • Balbes R, Dwinger P (1974) Distributive lattices. University of Mossouri Press, Columbia

    Google Scholar 

  • Bělohlávek R (2002) Determinism and fuzzy automata. Inform Sci 142:205–209

    Google Scholar 

  • Birkhoff G (1940) Lattice theory, 3rd edn (1973). American Mathematical Society, Providence, Rhode Island

  • Hopcroft JE, Ullman JD (1979) Introduction to automata theory, languages and computation. Addison-Wesley, New York

    Google Scholar 

  • Kandel A, Lee SC (1980) Fuzzy switching and automata: theory and applications. Arnold, London

    Google Scholar 

  • Lee ET, Zadeh LA (1969) Note on fuzzy languages. Inform Sci 1:421–434

    Google Scholar 

  • Li YM, Zhou M, Li ZH (2002) Projective objects and injective objects in the category of quantales. J Pure Appl Algebra 176(2–3):249–258

    Google Scholar 

  • Li YM, Shi ZK (2000) Remarks on uninorm aggregation operators. Fuzzy Sets Syst 114(3):377–380

    Google Scholar 

  • Li YM (2003) Finite automata with truth values in lattice-ordered monoid and and their languages. (preprint)

  • Li YM, Pedrycz W (2004) Regular expressions with truth values in lattice-moniod and their languages. In: 2004 Annual meeting of The North American Fuzzy Infromation Processing Society. 2004 IEEE ISBN 0-7803-8377-X IEEE Cat. No. 04TH8736C, Banff, Alberta, Canda, 27–30 June 2004, pp 572–577

  • Malik DS, Mordeson JN (2000) Fuzzy discrete structures. Physica-Verlag, New York

    Google Scholar 

  • Mordeson JN, Malik DS (2002) Fuzzy automata and languages: theory and applications. Chapman and Hall/CRC, Boca Raton, London

    Google Scholar 

  • Močkoř J (2002) Semigroup homomorphisms and fuzzy automata. Soft Comput 6:423–427

    Google Scholar 

  • Qiu DW (2001) Automata theory based on complete residuated lattice-valued logic. Sci China Ser F 44(6):419–429

    Google Scholar 

  • Rosenthal KL (1990) Quantales and their applications. Longman Scientific and Technical, London

    Google Scholar 

  • Santos ES (1975) Realization of fuzzy languages by probabilistic, max-product and maxmin automata. Inform Sci 8:39–53

    Google Scholar 

  • Santos ES (1976) Fuzzy automata and languages. Inform Sci 10:193–197

    Google Scholar 

  • Santos ES (1977) Regular fuzzy expressions. In: gupta MM, Saridis GN, Gaines BR (eds) Fuzzy Automata and Decision Processes. North-Holland, Amsterdam, pp 169–175

    Google Scholar 

  • Shen JZ (1996) Fuzzy language on free monoid. Inform Sci 88:149–168

    Google Scholar 

  • Thomason MG, Marinos PN (1974) Deterministic acceptors of regular fuzzy languages. IEEE Trans Syst Man Cybern 4:228–230

    Google Scholar 

  • Wechler W (1978) The concept of fuzziness in automata and language theory. Addison-Wesley, Reading

    Google Scholar 

  • Yager RR (1994) Aggregation operators and fuzzy systems modeling. Fuzzy Sets Systems 67:C129–C145

    Google Scholar 

  • Ying MS (2002) A formal model of computing with words. IEEE Trans Fuzzy Syst 10(5):640–652

    Google Scholar 

Download references

Acknowledgements

The authors would like to thank the anonymous referees for their careful reading of this paper and for a number of valuable comments which improved the quality of this paper. This work is supported by National Science Foundation of China (Grant No. 60174016, 10226023), “TRAPOYT” of China and 973 Program of China No. 2002CB312200.

Author information

Authors and Affiliations

  1. Institute of Fuzzy Systems, College of Mathematics and Information Science, Shaanxi Normal University, Xi’an, 710062, China

    Li Sheng & Yongming Li

Authors
  1. Li Sheng
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Yongming Li
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Li Sheng.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Sheng, L., Li, Y. Regular grammars with truth values in lattice-ordered monoid and their languages. Soft Comput 10, 79–86 (2006). https://doi.org/10.1007/s00500-004-0427-y

Download citation

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00500-004-0427-y

Keywords

Search

Navigation