In this paper, we study the minimization of lattice-valued multiset finite automata with membership values in a distributive lattice. First, we establish the equivalence of (nondeterministic) lattice multiset finite automata (LMA) and deterministic lattice multiset finite automata (DLMA). Furthermore, we present some operations on lattice-valued regular multiset languages, and prove that the family of lattice-valued regular multiset languages is closed under this operations. We also introduce and study the minimal DLMAs and present an effective algorithm to obtain a minimal DLMA for a given LMA. Finally, we give a decomposition of lattice-valued regular multiset language by some simple lattice-valued regular multiset languages accepted by some special minimal DLMAs.
Csuhaj-VarjúE., Martín-VideC. and MitranaV., Multiset automataCaludeC.S., ăunG., RozenbergG. and SalomaaA.(eds.), Multiset Processing-Mathematical. Computer Science and Molecular Computing Points of ViewSpringer, Berlin (2001) pp. 69–83.
3.
CiobanuG., Mealy multiset automata, International Journal of Foundations of Computer Science17 (2006), 111–126.
4.
ChiswellI., A Course in Formal Languages, Automata and Groups, Springer-Verlag London Limited, 2009.
5.
CavaliereM., FreundR., OswaldM. and SburlanD., Multiset random context grammars, checkers, and transducers, Theoretical Computer Science372 (2007), 136–151.
6.
Crespi-ReghizziS. and MandrioliD., Commutative grammars, Calcolo13(2) (1976), 173–189.
7.
GräzerG., General Lattice Theory, Academic Press, New York. San Franciso. 1978.
8.
IgnjatovićJ., ĆirićM. and BogdanovićS., Determinization of fuzzy automata with membership values in complete residuated lattices, Information Sciences178 (2008), 164–180.
9.
IgnjatovićJ., ĆirićM., BogdanovićS. and PetkovićT., Myhill-Nerode type theory for fuzzy languages and automata, Fuzzy Sets and Systems161 (2010), 1288–1324.
10.
JancićZ. and ĆirićM., Brzozowski type determinization for fuzzy automata, Fuzzy Sets and Systems249 (2014), 73–82.
LeeE.T. and ZadehL.A., Note on fuzzy languages, Information Sciences1 (1969), 421–434.
13.
LinF. and YingH., Modeling and control of fuzzy discrete event systems, IEEE Transactions on Systems Man and Cybernetics Part B: Cybernet32(4) (2002), 408–415.
14.
LiY.M. and PedryczW., Fuzzy finite automata and fuzzy regular expressions with membership values in lattice-ordered monoids, Fuzzy Sets and Systems156 (2005), 68–92.
15.
LiY.M. and PedryczW., Minimization of lattice finite automata and its application to the decomposition of lattice languages, Fuzzy Sets and Systems158 (2007), 1423–1436.
16.
LiY.M. and WangQ., The universal fuzzy automaton, Fuzzy Sets and Systems249 (2014), 27–48.
17.
KandelA. and LeeS.C., Fuzzy Switching and Automata: Theory and Applications, Crane Russak, New York. 1980.
18.
KudlekM. and MitranaV., Closure properties of multiset language families, Fundamenta Informaticae49 (2002), 191–203.
19.
KudlekM., TotzkeP. and ZetzscheG., Properties of multiset language classes defined by multiset pushdown automata, Fundamenta Informaticae93 (2009), 235–244.
20.
MordesonJ.N. and MalikD.S., Fuzzy Automata and Languages: Theory and Applications, Boca Raton. London: Chapman & Hall/CRC. 2002.
21.
McgregorS., Further results in multiset processing with neural networks, Neural Networks21 (2008), 830–837.
22.
MalikD.S. and MordesonJ.N., Fuzzy Discrete Structures, Physica-Verlag. New York. 2000.
23.
PedryczW. and GracekA., Learning of fuzzy automata, International Journal of Computational Intelligence and Applications1 (2001), 19–33.
24.
QiuD.W., Pumping lemma in automata theory based on complete residuated lattice-value logic: A note, Fuzzy Sets and Systems157 (2006), 2128–2138.
25.
Blanchet-SadriF. and MorganC., Multiset and set decipherable codes, Computers and Mathematics with Applications41 (2001), 1257–1262.
26.
SantosE.S., Maximin automata, Information and Control12 (1968), 367–377.
27.
SantosE.S., On reduction of max-min machines, Journal of Mathematical Analysis and Applications37 (1972), 677–686.
28.
TiwariS.P., GautamV. and DubeyM.K., On fuzzy multiset automata, Journal of Applied Mathematics and Computing8 (2015), 1–15.
29.
TaulerR., MaederM. and JuanA., Multiset data analysis: Extended multivariate curve resolution, in: BrownS.D.. TaulerR. and WalczakB.(eds.) Comprehensive Chemometrics: Chemical and Biochemical Data Analysis. Elsevier. Oxford. 2009, pp. 473–505.
30.
WangJ., YinM. and GuW., Fuzzy multiset finte automata and their languages, Soft Computing17 (2013), 381–390.
31.
WeeW.G., On generalizations of adaptive algorithm and application of the fuzzy sets concept to pattern classification., Ph.D. Thesis, Purdue University1967.
32.
YingM.S., A formal model of computing with words, IEEE Transactions on Fuzzy Systems10(5) (2002), 640–652.
