DFA Minimization of Fuzzy Multiset Automata

Authors

DOI:

https://doi.org/10.63924/jau.v2i1.363

Keywords:

DFA Minimization, Fuzzy Multiset Finite Automata, Fuzzy Multiset Language, Reverse Fuzzy Multiset Finite Automata, Crisp-Deterministic Fuzzy Multiset Automata, Brzozoswki,s Algorithm

Abstract

Deterministic finite automaton (DFA) minimization is the process of converting a DFA into an equivalent DFA with a minimum number of states. Here we apply on such process (i.e., Brzozowski’s algorithm) to crisp deterministic fuzzy multiset finite automata. We introduce reverse fuzzy multiset finite automata and establish a relation between their right and left fuzzy multiset languages. In between, we correlate two crisp-deterministic fuzzy multiset finite automata and show that the reachability and observability map of the given crisp deterministic fuzzy multiset finite automata to be isomorphic.

Author Biography

Binod Kumar Sharma, Birla Institute of Technology

Associate Professor Department of Computer Science and Engineering

References

R. Bělohlávek. “Determinism and fuzzy automata”. In: Information Sciences 143 (2002), pp. 205–209.

W.D. Blizard. “Multiset Theory”. In: Notre Dame Journal of Formal Logic 30 (1989), pp. 36–66.

J. A. Brzozowski. “Canonical regular expression and minimal state graphs for definite events”. In: Mathematical Theory of automata, MRI Symposia Series, Polytechnic Institute of Brooklyn, NY 12 (1962), pp. 529–561.

V. Cerf, E. Fernández, K. Gostelow, and S. Volansky. Formal Control-Flow Properties of a Model of Computation. Tech. rep. Report ENG. 7178. Los Angeles: Department of Computer Science, University of California, 1971.

G. Ciobanu and M. Gontineac. “Mealy Multiset Automata”. In: International Journal of Foundations of Computer Science 17 (2006), pp. 111–126.

E. Csuhaj-Varjú, C. Martín-Vide, and V. Mitrana. “Multiset Automata”. In: Multiset processing-mathematical, computer science and molecular computing points of view. Ed. by Calude C.S., G. Păun, G. Rozenberg, and A. Salomaa. Berlin: Springer, 2001, pp. 69–83.

J. E. Hopcroft, R. Motwani, and J. D. Ullman. Introduction to Automata Theory, Languages, and Computation. 3rd. London: Pearson Education Ltd, 2014.

J. Ignjatović, M. Ćirić, and S. Bogdanović. “Determinization of fuzzy automata with membership values in complete residuated lattices”. In: Information Sciences 178 (2008), pp. 164–180.

Z. Jančić and M. Ćirić. “Brzozowski type determinization for fuzzy automata”. In: Fuzzy Sets and Systems 249 (2014), pp. 73–82.

M. Kudlek, C. Martín-Vide, and G. Păun. “Toward a formal macroset theory”. In: Multiset processing-mathematical, computer science and molecular computing points of view. Ed. by Calude C. S., G. Păun, G. Rozenberg, and A. Salomaa. Berlin: Springer, 2001, pp. 123–133.

Y. Li. “Approximation and robustness of fuzzy finite automata”. In: International Journal of Approximate Reasoning 47.2 (2008), pp. 247–257.

Y. Li and W. Pedrycz. “Minimization of lattice finite automata and its application to the decomposition of lattice languages”. In: Fuzzy Sets and Systems 158 (2007), pp. 1423–1436.

Z. Lia, P. Lia, and Y. Li. “The relationships among several types of fuzzy automata”. In: Information Sciences 176.15 (2006), pp. 2208–2226.

W. Lihua and D. Qiu. “Automata theory based on complete residuated lattice-valued logic: Reduction and minimization”. In: Fuzzy Sets and Systems 161 (2010), pp. 1635–1656.

D. S. Malik and J. N. Mordeson. “On fuzzy regular languages”. In: Information Science 88 (1996), pp. 263–273.

D. S. Malik and J. N. Mordeson. Fuzzy discrete structures. New York: Physica Verlag, 2000.

D. S. Malik, J. N. Mordeson, and M. K. Sen. “Submachines of fuzzy finite state machine”. In: Journal of Fuzzy Mathematics 2 (1994), pp. 781–792.

J. N. Mordeson and D. S. Malik. Fuzzy automata and languages, theory and applications. London: Champan and Hall/CRC, 2002.

Tiwari S. P., V. Gautam, and M. K. Dubey. “On fuzzy multiset automata”. In: Journal of Applied Mathematics and Computing 51 (2016), pp. 643–657.

J. Peterson. “Computation sequence sets”. In: Journal of Computer System Science 13 (1976), pp. 1–24.

D. W. Qiu. “Supervisory control of fuzzy discrete event systems: a formal approach”. In: Transactions on Systems, Man, and Cybernetics: Part B (Cybernetics) 35.1 (2005), pp. 72–88.

A. Salomaa. Theory of Automata. Oxford: Pergamon Press, 1969.

E. S. Santos. “Maximin automata”. In: Information and Control 13.4 (1968), pp. 363–377.

A. Syropoulos. “Mathematics of Multisets”. In: Multiset Processing. Ed. by Cristian S. Calude, Gheorghe Păun, Grzegorz Rozenberg, and Arto Salomaa. Lecture Notes in Computer Science 2235. Berlin: Springer-Verlag, 2001, pp. 347–358.

J. Wang, M. Yin, and W. Gu. “Fuzzy multiset finite automata and their languages”. In: Soft Computing 17 (2013), pp. 381–390.

W. G. Wee. “On generalizations of adaptive algorithm and application of the fuzzy sets concepts to pattern classification”. PhD thesis. Purdue University, 1967.

W. G. Wee and K. S. Fu. “A formulation of fuzzy automata and its application as a model of learning systems”. In: Systems Science and Cybernetics, IEEE Transactions 5 (1969), pp. 215–223.

R. R. Yager. “On the theory of bags”. In: International Journal of General Systems 13 (1986), pp. 23–37.

S. Yu. “Regular Languages”. In: Handbook of Formal Languages. Ed. By Grzegorz Rozenberg and Arto Salomaa. Berlin: Springer, 1997, pp. 41–110.

L.A. Zadeh. “Fuzzy Sets”. In: Information and Control 8 (1965), pp. 338–353.

2

Downloads

Published

2026-11-17

How to Cite

Sharma, B. K., & Syropoulos, A. (2026). DFA Minimization of Fuzzy Multiset Automata. Journal of Analytical Uncertainty, 2(1), 90–98. https://doi.org/10.63924/jau.v2i1.363

Most read articles by the same author(s)