Abstract: 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 and is a forward bisimulation if and only if its kernel and co-kernel are forward bisimulation fuzzy equivalences on and and there is a special isomorphism between factor fuzzy automata with respect to these fuzzy equivalences. As a consequence we get that fuzzy automata and 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 and 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.
Recommendations
- Weak bisimulations for fuzzy automata
- Computation of the greatest simulations and bisimulations between fuzzy automata
- Nondeterministic automata: equivalence, bisimulations, and uniform relations
- Approximate bisimulation relations for fuzzy automata
- Approximate bisimulations and state reduction of fuzzy automata under fuzzy similarity measures
Cites work
- scientific article; zbMATH DE number 1183717 (Why is no real title available?)
- scientific article; zbMATH DE number 1189289 (Why is no real title available?)
- scientific article; zbMATH DE number 3716792 (Why is no real title available?)
- scientific article; zbMATH DE number 42752 (Why is no real title available?)
- scientific article; zbMATH DE number 3561239 (Why is no real title available?)
- scientific article; zbMATH DE number 3589732 (Why is no real title available?)
- scientific article; zbMATH DE number 3623470 (Why is no real title available?)
- scientific article; zbMATH DE number 1296290 (Why is no real title available?)
- scientific article; zbMATH DE number 1304993 (Why is no real title available?)
- scientific article; zbMATH DE number 1033559 (Why is no real title available?)
- scientific article; zbMATH DE number 1790419 (Why is no real title available?)
- scientific article; zbMATH DE number 1929949 (Why is no real title available?)
- scientific article; zbMATH DE number 941396 (Why is no real title available?)
- scientific article; zbMATH DE number 2086620 (Why is no real title available?)
- scientific article; zbMATH DE number 1862743 (Why is no real title available?)
- scientific article; zbMATH DE number 764336 (Why is no real title available?)
- scientific article; zbMATH DE number 2199279 (Why is no real title available?)
- scientific article; zbMATH DE number 2225808 (Why is no real title available?)
- A Formulation of Fuzzy Automata and Its Application as a Model of Learning Systems
- A GENERALIZATION OF KOZEN'S AXIOMATIZATION OF THE EQUATIONAL THEORY OF THE REGULAR SETS
- A calculus of communicating systems
- A note on Trillas' CHC models
- A theory of vague lattices based on many-valued equivalence relations. I: General representation results
- Algebraic properties of \(LA\)-languages
- An efficient algorithm for computing bisimulation equivalence
- An improved algorithm for determinization of weighted and fuzzy automata
- Automata theory based on complete residuated lattice-valued logic
- Automata theory based on complete residuated lattice-valued logic. II
- Automata theory based on complete residuated lattice-valued logic: Pushdown automata
- Automata theory based on complete residuated lattice-valued logic: Reduction and minimization
- Automata theory based on complete residuated lattice-valued logic: a categorical approach
- Automata, Languages and Programming
- Backward and Forward Bisimulation Minimisation of Tree Automata
- Backward and forward bisimulation minimization of tree automata
- Bisimulation relations for weighted automata
- CCS expressions, finite state processes, and three problems of equivalence
- Characterizations of fuzzy finite automata.
- Combinatorial Pattern Matching
- Computing behavior of finite fuzzy machines -- algorithm and its application to reduction and minimization
- Congruences and homomorphisms of fuzzy automata
- Conjugacy and Equivalence of Weighted Automata and Functional Transducers
- Decompositions of \(T\)-generalized transformation semigroups.
- Derivatives of rational expressions with multiplicity
- Determinism and fuzzy automata
- Determinization of fuzzy automata with membership values in complete residuated lattices
- Determinization of weighted finite automata over strong bimonoids
- Elements of automata theory. Translated from the French by Reuben Thomas
- Equational axioms for regular sets
- Equivalence in automata theory based on complete residuated lattice-valued logic
- FINITE ${\mathbb L}$–FUZZY ACCEPTORS, REGULAR ${\mathbb L}$–FUZZY GRAMMARS AND SYNTACTIC PATTERN RECOGNITION
- Factorization of Fuzzy Automata
- Finite \(L\)-fuzzy machines.
- Finite automata theory with membership values in lattices
- Finite nondeterministic automata: simulation and minimality
- Formal power series and regular operations on fuzzy languages
- Forward and backward simulations. I. Untimed Systems
- Foundations of fuzzy functions and vague algebra based on many-valued equivalence relations, part I: fuzzy functions and their applications
- From bisimulation to simulation: Coarsest partition problems
- Fuzzification of rational and recognizable sets
- Fuzzy automata and languages
- Fuzzy equational logic
- Fuzzy equivalence relations and their equivalence classes
- Fuzzy finite automata and fuzzy regular expressions with membership values in lattice-ordered monoids
- Fuzzy functions and their applications
- Fuzzy homomorphisms of algebras
- Fuzzy relation equations and reduction of fuzzy automata
- Fuzzy sets and systems. Theory and applications
- Generalized morphisms, a new tool for comparative evaluation of performance of fuzzy implications, t-norms and co-norms in relational knowledge elicitation
- Generalizing the Paige-Tarjan algorithm by abstract interpretation
- Homomorphism and Isomorphism Theorems Generalized from a Relational Perspective
- Kleene and Büchi theorems for weighted automata and multi-valued logics over arbitrary bounded lattices
- Lattice Automata
- Max-product machines
- Maximin automata
- Metamathematics of fuzzy logic
- Minimization algorithm of fuzzy finite automata.
- Minimization of fuzzy finite automata
- Minimization of lattice finite automata and its application to the decomposition of lattice languages
- Minimization of states in automata theory based on finite lattice-ordered monoids
- Myhill-Nerode type theory for fuzzy languages and automata
- NFA reduction algorithms by means of regular inequalities
- ON THE GENERAL THEORY OF RELATIONALMORPHISMS
- On covering of products of fuzzy finite state machines
- On quotient machines of a fuzzy automaton and the minimal machine
- On relational homomorphisms of automata
- On the generating sequences of regular languages on \(k\) symbols
- On the greatest solutions to weakly linear systems of fuzzy relation inequalities and equations
- Products of \(T\)-generalized state machines and \(T\)-generalized transformation semigroups
- Products of fuzzy finite state machines
- Pumping Lemma in context-free grammar theory based on complete residuated lattice-valued logic
- Pumping lemma in automata theory based on complete residuated lattice-valued logic: a note
- Reactive Systems
- Reducing NFAs by invariant equivalences.
- Reduction of fuzzy automata by means of fuzzy quasi-orders
- The algorithm design manual
- The relationships among several types of fuzzy automata
- Theory Is Forever
- Three Partition Refinement Algorithms
- Towards a unified view of bisimulation: A comparative study
- Uniform fuzzy relations and fuzzy functions
- Weighted finite automata over strong bimonoids
- What's decidable about hybrid automata?
- Words and bisimulations of dynamical systems
Cited in
(51)- Relative approximate bisimulations for fuzzy picture automata
- Computing the fuzzy partition corresponding to the greatest fuzzy auto-bisimulation of a fuzzy graph-based structure under the Gödel semantics
- Simulations and bisimulations for max-plus automata
- Weighted Automata over Vector Spaces
- \((f,g)\)-derivation of ordered \(\Gamma\)-semirings
- Distribution-based limited fuzzy bisimulations for nondeterministic fuzzy transition systems
- Bifuzzy core of fuzzy automata
- Characterizing fuzzy simulations for fuzzy labeled transition systems in fuzzy propositional dynamic logic
- Limited approximate bisimulations and the corresponding rough approximations
- Bisimulations for fuzzy transition systems revisited
- Bisimulations for weighted automata over an additively idempotent semiring
- Bisimulation and bisimilarity for fuzzy description logics under the Gödel semantics
- Coalgebras for fuzzy transition systems
- Direct and indirect methods for solving two-mode systems of fuzzy relation equations and inequalities
- Simulation for lattice-valued doubly labeled transition systems
- Inherent vacuity in lattice automata
- Computation of the greatest simulations and bisimulations between fuzzy automata
- The universal fuzzy automaton
- Weak bisimulations for fuzzy automata
- Bisimilarity in Fresh-Register Automata
- Approximate bisimulation relations for fuzzy automata
- Labeled fuzzy approximations based on bisimulations
- Further improvements of determinization methods for fuzzy finite automata
- Improved algorithms for computing the greatest right and left invariant Boolean matrices and their application
- scientific article; zbMATH DE number 7317445 (Why is no real title available?)
- Algorithmic and logical characterizations of bisimulations for non-deterministic fuzzy transition systems
- Fuzzy \(\epsilon\)-approximate regular languages and minimal deterministic fuzzy automata \(\epsilon\)-accepting them
- Bisimulation of type 2 for BL-general fuzzy automata
- Similarity-based minimization of fuzzy tree automata
- Regular fuzzy equivalences on two-mode fuzzy networks
- Logical characterizations of fuzzy bisimulations in fuzzy modal logics over residuated lattices
- Approximate bisimulations and state reduction of fuzzy automata under fuzzy similarity measures
- Quantitative simulations by matrices
- Determinization of fuzzy automata by factorizations of fuzzy states and right invariant fuzzy quasi-orders
- Fuzzy approximations of fuzzy relational structures
- Characterization and computation of approximate bisimulations for fuzzy automata
- Weakly linear systems for matrices over the max-plus quantale
- Polynomial-time algorithms for computing distances of fuzzy transition systems
- scientific article; zbMATH DE number 6612705 (Why is no real title available?)
- Nondeterministic automata: equivalence, bisimulations, and uniform relations
- A fuzzy modal logic for fuzzy transition systems
- Model checking fuzzy computation tree logic
- Computation of the greatest right and left invariant fuzzy quasi-orders and fuzzy equivalences
- Nondeterministic fuzzy automata with membership values in complete residuated lattices
- Fuzzy simulations and bisimulations between fuzzy automata
- Algebraic and topological structures on factorizations of fuzzy sets
- Lattice-valued simulations for quantitative transition systems
- Fuzzy Bisimulations in Fuzzy Description Logics Under the Gödel Semantics
- Construction of fuzzy automata from fuzzy regular expressions
- Weakly linear systems of fuzzy relation inequalities: the heterogeneous case
- Logical characterizations of simulation and bisimulation for fuzzy transition systems
This page was built for publication: Bisimulations for fuzzy automata
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q423147)
