Elsevier

Information Sciences

Volume 178, Issue 1, 2 January 2008, Pages 164-180
Information Sciences

Determinization of fuzzy automata with membership values in complete residuated lattices

https://doi.org/10.1016/j.ins.2007.08.003Get rights and content

Abstract

In this paper we introduce 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 [R. Bělohlávek, Determinism and fuzzy automata, Information Sciences 143 (2002), 205–209] and Li and Pedrycz [Y.M. Li, W. Pedrycz, Fuzzy finite automata and fuzzy regular expressions with membership values in lattice ordered monoids, Fuzzy Sets and Systems 156 (2005), 68–92], 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 also show that determinization of fuzzy automata is closely related to fuzzy right congruences on a free monoid and fuzzy automata associated with them, and in particular, to the concept of the Nerode’s fuzzy right congruence of a fuzzy automaton, which we introduce and study here.

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 L, and proved that any fuzzy language recognized by a fuzzy finite recognizer over L can be recognized by some deterministic fuzzy finite recognizer if and only if the semiring reduct of L (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 L, gives necessarily a fuzzy finite recognizer if and only if the semiring reduct L of L 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 L of L is not locally finite, for example, if L is the product structure, then there are initial fuzzy finite automata over L 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 A is a deterministic automaton isomorphic to the automaton obtained by determinization of A by means of the accessible fuzzy subset construction. We also determine certain conditions on a fuzzy automaton A 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 L 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 L is a residuated lattice, so we have assumed that L 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 L=(L,,,,,0,1) 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,xyzxyz.

If, in addition, (L, , , 0, 1) is a complete lattice, then L is called a complete residuated lattice. The operations ⊗

Fuzzy automata

By a fuzzy automaton over L, or simply a fuzzy automaton, a triple A=(A,X,δ) 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 A=(A,σ,X,δ,τ) be a fuzzy recognizer. By analogy with non-deterministic automata, we can make a deterministic fuzzy recognizer AF=(F(A),σ,X,δF,τF), where δF:F(A)×XF(A) and τF:F(A)L are defined by(δF(μ,x))(a)=bAμ(b)δ(b,x,a),τF(μ)=bAμ(b)τ(b),for any μF(A), a  A and x  X, or equivalently,δF(μ,x)=μδx,τF(μ)=μτ.It can be easily verified that L(A)=L(AF). However, this construction has an obvious shortage: in overwhelming majority of cases, the structure L 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 Aπ=(Aπ,X,δπ), where Aπ = X/π and a transition function δπ: Aπ × X  Aπ is defined byδπ(πu,x)=πux,for 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 δπ:Aπ×XAπ 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 A? We know that a crisp relation η on X can be assigned to a crisp initial deterministic automaton A=(A,a0,X,δ) in the following way: for any u, v  X,(u,v)ηδ(a0,u)=δ(a0,v).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)

  • D.S. Malik et al.

    On fuzzy regular languages

    Information Sciences

    (1996)
  • T. Petković

    Congruences and homomorphisms of fuzzy automata

    Fuzzy Sets and Systems

    (2006)
  • D.W. Qiu

    Characterizations of fuzzy finite automata

    Fuzzy Sets and Systems

    (2004)
  • D.W. Qiu

    Pumping lemma in automata theory based on complete residuated lattice-valued logic: A note

    Fuzzy Sets and Systems

    (2006)
  • D.W. Qiu

    A note on Trillas CHC models

    Artificial Intelligence

    (2007)
  • J. Shen

    Fuzzy language on free monoid

    Information Sciences

    (1996)
  • L. Valverde

    On the structure of F-indistinguishability operators

    Fuzzy Sets and Systems

    (1985)
  • H.G. Xing et al.

    Equivalence in automata theory based on complete residuated lattice-valued logic

    Fuzzy Sets and Systems

    (2007)
  • R. Bělohlávek

    Fuzzy Relational Systems: Foundations and Principles

    (2002)
  • Cited by (102)

    • Minimization of hesitant L-fuzzy automaton

      2024, Fuzzy Sets and Systems
    • L-fuzzy automata theory: Some characterizations via general fuzzy operators

      2023, Fuzzy Sets and Systems
      Citation 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]).

    View all citing articles on Scopus

    Research supported by Ministry of Science, Republic of Serbia, Grant No. 144011.

    View full text