Algorithms for computing the greatest simulations and bisimulations between fuzzy automata

Recently, two types of simulations (forward and backward simulations) and four types of bisimulations (forward, backward, forward-backward, and backward-forward bisimulations) between fuzzy automata have been introduced. If there is at least one simulation/bisimulation of some of these types between...

Full description

Saved in:
Bibliographic Details
Published in:arXiv.org 2011-03
Main Authors: Ćirić, Miroslav, Ignjatović, Jelena, Jančić, Ivana, Damljanović, Nada
Format: Article
Language:English
Subjects:
Algorithms
Automata theory
Computation
Computer simulation
Fixed points (mathematics)
Fuzzy sets
Fuzzy systems
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Recently, two types of simulations (forward and backward simulations) and four types of bisimulations (forward, backward, forward-backward, and backward-forward bisimulations) between fuzzy automata have been introduced. If there is at least one simulation/bisimulation of some of these types between the given fuzzy automata, it has been proved that there is the greatest simulation/bisimulation of this kind. In the present paper, for any of the above-mentioned types of simulations/bisimulations we provide an effective algorithm for deciding whether there is a simulation/bisimulation of this type between the given fuzzy automata, and for computing the greatest one, whenever it exists. The algorithms are based on the method developed in [J. Ignjatović, M. Ćirić, S. Bogdanović, On the greatest solutions to certain systems of fuzzy relation inequalities and equations, Fuzzy Sets and Systems 161 (2010) 3081-3113], which comes down to the computing of the greatest post-fixed point, contained in a given fuzzy relation, of an isotone function on the lattice of fuzzy relations.
ISSN:2331-8422
DOI:10.48550/arxiv.1103.5078