A path-based equivalence checking method for Petri net based models of programs

摘要

Programs are often subjected to significant optimizing and parallelizing transformations. It is therefore important to model parallel behaviours and formally verify the equivalence of their functionalities. In this work, the untimed PRES+ model (Petri net based Representation of Embedded Systems) encompassing data processing is used to model parallel behaviours. Being value based with inherent scope of capturing parallelism, PRES+ models depict such data dependencies more directly; accordingly, they are likely to be more convenient as the intermediate representations (IRs) of both the source and the transformed codes for translation validation than strictly sequential variable-based IRs like Finite State Machines with Datapath (FSMDs) (which are essentially sequential control data-flow graphs (CDFGs)). In this work, a path based equivalence checking method for PRES+ models is presented.