2023/07/06 by Linh Anh Nguyen, Nguyen, Linh Anh, Ivana Mičić +3
Computer Science · #Advanced Algebra and Logic #FOS: Computer and information sciences #Formal Languages and Automata Theory (cs.FL) #Formal Methods in Verification #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.2307.03318
openalex publication_date 2023/07/06 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Simulations and bisimulations are well-established notions in crisp/fuzzy automata theory and are widely used to compare the behaviors of automata. Their main drawback is that they compare the behaviors of fuzzy automata in a crisp manner. Recently, fuzzy simulations and fuzzy bisimulations have been defined for fuzzy automata as a kind of approximate simulations and approximate bisimulations that compare the behaviors of fuzzy automata in a fuzzy manner. However, they still suffer from serious shortcomings. First, they still cannot correlate all fuzzy automata that are intuitively "more or less" (bi)similar. Second, the currently known algorithms for computing the greatest fuzzy simulation or bisimulation between two finite fuzzy automata have an exponential time complexity when the Łukasiewicz or product structure of fuzzy values is used. This work deals with these problems, providing approximations of fuzzy simulations and fuzzy bisimulations. We define such approximations via a novel notion of decreasing sequences of fuzzy relations whose infima are, under some conditions, fuzzy simulations (respectively, bisimulations). We call such a sequence a depth-bounded fuzzy simulation (respectively, bisimulation), as the nth element from the sequence compares the behaviors of fuzzy automata, but only for words with a length bounded by n. We further provide a logical characterization of the greatest depth-bounded fuzzy simulation or bisimulation between two fuzzy automata by proving that it satisfies the corresponding Hennessy-Milner property. Finally, we provide polynomial-time algorithms for computing the nth component of the greatest depth-bounded fuzzy simulation (respectively, bisimulation) between two finite fuzzy automata.