Bisimulations for fuzzy automata
From MaRDI portal
Publication:423147
DOI10.1016/J.FSS.2011.07.003zbMATH Open1237.68113arXiv1102.5452OpenAlexW2097074325MaRDI QIDQ423147FDOQ423147
Milan Bašić, Miroslav Ćirić, Jelena Ignjatović, Nada Damljanović
Publication date: 18 May 2012
Published in: Fuzzy Sets and Systems (Search for Journal in Brave)
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.
Full work available at URL: https://arxiv.org/abs/1102.5452
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
simulationbisimulationcomplete residuated latticesequivalence of automatafuzzy automatafuzzy equivalence relationsfuzzy relation inequalitiesfuzzy relationsstate reductionuniform fuzzy relations
Formal languages and automata (68Q45) Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85)
Cites Work
- Weighted finite automata over strong bimonoids
- Generalizing the Paige-Tarjan algorithm by abstract interpretation
- Computing behavior of finite fuzzy machines -- algorithm and its application to reduction and minimization
- The algorithm design manual
- Fuzzy sets and systems. Theory and applications
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- What's decidable about hybrid automata?
- Metamathematics of fuzzy logic
- Forward and backward simulations. I. Untimed Systems
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Equational axioms for regular sets
- Three Partition Refinement Algorithms
- Title not available (Why is that?)
- Title not available (Why is that?)
- A note on Trillas' CHC models
- Uniform fuzzy relations and fuzzy functions
- Automata theory based on complete residuated lattice-valued logic: Pushdown automata
- Pumping Lemma in context-free grammar theory based on complete residuated lattice-valued logic
- Fuzzy homomorphisms of algebras
- Automata theory based on complete residuated lattice-valued logic: a categorical approach
- A calculus of communicating systems
- Fuzzy automata and languages
- Characterizations of fuzzy finite automata.
- Finite \(L\)-fuzzy machines.
- A theory of vague lattices based on many-valued equivalence relations. I: General representation results
- Minimization of fuzzy finite automata
- Fuzzy functions and their applications
- Determinism and fuzzy automata
- Formal power series and regular operations on fuzzy languages
- Fuzzy equivalence relations and their equivalence classes
- Equivalence in automata theory based on complete residuated lattice-valued logic
- Minimization of lattice finite automata and its application to the decomposition of lattice languages
- Determinization of fuzzy automata with membership values in complete residuated lattices
- Bisimulation relations for weighted automata
- Max-product machines
- Backward and Forward Bisimulation Minimisation of Tree Automata
- Title not available (Why is that?)
- Foundations of fuzzy functions and vague algebra based on many-valued equivalence relations, part I: fuzzy functions and their applications
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Reactive Systems
- An improved algorithm for determinization of weighted and fuzzy automata
- Factorization of Fuzzy Automata
- Maximin automata
- A Formulation of Fuzzy Automata and Its Application as a Model of Learning Systems
- Title not available (Why is that?)
- Fuzzy equational logic
- On the greatest solutions to weakly linear systems of fuzzy relation inequalities and equations
- Finite automata theory with membership values in lattices
- Reduction of fuzzy automata by means of fuzzy quasi-orders
- Fuzzy finite automata and fuzzy regular expressions with membership values in lattice-ordered monoids
- Congruences and homomorphisms of fuzzy automata
- Backward and forward bisimulation minimization of tree automata
- Pumping lemma in automata theory based on complete residuated lattice-valued logic: a note
- Minimization of states in automata theory based on finite lattice-ordered monoids
- Automata theory based on complete residuated lattice-valued logic
- Automata theory based on complete residuated lattice-valued logic. II
- CCS expressions, finite state processes, and three problems of equivalence
- Myhill-Nerode type theory for fuzzy languages and automata
- Automata theory based on complete residuated lattice-valued logic: Reduction and minimization
- Fuzzy relation equations and reduction of fuzzy automata
- Determinization of weighted finite automata over strong bimonoids
- On quotient machines of a fuzzy automaton and the minimal machine
- Towards a unified view of bisimulation: A comparative study
- The relationships among several types of fuzzy automata
- ON THE GENERAL THEORY OF RELATIONALMORPHISMS
- Conjugacy and Equivalence of Weighted Automata and Functional Transducers
- A GENERALIZATION OF KOZEN'S AXIOMATIZATION OF THE EQUATIONAL THEORY OF THE REGULAR SETS
- Automata, Languages and Programming
- Products of \(T\)-generalized state machines and \(T\)-generalized transformation semigroups
- Products of fuzzy finite state machines
- On covering of products of fuzzy finite state machines
- Minimization algorithm of fuzzy finite automata.
- Reducing NFAs by invariant equivalences.
- From bisimulation to simulation: Coarsest partition problems
- Finite nondeterministic automata: simulation and minimality
- Derivatives of rational expressions with multiplicity
- An efficient algorithm for computing bisimulation equivalence
- Algebraic properties of \(LA\)-languages
- On the generating sequences of regular languages on k symbols
- Kleene and Büchi Theorems for Weighted Automata and Multi-valued Logics over Arbitrary Bounded Lattices
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- FINITE ${\mathbb L}$–FUZZY ACCEPTORS, REGULAR ${\mathbb L}$–FUZZY GRAMMARS AND SYNTACTIC PATTERN RECOGNITION
- Title not available (Why is that?)
- Title not available (Why is that?)
- Lattice Automata
- Homomorphism and Isomorphism Theorems Generalized from a Relational Perspective
- On relational homomorphisms of automata
- Combinatorial Pattern Matching
- Theory Is Forever
- Generalized morphisms, a new tool for comparative evaluation of performance of fuzzy implications, t-norms and co-norms in relational knowledge elicitation
- Decompositions of \(T\)-generalized transformation semigroups.
- NFA reduction algorithms by means of regular inequalities
Cited In (51)
- Relative approximate bisimulations for fuzzy picture automata
- Simulations and bisimulations for max-plus automata
- Simulation for lattice-valued doubly labeled transition systems
- Coalgebras for fuzzy transition systems
- Distribution-based limited fuzzy bisimulations for nondeterministic fuzzy transition systems
- The universal fuzzy automaton
- Weak bisimulations for fuzzy automata
- (f, g)-derivation of ordered Γ-semirings
- Characterizing fuzzy simulations for fuzzy labeled transition systems in fuzzy propositional dynamic logic
- Limited approximate bisimulations and the corresponding rough approximations
- Bisimilarity in Fresh-Register Automata
- Improved algorithms for computing the greatest right and left invariant Boolean matrices and their application
- Labeled fuzzy approximations based on bisimulations
- Weakly linear systems for matrices over the max-plus quantale
- Computation of the greatest simulations and bisimulations between fuzzy automata
- Characterization and computation of approximate bisimulations for fuzzy automata
- Nondeterministic automata: equivalence, bisimulations, and uniform relations
- Fuzzy simulations and bisimulations between fuzzy automata
- Quantitative simulations by matrices
- Fuzzy approximations of fuzzy relational structures
- Bisimulations for weighted automata over an additively idempotent semiring
- Inherent Vacuity in Lattice Automata
- Polynomial-time algorithms for computing distances of fuzzy transition systems
- Bisimulation of type 2 for BL-general fuzzy automata
- Bisimulations for fuzzy transition systems revisited
- Algorithmic and logical characterizations of bisimulations for non-deterministic fuzzy transition systems
- Determinization of fuzzy automata by factorizations of fuzzy states and right invariant fuzzy quasi-orders
- A fuzzy modal logic for fuzzy transition systems
- Construction of fuzzy automata from fuzzy regular expressions
- Weakly linear systems of fuzzy relation inequalities: the heterogeneous case
- Approximate bisimulation relations for fuzzy automata
- Regular fuzzy equivalences on two - mode fuzzy Networksi
- Computation of the greatest right and left invariant fuzzy quasi-orders and fuzzy equivalences
- Fuzzy \(\epsilon\)-approximate regular languages and minimal deterministic fuzzy automata \(\epsilon\)-accepting them
- Title not available (Why is that?)
- Lattice-valued simulations for quantitative transition systems
- Weighted Automata over Vector Spaces
- Computing the fuzzy partition corresponding to the greatest fuzzy auto-bisimulation of a fuzzy graph-based structure under the Gödel semantics
- Logical characterizations of fuzzy bisimulations in fuzzy modal logics over residuated lattices
- Fuzzy Bisimulations in Fuzzy Description Logics Under the Gödel Semantics
- Title not available (Why is that?)
- Bifuzzy core of fuzzy automata
- Algebraic and topological structures on factorizations of fuzzy sets1
- Nondeterministic fuzzy automata with membership values in complete residuated lattices
- Bisimulation and bisimilarity for fuzzy description logics under the Gödel semantics
- Similarity-based minimization of fuzzy tree automata
- Approximate bisimulations and state reduction of fuzzy automata under fuzzy similarity measures
- Logical characterizations of simulation and bisimulation for fuzzy transition systems
- Direct and Indirect Methods for Solving Two-Mode Systems of Fuzzy Relation Equations and Inequalities
- Further improvements of determinization methods for fuzzy finite automata
- Model checking fuzzy computation tree logic
Uses Software
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)
