1. Breadth-first fuzzy bisimulations for fuzzy automata.
- Author
-
Stanimirović, Stefan, Nguyen, Linh Anh, Ćirić, Miroslav, and Stanković, Marko
- Subjects
- *
TIME complexity , *RESIDUATED lattices , *BISIMULATION , *FUZZY systems , *LINEAR systems - Abstract
We introduce two novel concepts: fuzzy weak (bi)simulations and their approximations, breadth-first fuzzy (bi)simulations , for fuzzy automata with membership values in an arbitrary complete residuated lattice. They offer improved approximations of the subsethood degree (equivalence degree) of fuzzy automata compared to previously established notions. Fuzzy weak (bi)simulations are defined as fuzzy relations, whereas breadth-first fuzzy (bi)simulations are characterized by decreasing sequences of fuzzy relations, where each component is a solution to a finite and linear system of fuzzy relation inequalities. Such systems consist of fuzzy sets that are nodes of the trees constructed in the classic breadth-first search manner. We provide an algorithm that computes the proposed simulations and bisimulations, along with a modified version that computes the subsethood/equality degree for given fuzzy automata. Both algorithms run in the exponential time complexity, reflecting the trade-off for achieving more precise approximations. • We introduce fuzzy weak bisimulations and their approximations, breadth-first fuzzy bisimulations, for fuzzy automata. • Both concepts provide better approximations of the equivalence degree for fuzzy automata compared to previous approaches. • Breadth-first fuzzy bisimulations are sequences of fuzzy relations where each component solves a system of fuzzy relation inequalities. • We calculate the fuzzy sets of these systems by constructing two complete m -ary trees in the classic breadth-first search manner. • The computation for the proposed bisimulations has a higher cost, as a trade-off for achieving greater precision. [ABSTRACT FROM AUTHOR]
- Published
- 2025
- Full Text
- View/download PDF