Minimization of lattice multiset finite automata

Article type: Research Article

Authors: Wang, Yongbing^{a; b; *} | Li, Yongming^b

Affiliations: [a] College of Mathematics and Computation, Anqing Normal University, Anqing, China | [b] College of Computer Science, Shaanxi Normal University, Xi’an, China

Correspondence: [*] Corresponding author. Yongbing Wang. E-mail: wangyongb@snnu.edu.cn, liyongm@snnu.edu.cn.

Abstract: 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.

Keywords: Lattice-valued multiset finite automata, lattice-valued regular multiset languages, deterministic lattice-valued multiset finite automata, minimization, lattice-valued unitary language

DOI: 10.3233/JIFS-161382

Journal: Journal of Intelligent & Fuzzy Systems, vol. 35, no. 1, pp. 627-637, 2018