Title: Optimisation of algebraic event structure using trace equivalence based on Gröbner basis

Authors: Weidong Tang; Weiwen Ge; Meiling Liu

Addresses: College of Artificial Intelligence, Guangxi Minzu University, Nanning, Guangxi, 530006, China ' College of Physics and Electronic Information, Guangxi Minzu University, Nanning, Guangxi, 530006, China ' College of Artificial Intelligence, Guangxi Minzu University, Nanning, Guangxi, 530006, China

Abstract: The process of data flow exchange in complex concurrent systems is often redundant and uncertain, leading to resource inefficiency and 'state explosion'. Equivalence relationships identify processes of the same behaviour, remove redundancy to simplify system verification and analysis, and effectively mitigate the 'state explosion' problem. In Glabbeek's equivalence spectrum, trace equivalence (systems that produce the same sequence of actions are considered equivalent) and bisimulation equivalence (requiring bidirectional behaviour correspondence between systems) are widely accepted. In this paper, we discuss the method of trace equivalence judgement on the polynomial algebraic event structure, propose the judgement of polynomial event equivalence, and use Gröbner basis for calculation. Gröbner basis, as an algebraic tool to determine the equality of polynomial systems, has the advantages of accuracy and efficiency, and provides a strict mathematical basis for the equivalence determination. Finally, a practical case is presented to show the optimisation effect of this method.

Keywords: state explosion; trace equivalence; bisimulation equivalence; polynomial algebraic event structure; Gröbner basis.

DOI: 10.1504/IJCSM.2025.149614

International Journal of Computing Science and Mathematics, 2025 Vol.22 No.1, pp.76 - 89

Received: 21 Nov 2024
Accepted: 15 Jun 2025
Published online: 07 Nov 2025 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article