Finite Nerode Construction for Fuzzy Automata over the Product Algebra | SpringerLink
Skip to main content
Springer Nature Link
Log in

Finite Nerode Construction for Fuzzy Automata over the Product Algebra

  • Conference paper
  • First Online:
Fuzzy Logic and Technology, and Aggregation Operators (EUSFLAT 2023, AGOP 2023)

Part of the book series: Lecture Notes in Computer Science ((LNCS,volume 14069))

  • 543 Accesses

Abstract

The Nerode’s automaton of a given fuzzy automaton \(\mathcal {A}\) is a crisp-deterministic fuzzy automaton obtained by determinization of \(\mathcal {A}\) using the well-known accessible fuzzy subset construction. This celebrated construction of a crisp-deterministic fuzzy automaton has served as a basis for various determinization procedures for fuzzy automata. However, the drawback of this construction is that it may not be feasible when the underlying structure for fuzzy automata is the product algebra because it is not locally finite. This paper provides an alternative way to construct a Nerode-like fuzzy automaton when the input fuzzy automaton is defined over the product algebra. This construction is always finite, since the fuzzy language recognized by this fuzzy automaton has a finite domain. However, this new construction does not accept the same fuzzy language as the initial fuzzy automaton. Nonetheless, it differs only in words accepted to some very small degree, which we treat as irrelevant. Therefore, our construction is an excellent finite approximation of Nerode’s automaton.

Z. Jančić, I. Micić, S. Stanimirović and M. Ćirić acknowledge the support of the Science Fund of the Republic of Serbia, GRANT No. 7750185, Quantitative Automata Models: Fundamental Problems and Applications - QUAM, and of the Ministry of Education, Science and Technological Development, Republic of Serbia, Contract No. 451-03-68/2022-14/200124.

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

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
JPY 3498
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
JPY 11210
Price includes VAT (Japan)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
JPY 14013
Price includes VAT (Japan)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Similar content being viewed by others

