Signal transition graphs

Theory of regions was used to derive an STG model and its circuit implementation in[29] for Counterflow Pipeline Processor due to Robert Sproull, Ivan Sutherland and Charles Molnar.

[30] One of the models closely related to STGs is Change Diagrams, proposed by Michael Kishinevsky, Alex Kondratyev, Alexander Taubin and Victor Varshavsky in.

[33] It has advantages over widely used interpreted Petri Nets and Finite State Machines for a class of systems which have many behavioral scenarios defined on the same set of actions, e.g., CPU microarchitecture controllers.

Placed into the synthesis flow from VHDL, STGs and Petri nets have been shown instrumental,[37] and likewise with Verilog,[38] where a tool VERISYN was developed.

[39] More recently STGs have been connected with notations that are believed to be easier for practical hardware designers, hence the emergence of the model of waveform-transition graphs (WTG).

[40] Likewise, realising that the model of finite state machine (FSM) can be easier for designers to handle than, for example, Petri nets or STGs, a link with Burst Mode FSMs[41] as a front-end has been developed.

[42] At the moment, arguably the most efficient methods for analysis and synthesis of asynchronous circuits are based on Petri net unfoldings - they were studied by Victor Khomenko in his PhD thesis.

[49] Synthesis methods for CSC detection and resolution based on partial orders and Petri net unfoldings have been developed by Alex Semenov[50][51] and Victor Khomenko.

Later, the work Alex Kondratyev et al [56] generalised this condition in the notion of monotonic cover, which found its realisation in software tools.

[57][58] The problem of scalability of synthesis for large size STGs, and needs to alleviate state space explosion have been tackled in methods based on contraction of STGs with respect to structural properties of the underlying Petri net - such as ways of partitioning a free-choice Petri net into state machines or marked graphs[5] - as well as fan-in signal subsets (trigger events for a signal).

[60] A particularly challenging problem is to automatically synthesise asynchronous circuits for arbiters, as their STG specification would contain behavioural conflicts in their underlying Petri nets.