Bisimulation is a fundamental concept for analyzing behavioral equivalence in automata and transition systems, with applications in model reduction, verification, and logical reasoning. In fuzzy automata, computing bisimulation relations using classical algorithms such as fixpoint iterations or partition refinement becomes computationally expensive as the state space grows, limiting their scalability to large systems. To address this limitation, we propose Approximate Bisimulation Learning (ABL), the first learning-based framework designed to estimate bisimilarity between states of fuzzy automata. ABL employs a neural architecture combining shared state encoders with a similarity prediction head, trained in a supervised manner on synthetic datasets where exact bisimulation values are computed using classical methods. Once trained, ABL provides fast and scalable inference of bisimilarity, effectively replacing costly iterative algorithms. We evaluate ABL on a dataset of over 10,000 synthetic fuzzy automata with diverse state sizes, transition densities, and fuzzy membership distributions. Experimental results demonstrate that ABL achieves a mean absolute deviation of less than 0.03 from true bisimulation scores while delivering up to 500 \(\times \) faster inference compared with classical algorithms. These results highlight the potential of learning-based approximate bisimulation for scalable analysis, model reduction, and neural-symbolic reasoning in fuzzy automata and related systems.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Approximate Bisimulation Learning: A Machine Learning Framework for Approximating Bisimilarity in Fuzzy Automata

  • Thi Hong Khanh Nguyen,
  • Trong Hieu Tran

摘要

Bisimulation is a fundamental concept for analyzing behavioral equivalence in automata and transition systems, with applications in model reduction, verification, and logical reasoning. In fuzzy automata, computing bisimulation relations using classical algorithms such as fixpoint iterations or partition refinement becomes computationally expensive as the state space grows, limiting their scalability to large systems. To address this limitation, we propose Approximate Bisimulation Learning (ABL), the first learning-based framework designed to estimate bisimilarity between states of fuzzy automata. ABL employs a neural architecture combining shared state encoders with a similarity prediction head, trained in a supervised manner on synthetic datasets where exact bisimulation values are computed using classical methods. Once trained, ABL provides fast and scalable inference of bisimilarity, effectively replacing costly iterative algorithms. We evaluate ABL on a dataset of over 10,000 synthetic fuzzy automata with diverse state sizes, transition densities, and fuzzy membership distributions. Experimental results demonstrate that ABL achieves a mean absolute deviation of less than 0.03 from true bisimulation scores while delivering up to 500 \(\times \) faster inference compared with classical algorithms. These results highlight the potential of learning-based approximate bisimulation for scalable analysis, model reduction, and neural-symbolic reasoning in fuzzy automata and related systems.