References

  1. Bělohlávek, R.: Determinism and fuzzy automata. Inf. Sci. 143, 205–209 (2002)

    Article  MathSciNet  MATH  Google Scholar 

  2. de Mendívil, J.R.G.: Conditions for minimal fuzzy deterministic finite automata via Brzozowski’s procedure. IEEE Trans. Fuzzy Syst. 26(4), 2409–2420 (2018)

    Article  Google Scholar 

  3. de Mendívil, J.R.G., Figueredo, F.F.: Canonization of max-min fuzzy automata. Fuzzy Sets Syst. 376, 152–168 (2019)

    Article  MathSciNet  MATH  Google Scholar 

  4. de Mendívil, J.R.G., Garitagoitia, J.R.: Determinization of fuzzy automata via factorization of fuzzy states. Inf. Sci. 283, 165–179 (2014)

    Article  MathSciNet  MATH  Google Scholar 

  5. Ignjatović, J., Ćirić, M., Bogdanović, S.: Determinization of fuzzy automata with membership values in complete residuated lattices. Inf. Sci. 178, 164–180 (2008)

    Article  MathSciNet  MATH  Google Scholar 

  6. Ignjatović, J., Ćirić, M., Bogdanović, S., Petković, T.: Myhill-Nerode type theory for fuzzy languages and automata. Fuzzy Sets Syst. 161(9), 1288–1324 (2010)

    Article  MathSciNet  MATH  Google Scholar 

  7. Jančić, Z., Ćirić, M.: Brzozowski type determinization for fuzzy automata. Fuzzy Sets Syst. 249, 73–82 (2014)

    Article  MathSciNet  MATH  Google Scholar 

  8. Jančić, Z., Ignjatović, J., Ćirić, M.: An improved algorithm for determinization of weighted and fuzzy automata. Inf. Sci. 181, 1358–1368 (2011)

    Article  MathSciNet  MATH  Google Scholar 

  9. Jančić, Z., Micić, I., Ignjatović, J., Ćirić, M.: Further improvement of determinization methods for fuzzy finite automata. Fuzzy Sets Syst. 301, 79–102 (2015)

    Article  MathSciNet  MATH  Google Scholar 

  10. Li, Y.: Approximation and robustness of fuzzy finite automata. Int. J. Approximate Reasoning 47(2), 247–257 (2008)

    Article  MathSciNet  MATH  Google Scholar 

  11. Li, Y., Pedrycz, W.: Fuzzy finite automata and fuzzy regular expressions with membership values in lattice-ordered monoids. Fuzzy Sets Syst. 156(1), 68–92 (2005)

    Article  MathSciNet  MATH  Google Scholar 

  12. Micić, I., Jančić, Z., Ignjatović, J., Ćirić, M.: Determinization of fuzzy automata by means of the degrees of language inclusion. IEEE Trans. Fuzzy Syst. 23(6), 2144–2153 (2015)

    Article  Google Scholar 

  13. Mordeson, J.N., Malik, D.S.: Fuzzy Automata and Languages. Chapman and Hall/CRC (2002)

    Google Scholar 

  14. Qiu, D.W.: Automata theory based on completed residuated lattice-valued logic (I). Sci. China Ser. F 44(6), 419–429 (2001). https://doi.org/10.1007/BF02713945

    Article  MathSciNet  MATH  Google Scholar 

  15. Qiu, D.W.: Automata theory based on completed residuated lattice-valued logic (II). Sci. China Ser. F 45(6), 442–452 (2002). https://doi.org/10.1360/02yf9038

    Article  MathSciNet  MATH  Google Scholar 

  16. Stanimirović, S., Ćirić, M., Ignjatović, J.: Determinization of fuzzy automata by factorizations of fuzzy states and right invariant fuzzy quasi-orders. Inf. Sci. 469, 79–100 (2018)

    Article  MathSciNet  MATH  Google Scholar 

  17. Yang, C., Li, Y.: Fuzzy \(\varepsilon \)-approximate regular languages and minimal deterministic fuzzy automata \(\varepsilon \)-accepting them. Fuzzy Sets Syst. 420, 72–86 (2021)

    Article  MathSciNet  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Faculty of Science and Mathematics, University of Niš, Niš, Serbia

    Zorana Jančić, Ivana Micić, Stefan Stanimirović & Miroslav Ćirić

  2. Departamento de Estadística, Informática y Matemáticas, Universidad Pública de Navarra, 31006, Pamplona, Spain

    Jose Ramón Gonzalez de Mendívil

Authors
  1. Zorana Jančić
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Ivana Micić
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Stefan Stanimirović
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Jose Ramón Gonzalez de Mendívil
    View author publications

    You can also search for this author in PubMed Google Scholar

  5. Miroslav Ćirić
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Zorana Jančić .

Editor information

Editors and Affiliations

  1. University of the Balearic Islands, Palma, Spain

    Sebastia Massanet

  2. University of Oviedo, Gijón, Spain

    Susana Montes

  3. University of the Balearic Islands, Palma, Spain

    Daniel Ruiz-Aguilera

  4. University of the Balearic Islands, Palma, Spain

    Manuel González-Hidalgo

Rights and permissions

Reprints and permissions

Copyright information

© 2023 The Author(s), under exclusive license to Springer Nature Switzerland AG

About this paper

Check for updates. Verify currency and authenticity via CrossMark

Cite this paper

Jančić, Z., Micić, I., Stanimirović, S., Gonzalez de Mendívil, J.R., Ćirić, M. (2023). Finite Nerode Construction for Fuzzy Automata over the Product Algebra. In: Massanet, S., Montes, S., Ruiz-Aguilera, D., González-Hidalgo, M. (eds) Fuzzy Logic and Technology, and Aggregation Operators. EUSFLAT AGOP 2023 2023. Lecture Notes in Computer Science, vol 14069. Springer, Cham. https://doi.org/10.1007/978-3-031-39965-7_46

Download citation

  • DOI: https://doi.org/10.1007/978-3-031-39965-7_46

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-031-39964-0

  • Online ISBN: 978-3-031-39965-7

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation