PaperlayerView exact revision on arXiv

Source-linked AI summary

Bisimulations for fuzzy automata

Miroslav Ćirić, Jelena Ignjatović, Nada Damljanović, Milan Bašić

arXiv:1102.5452v2cs.FLcs.AI

TL;DR

The paper addresses how to model equivalence between fuzzy automata when relations between different state sets are involved. It combines uniform fuzzy relations with bisimulations and characterizes when they are forward bisimulations. This yields a factor-automaton isomorphism test for UFB-equivalence, while backward-forward bisimulations do not define an equivalence between automata.

  • Problem

    Bisimulations between distinct systems have been less studied, with arbitrary relations too general and functions too restrictive, motivating a suitable relation concept for equivalence between fuzzy automata.

    Source: §1 · p. 2

  • Method

    The paper combines uniform fuzzy relations, which relate elements of different sets, with bisimulations, which enforce compatibility with fuzzy automaton structure.

    Source: §1 · p. 3

  • Results

    UFB-equivalence holds exactly when the factor automata for the greatest forward-bisimulation fuzzy equivalences have a special isomorphism, reducing its test to an isomorphism test closely related to graph isomorphism.

    Source: §1 · p. 3

  • Takeaways & Limitations

    Testing UFB-equivalence can proceed through greatest forward-bisimulation fuzzy equivalences, factor automata, and a suitably constrained isomorphism check.

    Source: §1 · p. 3, §7 · p. 27

    Backward-forward bisimulations cannot define equivalence between automata because they do not provide symmetry.

    Source: §8 · p. 30

Abstract

from arXiv · show

Bisimulations have been widely used in many areas of computer science to model equivalence between various systems, and to reduce the number of states of these systems, whereas uniform fuzzy relations have recently been introduced as a means to model the fuzzy equivalence between elements of two possible different sets. Here we use the conjunction of these two concepts as a powerful tool in the study of equivalence between fuzzy automata. We prove that a uniform fuzzy relation between fuzzy automata $\cal A$ and $\cal B$ is a forward bisimulation if and only if its kernel and co-kernel are forward bisimulation fuzzy equivalences on $\cal A$ and $\cal B$ and there is a special isomorphism between factor fuzzy automata with respect to these fuzzy equivalences. As a consequence we get that fuzzy automata $\cal A$ and $\cal B$ are UFB-equivalent, i.e., there is a uniform forward bisimulation between them, if and only if there is a special isomorphism between the factor fuzzy automata of $\cal A$ and $\cal B$ with respect to their greatest forward bisimulation fuzzy equivalences. This result reduces the problem of testing UFB-equivalence to the problem of testing isomorphism of fuzzy automata, which is closely related to the well-known graph isomorphism problem. We prove some similar results for backward-forward bisimulations, and we point to fundamental differences. Because of the duality with the studied concepts, backward and forward-backward bisimulations are not considered separately. Finally, we give a comprehensive overview of various concepts on deterministic, nondeterministic, fuzzy, and weighted automata, which are related to bisimulations.

1. Introduction

The introduction motivates combining uniform fuzzy relations with bisimulations to study equivalence between fuzzy automata. It previews characterizations of uniform bisimulations, a factor-automaton test for UFB-equivalence, and related work on other bisimulation types and algebraic connections.

1. Introduction

  • Uniform fuzzy relations and bisimulations together model equivalence between fuzzy automata: the former relate states across sets, while the latter enforce compatibility with automaton structure.The compatibility concerns transitions, initial states, and terminal states.Source: §1 · p. 2
  • The paper also aims to clarify simulation terminology, connect the study to homomorphisms, congruences, and relational morphisms, and review related concepts across automata types.The overview covers deterministic, nondeterministic, fuzzy, and weighted automata.Source: §1 · pp. 2–3
  • The paper defines forward, backward, and two heterotypic bisimulation types, then focuses on forward and backward-forward bisimulations because the paired concepts are dual.It also studies distinctions between forward and backward-forward bisimulations.Source: §1 · pp. 2–3
  • A uniform relation between two fuzzy automata is a forward bisimulation exactly when its kernel and co-kernel are forward-bisimulation fuzzy equivalences and the corresponding factor automata have a special isomorphism.The paper also gives an equality-based alternative definition and conditions for a uniform forward bisimulation with specified kernel and co-kernel.Source: §1 · p. 3
  • UFB-equivalence can be tested by computing greatest forward-bisimulation fuzzy equivalences, forming factor automata, and checking a suitably constrained isomorphism, a step that may be hard and is closely related to graph isomorphism.In numerous cases the equivalences can be computed effectively using the algorithm in [21].Source: §1 · p. 3

2. Preliminaries

The preliminaries establish complete residuated lattices as the setting for membership values and define the fuzzy-set, relation, and equivalence machinery used later. They also introduce factor sets for fuzzy equivalences.

2. Preliminaries

  • Membership values are taken from a complete residuated lattice, whose operations include lattice meet and join, a commutative monoidal product, and its adjoint residuum.The paper lists Łukasiewicz, Goguen, Gödel, and Boolean structures as examples.Source: §2 · pp. 3–4
  • A fuzzy subset assigns each element a lattice value, and a fuzzy relation assigns such values to pairs; relations compose through the lattice operations.For finite sets, fuzzy relations can be treated as matrices, with relation composition corresponding to matrix product.Source: §2 · pp. 4–6
  • A fuzzy equivalence relation is reflexive, symmetric, and transitive, with transitivity expressed using the monoidal product and relation composition.Its factor set consists of the equivalence classes determined by its states.Source: §2 · p. 6
  • The crisp part of a fuzzy equivalence is a crisp equivalence with the same index, and the induced relation on the factor set is a fuzzy equality.The factor set is denoted A/E for an equivalence E on A.Source: §2 · p. 6

3. Fuzzy automata

This section defines fuzzy automata over a complete residuated lattice, including their transition, initial, and terminal membership values. It also sets out word recognition, factor automata, and isomorphism notions used in later results.

3. Fuzzy automata

  • A fuzzy automaton consists of a nonempty state set, a fuzzy transition function, and fuzzy sets of initial and terminal states over the chosen lattice.The transition value represents the degree of transition between states on an input letter; initial and terminal values represent their respective degrees.Source: §3 · pp. 6–7
  • For an input word, the transition degree between two states is the supremum over paths of the products of their transition degrees.A fuzzy language assigns each word its recognition degree, and automata are language-equivalent when they recognize the same fuzzy language.Source: §3 · pp. 7–8
  • Any fuzzy equivalence on an automaton’s states defines a factor fuzzy automaton on its equivalence classes.The quotient automaton recognizes the same fuzzy language as the original exactly when the equivalence solves the stated system of fuzzy relation equations.Source: §3 · pp. 8–9
  • A minimal fuzzy automaton for a language need not be unique up to isomorphism, and minimization is computationally hard.The paper therefore focuses on constructing minimal automata within special subclasses of automata recognizing the language.Source: §3 · p. 9

4. Uniform fuzzy relations

Uniform fuzzy relations provide a structured relation between two possibly different sets, with induced fuzzy equivalences on each side. The section develops their factor-set correspondence and composition properties.

4. Uniform fuzzy relations

  • A uniform fuzzy relation is a surjective L-function that is also a partial fuzzy function, equivalently a perfect fuzzy function with the added surjectivity condition.Its inverse is also uniform, and the relation’s kernel and co-kernel exchange roles under inversion.Source: §4 · pp. 10–11
  • A uniform fuzzy relation induces a bijection between the factor sets of its kernel and co-kernel, independent of the crisp description and class representative used.The inverse bijection is induced by the inverse relation.Source: §4 · p. 11
  • A uniform fuzzy relation is uniquely determined by its crisp representation together with either its kernel or its co-kernel.The section presents this as a consequence of equivalent characterizations of uniform fuzzy relations.Source: §4 · p. 12
  • Composing two uniform fuzzy relations need not yield a uniform relation, but it does when the first relation’s co-kernel is contained in the second relation’s kernel.The composition of surjective L-functions remains a surjective L-function.Source: §4 · p. 12

5. Bisimulations for fuzzy automata

This section defines forward, backward, and mixed bisimulations for fuzzy automata and examines what they imply about language behavior and equivalence. It establishes that a greatest forward bisimulation exists when any forward bisimulation exists, and that this greatest relation is a partial fuzzy function.

Definitions and properties

  • A forward bisimulation is a relation whose inverse is also a forward simulation; the section distinguishes homotypic and heterotypic bisimulations by the simulation directions of the relation and its inverse.Forward and backward bisimulations are homotypic; backward-forward and forward-backward bisimulations are heterotypic.Source: §5 · p. 13
  • Forward simulations preserve language inclusion, but two automata with simulations in both directions need not have a forward bisimulation between them.The section also notes that simulation sequences can extend from letters to arbitrary words.Source: §5 · pp. 14–15
  • Language equivalence does not guarantee any simulation or bisimulation between fuzzy automata.An example has equal languages but no simulation in either direction, and therefore no bisimulation.Source: §5 · pp. 15–16
  • A backward simulation between two automata is a forward simulation between their reverse automata, so the section uses this duality to focus on forward bisimulations.The discussion treats backward-forward bisimulations separately and identifies forward-backward bisimulations as their dual counterparts.Source: §5 · pp. 13, 16
  • If at least one forward bisimulation exists between two fuzzy automata, then a greatest one exists and is a partial fuzzy function.The existence assumption matters because the empty relation does not satisfy the initial-state conditions except when both initial-state sets are empty.Source: §5 · pp. 16–17
  • The section focuses on uniform fuzzy relations because surjective L-functions that are partial fuzzy functions are exactly uniform fuzzy relations, which can relate whole automata.This motivates studying bisimulations that are uniform fuzzy relations as a model of automata equivalence.Source: §5 · p. 17
  • A forward bisimulation on an automaton is a forward bisimulation from that automaton to itself; when it is also a fuzzy equivalence relation, it is a forward bisimulation fuzzy equivalence relation.The section also gives corresponding criteria for forward and backward bisimulation fuzzy equivalences.Source: §5 · p. 17

6. Uniform forward bisimulations

This section characterizes uniform forward bisimulations through their induced relations on each automaton and isomorphisms between factor automata. It also gives an equality-based characterization and a criterion for when such a relation exists.

6. Uniform forward bisimulations

  • A uniform forward bisimulation induces forward bisimulations on each automaton by composing the relation with its inverse; when uniform, these compositions are forward-bisimulation fuzzy equivalences.These are the kernel and co-kernel of the relation.Source: §6 · p. 18
  • The proof uses compatibility of the ordering of fuzzy relations with composition to derive inequalities for the relation and its inverse.Those inequalities imply that the two compositions are forward bisimulations.Source: §6 · p. 18
  • Uniform forward bisimulations can also be characterized using equalities rather than the inequalities used to define forward and backward bisimulations.The section presents equalities as a more convenient way to work with uniform forward bisimulations.Source: §6 · p. 18
  • For a uniform forward bisimulation, the initial-state conditions include σA ◦ ϕ ◦ ϕ−1 = σB ◦ ϕ−1 and σA ◦ ϕ = σB ◦ ϕ−1 ◦ ϕ.Theorem 6.2 states that forward bisimulation is characterized by a collection of equalities; these are the supplied initial-state equalities.Source: §6 · p. 18
  • A uniform relation is a forward bisimulation exactly when its induced relations are forward bisimulations and its induced map between the factor automata is an isomorphism.Theorem 6.3 states this characterization through conditions on both automata and the factor-automaton map.Source: §6 · p. 19
  • Given forward bisimulations E and F on A and B, respectively, a uniform forward bisimulation with kernel E and co-kernel F exists exactly when a factor-automaton isomorphism satisfies the stated condition.The theorem gives both directions of this existence criterion.Source: §6 · p. 20

7. UFB-equivalent fuzzy automata

This section characterizes UFB-equivalence through isomorphism of factor fuzzy automata formed using each automaton’s greatest forward bisimulation, and examines related quotient properties and computational implications. It shows that the greatest forward-bisimulation quotient is minimal in its UFB-equivalence class, although minimal automata in that class need not be isomorphic.

7. UFB-equivalent fuzzy automata

  • A fuzzy equivalence E is a forward bisimulation exactly when its quotient map is a forward bisimulation, equivalently a backward-forward bisimulation.The quotient map is always both a forward and backward simulation.Source: §7 · pp. 21–22
  • If E is a forward bisimulation and E ≤ G, then G/E preserves whether G is a forward bisimulation or the greatest one, and the corresponding iterated quotient is isomorphic to A/G.G is a forward bisimulation exactly when G/E is one on A/E; G is greatest exactly when G/E is greatest there.Source: §7 · p. 23
  • Two fuzzy automata are UFB-equivalent exactly when their quotients by their greatest forward bisimulations admit an isomorphism satisfying the stated condition.For UFB-equivalent automata, a uniform forward bisimulation has kernels and co-kernels equal to the respective greatest forward bisimulations and is itself the greatest forward bisimulation between them.Source: §7 · pp. 24, 26
  • UFB-equivalence is an equivalence relation, with transitivity established through isomorphisms between quotients by the greatest forward bisimulations.The composition of arbitrary uniform fuzzy relations need not be uniform, but the relevant quotient isomorphisms compose.Source: §7 · p. 26
  • Language equivalence does not imply UFB-equivalence: the section gives automata that are language equivalent but whose greatest-forward-bisimulation quotients are non-isomorphic.Those automata are also minimal among automata language-equivalent to them.Source: §7 · pp. 26–27
  • Testing UFB-equivalence requires computing greatest forward bisimulations, forming their factor automata, and checking for an isomorphism satisfying the stated condition.The isomorphism problem for Boolean fuzzy automata is exactly graph isomorphism; quotient automata can have far fewer states than the originals, potentially reducing testing time.Source: §7 · p. 27
  • A/E is minimal among fuzzy automata UFB-equivalent to A.For any B in that class, A/E is isomorphic to B/F, where F is B’s greatest forward bisimulation, so |A/E| = |B/F| ≤ |B|.Source: §7 · p. 27
  • A and B can be UFB-equivalent and minimal in the same class without being isomorphic.In the example, both are also minimal among automata language-equivalent to them.Source: §7 · p. 28
  • Factoring by a fuzzy equality preserves the number of states but need not yield an automaton isomorphic to the original.In the example, B/F is isomorphic to B, but A/E is not isomorphic to A.Source: §7 · p. 28

8. Backward-forward bisimulations

The section characterizes uniform backward-forward bisimulations through bisimulation relations on each automaton and an isomorphism between factor automata. It also identifies differences from forward and backward bisimulations, including the inability to use backward-forward bisimulations to define equivalence between automata.

8. Backward-forward bisimulations

  • A backward-forward bisimulation between A and B corresponds under inversion to a forward-backward bisimulation between B and A.The two types are treated through their duality on reverse fuzzy automata.Source: §8 · p. 28
  • When at least one backward-forward bisimulation exists, a greatest one exists, but it cannot be shown to be a partial fuzzy function.Composition and arbitrary joins preserve backward-forward bisimulations; the partial-function argument fails because the relevant composite need not be a backward-forward bisimulation.Source: §8 · p. 28
  • For a forward bisimulation E on A and a backward bisimulation F on B, a uniform backward-forward bisimulation exists exactly when the stated isomorphism between A/E and B/F exists.The theorem gives the isomorphism condition for these factor automata.Source: §8 · p. 29
  • Backward-forward bisimulations cannot define equivalence between fuzzy automata because they do not provide symmetry, although they ensure language-equivalence and generalize homomorphisms.The text identifies language-equivalence and their relation to homomorphisms as reasons for their use.Source: §8 · p. 30

9. Related concepts

This section surveys automata concepts related to homomorphisms, congruences, relational morphisms, and bisimulations, including unresolved fuzzy-automata reduction questions and weighted-automata bisimulation terminology and limitations. It also points to related automata and relational-structure settings.

9.1. Deterministic automata

  • For deterministic automata, relational morphisms are forward bisimulations, and congruences are forward-bisimulation equivalence relations, though not necessarily backward simulations.Source: §9.1 · p. 31

9.2. Non-deterministic automata

  • Simulations between nondeterministic automata correspond to backward-forward bisimulations, while the studied nondeterministic morphisms correspond to backward simulations.Source: §9.2 · p. 32
  • For nondeterministic automata, language-preserving equivalences are solutions to the general system, but no unique congruence definition is established.Forward and backward bisimulation equivalences are useful finite instances, and alternating them can achieve exponential state reduction where either alone yields polynomial reduction.Source: §9.2 · p. 33

9.3. Fuzzy automata

  • Fuzzy homomorphisms are backward-forward bisimulations, while the cited fuzzy congruence concepts correspond to forward bisimulation equivalences.For fuzzy equivalences, the factor automaton recognizes the same fuzzy language as the original exactly when the equivalence solves the general system; greatest forward and backward bisimulation fuzzy equivalences can be computed and can yield better reductions than crisp counterparts.Source: §9.3 · pp. 33–35
  • Strongly right- and left-invariant fuzzy equivalences are easier to compute than forward and backward bisimulation equivalences, but can yield worse state reductions.Source: §9.3 · p. 35
  • Weakly invariant fuzzy equivalences can yield better reductions, but their defining systems may have infinitely many equations or exponentially many in the automaton’s state count.Source: §9.3 · p. 35
  • Fuzzy-automata reduction remains difficult, and how prior reduction results relate to fuzzy-relation methods is unclear.Fuzzy equivalences and quasi-orders can yield better reductions than crisp state relations; “minimization” is often an imprecise label, since the cited algorithms do not necessarily produce minimal automata, and actual minimization algorithms were given only for crisp-deterministic fuzzy automata.Source: §9.3 · p. 36

9.4. Weighted automata

  • Weighted automata resemble fuzzy automata, but extending forward and backward bisimulations requires an ordering on semirings or a suitable equivalent definition.Related literature calls weighted-relation simulations by several names, including conjugacy and backward elementary equivalence; for some semirings, equivalence holds exactly when automata are connected by a finite chain of simulations, while the tropical semiring is an exception.Source: §9.4 · pp. 36–37

9.5. A few additional comments

  • Homomorphisms, congruences, relational morphisms, and their generalizations also arise in relational structures and stochastic, timed, and hybrid automata.The paper points to further literature on these settings rather than discussing them in detail.Source: §9.5 · p. 37

10. Concluding remarks

The paper characterizes uniform forward bisimulations using bisimulation fuzzy equivalences and isomorphisms between factor automata. Its conclusions also distinguish backward-forward bisimulations and survey related concepts across automata and algebraic structures.

10. Concluding remarks

  • UFB-equivalence holds exactly when the factor automata formed using the greatest forward bisimulation fuzzy equivalences are specially isomorphic.This reduces testing UFB-equivalence to testing isomorphism of fuzzy automata, a problem closely related to graph isomorphism.Source: §10 · p. 37
  • A uniform fuzzy relation is a forward bisimulation exactly when its kernel and co-kernel are forward bisimulation fuzzy equivalences and the corresponding factor automata have a special isomorphism.The kernel and co-kernel are on the respective automata.Source: §10 · p. 37
  • Forward and backward bisimulation fuzzy equivalences give equally good state-reduction results, but only backward ones are reported as useful for conflict analysis.The cited work reports that forward bisimulation fuzzy equivalences cannot be used for conflict analysis.Source: §10 · p. 37
  • Further work will address forward bisimulations for weighted automata, backward-forward bisimulations for weighted automata, and structural equivalences and outputs in fuzzy automata.For weighted automata, the authors identify the lack of suitable semiring ordering as an issue to address.Source: §10 · p. 38
Loading 1102.5452v2…