Computing markings for fuzzy minimax nets over the Gödel structure

Abstract

Fuzzy minimax nets were recently introduced as a tool for computing the greatest fuzzy bisimulation and simulation between two finite fuzzy graph-based structures. In this work, we provide an efficient algorithm with time complexity $O(m+n+l\log l)$ for computing the greatest correct marking of a finite fuzzy minimax net over the Gödel structure, where $n$, $m$, and $l$ denote the numbers of nodes, positive edges, and distinct fuzzy values used in the net, respectively. Building on this result, we derive the first algorithm with time complexity $O((m+n)n)$ for computing the greatest fuzzy directed simulation between two finite fuzzy graphs over the Gödel structure, where $n$ and $m$ denote the total numbers of vertices and positive edges, respectively, in the input graphs.