Approximate state reduction of fuzzy finite automata
Stefan Stanimirović, Linh Anh Nguyen, Miroslav Ćirić, Marko Stanković · Fuzzy Sets and Systems · 2025
State reduction of fuzzy automata aims to efficiently construct a suitably small fuzzy automaton equivalent to a given one. It is a significant and well-studied problem in automata theory due to its practical applications in various fields. If we relax the requirement for exact equivalence, then we talk about the approximate state reduction problem, which has gained attention only recently. There are two approaches to approximate state reduction: one seeks approximate equivalence to a specified threshold, while the other aims for exact equivalence for length-bounded words. These two approaches have been considered separately. In this paper, we demonstrate that both approaches, and even their combination, can be achieved by merging indistinguishable states of a fuzzy automaton through the use of sequences of fuzzy relations that we introduce in this paper. We provide characterizations of these sequences, and show that they are closely related to certain approximate simulations for fuzzy automata that emerged in the recent literature. However, their subtle differences significantly affect the process of approximate state reduction. By formally proving this distinction, we generalize some well-known results and offer new insight into approximate state reduction. We discuss how all forms of approximate state reduction can be realized and provide algorithms for calculating the proposed sequences and performing the reductions, along with illustrative examples.