Determinization of fuzzy automata with membership values in complete residuated lattices☆
Introduction
The concept of a fuzzy automaton is a natural generalization of the concept of a non-deterministic automaton, as the concepts of a fuzzy set and a fuzzy relation are generalizations of the classical concepts of a set and a relation. Relationships between fuzzy, non-deterministic and deterministic automata have been studied by Močkoř [23], Bělohlávek [2] and Li and Pedrycz [18]. Močkoř in [23] represented fuzzy automata as nested systems of non-deterministic automata, and by Bělohlávek in [2], deterministic automata with fuzzy sets of final states, called here deterministic fuzzy recognizers, were represented as nested systems of deterministic automata. Moreover, Bělohlávek studied fuzzy automata over a locally finite complete lattice, and he proved that any fuzzy language recognized by a fuzzy finite recognizer can be also recognized by a deterministic fuzzy finite recognizer. A more general result was given by Li and Pedrycz in [18], who studied fuzzy automata with membership values in a lattice ordered monoid , and proved that any fuzzy language recognized by a fuzzy finite recognizer over can be recognized by some deterministic fuzzy finite recognizer if and only if the semiring reduct of (with respect to the supremum and multiplication operations) is locally finite.
The method for determinization of fuzzy automata used by Bělohlávek in [2], and Li and Pedrycz in [18], is analogous to the well-known subset construction, used in determinization of crisp non-deterministic automata (cf. [13]), and it is called here the fuzzy subset construction. That construction has the same shortcoming as its crisp counterpart: some states of the resulting deterministic fuzzy recognizer can be needless. For that reason, here we study another construction, called the accessible fuzzy subset construction, which is an analogue of the well-known accessible subset construction, used in determinization of non-deterministic automata. Following the methodology by Li and Pedrycz, we show that our method of determinization, applied to an initial fuzzy finite automaton over a complete residuated lattice , gives necessarily a fuzzy finite recognizer if and only if the semiring reduct of is locally finite. In this case we give a determinization algorithm which always results in a smaller automaton than the fuzzy subset construction. Complete Heyting algebras, Łukasiewicz and Gödel structures are some of the most important examples of complete residuated lattices having locally finite semiring reducts. If the semiring reduct of is not locally finite, for example, if is the product structure, then there are initial fuzzy finite automata over whose determinization by means of the accessible fuzzy subset construction results in an infinite deterministic fuzzy recognizer. However, we show that even in this case, and even if the fuzzy subset construction gives an infinite automaton, our method can give a finite one. It is worth noting that determinization of fuzzy automata was also studied by Li and Pedrycz in [20], whereas Li in [17] considered the problem of approximation of a non-deterministic fuzzy finite automaton by a deterministic one.
By a classical result of the theory of automata, any accessible automaton can be constructed starting from a right congruence on its input monoid. The mentioned right congruence is known as the Nerode’s right congruence of this automaton. Motivated by this fact, here we also study fuzzy right congruences on a free monoid and fuzzy automata associated with them, called fuzzy right congruence automata, as well as fuzzy right congruences on a free monoid assigned to initial fuzzy automata, called their Nerode’s fuzzy relations. In particular, we prove that the crisp part of the fuzzy automaton assigned to the Nerode’s fuzzy relation of an initial fuzzy automaton is a deterministic automaton isomorphic to the automaton obtained by determinization of by means of the accessible fuzzy subset construction. We also determine certain conditions on a fuzzy automaton under which its Nerode’s fuzzy right congruence has a finite index, and hence, under which its determinization by means of the accessible fuzzy subset construction gives a finite automaton.
Let us note that all results presented in Sections 3 Fuzzy automata, 4 Determinization algorithms, 5 Fuzzy right congruence automata can be proved in a more general setting, where is a lattice ordered monoid (see [18], for its definition). However, to define the Nerode’s fuzzy relation and to state the results concerning it, presented in Section 6, it is necessary that is a residuated lattice, so we have assumed that is a complete residuated lattice throughout the entire paper. It is worth of mention that automata theory based on residuated lattice-valued logic was initiated by Qiu [28], [29], [32], and automata theory based on lattice ordered monoids was initiated by Li and Pedrycz [18]. Both fuzzy automata with membership values in a complete residuated lattice, and those with membership values in a lattice ordered monoid, have recently attracted a considerable attention of researchers working in the fuzzy automata theory (cf. [5], [12], [14], [15], [16], [17], [18], [19], [20], [21], [28], [29], [30], [32], [35], [38]). Notably, fuzzy automata have been used to deal with fuzzy discrete event systems [22], [31] and computing with words [37].
Remark also that fuzzy automata have been already studied in [3], [24], [25], [27], [34] through certain crisp relations on a free monoid, but never through fuzzy relations. Here, as well as in [5], [12], we show that fuzzy relations can be very useful in study of fuzzy automata.
Section snippets
Preliminaries
In this paper we will use complete residuated lattices as the structures of truth values. A residuated lattice is an algebra such that
- (L1)
(L, , , 0, 1) is a lattice with the least element 0 and the greatest element 1,
- (L2)
(L, ⊗, 1) is a commutative monoid with the unit 1,
- (L3)
⊗ and → form an adjoint pair, i.e., they satisfy the adjunction property: for all x, y, z ∈ L,
If, in addition, (L, , , 0, 1) is a complete lattice, then is called a complete residuated lattice. The operations ⊗
Fuzzy automata
By a fuzzy automaton over , or simply a fuzzy automaton, a triple is meant, where A and X are sets, called, respectively, a set of states and an input alphabet, and δ:A × X × A → L is a fuzzy subset of A × X × A, called a fuzzy transition function. We can interpret δ(a, x, b) as the degree to which an input letter x ∈ X causes a transition from a state a ∈ A into a state b ∈ A. The input alphabet X will be always finite, but from methodological reasons we will allow the set of states A to be infinite.
Determinization algorithms
Let be a fuzzy recognizer. By analogy with non-deterministic automata, we can make a deterministic fuzzy recognizer , where and are defined byfor any , a ∈ A and x ∈ X, or equivalently,It can be easily verified that . However, this construction has an obvious shortage: in overwhelming majority of cases, the structure of truth values is infinite, and
Fuzzy right congruence automata
Let S be a semigroup. An equivalence relation π on S is called a right congruence if for all a, b, c ∈ S we have that (a, b) ∈ π implies (ac, bc) ∈ π. To any crisp right congruence π on a free monoid X∗ we can associate a crisp deterministic automaton , where Aπ = X∗/π and a transition function δπ: Aπ × X → Aπ is defined byfor all u ∈ X∗ and x ∈ X (cf. [6], [39]), where πu denotes the equivalence class determined by u. We also know that δπ can be extended up to a mapping so
Nerode’s fuzzy relation
In the previous section we showed how to construct a fuzzy automaton starting from a given fuzzy right congruence on the free monoid X∗. We can also consider the opposite problem: How to assign, in a natural way, a fuzzy right congruence on X∗ to a given fuzzy automaton ? We know that a crisp relation η on X∗ can be assigned to a crisp initial deterministic automaton in the following way: for any u, v ∈ X∗,The relation η is a right congruence on X∗, and we
Concluding remarks
In this paper we have introduced a new method for determinization of fuzzy finite automata with membership values in complete residuated lattices. In comparison with the previous methods, developed by Bělohlávek [2] and Li and Pedrycz [18], [20], our method always gives a smaller automaton, and in some cases, when the previous methods result in infinite automata, our method can result in a finite one.
We have connected the determinization of fuzzy finite automata with the concept of a fuzzy
Acknowledgement
The authors are very grateful to the referees for valuable remarks which helped to improve quality of the paper.
References (39)
Determinism and fuzzy automata
Information Sciences
(2002)- et al.
On the recognizability of fuzzy languages I
Fuzzy Sets and Systems
(2006) - et al.
Fuzzy equivalence relations and their equivalence classes
Fuzzy Sets and Systems
(2007) - et al.
Weighted automata and weighted logics
Theoretical Computer Science
(2007) - et al.
Minimization of states in automata theory based on finite lattice-ordered monoids
Information Sciences
(2007) - et al.
Algebraic properties of LA-languages
Information Sciences
(2006) A categorical approach to lattice-valued fuzzy automata
Fuzzy Sets and Systems
(2006)- et al.
Fuzzy finite automata and fuzzy regular expressions with membership values in lattice ordered monoids
Fuzzy Sets and Systems
(2005) - et al.
Minimization of lattice finite automata and its application to the decomposition of lattice languages
Fuzzy Sets and Systems
(2007) - et al.
The relationships among several types of fuzzy automata
Information Sciences
(2006)
On fuzzy regular languages
Information Sciences
Congruences and homomorphisms of fuzzy automata
Fuzzy Sets and Systems
Characterizations of fuzzy finite automata
Fuzzy Sets and Systems
Pumping lemma in automata theory based on complete residuated lattice-valued logic: A note
Fuzzy Sets and Systems
A note on Trillas CHC models
Artificial Intelligence
Fuzzy language on free monoid
Information Sciences
On the structure of F-indistinguishability operators
Fuzzy Sets and Systems
Equivalence in automata theory based on complete residuated lattice-valued logic
Fuzzy Sets and Systems
Fuzzy Relational Systems: Foundations and Principles
Cited by (102)
Minimization of hesitant L-fuzzy automaton
2024, Fuzzy Sets and SystemsOn compositions of (L-fuzzy) automata: A categorical approach
2024, Fuzzy Sets and SystemsOn L-fuzzy automata, coalgebras and dialgebras: Associated categories and L-fuzzy topologies
2023, Fuzzy Sets and SystemsL-fuzzy automata theory: Some characterizations via general fuzzy operators
2023, Fuzzy Sets and SystemsCitation Excerpt :These studies were initiated by Santos [41], Wee [54], and Wee and Fu [55], and further developed by many researchers (cf., [18,26]). Fuzzy automata and languages with membership values in different lattice structures have attracted considerable attention from researchers working in this area (cf., [2–4,8,14–18,21,27,28,30–33,35,36,44,45,47,49,51,53,56–59]). Among these works, Qiu [30,31] first established a fundamental framework of the fuzzy automata and languages with membership values in a complete residuated lattice, which was further developed by Qiu and his co-authors (cf., [32,33,35,36,56–59]); the work of Jin and his co-authors [17] is towards the algebraic study of fuzzy automata based on po-monoids; the work of Kim, Kim and Cho [18] is towards the algebraic study of generalized fuzzy automata based on t-norms; the work of Horry and Zahedi [14] is towards the use fuzzy topologies for the study of a max-min general fuzzy automaton; the work of Das [8] is towards the fuzzy topological characterization of a fuzzy automaton; the work of Li and Pedrycz [21] is towards the fuzzy automata based on lattice-ordered monoids; the work of Ćirić and his co-authors is towards the study of determinism in fuzzy automata theory based on residuated lattices (cf., [15,16]), and the work of Tiwari and his co-authors is towards the algebraic and topological study of fuzzy automata (cf., [45,47,49,51,53]).
On the category of L-fuzzy automata, coalgebras and dialgebras
2021, Fuzzy Sets and SystemsOn a factorized L-fuzzy automaton and its L-fuzzy topological characterization
2021, Fuzzy Sets and Systems
- ☆
Research supported by Ministry of Science, Republic of Serbia, Grant No. 144011.