Outrunning Big KATs: Efficient Decision Procedures for Variants of GKAT Cheng Zhang, Qiancheng Fu, Hang Ji, Ines Santacruz Del Valle, Alexandra Silva, Marco Gaboardi Abstract This paper presents several efficient decision procedures for trace equivalence of GKAT automata, which make use of on-the-fly symbolic techniques via SAT solvers. To demonstrate applicability of our algorithms, we designed symbolic derivatives for CF-GKAT , a practical system based on GKAT designed to validate control-flow transformations. We implemented the algorithms in Rust and evaluated them on both randomly generated benchmarks and real-world control-flow transformations. Indeed, we observed order-of-magnitude performance improvements against existing implementations for both KAT and CF-GKAT . Notably, our experiments also revealed a bug in Ghidra, an industry-standard decompiler, highlighting the practical viability of these systems. 1 Introduction Kleene Algebra with Tests (KAT) [ 23 ] is an algebraic framework which has been widely applied for modeling and verification in different domains, including but not limited to software-defined networks [ 2 , 40 ] , concurrency [ 47 , 20 ] , program logics [ 50 , 51 , 13 ] , and program transformations [ 3 , 22 ] . Besides its broad applicability, Kleene Algebra with Tests has also attracted interest for the efficiency of some of its decision procedures. Despite the fact that deciding equivalence for general KAT expressions is PSPACE-complete [ 10 ] , in some applications, decision procedures based on subsets of KAT are able to outperform state-of-the-art tools with domain-specific tasks [ 41 ] . This has led to the systematic study of an efficient fragment of KAT, named Guarded Kleene Algebra with Tests (GKAT) [ 39 ] , where the non-deterministic addition e+f and iteration e^{*} operations are restricted to if-statement e+_{b}f and while-loop e^{(b)} , respectively. Despite being a more restrictive language, GKAT has proven to be a powerful framework, and also found applications in different domains, from control-flow equivalences [ 52 ] , to network verification [ 41 ] , to weighted and probabilistic programming [ 35 , 19 , 44 ] . In particular, the extension presented in [ 52 ] —Control-flow GKAT ( CF-GKAT )—augments GKAT with non-local control-flow structures, like goto and break , and indicator variables; providing a comprehensive framework to validate control-flow transformations. Take the programs in Figure 1 as an example: the program on the left is a high-level program, and the program on the right can be an optimized pseudo-assembly that was obtained from the high-level program. Despite their different appearances, CF-GKAT is able to validate their equivalence with automata-based techniques. \displaystyle{\color[rgb]{0.0508,0.2773,0.6328}{\displaystyle\texttt{\small{if}}}}~t_{1}~{\color[rgb]{0.0508,0.2773,0.6328}{\texttt{\small{then}}}}~p; \displaystyle{\color[rgb]{0.0508,0.2773,0.6328}{\displaystyle\texttt{\small{while}}}}~t_{1}\lor t_{2}~{\color[rgb]{0.0508,0.2773,0.6328}{\texttt{\small{do}}}}~ \displaystyle{\color[rgb]{0.0508,0.2773,0.6328}{\displaystyle\texttt{\small{if}}}}~t_{1}\land\overline{t_{2}}~{\color[rgb]{0.0508,0.2773,0.6328}{\texttt{\small{then}}}}~(q;{\color[rgb]{0.5117,0.4648,0.0898}{\texttt{\small{assert}}}}~t_{1}\land\overline{t_{2}}); \displaystyle{\color[rgb]{0.0508,0.2773,0.6328}{\displaystyle\texttt{\small{else}}}}~p; \displaystyle{\color[rgb]{0.5117,0.4648,0.0898}{\displaystyle\texttt{\small{return}}}}; (a) A while -loop program. \displaystyle{\color[rgb]{0.0508,0.2773,0.6328}{\displaystyle\texttt{\small{if}}}}~t_{1}\lor t_{2}~{\color[rgb]{0.0508,0.2773,0.6328}{\texttt{\small{then}}}}~p; \displaystyle{\color[rgb]{0.0508,0.2773,0.6328}{\displaystyle\texttt{\small{else}}}}~{\color[rgb]{0.5117,0.4648,0.0898}{\texttt{\small{label}}}}\!~l; \displaystyle{\color[rgb]{0.0508,0.2773,0.6328}{\displaystyle\texttt{\small{if}}}}~t_{2}~{\color[rgb]{0.0508,0.2773,0.6328}{\texttt{\small{then}}}}~p;{\color[rgb]{0.5117,0.4648,0.0898}{\texttt{\small{goto}}}}\!~l; \displaystyle{\color[rgb]{0.0508,0.2773,0.6328}{\displaystyle\texttt{\small{else}}}}~{\color[rgb]{0.0508,0.2773,0.6328}{\texttt{\small{if}}}}~t_{1}~{\color[rgb]{0.0508,0.2773,0.6328}{\texttt{\small{then}}}}~{\color[rgb]{0.5117,0.4648,0.0898}{\texttt{\small{diverge}}}}; \displaystyle{\color[rgb]{0.5117,0.4648,0.0898}{\displaystyle\texttt{\small{return}}}}; (b) A goto program. Figure 1 : Two finite-trace equivalent CF-GKAT programs, where (q;\texttt{assert}~t_{1}\land\overline{t_{2}}) encodes the knowledge that the test t_{1}\land\overline{t_{2}} always holds after action q . Indeed, at the core of the success of languages like KAT , GKAT , and extensions thereof, is a strong automata-theoretic foundation. The original decision procedures of both GKAT and CF-GKAT rely on a special type of automaton introduced as the operational semantics of the languages— GKAT automata [ 52 , 39 ] . Concretely, both decision procedures first convert expressions into GKAT automata, then check the trace equivalence of the generated automata. Notably, the trace-equivalence checking for GKAT automata is sound and complete , that is, the algorithm outputs true if and only if the input automata are trace equivalent. Thus, improving the existing equivalence procedure for GKAT automata will not only speed up the decision procedure for GKAT , but also some of its variants. In this paper, we made two important improvements on the original algorithm for equivalence check of GKAT -automata, as outlined in Figure 2 . Firstly, we designed an on-the-fly algorithm for equivalence checking: the algorithm can terminate as soon as a counter example is encountered without iterating through the entire generated automata. Secondly, we lift the on-the-fly algorithm to a symbolic algorithm , which not only enjoys short-circuiting upon counter-examples, but also prevents the exponential blow-up with the addition of new primitive tests. In the following paragraphs, we will delve deeper into the challenges in designing these algorithms and our contributions. Normalization v.s. On-the-fly: originally, deciding trace equivalence requires a normalization procedure, which reroutes transitions that do not produce finite traces (e.g. infinite loops) into immediate rejection. This simple step introduces significant performance penalties: although GKAT automata can be generated on-the-fly [ 38 ] , normalization requires iterating through the entire automaton once, which nullifies the performance improvements of on-the-fly verification [ 15 ] . In Section 2.2 , we present our on-the-fly algorithm , which invokes normalization lazily : we only perform it when the bisimulation failed. This change allows the algorithm to halt immediately when a counter-example is encountered, greatly improving the efficiency in the negative case. Moreover, our normalization algorithm only iterates through the reachable states of the failed checks, instead of the entire automata, improving the performance in the positive cases as well. (CF-)GKAT Program GKAT Automata Normalized GKAT Automata Trace Equivalence Symbolic GKAT Automata Thompson’s Construction [ 39 , 52 ] Derivative [ 38 ] Normalization Bisimulation Concretization Definition 3 On-the-fly Symbolic Algorithm Figure 7 Symbolic Derivative Section 4 Appendix 0.C On-the-fly Figure 5 Figure 2 : A summary of algorithms mentioned in this paper: the original one is marked in red ; the on-the-fly is marked in blue ; and the symbolic on-the-fly is marked in green . Symbolic Equivalence Checking: GKAT and KAT automata both transition via atoms , which are truth assignments for all the primitive tests. This means the sizes of automata are exponential to the number of primitive tests. In Section 2.3 , we present the notion of symbolic GKAT automata , which groups collections of atoms using Boolean formulae, circumventing the exponential blow-up. Additionally, we also present a symbolic on-the-fly algorithm to determine the trace equivalence between two symbolic GKAT automata. We use a Boolean-formulae-based approach which contrasts with a more standard symbolic approach to KAT pioneered in SymKAT [ 33 ] using binary decision diagrams (BDDs). We will show that our approach opens the door to the use of arbitrary SAT solvers to store and compare Boolean expressions, which in turn leads to better performance than SymKAT (see Section 5 ) in checking the trace equivalence of GKAT expressions. Of course, as a trade-off, our symbolic equivalence checking algorithm currently only works on GKAT automata, instead of the more general KAT automata. Correctness: In Section 3 , we show that both our on-the-fly algorithm ( Figure 5 ) and symbolic on-the-fly algorithm ( Figure 7 ) for trace equivalence are sound and complete , i.e. they will produce neither false-positive nor false-negative with respect to trace equivalence. Additionally, we show that both of our algorithms can be tweaked to correctly check infinite-trace equivalence [ 37 ] , a useful notion of equivalence which SymKAT does not support. Expressions to Symbolic Automata: while the equivalence algorithm is designed for automata, one ultimately wants to reason about program equivalence, therefore a bridge between expressions and automata is needed. In Section 4 , we present an on-the-fly algorithm to generate symbolic GKAT automata from CF-GKAT program [ 52 ] , an extension of GKAT with non-local control-flow structures and indicator variables. The complexity of these extra constructs make the derivative construction for CF-GKAT quite intricate and not a simple instance of GKAT . Additionally, since GKAT is a subsystem of CF-GKAT , this algorithm also induces an on-the-fly generation algorithm for GKAT expressions. In a nutshell, in this paper we designed symbolic algorithms to overcome several crucial performance issues in the original decision procedure, while preserving the soundness and completeness guarantee. To demonstrate the efficiency of our approach, we provide a Rust implementation and compared it with state-of-the-art tools for (CF-)GKAT equivalence checking, as detailed in Section 5 . We will show that our implementation exhibits orders-of-magnitude improvements in both runtime and memory usage, and the flexibility to switch between different (UN)SAT solvers allows us to utilize the most efficient solvers for each specific scenario. Moreover, during our evaluation, we also identified a bug [ 34 ] in the industry standard decompiler Ghidra [ 30 , 34 ] demonstrating the real-world applicability of our tools. In the next section, we explain the motivations and intuitions behind our approaches with examples, and introduce primaries used in our development. 2 Overview In this section, we provide an overview of the paper’s main contributions through examples. In Section 2.1 , we introduce basic notations and explain the core motivation of our developments: to overcome two challenging inefficiencies in the original trace-equivalence algorithms for GKAT automata [ 39 ] : the lack of support for short-circuiting on counter-examples due to the “normalization” process and the exponential increase of transitions with the addition of primitive tests. In Sections 2.2 and 2.3 , we explain how we address the aforementioned problems in two stages. First, we propose a new trace-equivalence decision procedure, that only invokes the normalization when necessary. This crucial change not only enables short-circuiting on counter-examples, but also reduces the number of states needed to be checked. Second, we extend our algorithm to a novel symbolic representation of GKAT automata, where transitions with the same source and target are often combined into one, effectively mitigating the exponential growth of transitions, and enabling scaling to large programs. 2.1 Original CF-GKAT Decision Procedures We begin by briefly walking through original decision procedures for Guarded Kleene Algebra with Tests (GKAT) [ 39 ] and Control-flow GKAT ( CF-GKAT ) [ 52 ] , using the example CF-GKAT programs presented in Figure 1 , The original algorithm [ 52 ] first converts the CF-GKAT programs in Figure 1 into GKAT automata, where each state corresponds to a location in the program, and transitions are based on the current truth assignment of all the primitive tests. These truth assignments are represented as atoms [ 23 ] : for a finite set of primitive tests T\triangleq\{t_{1},t_{2},t_{3},\dots,t_{n}\} , atoms \mathbf{At} over T are sequences of all the tests (in a fixed order) in its positive or negative form: \alpha,\beta,\gamma\in\mathbf{At}=\{\tau_{1}~\tau_{2}~\tau_{3}~\dots~\tau_{n}\mid\tau_{i}\in\{t_{i},\overline{t_{i}}\}\}. Based on the given atom, a state in a GKAT automaton will either accept, denoted as {\mathbf{ret}} ; reject, denoted as \bot ; or transition to the next state while executing an action in \Sigma . Formally, GKAT automata consist of a finite set of states S , a start state s_{0}\in S , and a transition function: \zeta:S\to\mathbf{At}\to\{\bot,{\mathbf{ret}}\}+S\times\Sigma. We often use s\mathrel{\resizebox{}{}{{\hbox{\hskip 0.0pt\raise-5.0pt\hbox{{$\xRightarrow{\alpha}$}}}}}}{\mathbf{ret}} to denote \zeta(s)_{\alpha}={\mathbf{ret}} ; use s\lightning^{\alpha} to denote \zeta(s)_{\alpha}=\bot ; use s\mathrel{\raisebox{-2.0pt}{$\xrightarrow{\alpha\mid p}$}}s^{\prime} to denote \zeta(s)_{\alpha}=(s^{\prime},p) ; and use s\mathrel{\resizebox{}{}{{\hbox{\hskip 0.0pt\raise-2.0pt\hbox{{$\xhookrightarrow{\alpha}$}}}}}}r to denote \zeta(s)_{\alpha}=r . It is important to observe that the number of atoms is exponential with respect to the number of primitive tests, and so is the number of transitions in a GKAT automaton. For example, the programs in Figure 1 contains two primitive tests: t_{1} and t_{2} ; which gives 2^{2}=4 distinct atoms labelling the outgoing transitions of each state in the generated automata, as shown in Figure 3 . {\color[rgb]{0.1055,0.3672,0.125}s_{0}} {\color[rgb]{0,0,1}s_{1}} {\color[rgb]{0,0,1}s_{2}} {\color[rgb]{1,0,0}s_{3}} {\mathbf{ret}} {\mathbf{ret}} {\mathbf{ret}} \overline{t_{1}}\overline{t_{2}} \overline{t_{1}}\overline{t_{2}} \overline{t_{1}}\overline{t_{2}} t_{1}t_{2}\mid p t_{1}\overline{t_{2}}\mid p \overline{t_{1}}t_{2}\mid p t_{1}t_{2}\mid p \overline{t_{1}}t_{2}\mid p t_{1}\overline{t_{2}}\mid p t_{1}\overline{t_{2}}\mid p t_{1}\overline{t_{2}}\mid q t_{1}t_{2}\mid p \overline{t_{1}}t_{2}\mid p (a) The automaton for Figure 1(a) . {\color[rgb]{0.1055,0.3672,0.125}u_{0}} {\color[rgb]{0,0,1}u_{1}} {\color[rgb]{0,0,1}u_{2}} {\mathbf{ret}} {\mathbf{ret}} {\mathbf{ret}} \overline{t_{1}}\overline{t_{2}} \overline{t_{1}}\overline{t_{2}} \overline{t_{1}}\overline{t_{2}} t_{1}t_{2}\mid p \overline{t_{2}}t_{2}\mid p t_{1}\overline{t_{2}}\mid p t_{1}t_{2}\mid p \overline{t_{1}}t_{2}\mid p t_{1}t_{2}\mid p \overline{t_{1}}t_{2}\mid p (b) The automaton for Figure 1(b) . Figure 3 : The automata generated for programs in Figure 1 using the algorithm in [ 52 , Section 3] . We omit transitions that output rejection. All the dead states of the automata are highlighted in red and equivalent states are marked using the same colors. After generating the automata, the algorithm performs a process called normalization , which reroutes all transitions that cannot lead to acceptance into immediate rejection [ 39 ] . To identify these transitions, the algorithm iterates through the entire automaton and identifies all the dead states : states that never reaches acceptance; and then modifies all transitions to dead states into rejection. For instance, {\color[rgb]{1,0,0}s_{3}} is a dead state in Figure 3(a) , therefore the transition {\color[rgb]{0,0,1}s_{1}}\mathrel{\raisebox{-2.0pt}{$\xrightarrow{t_{1}\overline{t_{2}}\mid p}$}}{\color[rgb]{1,0,0}s_{3}} in Figure 3(a) will be modified to rejection {\color[rgb]{0,0,1}s_{1}}\lightning^{t_{1}\overline{t_{2}}} during normalization. Finally, to decide the trace equivalence of these programs ( Definition 1 ), the algorithm performs bisimulation [ 39 , Algorithm 1] on the normalized GKAT automata. In Figure 3 , we mark the trace equivalent states with the same color. Despite its simplicity, the original algorithm is sufficient to decide trace equivalence between two GKAT automata without producing false negatives or false positives; that is, it is correct or sound and complete [ 39 , 52 ] . Notably, normalization is necessary for this correctness result : if the transition into {\color[rgb]{1,0,0}s_{3}} is not removed, the pair of automata in Figure 3 will fail the bisimulation checking, even though they are indeed trace equivalent. In this work, we propose novel algorithms for ( CF) - GKAT equivalence that we will show scales to expressions with thousands of tests and actions, while preserving the simplicity, soundness, and completeness of the original one. Our algorithms are designed to solve the two aforementioned challenging performance problems that remained open since the work of 39 . 1. The original algorithm requires one iteration of the entire automata to perform normalization. This necessity forces the generation of the entire automata, preventing the use of techniques like derivatives, which enable short-circuiting on counter-examples and avoid generating the remaining automata. 2. The number of transitions is exponential to the number of primitive tests. In program with just tens of primitive tests, the generated automata can already contain more than thousands of outgoing transitions per state, resulting in inefficient storage and iteration. In the following subsections, we will delve deeper into these two problems through illustrative examples, and outline our solutions. We then demonstrate how our algorithm outperforms the original approaches, including the symbolic algorithm provided by 33 . Besides the performance improvement, our algorithm also preserves the soundness and completeness of the original algorithms, providing a strong theoretical guarantee for the correctness of our results. 2.2 When Normalization Flies On-the-fly automata generation techniques, like derivatives [ 9 , 4 , 25 ] , have long been an essential for efficient bisimulation construction. Since the automata are generated on-demand while checking for bisimulation, the generation process can stop when the bisimulation fails, avoiding unnecessary state generation [ 15 , 1 ] . \displaystyle{\color[rgb]{0.0508,0.2773,0.6328}{\displaystyle\texttt{\small{if}}}}~t_{1}~{\color[rgb]{0.0508,0.2773,0.6328}{\texttt{\small{then}}}}~p; \displaystyle{\color[rgb]{0.0508,0.2773,0.6328}{\displaystyle\texttt{\small{else}}}}~{\color[rgb]{0.5117,0.4648,0.0898}{\texttt{\small{label}}}}\!~l; \displaystyle{\color[rgb]{0.0508,0.2773,0.6328}{\displaystyle\texttt{\small{if}}}}~t_{2}~{\color[rgb]{0.0508,0.2773,0.6328}{\texttt{\small{then}}}}~p;{\color[rgb]{0.5117,0.4648,0.0898}{\texttt{\small{goto}}}}\!~l; \displaystyle{\color[rgb]{0.0508,0.2773,0.6328}{\displaystyle\texttt{\small{else}}}}~{\color[rgb]{0.0508,0.2773,0.6328}{\texttt{\small{if}}}}~t_{1}~{\color[rgb]{0.0508,0.2773,0.6328}{\texttt{\small{then}}}}~{\color[rgb]{0.5117,0.4648,0.0898}{\texttt{\small{diverge}}}} \displaystyle{\color[rgb]{0.5117,0.4648,0.0898}{\displaystyle\texttt{\small{return}}}}; (a) u_{0}^{\prime} u_{1}^{\prime} u_{2}^{\prime} {\mathbf{ret}} {\mathbf{ret}} {\mathbf{ret}} \overline{t_{1}}t_{2} \overline{t_{1}}\overline{t_{2}} \overline{t_{1}}\overline{t_{2}} \overline{t_{1}}\overline{t_{2}} t_{1}t_{2}\mid p t_{1}\overline{t_{2}}\mid p t_{1}t_{2}\mid p \overline{t_{1}}t_{2}\mid q t_{1}t_{2}\mid p \overline{t_{1}}t_{2}\mid p (b) Figure 4 : On the left, an erroneous version of the low-level program that is not trace equivalent to Figure 1(a) , where the t_{1}\lor t_{2} in the first if-statement is mistaken as t_{1} . On the right, the corresponding automaton (with omitted reject transitions). The normalization algorithm needed in GKAT equivalence checking requires iterating through the entire automaton prior to bisimulation checking , and thus forces the generation of the entire automaton, even when a counter-example might have been encountered very early in the bisimulation. For instance, consider the program in Figure 4 , which erroneously uses t_{1} as the condition of the first if-statement, instead of t_{1}\lor t_{2} in Figure 1(b) . This mistake makes the program in Figure 4 no longer equivalent to the one in Figure 1(a) . Indeed, we can conclude the inequivalence of their respecitve automata, presented in Figures 4(b) and 3(a) ; by examining the t_{1}\overline{t_{2}} transition from the start states s_{0} and u_{0}^{\prime} . To show that these two automata are not trace equivalent, we notice that the start state u_{0}^{\prime} accepts the atom t_{1}\overline{t_{2}} , which implies that t_{1}\overline{t_{2}} is a trace of u_{0}^{\prime} . In contrast, the start state {\color[rgb]{0.1055,0.3672,0.125}s_{0}} executes the action p on atom t_{1}\overline{t_{2}} , excluding t_{1}\overline{t_{2}} to be a trace of {\color[rgb]{0.1055,0.3672,0.125}s_{0}} . However, despite this inequality being witnessed by two transitions from the start state, the original algorithm still requires generating the entire automata in order to perform normalization. In this paper, we introduce both a naive and a symbolic algorithm that avoid this issue. The non-symbolic version of our trace-equivalence algorithm, presented in Figure 5 , prevents generating the remaining automaton upon encountering a counter-example. This efficiency improvement is achieved by only invoking normalization, or dead-state detection, when necessary. In Figure 5 , the primary checks are listed on lines 8-13, where we attempt to verify the bisimulation conditions for each atom, and cache all the checked states using a union-find data structure, inspired by previous bisimulation works [ 39 , 21 ] . When the bisimulation checks fail, the algorithm invokes dead state detection on the mismatched states, via the isDead function. For example, the condition on line 10 in Figure 5 states when s\mathrel{\raisebox{-2.0pt}{$\xrightarrow{\alpha\mid p}$}}s^{\prime} yet u\lightning^{\alpha} , then the s and u are trace-equivalent only if s^{\prime} is dead. In addition to the bisimulation check, this algorithm can sometimes take a shortcut, as detailed on lines 4-7: if one of the states s,u is known to be dead, then s and u are trace equivalent if and only if the other state is also dead; saving us from further bisimulation checks. 1: function equiv ( s,u ) 2: if rep ( s ) = rep ( u ) then return true 3: union (s, u); 4: if knownDead ( s ) then return isDead ( u ) 5: if knownDead ( u ) then return isDead ( s ) 6: return \forall\alpha\in\mathbf{At} 7: s\mathrel{\resizebox{}{}{{\hbox{\hskip 0.0pt\raise-5.0pt\hbox{{$\xRightarrow{\alpha}$}}}}}}{\mathbf{ret}}\text{ iff }u\mathrel{\resizebox{}{}{{\hbox{\hskip 0.0pt\raise-5.0pt\hbox{{$\xRightarrow{\alpha}$}}}}}}{\mathbf{ret}}\mathrel{\&\!\&} 8: s\mathrel{\raisebox{-2.0pt}{$\xrightarrow{\alpha\mid p}$}}s^{\prime}\text{ and }u\lightning^{\alpha}\text{ implies }\textsc{isDead}(s^{\prime})\mathrel{\&\!\&} 9: u\mathrel{\raisebox{-2.0pt}{$\xrightarrow{\alpha\mid p}$}}u^{\prime}\text{ and }s\lightning^{\alpha}\text{ implies }\textsc{isDead}(u^{\prime})\mathrel{\&\!\&} 10: s\mathrel{\raisebox{-2.0pt}{$\xrightarrow{\alpha\mid p}$}}s^{\prime}\text{ and }u\mathrel{\raisebox{-2.0pt}{$\xrightarrow{\alpha\mid q}$}}u^{\prime}\text{ and }p\neq q\text{ implies }\textsc{isDead}(s^{\prime})\text{ and }\textsc{isDead}(u^{\prime})\mathrel{\&\!\&} 11: s\mathrel{\raisebox{-2.0pt}{$\xrightarrow{\alpha\mid p}$}}s^{\prime}\text{ and }u\mathrel{\raisebox{-2.0pt}{$\xrightarrow{\alpha\mid p}$}}u^{\prime}\text{ implies }\textsc{equiv}(s^{\prime},u^{\prime}) Figure 5 : Non-symbolic on-the-fly bisimulation algorithm. The call isDead ( s ) first checks whether s is in the set of cached “known-dead states” ( knownDead ( s )): if so, returns true, else it runs a DFS to see if the state s can reach any accepting state; if s cannot reach an accepting state, all the reachable states of s are cached as known-dead states. The call union ( s,u ) links s,u to the same representative in the union-find object, and rep ( s ) returns the representative of s from said union-find object. “iff”, “and”, “implies” are the respective logical operators on Booleans, and \&\!\& is the logical conjunction. The simple change underlying the new algorithm has big gains as we can now benefit from on-the-fly generation of automata, and terminate immediately after a counter-example. We revisit the automata in Figures 3 and 4(b) using this new algorithm, and assume these automata are generated on-the-fly. If the first explored atom is t_{1}\overline{t_{2}} , then the transitions from the start states ( {\color[rgb]{0.1055,0.3672,0.125}s_{0}}\mathrel{\raisebox{-2.0pt}{$\xrightarrow{t_{1}\overline{t_{2}}\mid p}$}}{\color[rgb]{0,0,1}s_{1}} and u_{0}^{\prime}\mathrel{\resizebox{}{}{{\hbox{\hskip 0.0pt\raise-4.0pt\hbox{{$\xRightarrow{t_{1}\overline{t_{2}}}$}}}}}}{\mathbf{ret}} ) will immediately violate the first condition on line 9 of Figure 5 , allowing us to short-circuit the algorithm and conclude that the input programs are not trace equivalent, without generating any other states and transitions. Remark 1 In the previous example, we assumed the algorithm checks atom t_{1}\overline{t_{2}} first. However, this assumption is not necessary for the symbolic case, since all the atoms leading to immediate acceptance are grouped into Boolean expressions; allowing the algorithm to always check the terminating atoms first. Besides early termination on negative cases, our algorithm can offer benefits in the positive cases as well, since isDead only checks the reachable states of the discrepancy. For example, consider the automata in Figures 3(a) and 3(b) : the original algorithm iterates through all 7 states in both automata for normalization, then checks bisimulation on the 6 live states to determine their equivalence. Our algorithm only iterates through all the 7 states once, including one invocation of isDead on {\color[rgb]{1,0,0}s_{3}} , nearly halving the complexity to confirm equivalence. In the extreme case, when the two input programs generate bisimilar GKAT automata [ 39 ] , the bisimulation condition check will always succeed, preventing the invocation of dead-state checking in our algorithm. Thus, our algorithm only needs one iteration of the automata to confirm the equivalence of bisimilar automata, whereas the original algorithm requires two passes: one for normalization, and the next for bisimulation. This improvement is crucial for several applications, as many program-transformation algorithms often produce output program that is bisimilar to the input [ 14 , 24 ] i.e. they do not discard actions that will eventually diverge. Hence, our algorithm will bring a significant performance improvement when validating the correctness of these transformations, which involves validating the equivalence of the input and output program. Remark 2 If the functions isDead and knownDead are substituted with the constant false function, the algorithm presented in Figure 5 will detect a finer notion of equivalence, namely infinite-trace equivalence (coinciding with bisimularity) [ 38 ] , which accounts for actions in non-terminating executions. For instance, this semantics can distinguish between expressions such as while true do p and while true do q. This modification is also applicable to the symbolic algorithm in Figure 7 , resulting in a efficient algorithm for infinite-trace equivalence. However, we do not investigate these generalizations in our evaluation, as the existing tools we compared against do not support infinite-trace equivalence. 2.3 Symbolic Approach For GKAT Automata The transitions of both GKAT and KAT automata are indexed by atoms; and since atoms are truth assignments to all the primitive tests , (G)KAT automata obtained from the original constructions can often blow-up exponentially with the increase of primitive tests. In fact, this problem is noted in several previous works [ 39 , 52 ] , and both works hypothesized that symbolic techniques can aid in this regard. Consider the transitions from {\color[rgb]{0.1055,0.3672,0.125}s_{0}} to {\color[rgb]{0,0,1}s_{1}} in Figure 3(a) , as shown on {\color[rgb]{0.1055,0.3672,0.125}s_{0}}\xrightarrow{t_{1}t_{2}\mid p}{\color[rgb]{0,0,1}s_{1}} {\color[rgb]{0.1055,0.3672,0.125}s_{0}}\xrightarrow{t_{1}\overline{t_{2}}\mid p}{\color[rgb]{0,0,1}s_{1}} T=\{t_{1},t_{2}\} {\color[rgb]{0.1055,0.3672,0.125}s_{0}}\xrightarrow{t_{1}t_{2}t_{3}\mid p}{\color[rgb]{0,0,1}s_{1}} {\color[rgb]{0.1055,0.3672,0.125}s_{0}}\xrightarrow{t_{1}t_{2}\overline{t_{3}}\mid p}{\color[rgb]{0,0,1}s_{1}} {\color[rgb]{0.1055,0.3672,0.125}s_{0}}\xrightarrow{t_{1}\overline{t_{2}}t_{3}\mid p}{\color[rgb]{0,0,1}s_{1}} {\color[rgb]{0.1055,0.3672,0.125}s_{0}}\xrightarrow{t_{1}\overline{t_{2}}\overline{t_{3}}\mid p}{\color[rgb]{0,0,1}s_{1}} T=\{t_{1},t_{2},t_{3}\} adding unused t_{3} the right. These transitions correspond to the first if statement in Figure 1(a) , namely \texttt{if}~t_{1}~\texttt{then}~p : when t_{1} is true, the state {\color[rgb]{0.1055,0.3672,0.125}s_{0}} will transition to {\color[rgb]{0,0,1}s_{1}} and execute p , regardless of the truth value of t_{2} . However, both transitions have to include t_{2} in the atom that labels them. Even worse, the number of transitions from {\color[rgb]{0.1055,0.3672,0.125}s_{0}} to {\color[rgb]{0,0,1}s_{1}} will double when adding an unused primitive test t_{3} , because atoms are defined to carry the truth assignment of every primitive test. This problem is not exclusive to GKAT and some solutions have been explored. Indeed, the seminal work of 33 introduced an alternative presentation of KAT automata using Binary Decision Diagrams (BDDs) [ 8 ] , which was also generalized to NetKAT [ 29 ] . However, the construction of Pous requires the use of BDDs when comparing Boolean expressions, and we aim to provide a more modular approach by preserving the Boolean expressions. Our symbolic automata are designed to carry Boolean formulae on the transitions, allowing the algorithm to leverage arbitrary (UN)SAT solvers, including BDD-based solvers and other more efficient ones. {\color[rgb]{0.1055,0.3672,0.125}(p+_{t_{1}}1)\fatsemi\mathrm{loop}} {\color[rgb]{0,0,1}\mathrm{loop}} {\color[rgb]{1,0,0}(t_{1}\land\overline{t_{2}})\fatsemi\mathrm{loop}} {\mathbf{ret}} {\mathbf{ret}} \overline{t_{1}}\land\overline{t_{2}} \overline{t_{1}}\land\overline{t_{2}} t_{1}\mid p \overline{t_{1}}\land t_{2}\mid p t_{2}\mid p t_{1}\land\overline{t_{2}}\mid q 0\mid p t_{1}\land\overline{t_{2}}\mid q (a) Symbolic GKAT automaton. {\color[rgb]{0.1055,0.3672,0.125}(p+_{t_{1}}1)\fatsemi\mathrm{loop}} {\color[rgb]{0,0.5,0.5}t_{1}} {\color[rgb]{0,0.5,0.5}t_{2}} \color[rgb]{0,0,1}\mathrm{loop} \color[rgb]{0,0.5,0.5}t_{1} \color[rgb]{1,0,0}(t_{1}\land\overline{t_{2}})\fatsemi\mathrm{loop} \color[rgb]{0,0.5,0.5}t_{2} {\mathbf{ret}} {\mathbf{ret}} \overline{t_{1}}\land\overline{t_{2}} \overline{t_{1}}\land\overline{t_{2}} p p q q (b) SymKAT [ 33 ] automaton. Figure 6 : A comparison between symbolic GKAT and SymKAT automata using the example in Figure 1(a) . We use “ \mathrm{loop} ” to refer to the while loop in Figure 1(a) . In Figure 6(a) , we present the symbolic GKAT automata generated from the program in Figure 1(a) , using symbolic derivative described in Section 4 . Compare to the GKAT automaton generated by the original algorithm in Figure 3(a) , our new automaton is more compact in several ways. Firstly, two trace-equivalent states {\color[rgb]{0,0,1}s_{1}} and {\color[rgb]{0,0,1}s_{2}} are merged into one state {\color[rgb]{0,0,1}\mathrm{loop}} . This efficiency is due to the derivative construction generally producing more compact automata than other original constructions, e.g. Thompson’s construction [ 31 ] . Second, multiple transitions between the same states are consolidated into Boolean {\color[rgb]{0.1055,0.3672,0.125}s_{0}}\mathrel{\raisebox{-2.0pt}{$\xrightarrow{t_{1}t_{2}\mid p}$}}{\color[rgb]{0,0,1}s_{1}} {\color[rgb]{0.1055,0.3672,0.125}s_{0}}\mathrel{\raisebox{-2.0pt}{$\xrightarrow{t_{1}\overline{t_{2}}\mid p}$}}{\color[rgb]{0,0,1}s_{1}} concrete transitions {\color[rgb]{0.1055,0.3672,0.125}(p+_{t_{1}}1)\fatsemi\mathrm{loop}}\mathrel{\raisebox{-2.0pt}{$\xrightarrow{t_{1}\mid p}$}}{\color[rgb]{0,0,1}\mathrm{loop}} symbolic transitions concretize expressions ; intuitively, a Boolean expression represents the collection of atoms that satisfies them. For example, the two transitions from \color[rgb]{0.1055,0.3672,0.125}s_{0} to \color[rgb]{0,0,1}s_{1} in Figure 3(a) is merged into one in Figure 6(a) , as shown on the left, where t_{1}t_{2} and t_{1}\overline{t_{2}} are the two atoms that satisfy the Boolean expression t_{1} . Unlike the non-symbolic case, the addition of an unused primitive test t_{3} will not enlarge the symbolic automata; thereby avoiding the exponential size blowup of the GKAT automata. To decide the trace equivalence of symbolic GKAT automata, we lift the non-symbolic algorithm in Figure 5 to the symbolic setting, which is presented in Figure 7 , where \rho(s) contains all the atoms that are rejected by s , and \epsilon(s) contains all the Boolean expression that s accepts (see Section 3.3 for details). As mentioned in Remark 1 , the algorithm will immediately conclude that s is not trace-equivalent to u when there exists an atom \alpha , s.t. s\mathrel{\resizebox{}{}{{\hbox{\hskip 0.0pt\raise-5.0pt\hbox{{$\xRightarrow{\alpha}$}}}}}}{\mathbf{ret}} and u\mathrel{\raisebox{-2.0pt}{$\xrightarrow{\alpha\mid p}$}}u^{\prime} ; since that would imply \alpha\in\bigvee\varepsilon(s) but \alpha\notin\bigvee\varepsilon(u) , thus \bigvee\varepsilon(s)\not\equiv\bigvee\varepsilon(u) , contradicting the first requirement on line 9 of the symbolic algorithm. 1: function equiv ( s,u ) 2: if rep ( s ) = rep ( u ) then return true; 3: union ( s , u ); 4: if knownDead ( s ) then return isDead ( u ) 5: if knownDead ( u ) then return isDead ( s ) 6: return 7: \bigvee\varepsilon(s)\equiv\bigvee\varepsilon(u)\mathrel{\&\!\&} 8: s\mathrel{\raisebox{-2.0pt}{$\xrightarrow{b\mid p}$}}s^{\prime}\text{ and }(b\land\rho(u))\not\equiv 0\text{ implies {isDead}($s^{\prime}$)}\mathrel{\&\!\&} 9: u\mathrel{\raisebox{-2.0pt}{$\xrightarrow{b\mid p}$}}u^{\prime}\text{ and }(b\land\rho(s))\not\equiv 0\text{ implies {isDead}($u^{\prime}$)}\mathrel{\&\!\&} 10: s\mathrel{\raisebox{-2.0pt}{$\xrightarrow{b\mid p}$}}s^{\prime}\text{, }u\mathrel{\raisebox{-2.0pt}{$\xrightarrow{a\mid q}$}}u^{\prime}\text{, }b\land a\not\equiv 0\text{, and }p\neq q\text{ implies {isDead}($s^{\prime}$), {isDead}($u^{\prime}$)}\mathrel{\&\!\&} 11: s\mathrel{\raisebox{-2.0pt}{$\xrightarrow{b\mid p}$}}s^{\prime}\text{ and }u\mathrel{\raisebox{-2.0pt}{$\xrightarrow{a\mid p}$}}u^{\prime}\text{ and }b\land a\not\equiv 0\text{ implies }\text{{equiv}($s^{\prime},u^{\prime}$)} Figure 7 : Symbolic on-the-fly bisimulation algorithm, lifting the algorithm in Figure 5 to symbolic GKAT automata. We use knownDead and isDead to denote dead-state detection: isDead ( s ) runs a DFS on all the non-blocking transitions ( Remark 4 ) from s , and return if s can reach an accepting state u , which is checked by \bigvee\varepsilon(u)\not\equiv 0 . We also present the corresponding SymKAT automaton [ 33 ] in Figure 6(b) , in which all Boolean expressions are unfolded into BDDs during the generation process, creating several intermediate nodes marked by {\color[rgb]{0,0.5,0.5}t_{1}} and {\color[rgb]{0,0.5,0.5}t_{2}} . Our symbolic GKAT automaton preserves the Boolean expressions on transitions, providing the flexibility to leverage external tools for their efficient representation and satisfiability solving. In Section 5 , we detailed our implementation which offers orders-of-magnitude performance improvement over SymKAT, in both runtime and memory consumption using miniSAT [ 7 ] and a state-of-the-art BDD solver [ 26 , 42 ] . Notably, our approach enables the user to select the most efficient solver for specific tasks, and to employ high - performance BDD implementations as black - boxes—capabilities lacking in prior BDD - based methods. Roadmap for the rest of the paper . In the current section, we illustrated our approaches through concrete examples. In the rest of the paper, we will delve deeper into the formalism, including the correctness guarantees of our symbolic and non-symbolic algorithm, their complexity, and the on-the-fly symbolic automata constructions for CF-GKAT . Section 3 proves the termination, soundness, completeness, and complexity of our decision procedures, and compares it with prior approaches. Section 4 provides an on-the-fly algorithm to generate symbolic GKAT automata from CF-GKAT programs. Despite its complexity, we are able to give an efficient decision procedure for CF-GKAT based on our framework. Section 5 provides more details on our implementations, and our evaluation results against the current tools to check (CF-)GKAT equivalences. 3 Correctness and Complexity In this section, we will first provide some comparison with the previous decision procedure by 39 and prove that both of our algorithms in Figures 5 and 7 are sound and complete. Additionally, as mentioned in Remark 2 , these algorithms can also be adapted to check for infinite-trace equality [ 38 ] , thus we prove the correctness of these variants as well. Details of these correctness proofs can be found in Appendices 0.A and 0.B . Finally, we also discuss the theoretical complexity of both the symbolic and non-symbolic algorithms; whereas the real-world performances of our implementations are presented in Section 5.2 . 3.1 Comparison With Previous Decision Procedures In this section, we outline the tradeoffs and advantages of our non-symbolic decision procedure v.s. the original procedures proposed by 39 . Differences in complexity . In the worst case, all calls to isDead in our algorithm will iterate through the entire automata at most once, thanks to the caching of explored states; and the equiv function will again iterate through all the states at most once, since explored states are cached via the union-find object [ 21 ] . In the same vein, the original algorithm will also make two passes in the worst case: one for normalization and one for bisimulation. Unfortunately, {s_{0}} {s_{1}} {s_{2}} \alpha\mid p \alpha\mid p \color[rgb]{1,0,0}\alpha\mid p {u_{0}} {u_{1}} {u_{2}} \alpha\mid p \alpha\mid p \color[rgb]{1,0,0}\alpha\mid q when the automata have many dead states, the original algorithm can outperform our new algorithm. Take the pair of GKAT automata on the left, these automata are indeed trace-equivalent, despite s_{2} and u_{2} executes different actions (transition marked in red ), since all their states are dead . The original algorithm [ 39 ] will iterate through both automata (6 states) for the normalization, then conclude that all the states are dead; then in the bisimulation phase, only the start states s_{0} and u_{0} is checked. In total, the original algorithm performed 7 checks, including 6 states for normalization and 1 pair of states for bisimulation. Yet, the new algorithm will first check the transition of the pairs (s_{0},u_{0}) and (s_{1},u_{1}) , then because s_{2} and u_{2} executes different actions, failing the premise on line 12 of Figure 5 and invoking {\textsc{isDead}}(s_{2}) and {\textsc{isDead}}(u_{2}) . Our new algorithm will proceed to iterate through both automata again, to confirm that s_{2} and u_{2} are dead. Thus, the new algorithm performs 9 checks : 3 pairs of state during bisimulation, and 6 states during liveness checking; exceeding the 7 checks performed by the original algorithm. When taking the number of primitive tests into account, our algorithm achieves PSPACE complexity, by storing one atom at a time, instead of storing the entire automaton for normalization. This complexity represents a theoretical speedup over the original EXPSPACE algorithm given by 39 . Although it is known that the complexity of GKAT is within PSPACE using the decision procedure for KAT [ 10 ] , leveraging Savitch’s theorem; our algorithm is the first concrete PSPACE algorithm for GKAT equivalence. However, the worst-case complexity does not necessarily reflect real-world performance. For example, our algorithm only explores the reachable states of the mismatched in bisimulation (see Section 2.2 ) instead of the entire automata, this often leads to fewer explored states in examples like Figure 3 . Additionally, many real-world transformations produce bisimilar programs, since it is a stronger equivalence than trace equivalence; in these cases, our algorithm skips dead state detection entirely, potentially halving the complexity of the original algorithm. Differences in implementation . Despite its simple description, the normalization procedure is comparatively complex to implement. Consider implementation by 53 : first, the algorithm makes one pass to identify all the accepting states, and produces a backward map, which maps every state s to all states that transitions to s ; then with the backward map, the algorithm performs a reverse search from accepting states, marking the reachable states as live states; finally, the algorithm executes another forward pass to reroute all the transition to dead state, i.e. those are not marked as live, into rejection. The backward map and additional passes are necessary because the normalization procedure requires the identification of all the live states . And since liveness is a global property (a property that cannot be determined by only inspecting a individual state and its transitions), it is unclear how to identify all the live/dead states without an additional pass of the automata. Our algorithm, on the other hand, forgoes identifying the liveness of all the states, removing the need for a backward map and additional passes. Specifically, isDead only checks the liveness of one state at a time: it continues when detecting a dead state; halts the entire equivalence check otherwise. Additionally, since {\textsc{isDead}}(s) explore and stores all the reachable states from s , if s is dead, we can mark all its reachable state as dead, allowing isDead to iterate through the automata at most once, no matter how many times it is called. The same property doesn’t hold for live states: dead states can be reachable from live ones. These intricate designs allow our simple algorithm to not only outperform the original algorithm in many real-world tasks, but also provide simpler implementations. Challenges in proving correctness . However, this efficiency also introduces significant challenge in the correctness proof: although the intuition behind our algorithm is simple, our algorithm no longer explicitly identifies a bisimulation on normalized GKAT automata, which underpins the correctness result of 39 . Indeed, proving our algorithm yields such bisimulation is challenging; instead, we show conditions in our algorithm defines a progression [ 32 ] , and that trace equivalence is the maximal invariant of this progression. This approach not only provides a sufficiently strong induction hypothesis to establish the desired results, but also enables the use of up-to technique [ 32 ] , an important framework to justify the use of union-find data-structure. Additionally, we also resolved a significant challenge in applying the up-to technique: because its subtlety, the progression defined by our algorithm is no longer compatible with the transitive closure, which we demonstrate in Example 2 . To solve this problem, we show that transitive closure satisfy a weaker condition than compatiblity, but nevertheless allows us to utilize up-to technique in our correctness proof. 3.2 Correctness of the Non-symbolic Algorithm In this section, we offer a sketch of the correctness of the algorithm in Figure 5 , to provide intuition. The complete proof can be found in Appendix 0.A . Definition 1 (Trace Semantics [ 39 ] ) Fix a GKAT automaton A\triangleq(S,s_{0},\zeta) , the finite trace semantics \llbracket s\rrbracket for a state s\in S is defined as follows: if s\mathrel{\resizebox{}{}{{\hbox{\hskip 0.0pt\raise-5.0pt\hbox{{$\xRightarrow{\alpha}$}}}}}}{\mathbf{ret}} , then \alpha\in\llbracket s\rrbracket ; if s\mathrel{\raisebox{-2.0pt}{$\xrightarrow{\alpha\mid p}$}}s^{\prime} and w\in\llbracket s^{\prime}\rrbracket , then \alpha p\cdot w\in\llbracket s\rrbracket . Two states s and u are trace equivalent when \llbracket s\rrbracket=\llbracket u\rrbracket . Our proof uses coinduction up-to [ 32 , 6 ] . First, we define an instance of progression [ 32 ] : for a pair of relations over state sets R,R^{\prime}\subseteq S\times U , we say that R progresses into R^{\prime} when all the conditions from lines 9-13 in Figure 5 holds for all atoms, except the last condition is replaced by s\mathrel{\raisebox{-2.0pt}{$\xrightarrow{\alpha\mid p}$}}s^{\prime} and u\mathrel{\raisebox{-2.0pt}{$\xrightarrow{\alpha\mid p}$}}u^{\prime} implies (s^{\prime},u^{\prime})\in R^{\prime} . We write R\rightarrowtail R^{\prime} when R progresses into R^{\prime} ; and we say R is an invariant when R\rightarrowtail R . Then we prove two core theorems (1) trace equivalence is the maximal invariant in Theorem 0.A.5 ; (2) the equivalence closure e is “sound” with respect to \rightarrowtail in Corollary 2 , i.e. R\rightarrowtail e(R) implies R is contained in an invariant, and thereby contained in the trace equivalence relation. Then we show that the algorithm in Figure 5 indeed identifies an invariant. We let R denote all the pairs of states that have been sent into the union function and let R_{0} denote the R at the start of the function equiv . If {\textsc{equiv}}(s,u) returns true, then we can derive (s,u)\in e(R) and (R\setminus R_{0})\rightarrowtail e(R) both hold after the program terminates. Finally, we assume that equiv starts with a fresh union-find object, R_{0} will be empty and R\rightarrowtail e(R) , implying R is contained in an invariant. Then because (s,u)\in R , the states s and u are trace-equivalent. Theorem 3.1 (Correctness) equiv in Figure 5 always terminates when the input states are from finite GKAT automata; and the algorithm is sound and complete , in the sense that (1) {\textsc{equiv}}(s,u) returns true iff s and u are trace-equivalent; (2) when we replace isDead and knownDead with false, {\textsc{equiv}}(s,u) returns true if and only if s and u are infinite-trace equivalent i.e. bisimilar. Our non-symbolic algorithm improves upon the original GKAT decision procedure, while preserving correctness; but like the original algorithm it does not scale well with a large number of primitive tests. To address this issue, we introduce a symbolic decision procedure, which is outlined in section 2.3 . 3.3 Symbolic Automata and Its Equivalence Algorithm Before we introduce the correctness proof, we first formally define symbolic GKAT automata , where instead of giving a transition result for every atom, we compact atoms that lead to the same results into Boolean expressions . Definition 2 (Symbolic GKAT Automata) A symbolic GKAT automaton over primitive actions \Sigma and primitive tests T consists of four components: a finite state set S , a start state s_{0}\in S , an accepting function \varepsilon , and a transition function \delta with the following types: \displaystyle\varepsilon \displaystyle:S\to\mathcal{P}({\mathsf{BExp}_{T}}); \displaystyle\delta \displaystyle:S\to\mathcal{P}({\mathsf{BExp}_{T}\times S\times\Sigma}), where \mathcal{P}({X}) represents the power set of X . In addition, we require a disjointedness condition : if we take any two distinct elements r_{1},r_{2}\in\varepsilon(s)\cup\delta(s), then Boolean expressions within r_{1},r_{2} need to be disjoint i.e. their conjunction is equivalent to falsehood under Boolean Algebra. We inherit the notation of non-symbolic GKAT automata: we write s\mathrel{\resizebox{}{}{{\hbox{\hskip 0.0pt\raise-5.0pt\hbox{{$\xRightarrow{b}$}}}}}}{\mathbf{ret}} when b\in\varepsilon(s) and s\mathrel{\raisebox{-2.0pt}{$\xrightarrow{b\mid p}$}}s^{\prime} when (b,s^{\prime},p)\in\delta(s) . In Figure 6(a) , we provided an example of symbolic GKAT automata, and the accepting function \varepsilon and transition function \delta for the state {\color[rgb]{0,0,1}\mathrm{loop}} here as an example: \displaystyle\varepsilon({\color[rgb]{0,0,1}\mathrm{loop}}) \displaystyle=\{\overline{t_{1}}\land\overline{t_{2}}\} \displaystyle\delta({\color[rgb]{0,0,1}\mathrm{loop}}) \displaystyle=\{(t_{2},{\color[rgb]{0,0,1}\mathrm{loop}},p),(t_{1}\land\overline{t_{2}},{\color[rgb]{1,0,0}(t_{1}\land\overline{t_{2}})\fatsemi\mathrm{loop}},q).\} As discussed in Section 2.3 , s\mathrel{\raisebox{-2.0pt}{$\xrightarrow{b\mid p}$}}s^{\prime} represents that s\mathrel{\raisebox{-2.0pt}{$\xrightarrow{\alpha\mid p}$}}s^{\prime} for all \alpha satisfying b ; and s\mathrel{\resizebox{}{}{{\hbox{\hskip 0.0pt\raise-5.0pt\hbox{{$\xRightarrow{b}$}}}}}}{\mathbf{ret}} represents that s\mathrel{\resizebox{}{}{{\hbox{\hskip 0.0pt\raise-5.0pt\hbox{{$\xRightarrow{\alpha}$}}}}}}{\mathbf{ret}} for all \alpha satisfying b , and the rest of the atoms lead to rejection. We do not include the rejection function \rho in the signature of the symbolic automata, since it can be computed from \varepsilon and \delta : \rho(s)\triangleq\bigwedge\{\overline{b}\mid b\in\varepsilon(s)\}\cup\{\overline{b}\mid(b,s^{\prime},p)\in\delta(s)\}. To give semantics to a symbolic GKAT automaton, we will first unfold it into a concrete GKAT automaton , and then compute the semantics of said concrete automaton. Indeed, the concretization process exactly defines the operation to unfold all Boolean expressions into atoms. Definition 3 (Concretization) Given a symbolic GKAT automaton, with start state s_{0}\in S , accepting function \varepsilon , and a transition function \delta ; then we can define a GKAT automaton which is the concrete automaton, with the same state set S and start state s_{0} and the following transition function: \zeta_{\varepsilon,\delta}(s,\alpha)\triangleq\begin{cases}{\mathbf{ret}}&\text{if there exists }b\in\varepsilon(s),\alpha\text{ satisfies }b\\ (s^{\prime},p)&\text{if there exists }(b,s^{\prime},p)\in\delta(s),\alpha\text{ satisfies }b\\ \bot&\text{otherwise}\end{cases} Because of the disjointedness condition, the concretization of symbolic automata is well-defined: for all state s\in S , there exists at most one Boolean expression b\in\varepsilon(s) or transition (b,s^{\prime},p)\in\delta(s) s.t. \alpha satisfies b . Remark 3 (Determinacy) The concretization of any symbolic GKAT automaton, like every other GKAT automaton, will deterministically accept, reject, or transition, when given a state and an atom. Thus, despite the use of power set in its signature, symbolic GKAT automata are still deterministic , making our derivative constructions in Section 4 more akin to the deterministic derivative by 9 than the nondeterministic version by 4 . Remark 4 (Blocked Transition) Transitions s\mathrel{\raisebox{-2.0pt}{$\xrightarrow{b\mid p}$}}s^{\prime} where b\equiv 0 are called blocked . For example, {\color[rgb]{1,0,0}(t_{1}\land t_{2})\fatsemi\mathrm{loop}}\mathrel{\raisebox{-2.0pt}{$\xrightarrow{0\mid p}$}}{\color[rgb]{0,0,1}\mathrm{loop}} in Figure 6(a) is blocked. Removing such transitions will not change the concrete automata, as there doesn’t exist an atom \alpha\leq 0 . Thus, we do not include blocked transition in future drawings of automata and in our implementation (see Section 5.1 ). By definition, the equivalence of symbolic GKAT automata coincides with the equivalence of the concrete automata. Therefore, the correctness of the symbolic algorithm ( Figure 7 ) can be reduced into the correctness of the non-symbolic algorithm ( Figure 5 ). Indeed, the strategy for soundness of completeness proof is by defining a symbolic progression , which corresponds to the conditions checked on line 9-13 in the symbolic algorithm. Then we show the correspondence between symbolic progression on the symbolic automata and progression on the concrete automata; this allows us to derive the same post-condition as the non-symbolic correctness on the concrete automata, which concludes the correctness. Theorem 3.2 (Correctness) The algorithm in Figure 7 always terminates if the inputs are from finite GKAT automata, and it is sound and complete : (1) equiv returns true if and only if the inputs are trace-equivalent in the concretization; (2) if isDead and knownDead in Figure 7 is replaced with false, then equiv returns true if and only if the inputs are bisimilar in the concretization. Complexity analysis of symbolic algorithm . Since the algorithm require solving both SAT and UNSAT problems, our algorithm in Figure 7 is technically in PSPACE with respect to the number of primitive tests, even though both SAT and UNSAT are reasonably efficient in real-world applications. Our algorithm achieves a complexity improvement over SymKAT [ 33 ] , which despite its efficiency is technically in EXPSPACE. This improvement is due to us opt to not completely unfold Boolean expressions into BDDs, which can be exponential in the number of primitive tests in the worst case. This theoretical improvement is also reflected in real-world performance in our evaluations, where we observed orders-of-magnitude speed up compare to SymKAT, as detailed in Section 5.2 . 4 Application: Decision Procedure for CF-GKAT In Sections 2 and 3 , we presented decision procedures for GKAT automata and symbolic GKAT automata. We now want to apply these algorithms to decide equivalence between programs directly and therefore need algorithms to compile expressions to automata. Although the procedure to generate GKAT automata from GKAT and CF-GKAT expressions has been presented in previous works [ 39 , 38 , 52 ] , we need an algorithm to generate symbolic GKAT automata on-the-fly in order to take advantage of our efficient algorithm in Figure 7 . In this section, we introduce an algorithm to generate symbolic GKAT automata from CF-GKAT programs, in the following steps: CF-GKAT Programs Symbolic CF-GKAT Automata Symbolic GKAT Automata Equivalence Derivative Section 4.2 Section 4.3 Jump Resolution Section 4.4 Figure 7 Similar to the original algorithm [ 52 ] , we rely on an intermediate representation called symbolic CF-GKAT automata, which holds additional information to indicate how the computation can be resumed. Our algorithm first computes the symbolic CF-GKAT automata on-the-fly using derivatives, as detailed in Sections 4.2 and 4.3 ; then for each transition, we connect all the jump continuations, generated by goto s, to the appropriate program location, through label extraction and jump resolution , which we describe in Section 4.4 . Remark 5 (Thompson’s Construction v.s. Derivatives) 52 defines the operational semantics of CF-GKAT through Thompson’s construction, which inductively computes the entire automaton from a program. While our algorithms can decide the equivalences between fully computed automata, the derivative leverages the on-the-fly nature of our algorithm: it computes one-step transitions from a given program, allowing immediate termination of automata generation upon failures. However, transitioning from Thompson’s construction to the derivative is not straightforward, as the derivative lacks access to the automata of sub-expressions. One challenge is to ensure that break and continue resume correctly at their parent loop in the presence of nested loops, which is elegantly resolved using the unfolding operator (see Figure 8 and Remark 7 ). One significant application of CF-GKAT is validating the control-flow structuring phase of decompilers [ 49 , 14 ] , which we used in some of our experiments. Interestingly, in the process of benchmarking our implementations, we identified a bug [ 34 ] in the industry standard decompiler: Ghidra. Remark 6 (Equivalence for GKAT Expressions) Because CF-GKAT is a super system of GKAT , the compilation algorithm for GKAT ( in Appendix 0.C ) can be derived from that of CF-GKAT , by ignoring indicator variables and continuations. 4.1 Syntax and Symbolic CF-GKAT Automata In addition to the common control-flow structues like if-states and while-loops, CF-GKAT also includes indicator variable and non-local control-flow structures like break, continue, return, and goto’s. Formally, CF-GKAT expressions are defined over a finite set of indicator variables x\in X , a finite set of indicator values i\in I , and a finite set of labels l\in L : \displaystyle\mathsf{BExp}^{I}_{T}\ni b,c\triangleq{} \displaystyle 0\mid 1\mid t\in T\mid{x=i}\mid b\lor c\mid b\land c\mid\overline{b} \displaystyle\textsf{CF-GKAT}\ni e,f\triangleq{} \displaystyle b\in\mathsf{BExp}^{I}\mid p\in\Sigma\mid{x:=i}\mid{e\vartriangleleft f}\mid e\fatsemi f\mid e+_{b}f\mid \displaystyle e^{(b)}\mid{\texttt{break}}\mid{\texttt{continue}}\mid{\texttt{return}}\mid{\texttt{goto}\!~l}\mid{\texttt{label}\!~l} \mathsf{BExp}^{I}_{T} are Boolean expressions generated by indicator tests x=i and the primitive tests from T ; and we write \mathsf{BExp}^{I} when T is irrelevant or clear from context. For a CF-GKAT expression e to be a CF-GKAT program (or well-formed expressions ), we enforce the following constraint: (1) Each \texttt{label}\!~l appears at most once in the program e . (2) If \texttt{goto}\!~l appears in e , then so does \texttt{label}\!~l . (3) break or continue either appears in loop, or the left side of an unfolding \vartriangleleft . (4) All programs must end in return, i.e. of the form f\fatsemi\texttt{return} or return . In addition to the syntax introduced in the original paper [ 52 ] , we added two additional constructions: continue , a common control-flow manipulating structure used in while-loops; and the unfolding operator e\vartriangleleft f is an expression replaces sequencing in the loop unfolding. Remark 7 (The Unfolding Operator) It is common to assume that the loop e^{(b)} can be unfolded into an if-statement: e^{(b)}\equiv e\fatsemi e^{(b)}+_{b}1 [ 39 ] . However, this identity no longer holds in CF-GKAT with the addition of break and continue. Consider \texttt{break}^{(1)} (i.e. \texttt{while}~\mathrm{true}~\texttt{do}~\texttt{break} ): the behavior of this program is equivalent to 1 (i.e. skip ), as the execution always enters the loop, then immediately breaks and halts, without executing any action. However, \texttt{break}\fatsemi\texttt{break}^{(1)}+_{b}1 is equivalent to \texttt{break}+_{b}1 , because break annihilates the right side of sequencing [ 52 ] . Therefore, we introduce the unfolding operator \vartriangleleft , which satisfies the equality e^{(b)}\equiv e\vartriangleleft e^{(b)}+_{b}1 , by properly handling the break and continue within e . Additionally, we can soundly encode do-while loop: \texttt{do}~e~\texttt{while}~b , as e\vartriangleleft e^{(b)} , even when e contains continue or break . As we have noted before, our goal for this section is to construct a symbolic GKAT automaton for each CF-GKAT program, enabling the use of symbolic equivalence algorithm to efficiently decide equivalences of CF-GKAT terms. However, to get there, we will first construct symbolic CF-GKAT automata, which is the symbolic version of the CF-GKAT automata [ 52 ] . The difference between GKAT and CF-GKAT automata is that CF-GKAT automata also keep track of ending state , by outputting continuations , allowing the computation to resume under appropriate conditions. Formally, we define the set of continuations C with the following elements: let \pi:X\to I ranges over all the indicator states, • {\mathbf{acc}~\pi} : the program terminates normally with the ending assignment \pi ; • {\mathbf{ret}} : the program halts by a return statement, annihilating further actions; • \mathbf{brk}~\pi : the program will break out of the current loop with assignment \pi ; • {\mathbf{cont}~\pi} : the program will restart the current loop with assignment \pi ; • {\mathbf{jmp}~l,\pi} : the program jumps to label l with assignment \pi . Definition 4 A symbolic CF-GKAT automaton is a tuple (S,s_{0},\varepsilon,\delta) , with a set of states S , a start state s_{0} , an accepting function \varepsilon , and a transition function \delta with the following signature: \displaystyle\varepsilon \displaystyle\colon S\to\mathcal{P}(\mathsf{BExp}\times C), \displaystyle\delta \displaystyle\colon S\to\mathcal{P}(\mathsf{BExp}\times S\times\Sigma). We use s\mathrel{\resizebox{}{}{{\hbox{\hskip 0.0pt\raise-5.0pt\hbox{{$\xRightarrow{b}$}}}}}}{c} to denote (b,c)\in\varepsilon(s) ; s\mathrel{\raisebox{-2.0pt}{$\xrightarrow{b\mid p}$}}s^{\prime} to denote (b,s^{\prime},p)\in\delta(s) ; and s\mathrel{\resizebox{}{}{{\hbox{\hskip 0.0pt\raise-2.0pt\hbox{{$\xhookrightarrow{b}$}}}}}}r to denote (b,c)\in\varepsilon(s) if r=c\in C or (b,s^{\prime},p)\in\delta(s) if r=(s^{\prime},p)\in S\times\Sigma . 4.2 Generating Symbolic CF-GKAT Automata With Derivatives We use derivatives [ 38 , 25 , 4 , 9 ] to generate CF-GKAT automata, which will enable early termination upon counter-examples in the symbolic algorithm. We first introduce several operations on indicator states \pi:X\to I . The first operation reassigns a variable x\in X of a indicator state \pi to i\in I : \pi[x\mapsto i](y)\triangleq\begin{cases}i&\text{if }x=y\\ \pi(y)&\text{otherwise}\end{cases} The second operation will resolve all the indicator tests in b\in\mathsf{BExp}^{I} when given an indicator state \pi , giving us a condition b[\pi]:\mathsf{BExp} to be used for transitions in a CF-GKAT automaton: \displaystyle\mathrm{false}[\pi] \displaystyle\triangleq\mathrm{false} \displaystyle\mathrm{true}[\pi] \displaystyle\triangleq\mathrm{true} \displaystyle(x=i)[\pi] \displaystyle\triangleq\begin{cases}\mathrm{true}&\pi(x)=i\\ \mathrm{false}&\pi(x)\neq i\end{cases} \displaystyle(b\land c)[\pi] \displaystyle\triangleq b[\pi]\land c[\pi] \displaystyle(b\lor c)[\pi] \displaystyle\triangleq b[\pi]\lor c[\pi] \displaystyle(\neg b)[\pi] \displaystyle\triangleq\neg(b[\pi]) Primitives Rules \begin{aligned} &(\pi,\texttt{assert}~b)\mathrel{\resizebox{}{}{{\hbox{\hskip 0.0pt\raise-3.25pt\hbox{{$\xRightarrow{b[\pi]}$}}}}}}{{\mathbf{acc}~\pi}}&&(\pi,\texttt{break})\mathrel{\resizebox{}{}{{\hbox{\hskip 0.0pt\raise-5.0pt\hbox{{$\xRightarrow{\mathrm{true}}$}}}}}}{\mathbf{brk}~\pi}&&(\pi,\texttt{continue})\mathrel{\resizebox{}{}{{\hbox{\hskip 0.0pt\raise-5.0pt\hbox{{$\xRightarrow{\mathrm{true}}$}}}}}}{{\mathbf{cont}~\pi}}\\ &(\pi,\texttt{goto}\!~l)\mathrel{\resizebox{}{}{{\hbox{\hskip 0.0pt\raise-5.0pt\hbox{{$\xRightarrow{\mathrm{true}}$}}}}}}{{\mathbf{jmp}~l,\pi}}&&(\pi,\texttt{return})\mathrel{\resizebox{}{}{{\hbox{\hskip 0.0pt\raise-5.0pt\hbox{{$\xRightarrow{\mathrm{true}}$}}}}}}{{\mathbf{ret}}}&&(\pi,x:=i)\mathrel{\resizebox{}{}{{\hbox{\hskip 0.0pt\raise-5.0pt\hbox{{$\xRightarrow{\mathrm{true}}$}}}}}}{{\mathbf{acc}~\pi[x\mapsto i]}}\\ &&&(\pi,p)\mathrel{\raisebox{-2.0pt}{$\xrightarrow{\mathrm{true}\mid p}$}}(\pi,\texttt{skip})\end{aligned} Sequencing Rules Unfolding Rules \frac{(\pi,e)\mathrel{\resizebox{}{}{{\hbox{\hskip 0.0pt\raise-5.0pt\hbox{{$\xRightarrow{b}$}}}}}}{{\mathbf{acc}~\pi^{\prime}}}\quad(\pi^{\prime},f)\mathrel{\resizebox{}{}{{\hbox{\hskip 0.0pt\raise-2.0pt\hbox{{$\xhookrightarrow{a}$}}}}}}r}{(\pi,e\fatsemi f)\mathrel{\resizebox{}{}{{\hbox{\hskip 0.0pt\raise-2.0pt\hbox{{$\xhookrightarrow{b\land a}$}}}}}}r}\frac{(\pi,e)\mathrel{\raisebox{-2.0pt}{$\xrightarrow{b\mid p}$}}(\pi^{\prime},e^{\prime})}{(\pi,e\fatsemi f)\mathrel{\raisebox{-2.0pt}{$\xrightarrow{b\mid p}$}}(\pi^{\prime},e^{\prime}\fatsemi f)}{\frac{(\pi,e)\mathrel{\resizebox{}{}{{\hbox{\hskip 0.0pt\raise-5.0pt\hbox{{$\xRightarrow{b}$}}}}}}{c}\quad c\neq{\mathbf{acc}~\pi^{\prime}}}{(\pi,e\fatsemi f)\mathrel{\resizebox{}{}{{\hbox{\hskip 0.0pt\raise-5.0pt\hbox{{$\xRightarrow{b}$}}}}}}{c}}} \displaystyle{\frac{(\pi,e)\mathrel{\resizebox{}{}{{\hbox{\hskip 0.0pt\raise-5.0pt\hbox{{$\xRightarrow{b}$}}}}}}{\mathbf{brk}~\pi^{\prime}}}{(\pi,e\vartriangleleft f)\mathrel{\resizebox{}{}{{\hbox{\hskip 0.0pt\raise-5.0pt\hbox{{$\xRightarrow{b}$}}}}}}{{\mathbf{acc}~\pi^{\prime}}}}} \displaystyle{\frac{(\pi,e)\mathrel{\resizebox{}{}{{\hbox{\hskip 0.0pt\raise-5.0pt\hbox{{$\xRightarrow{b}$}}}}}}{c}\quad c\in\{{\mathbf{cont}~\pi^{\prime}},{\mathbf{acc}~\pi^{\prime}}\}\quad(\pi^{\prime},f)\mathrel{\resizebox{}{}{{\hbox{\hskip 0.0pt\raise-2.0pt\hbox{{$\xhookrightarrow{a}$}}}}}}r}{(\pi,e\vartriangleleft f)\mathrel{\resizebox{}{}{{\hbox{\hskip 0.0pt\raise-2.0pt\hbox{{$\xhookrightarrow{b\land a}$}}}}}}{r}}} \displaystyle{\frac{(\pi,e)\mathrel{\resizebox{}{}{{\hbox{\hskip 0.0pt\raise-5.0pt\hbox{{$\xRightarrow{b}$}}}}}}{c}\quad c\in\{{\mathbf{ret}},{\mathbf{jmp}~(l,\pi^{\prime})}\}}{(\pi,e\vartriangleleft f)\mathrel{\resizebox{}{}{{\hbox{\hskip 0.0pt\raise-5.0pt\hbox{{$\xRightarrow{b}$}}}}}}{c}}} \displaystyle\frac{(\pi,e)\mathrel{\raisebox{-2.0pt}{$\xrightarrow{b\mid p}$}}(\pi^{\prime},e^{\prime})}{(\pi,e\vartriangleleft f)\mathrel{\raisebox{-2.0pt}{$\xrightarrow{b\mid p}$}}(\pi^{\prime},e^{\prime}\vartriangleleft f)} Conditional Rules and Loop Rules \frac{(\pi,e)\mathrel{\resizebox{}{}{{\hbox{\hskip 0.0pt\raise-2.0pt\hbox{{$\xhookrightarrow{a}$}}}}}}r}{(\pi,e+_{b}f)\mathrel{\resizebox{}{}{{\hbox{\hskip 0.0pt\raise-0.25pt\hbox{{$\xhookrightarrow{b[\pi]\land a}$}}}}}}r}\quad\frac{(\pi,f)\mathrel{\resizebox{}{}{{\hbox{\hskip 0.0pt\raise-2.0pt\hbox{{$\xhookrightarrow{a}$}}}}}}r}{(\pi,e+_{b}f)\mathrel{\resizebox{}{}{{\hbox{\hskip 0.0pt\raise-0.25pt\hbox{{$\xhookrightarrow{\neg b[\pi]\land a}$}}}}}}r}\quad\frac{\quad}{(\pi,e^{(b)})\mathrel{\resizebox{}{}{{\hbox{\hskip 0.0pt\raise-3.25pt\hbox{{$\xRightarrow{\neg b[\pi]}$}}}}}}{{\mathbf{acc}~\pi}}}\quad{\frac{(\pi,e\vartriangleleft e^{(b)})\mathrel{\resizebox{}{}{{\hbox{\hskip 0.0pt\raise-2.0pt\hbox{{$\xhookrightarrow{a}$}}}}}}r}{(\pi,e^{(b)})\mathrel{\resizebox{}{}{{\hbox{\hskip 0.0pt\raise-0.25pt\hbox{{$\xhookrightarrow{b[\pi]\land a}$}}}}}}r}} Figure 8 : Operational rules to derive the continuation semantics of CF-GKAT . In Figure 8 , we present the operational semantics of a CF-GKAT expression as a symbolic CF-GKAT automaton. The states in the automaton consist of two components: \pi:X\to I is the current indicator state, and e:\textsf{CF-GKAT} is the remaining expression to execute. With the rules in Figure 8 , we can now construct an automaton for every expression e with a starting indicator state \pi , which we denote by \langle\pi,e\rangle . The states of \langle\pi,e\rangle are all the pairs of expressions and indicator-states that are reachable from (\pi,e) by the transition function \delta defined in Figure 8 , the start state is (\pi,e) , and the accepting and transition functions are \varepsilon and \delta defined in Figure 8 restricted to the reachable states. Example 1 We compute automata \langle x\mapsto 3,e\rangle and \langle x\mapsto 4,e\rangle for the loop body e in Figure 9(a) . For the starting indicator state x\mapsto 3 , the branches x=1 and x=0 are not executed, because (x=1)[x\mapsto 3]\triangleq\mathrm{false} and (x=0)[x\mapsto 3]=\mathrm{false} . Thus, the automaton can only go into third branch when x=3 . On the other hand, when x is set to 4 , (x=3\land b)[x\mapsto 4] also evaluates to false; therefore, only the last branch will execute. We draw both automata as follows (with blocked transitions removed): (x\mapsto 3,e) (x\mapsto 3,\texttt{skip}) {\mathbf{acc}~(x\mapsto 3)} {\mathbf{acc}~(x\mapsto 4)} b \overline{b}\land a\mid p 1 \langle x\mapsto 3,e\rangle: (x\mapsto 4,e) (x\mapsto 4,\texttt{skip}) {\mathbf{acc}~(x\mapsto 4)} a\mid p 1 \langle x\mapsto 4,e\rangle: 4.3 Computing Loops As shown in Figure 8 , the transitions of most expressions can be computed from transitions of its sub-expressions. While loops e^{(b)} are the only exception, as the premise for the second loop rule relies on the transition of its unfolding e\vartriangleleft e^{(b)} , which is a larger expression than e^{(b)} . \displaystyle{\color[rgb]{0.0508,0.2773,0.6328}{\texttt{\small{while}}}}~x\neq 2~{\color[rgb]{0.0508,0.2773,0.6328}{\texttt{\small{do}}}}~ \displaystyle\quad{\color[rgb]{0.0508,0.2773,0.6328}{\texttt{\small{if}}}}~x=1~{\color[rgb]{0.0508,0.2773,0.6328}{\texttt{\small{then}}}}~ \displaystyle\qquad x:=0; \displaystyle\quad{\color[rgb]{0.0508,0.2773,0.6328}{\texttt{\small{else}}}}~{\color[rgb]{0.0508,0.2773,0.6328}{\texttt{\small{if}}}}~x=0~{\color[rgb]{0.0508,0.2773,0.6328}{\texttt{\small{then}}}}~ \displaystyle\qquad x:=1; \displaystyle\quad{\color[rgb]{0.0508,0.2773,0.6328}{\texttt{\small{else}}}}~{\color[rgb]{0.0508,0.2773,0.6328}{\texttt{\small{if}}}}~x=3\land b~{\color[rgb]{0.0508,0.2773,0.6328}{\texttt{\small{then}}}}~ \displaystyle\qquad x:=4; else \displaystyle\qquad({\color[rgb]{0.5117,0.4648,0.0898}{\texttt{\small{assert}}}}~a);p; (a) (x\mapsto 1,e^{(x\neq 2)}) (x\mapsto 2,e^{(x\neq 2)}) (x\mapsto 3,e^{(x\neq 2)}) (x\mapsto 4,e^{(x\neq 2)}) {\mathbf{acc}~(x\mapsto 2)} \mathrm{true} \overline{b}\land a\mid p b\land a\mid p a\mid p \langle x\mapsto 3,e^{(x\neq 2)}\rangle: \langle x\mapsto 2,e^{(x\neq 2)}\rangle: \langle x\mapsto 1,e^{(x\neq 2)}\rangle: (b) Figure 9 : Program e^{(x\neq 2)} , on the left, where e denotes the loop body. On the right, the automata for different starting indicator assignments, with blocked transitions removed. In this section, we will show that the transitions of e^{(b)} is computable from the transition of e . for CF-GKAT , computing the transition of e^{(b)} is particularly difficult, because the first action might be encountered after arbitrarily long iteration of the loop body. For example, consider the transition of state (x\mapsto 3,e^{(x\neq 2)}) in Figure 9(b) , its self-loop under condition \overline{b}\land a is derivable in one iteration of the body; yet the transition to (x\mapsto 4,e^{(x\neq 2)}) under condition b\land a requires two iterations (transitions of the loop body e is in Example 1 ): \frac{\frac{(x\mapsto 3,e)\mathrel{\raisebox{-2.0pt}{$\xrightarrow{\overline{b}\land a\mid p}$}}(x\mapsto 3,e)}{\vdots}}{(x\mapsto 3,e^{(x\neq 2)})\mathrel{\raisebox{-2.0pt}{$\xrightarrow{\overline{b}\land a\mid p}$}}(x\mapsto 3,e^{(x\neq 2)})}\quad\frac{\frac{(x\mapsto 3,e)\mathrel{\resizebox{}{}{{\hbox{\hskip 0.0pt\raise-5.0pt\hbox{{$\xRightarrow{b}$}}}}}}{\mathbf{acc}~(x\mapsto 4)}\hskip 7.3612pt(x\mapsto 4,e)\mathrel{\raisebox{-2.0pt}{$\xrightarrow{a\mid p}$}}(x\mapsto 4,\texttt{skip})}{\vdots}}{(x\mapsto 3,e^{(x\neq 2)})\mathrel{\raisebox{-2.0pt}{$\xrightarrow{b\land a\mid p}$}}(x\mapsto 4,e^{(x\neq 2)})} Formal derivation of these two results can be found in Appendix 0.D ( Figure 13 ). To compute the transition of a loop, we will need to iterate the transition of the loop body . 52 named this process “iteration lifting”, which iterates the result for a fixed atom, until the program outputs a continuation, executes an action, or goes into an infinite loop without executing any actions. However, the situation in the symbolic case is more complicated, as we will need to combine the result of the first iteration with the rest. \frac{\frac{(\pi,e)\mathrel{\resizebox{}{}{{\hbox{\hskip 0.0pt\raise-5.0pt\hbox{{$\xRightarrow{a}$}}}}}}{\mathbf{acc}~\pi^{\prime}}\hskip 8.19447pt(\pi^{\prime},e^{(b)})\mathrel{\resizebox{}{}{{\hbox{\hskip 0.0pt\raise-5.0pt\hbox{{$\xRightarrow{d}$}}}}}}c}{\vdots}}{(\pi,e^{(b)})\mathrel{\resizebox{}{}{{\hbox{\hskip 0.0pt\raise-3.25pt\hbox{{$\xRightarrow{b[\pi]\land a\land d}$}}}}}}c} For example, take the derivation on the left, we need to combine the condition to enter the loop b[\pi] , the condition for the first iteration a , with the condition of the rest d , to get the final condition b[\pi]\land a\land d . To account for this difference, our accumulation function, defined below, outputs a function h in the recursive case to transform the result obtained from recursion. Definition 5 (Accumulation) We use N to denote the type of input, and R the type of output. \mathrm{accu} takes two functions \mathrm{res}:N\to\mathcal{P}(R) , \mathrm{con}:N\to\mathcal{P}(N\times(R\to R)) , and an initial input n\in N : • \mathrm{res} takes an input in N and return a set of results computed in one step. • \mathrm{con} takes an input n\in N and return a set of next iterations n^{\prime}\in N paired with the function h:R\to R to be applied onto the results generated by n^{\prime} . Formally, \mathrm{accu}_{\mathrm{res},\mathrm{con}}(n) is the set of elements derivable by the inference rules: \frac{r\in\mathrm{res}(n)}{r\in\mathrm{accu}_{\mathrm{res},\mathrm{con}}(n)}\frac{(n^{\prime},h)\in\mathrm{con}(n)\quad r\in\mathrm{accu}_{\mathrm{res},\mathrm{con}}(n^{\prime})}{h(r)\in\mathrm{accu}_{\mathrm{res},\mathrm{con}}(n)}\vskip-8.00003pt We then show that \mathrm{accu} is computable under some side conditions; this result will later give as a way to compute the transitions for while-loops and jump continuations expressing their transitions using \mathrm{accu} . Theorem 4.1 (Computablity) When the set of input N is finite and all the h in (n^{\prime},h)\in\mathrm{con}(n) is computable, then \mathrm{accu}_{\mathrm{res},\mathrm{con}}(n)\in\mathcal{P}(R) is computable. In the rest of the section, we use the \mathrm{accu} function to express the \delta and \varepsilon for a loop e^{(b)} , then we prove the correctness of this encoding by \mathrm{accu} . Combining the computability of \mathrm{accu} with the following two results gives a correct and computable procedure to compute \delta(\pi,e^{b}) and \varepsilon(\pi,e^{(b)}) . Expressing \delta of while-loops . We first express \delta(\pi,e^{(b)}) as \mathrm{accu}(\mathrm{res}_{\delta},\mathrm{con}_{\delta},\pi) , where the elements of \mathrm{res}_{\delta} and \mathrm{con}_{\delta} are defined by the following inference rules: \frac{(\pi,e)\mathrel{\raisebox{-2.0pt}{$\xrightarrow{a\mid p}$}}(\pi^{\prime},e^{\prime})}{(b[\pi]\land a,(\pi^{\prime},e^{\prime}\vartriangleleft e^{(b)}),p)\in\mathrm{res}_{\delta}(\pi)}\frac{(\pi,e)\mathrel{\resizebox{}{}{{\hbox{\hskip 0.0pt\raise-5.0pt\hbox{{$\xRightarrow{a}$}}}}}}{c}\quad c\in\{{\mathbf{acc}~\pi^{\prime}},{\mathbf{cont}~\pi^{\prime}}\}}{(\pi^{\prime},\langle b[\pi]\land a|)\in\mathrm{con}_{\delta}(\pi)}\vskip-8.00003pt where \langle b| guards the transition condition with b\in\mathsf{BExp} : \langle b|(a,s,p)\triangleq(b\land a,s,p). Intuitively, \mathrm{res}_{\delta} corresponds to the transitions that can computed by single iteration of the loop body. Whereas \mathrm{con}_{\delta} describes the way to compute all the transitions that can be formed by more-than-one iterations of the loop body e . Indeed, the \mathrm{res}_{\delta} and \mathrm{con}_{\delta} function is obtained by unfolding the only two ways to derive the transitions of e\vartriangleleft e^{(b)} and e^{(b)} : \frac{\frac{(\pi,e)\mathrel{\raisebox{-2.0pt}{$\xrightarrow{a\mid p}$}}(\pi^{\prime},e^{\prime})}{(\pi,e\vartriangleleft e^{(b)})\mathrel{\raisebox{-2.0pt}{$\xrightarrow{a\mid p}$}}(\pi^{\prime},e^{\prime}\vartriangleleft e^{(b)})}}{(\pi,e^{(b)})\mathrel{\raisebox{-2.0pt}{$\xrightarrow{b[\pi]\land a\mid p}$}}(\pi^{\prime},e^{\prime}\vartriangleleft e^{(b)})} \frac{\frac{(\pi,e)\mathrel{\resizebox{}{}{{\hbox{\hskip 0.0pt\raise-5.0pt\hbox{{$\xRightarrow{a}$}}}}}}{c}\hskip 7.3612ptc\in\{{\mathbf{acc}~\pi^{\prime}},{\mathbf{cont}~\pi^{\prime}}\}\hskip 7.3612pt(\pi^{\prime},e^{(b)})\mathrel{\raisebox{-2.0pt}{$\xrightarrow{d\mid p}$}}(\sigma,f)}{(\pi,e\vartriangleleft e^{(b)})\mathrel{\raisebox{-2.0pt}{$\xrightarrow{a\land d\mid p}$}}(\sigma,f)}}{(\pi,e^{(b)})\mathrel{\raisebox{-2.0pt}{$\xrightarrow{b[\pi]\land a\land d\mid p}$}}(\sigma,f)} The first case is represented by \mathrm{res}_{\delta} : the transition of e^{(b)} is directly computed from transitions of e ; the second case is represented by \mathrm{con}_{\delta} : the transition of (\pi,e^{(b)}) is inductively constructed by the transition of (\pi^{\prime},e^{(b)}) , then the resulting condition d is guarded by b[\pi]\land a to become b[\pi]\land a\land d . The \varepsilon of while loop, i.e. elements in \varepsilon(\pi,e^{(b)}) can also be expressed using \mathrm{accu} by defining \mathrm{res}_{\varepsilon} and \mathrm{con}_{\varepsilon} , similarly to how we defined \mathrm{res}_{\delta} and \mathrm{con}_{\delta} . We defer the precise formulation of this result in Appendix 0.D . Theorem 4.2 (Correctness) For any GKAT expression e , a Boolean expression b , and an indicator assignment \pi , the transition function \delta and continuation \varepsilon computed by \mathrm{accu} is the same as derived from the operational rules in Figure 8 : \delta(\pi,e^{(b)})=\mathrm{accu}(\mathrm{res}_{\delta},\mathrm{con}_{\delta},\pi)\text{and}\varepsilon(\pi,e^{(b)})=\mathrm{accu}(\mathrm{res}_{\varepsilon},\mathrm{con}_{\varepsilon},\pi) 4.4 Label Extraction And Jump Resolution By an induction and closure argument, we can show that given e , then for all \pi:X\to I , the states in \langle\pi,e\rangle can only output either {\mathbf{jmp}~l,\pi} or {\mathbf{ret}} as a continuation. Indeed, because all the continue and break can only either appear on the left side of the unfold operation \vartriangleleft or in a loop, then the continuation {\mathbf{cont}~\pi} and \mathbf{brk}~\pi will be resolved when computing the transition for \vartriangleleft , as detailed in Figure 8 . Also, since every program ends with return , all the {\mathbf{acc}~\pi} continuation will be replaced by {\mathbf{ret}} in the end. Hence, to obtain a symbolic GKAT automaton from \langle\pi,e\rangle , we will only need to resolve the jump continuation by connecting it to the appropriate location of the program. Indeed, the location of each label l in e can be extracted syntactically, by recursively diving into the expression until the command \texttt{label}\!~l is reached. For readers familiar with the work of 52 , our definition is a syntactic counterpart to their inductive semantics \llbracket-\rrbracket^{l} . Formally, given a label l\in L , and an expression e\in\textsf{CF-GKAT} where \texttt{label}\!~l appears exactly once , then the label extraction e_{l} gives an expression that corresponds to the location of l : \displaystyle(\texttt{label}\!~l)_{l} \displaystyle\triangleq 1\quad(e^{(b)})_{l}\triangleq(e)_{l}\vartriangleleft e^{(b)} \displaystyle(e+_{b}f)_{l} \displaystyle\triangleq\begin{cases}\mathrlap{(e)_{l}}\hphantom{(e)_{l}\vartriangleleft f}&\text{if $\texttt{label}\!~l$ in $e$}\\ (f)_{l}&\text{if $\texttt{label}\!~l$ in $f$}\end{cases} \displaystyle(e;f)_{l} \displaystyle\triangleq\begin{cases}(e)_{l};f&\text{if $\texttt{label}\!~l$ in $e$}\\ (f)_{l}&\text{if $\texttt{label}\!~l$ in $f$}\end{cases} \displaystyle(e\vartriangleleft f)_{l} \displaystyle\triangleq\begin{cases}(e)_{l}\vartriangleleft f&\text{if $\texttt{label}\!~l$ in $e$}\\ (f)_{l}&\text{if $\texttt{label}\!~l$ in $f$}\end{cases} We ignore other expressions, as they do not contain \texttt{label}\!~l . Unlike the approach taken by 52 , which resolves the semantics of l in an expression without \texttt{label}\!~l to divergence, we only define label extraction on expression e that contains a unique \texttt{label}\!~l . This constraint aligns with the requirement of most real-world languages, and is compatible with a CF-GKAT program e : all the {\mathbf{jmp}~l,\sigma^{\prime}} continuations are produced by \texttt{goto}\!~l ; and if e contains \texttt{goto}\!~l , then e contains a unique \texttt{label}\!~l , by definition of a CF-GKAT program. We formally define the jump resolution process: when given a program e , jump resolution will turn a symbolic CF-GKAT automaton \langle\pi,e\rangle into a symbolic GKAT automaton \langle\pi,e\rangle\!\downarrow . The transition of state (\sigma,f) in \langle\pi,e\rangle\!\downarrow can be computed from the transition of (\sigma,f) in CF-GKAT automaton \langle\pi,e\rangle , by connection all the jump continuation {\mathbf{jmp}~l,\sigma^{\prime}} with the dynamics of the state (\sigma^{\prime},e_{l}) . Formally, take any state (\sigma,f)\in\langle\pi,e\rangle , we derive its transition in \langle\pi,e\rangle\!\downarrow with the following rules, when (\sigma,f)\mathrel{\resizebox{}{}{{\hbox{\hskip 0.0pt\raise-5.0pt\hbox{{$\xRightarrow{a}$}}}}}}{{\mathbf{jmp}~l,\sigma^{\prime}}} in \langle\pi,e\rangle : \frac{(\sigma,f)\mathrel{\resizebox{}{}{{\hbox{\hskip 0.0pt\raise-5.0pt\hbox{{$\xRightarrow{a}$}}}}}}{{\mathbf{jmp}~l,\sigma^{\prime}}}\text{ in }\langle\pi,e\rangle\quad(\sigma^{\prime},e_{l})\mathrel{\resizebox{}{}{{\hbox{\hskip 0.0pt\raise-2.0pt\hbox{{$\xhookrightarrow{b}$}}}}}}r\text{ in }\langle\pi,e\rangle\!\downarrow}{(\sigma,f)\mathrel{\resizebox{}{}{{\hbox{\hskip 0.0pt\raise-2.0pt\hbox{{$\xhookrightarrow{a\land b}$}}}}}}r\text{ in }\langle\pi,e\rangle\!\downarrow} All transitions of (\sigma,f) that do not result in a jump remain the same as in \langle\pi,e\rangle . The inference rule for jump resolution is also recursive: the transitions of \langle\pi,e\rangle\!\downarrow appears both in the conclusion and the premise, thus we can compute the transitions in \langle\pi,e\rangle\!\downarrow with the \mathrm{accu} function defined in Definition 5 . Theorem 4.3 (Computability) Fix a program e , the transitions in the symbolic automata \langle\pi,e\rangle is computable, by expressing it as a \mathrm{accu} . Finally, given any program e and a starting indicator state \pi , we obtain an on-the-fly algorithm to construct the symbolic GKAT automata \langle\pi,e\rangle\!\downarrow . Thus, to decide the equivalence between the equivalence of two CF-GKAT programs e and f with its respective starting indicator states \pi and \sigma , we can construct the automata \langle\pi,e\rangle\!\downarrow and \langle\sigma,f\rangle\!\downarrow , and apply the algorithm in Figure 7 . Indeed, this development represents a significant increase in the efficiency of equivalence checking for CF-GKAT and GKAT . In the next section, we outline how we implemented the decision procedure for both GKAT and CF-GKAT in Rust, and compared them with the current state-of-the-art on both generated examples and real-world control-flow to demonstrate our efficiency. Indeed, our implementation have not only exhibited orders-of-magnitude performance improvement over the existing tool, but also able to help us locate a bug in Ghidra [ 30 ] , an industry standard decompiler. 5 Implementation and Evaluation In this section, we detail our Rust implementation [ 17 ] and evaluation of the on-the-fly symbolic decision procedures for (CF-)GKAT . We implemented the symbolic on-the-fly algorithm in Figure 7 , the symbolic derivatives from Section 4 , and the GKAT variants in Appendix 0.C . Then, we compare our implementation against SymKAT [ 33 ] and artifact of CF-GKAT [ 53 ] . 5.1 Implementation Details In our implementations, all Boolean expressions are directly converted into the internal format of the Boolean solvers, which currently include miniSAT [ 7 ] and BDD [ 42 , 26 ] . But, we can easily extend our implementation with more solvers as our algorithm supports the use of arbitrary (UN)SAT solvers. Both GKAT and CF-GKAT expressions are hash-consed for faster syntactical comparison and reduced memory footprint. Our optimization on the expressions are relatively light compared to previous works [ 33 , 28 ] : we only remove left sequencing and unfoldings of skip: (1\fatsemi e)\rightsquigarrow e and (1\vartriangleleft e)\rightsquigarrow e ; yet, we can already outperform existing works by a significant margin. Besides standard optimizations, the following paragraphs present additional details that are specific to our algorithm. Eager Pruning of Blocked Transitions . When generating a transition s\mathrel{\raisebox{-2.0pt}{$\xrightarrow{b\mid p}$}}s^{\prime} , we will immediately check whether this transition is blocked, i.e. whether b\equiv 0 ; if so, this transition will be immediately removed (see Remark 4 for soundness argument). This optimization significantly reduces the size of the generated automata, and avoids many unnecessary Boolean inequivalence checks. Encoding of Indicator Variables . When adapting our algorithm to CF-GKAT , we need to handle indicator variables within \mathsf{BExp}^{I} . While it is possible to naively construct their abstract syntax tree, and instantiate them when given an indicator state, it is better to store these expressions using the native representations within the Boolean solver. Since off-the-shelf solvers operate on Boolean formulae without indicator variables ( \mathsf{BExp} ), we encode constraints on indicator variables using fresh (Boolean) variables in the solver, (x=1)\land(y=2)\lor a t_{1}\land t_{2}\lor a Encoded Expression (x=1)\mapsto t_{1} (y=2)\mapsto t_{2} Indicator Constraint Table encode and use a table to track the correspondence of indicator constraints to these fresh variables. For example, consider the expression on the left, where x and y are indicator variables and a\in\mathsf{BExp} . The encoding produces two fresh variables t_{1} and t_{2} that represent the constraints x=1 and y=2 , respectively. The expression is transformed into t_{1}\land t_{2}\lor a , which is compatible with solver backends, with an indicator constraint table. When generating these fresh Boolean variables, we ensure that the same indicator constraint is always mapped to the same variable. When resolving the encoded expression b\in\mathsf{BExp}^{I} with some indicator state \pi , we iterate through all (x=i)\mapsto t in the table for b : if \pi(x) is indeed i , then we set the variable t in b to be true, otherwise false. 5.2 Empirical Evaluation Our implementation can utilize arbitrary (UN)SAT solvers; for evaluation we choose two as backend: BDD (CUDD) [ 26 , 42 ] and SAT (MiniSAT) [ 7 ] . We then compare against existing implementations: SymKAT [ 33 ] and CF-GKAT [ 53 ] . Our experiments are performed on a laptop with an AMD Ryzen 7 8845HS CPU with a time limit of 1000s and memory limit of 8GB. We study the performance of these algorithms on both randomly generated benchmarks and real-world control-flows extracted from GNU Coreutils 9.5 [ 18 ] . Figure 10 : Performance comparison of symbolic GKAT , symbolic CF-GKAT , and SymKAT in lo g arithm scale on the vertical axis. Synthetic Benchmarks . Using the equational rules of GKAT [ 39 ] , we randomly generate equivalent GKAT -program pairs of varying sizes and Boolean expression sizes. We compare our symbolic algorithms against a patched version of SymKAT that handles a larger number of primitive tests on these equivalent pairs, and present the runtime and memory footprint of these experiments in Figure 10 . Each point in these graphs represents an average performance on 100 randomly generated program pairs, and the ‘X’ markers on the SymKAT line indicate that a dataset failed to be checked within the time limit or memory limit. We do not include the implementation of CF-GKAT [ 53 ] in these comparisons, as it failed to complete any benchmark within the allotted time and memory. Our symbolic algorithms exhibit orders-of-magnitude performance increase over SymKAT in both runtime and memory usage, especially for larger programs. Notably, even the symbolic CF-GKAT implementations, with the overheads of handling indicator variables and continuations, are able to outperform SymKAT. We also note that the performance of BDD-based algorithms, including SymKAT, becomes more erratic as the size of the Boolean expressions grows; whereas MiniSAT-based algorithms exhibit more stable performance behaviors. GNU Coreutils Decompilation Validation . We evaluate our symbolic CF-GKAT algorithm by compiling and decompiling real-world control flows extracted from GNU Coreutils 9.5 [ 18 ] ; then test the trace equivalence of the original and decompiled control flow via CF-GKAT . Similarly to the original CF-GKAT evaluation [ 52 , 53 ] , we extract the control-flow of C source code through blinding , which replaces all the commands and conditions with undefined functions. This process abstracts away the data flow, and ensures that the compiler and decompiler only transforms control flows. Compared to the original blinder [ 53 ] , our new blinder supports more control-flow constructs such as continue , simple switch statements, do-while loops, and for-loops with nested continue s. We also make fewer assumptions about the conditions in C in this iteration of the blinder. In particular, the semantics of CF-GKAT assumes the same primitive test always has the same truth value within a Boolean expression. However, in the condition (x = !x) &​& (x = !x) , the first test (x = !x) will have different truth value than the second one, even though they are syntactically the same. Thus, our blinder always generates fresh primitive tests, even for syntactically equal conditions. As a trade-off, our blinder produces a larger number primitive tests, which increases the complexity of equivalence checking. Through blinding, we obtain the abstract control flow of a function, which we compile using Clang 20.1.2 [ 27 ] , and then decompile using Ghidra 11.4 [ 30 ] . Additionally, some manual cleanup is performed to remove artifacts generated by Ghidra, adjusting it into a fragment of C that can be read by our implementation of CF-GKAT . Figure 11 : Performance comparison of Symbolic CF-GKAT and CF-GKAT on Coreutils. Figure 11 shows the performance of our symbolic CF-GKAT algorithm against the original CF-GKAT implementation on 237 Coreutils functions. The ‘X’ markers in orange indicate that either the original CF-GKAT implementation failed to check these test cases within the time or memory limit or encountered unsupported control-flow constructs, like continue . SymKAT is not included in this comparison as it does not support the control-flow structures in CF-GKAT . Our symbolic CF-GKAT implementation outperforms the original one on all metrics by significant margins, regardless of the Boolean solver. In fact, both variants of symbolic CF-GKAT are able to check the almost all of the 237 functions in approximately 7 seconds and within a memory footprint of less than 100MB. In this particular application, the BDD-based symbolic CF-GKAT algorithm performs slightly better than miniSAT in runtime, as the size of the conditions in Coreutils are usually below where SAT overtakes BDD in efficiency. Discovered Bug in Ghidra . During benchmarking of the implementation, we identified a bug in Ghidra [ 34 ] , which is confirmed and fixed a month later. This bug is identified by a mismatch of control - flow between the blinded code for the copy_internal function in Coreutils 9.5, and its compiled and decompiled output. The original copy_internal function spans 1195 lines, and the blinded one spans 559 lines. Without the efficiency of our algorithm, testing control - flow equivalence for functions of this size would be difficult. Moreover, the efficiency of our tool provides rapid feedback when shrinking the code, allowing us to quickly isolate a minimal counter - example for submission to the developer. The minimal input code that triggers the bug contains multiple goto statements and indicator variables. Thus, supports for these complex control-flow structures are required to identify bugs like these. The fix for this bug takes roughly 100 lines of code changes, including modifications to the underlying logic. This experience confirms that our approach can uncover complex bugs in widely used decompilers, even when we didn’t target bug-finding in our experiments. It demonstrates the practicality of our method and highlights the challenges in implementing correct decompilers, which our tools are well - equipped to facilitate. In the future, we plan to design more comprehensive fuzzing frameworks to evaluate additional decompilers across a broader set of input programs. 6 Discussion We presented new symbolic decision procedures for GKAT , leveraging SAT solvers for equivalence checking. We evaluated our procedures on a series of benchmarks that show significant performance improvement over existing implementations for (CF-)GKAT . Notably, our experiments also revealed a bug in Ghidra, an industry-standard decompiler, highlighting the practicality of our algorithms. Symbolic techniques have been successfully applied to various problems surrounding (extended) regular expressions, with a wide range of real-world applications, including but not limited to low level program analysis [ 11 ] , list comprehension [ 36 ] , constraint solving [ 43 ] , HTML decoding, malware fingerprinting, image blurring, location privacy [ 45 ] , regex processing, and string sanitizer [ 46 ] . Our paper deviates from this line of research in the following ways: first, the problem of normalization is unique to GKAT and not present in other works; second, GKAT automata have a unique shape, where accepting states are replaced by functions on atoms, similar to automata on guarded strings [ 25 ] . The closest symbolic work to ours is by 33 and 29 , which provide symbolic algorithm for KAT and NetKAT, respectively, using BDDs. Our work demonstrates the efficiency and flexibility of Boolean formulae, and it would be interesting to explore whether our approach can be applied to extensions of KAT and not just GKAT . Further research is also needed to apply our method in other extensions of GKAT other than CF-GKAT . For example, the decision procedures for weighted and probabilistic GKAT [ 35 , 44 ] both rely on coalgebraic partition refinement [ 12 ] . It would be interesting to see if we can generalize our symbolic techniques to provide support for (coalgebraic) partition refinement. Another challenging extension is (Guarded) NetKAT [ 2 , 48 ] , which allows packet field assignments and tests, similar to indicator assignments and tests in CF-GKAT . However, the indicator state in CF-GKAT is not symbolic, and hence our current algorithm cannot be easily adapted to improve the performance of (Guarded) NetKAT . This inefficiency is mostly inconsequential when testing Ghidra, as indicator variables are seldom produced by its decompilation. Nevertheless, it would be interesting to see if we can develop a symbolic version of NetKAT automata [ 16 ] with Boolean formulae, and evaluate it against KATch [ 29 ] , an equivalence checker based on extended BDDs. Data Availability Statement The code for our implementations and test suites are included in our artifact [ 17 ] . The software and source code used in evaluating our project, like Ghidra [ 30 ] , Clang [ 27 ] , SymKAT [ 33 ] , previous CF-GKAT implementation [ 52 , 53 ] , and CoreUtils [ 18 ] are all publically available and open-source. Appendix 0.A Correctness of Non-symbolic Algorithm And Up-to Technique 0.A.1 Progression and Compatiblity Before we prove the correctness of the non-symbolic version, we will introduce a more generic notation for the checks performed on in algorithm Figure 5 . In this definition we range over a generic predicate P instead of just isDead as in Figure 5 ; in this way, we have a uniform notation for the trace equivalence algorithm and bisimulation equivalence algorithm, where isDead is replaced by the constant false function. Definition 6 (Progression) Given two automata over state sets S and U , and two relations R,R^{\prime}\subseteq S\times U . We write R\rightarrowtail^{P}_{\alpha}R^{\prime} when all the following conditions hold: 1. s\mathrel{\resizebox{}{}{{\hbox{\hskip 0.0pt\raise-5.0pt\hbox{{$\xRightarrow{\alpha}$}}}}}}{\mathbf{ret}} if and only if u\mathrel{\resizebox{}{}{{\hbox{\hskip 0.0pt\raise-5.0pt\hbox{{$\xRightarrow{\alpha}$}}}}}}{\mathbf{ret}} ; 2. if s\mathrel{\raisebox{-2.0pt}{$\xrightarrow{\alpha\mid p}$}}s^{\prime} and u\lightning^{\alpha} , then P(s^{\prime}) ; 3. if u\mathrel{\raisebox{-2.0pt}{$\xrightarrow{\alpha\mid p}$}}u^{\prime} and s\lightning^{\alpha} , then P(u^{\prime}) ; 4. if s\mathrel{\raisebox{-2.0pt}{$\xrightarrow{\alpha\mid p}$}}s^{\prime} and u\mathrel{\raisebox{-2.0pt}{$\xrightarrow{\alpha\mid q}$}}u^{\prime} and p\neq q , then both P(s^{\prime}) and P(u^{\prime}) ; 5. if s\mathrel{\raisebox{-2.0pt}{$\xrightarrow{\alpha\mid p}$}}s^{\prime} and u\mathrel{\raisebox{-2.0pt}{$\xrightarrow{\alpha\mid p}$}}u^{\prime} then (s^{\prime},u^{\prime})\in R^{\prime} . We write R\rightarrowtail^{P}R^{\prime} when R\rightarrowtail^{P}_{\alpha}R^{\prime} for all \alpha\in\mathbf{At} , and we call the relation R an invariant if R\rightarrowtail^{P}R . The definition of R\rightarrowtail^{P}R^{\prime} parameterize over a predicate P . In the case of trace equivalence, the predicate P is instantiated to isDead , then R\rightarrowtail^{{\textsc{isDead}}}R^{\prime} exactly represents the condition checked by the non-symbolic algorithm Figure 5 ; when P is instantiated to the constant false function, then R\rightarrowtail^{\mathrm{false}}R^{\prime} will represent the conditions checked by the version of the algorithm that checks for bisimulation equivalence, where all the isDead and knownDead is replaced by the constant false function. The name progression is not chosen at random, 32 give a general criteria for progressions that supports the up-to techniques in a complete lattice. Indeed, as R and R^{\prime} are relations, they live in a complete lattice ordered by set inclusion. Theorem 0.A.1 (Progression Soundness) Progression as defined in Definition 6 indeed satisfies the two requirements set by 32 , which are listed below: \frac{R_{1}\subseteq R_{0}\quad R_{0}\rightarrowtail^{P}R_{0}^{\prime}\quad R_{0}^{\prime}\subseteq R_{1}^{\prime}}{R_{1}\rightarrowtail^{P}R_{1}^{\prime}}\frac{\forall i\in I,~R_{i}\rightarrowtail^{P}R^{\prime}}{(\textstyle{\bigcup_{i\in I}R_{i}})\rightarrowtail^{P}R^{\prime}} Proof The proof is simply by unfolding the five conditions in Definition 6 . To prove R_{1}\rightarrowtail^{P}R_{1}^{\prime} in the first requirement, we will need to show all five conditions in Definition 6 holds, take any pair of states (s,u)\in R_{1}\subseteq R_{0} , we will need to show the transition of (s,u) follows all the five conditions required for R_{1}\rightarrowtail^{P}R_{1}^{\prime} : 1. s\mathrel{\resizebox{}{}{{\hbox{\hskip 0.0pt\raise-5.0pt\hbox{{$\xRightarrow{\alpha}$}}}}}}{\mathbf{ret}} if and only if u\mathrel{\resizebox{}{}{{\hbox{\hskip 0.0pt\raise-5.0pt\hbox{{$\xRightarrow{\alpha}$}}}}}}{\mathbf{ret}} , because (s,u)\in R_{0} and R_{0}\rightarrowtail^{P}R_{0}^{\prime} . 2. If s\mathrel{\raisebox{-2.0pt}{$\xrightarrow{\alpha\mid p}$}}s^{\prime} and u\lightning^{\alpha} , then P(s^{\prime}) , because (s,u)\in R_{0} and R_{0}\rightarrowtail^{P}R_{0}^{\prime} . And the rest of the cases follows exactly the same pattern. Then we show \bigcup_{i\in I}R_{i}\rightarrowtail^{P}R^{\prime} , take any pair of states (s,u)\in\bigcup_{i\in I}R_{i} , then there exists j\in I , s.t. (s,u)\in R_{j} . Thus, all the five condition indeed hold for (s,u) , because (s,u)\in R_{j}\rightarrowtail^{P}R^{\prime} . We first prove that the equivalence closure e is a compatible function with the progression we have developed, this allows us to use the up-to technique in the correctness theorem of the algorithms ( Theorems 0.A.4 and 0.A.7 ). Theorem 0.A.2 Reflexive closure \mathsf{ref} and symmetric closure \mathsf{sym} are compatible with the progression R\rightarrowtail^{P}R^{\prime} for R,R^{\prime}\subseteq S\times S . Proof Recall that a function f is compatible with the progression \rightarrowtail^{P} if R\rightarrowtail^{P}R^{\prime}\implies f(R)\rightarrowtail^{P}f(R^{\prime}) which because our progression is sound ( Theorem 0.A.1 ), we only need to show for all (s,u)\in f(R) , then \{(s,u)\}\rightarrowtail^{P}f(R^{\prime}) , then the conclusion f(R)\rightarrowtail^{P}f(R^{\prime}) can be reached by unioning all of these singleton set \{(s,u)\} . \mathsf{ref} is compatible: since \mathsf{ref}(R)=R\cup\{(s,s)\mid s\in S\} , • If (s,u)\in R , then \{(s,u)\}\rightarrowtail^{P}R^{\prime} , and because R^{\prime}\subseteq\mathsf{ref}(R^{\prime}) , by definition of progression, we get \{(s,u)\}\rightarrowtail^{P}\mathsf{ref}(R^{\prime}) . • If (s,u) for s=u , then there transitions needs will satisfy all the rules of Definition 6 : rule 1 and rule 5 is trivial, the premise of rule 2, 3, 4 will always be false. \mathsf{sym} is compatible: since \mathsf{sym}(R)=R\cup\{(u,s)\mid(s,u)\in R\} , • If (s,u)\in R , then \{(s,u)\}\rightarrowtail^{P}R^{\prime} , and because R^{\prime}\subseteq\mathsf{sym}(R^{\prime}) , by definition of progression, we get \{(s,u)\}\rightarrowtail^{P}\mathsf{sym}(R^{\prime}) . • If (s,u)\in R , then \{(u,s)\}\rightarrowtail^{P}\mathsf{sym}(R^{\prime}) , because all the conditions in our progression are symmetric: condition 1 is true for (u,s) because condition 1 is true for (s,u) ; condition 2 is true for (u,s) because condition 3 is true for (s,u) ; similarly for the rest of the conditions. However, the situation for transitive closure is a bit more convoluted, as the transitive closure \mathsf{trans} is not compatible with our instance of progression \rightarrowtail^{P} , even in the special case where P={\textsc{isDead}} . Example 2 (Transitive Closure is not Compatible) Consider a GKAT automaton with only one atom 1 (i.e. have no primitive tests), and the following states: s_{0}\lightning^{1}\qquad s_{1}\mathrel{\raisebox{-2.0pt}{$\xrightarrow{1\mid p}$}}s_{1}\qquad s_{2}\mathrel{\raisebox{-2.0pt}{$\xrightarrow{1\mid p}$}}s_{3}\qquad s_{3}\mathrel{\resizebox{}{}{{\hbox{\hskip 0.0pt\raise-5.0pt\hbox{{$\xRightarrow{1}$}}}}}}{\mathbf{ret}} then let R\triangleq\{(s_{0},s_{1}),(s_{1},s_{2})\} and R^{\prime}\triangleq\{(s_{1},s_{3})\} : even though R\rightarrowtail^{{\textsc{isDead}}}R^{\prime} , the transitive closure \mathsf{trans}(R)=\{(s_{0},s_{1}),(s_{1},s_{2}),(s_{0},s_{2})\} does not progress to \mathsf{trans}(R^{\prime})=\{(s_{1},s_{3})\} , as s_{0}\lightning^{1} , yet s_{2} transitions to a live state s_{3} . Thus, R\rightarrowtail^{{\textsc{isDead}}}R^{\prime}\quad\text{does \emph{not} imply}\quad\mathsf{trans}(R)\rightarrowtail^{{\textsc{isDead}}}\mathsf{trans}(R^{\prime})\ . For people familiar with the work of 32 , this example also shows that the progression \rightarrowtail^{{\textsc{isDead}}} does not preserve the internal monoid of relations, where the monoidal operation is relation composition. 0.A.2 Correctness of the Algorithm for Infinite-trace Equivalence In fact, the core difficulty behind the incompatibility of transitive closure is that the progression \rightarrowtail^{{\textsc{isDead}}} does not preserve relation composition \fatsemi , as demonstrated by Example 2 : R_{1}\rightarrowtail^{{\textsc{isDead}}}R_{1}^{\prime}\text{ and }R_{2}\rightarrowtail^{{\textsc{isDead}}}R_{2}^{\prime}\quad\text{does \emph{not} imply}\quad R_{1}\fatsemi R_{2}\rightarrowtail^{{\textsc{isDead}}}R_{1}^{\prime}\fatsemi R_{2}^{\prime}\ . However, the progression \rightarrowtail^{\mathrm{false}} , used for infinite-trace equivalence, does preserve composition, which we will demonstrate below, and show how the preservation of composition leads to compatiblity of transitive closure. Lemma 1 (Preservation of Composition) The progression \rightarrowtail^{\mathrm{false}} preserves relation composition \fatsemi : R_{1}\rightarrowtail^{\mathrm{false}}R_{1}^{\prime}\quad\text{and}\quad R_{2}\rightarrowtail^{\mathrm{false}}R_{2}^{\prime}\quad\text{implies}\quad R_{1}\fatsemi R_{2}\rightarrowtail^{\mathrm{false}}R_{1}^{\prime}\fatsemi R_{2}^{\prime}\ . Proof We show that for all (s,u)\in R_{1}\fatsemi R_{2} and \alpha\in\mathbf{At} , \{(s,u)\}\rightarrowtail^{\mathrm{false}}R_{1}^{\prime}\fatsemi R_{2}^{\prime} . Recall that (s,u)\in R_{1}\fatsemi R_{2} if and only if there exists an m s.t. (s,m)\in R_{1} and (m,u)\in R_{2} : • Condition 1 holds because s\mathrel{\resizebox{}{}{{\hbox{\hskip 0.0pt\raise-5.0pt\hbox{{$\xRightarrow{\alpha}$}}}}}}{\mathbf{ret}} iff m\mathrel{\resizebox{}{}{{\hbox{\hskip 0.0pt\raise-5.0pt\hbox{{$\xRightarrow{\alpha}$}}}}}}{\mathbf{ret}} iff u\mathrel{\resizebox{}{}{{\hbox{\hskip 0.0pt\raise-5.0pt\hbox{{$\xRightarrow{\alpha}$}}}}}}{\mathbf{ret}} . • Condition 2: assume s\lightning^{\alpha} and u\mathrel{\raisebox{-2.0pt}{$\xrightarrow{\alpha\mid p}$}}u^{\prime} , we will derive a contradiction by analyzing the transition of m : – if m\mathrel{\resizebox{}{}{{\hbox{\hskip 0.0pt\raise-5.0pt\hbox{{$\xRightarrow{\alpha}$}}}}}}{\mathbf{ret}} , then there is a contradiction because s\lightning^{\alpha} and (s,m)\in R_{1} . – if m\lightning^{\alpha} , then there is a contradiction because u\mathrel{\raisebox{-2.0pt}{$\xrightarrow{\alpha\mid p}$}}u^{\prime} and (m,u)\in R_{2} ; – if m\mathrel{\raisebox{-2.0pt}{$\xrightarrow{\alpha\mid q}$}}m^{\prime} , then there is a contradiction because s\lightning^{\alpha} and (s,m)\in R_{1} ; • The proof of condition 3 is symmetric to condition 2. • Condition 4: assume s\mathrel{\raisebox{-2.0pt}{$\xrightarrow{\alpha\mid p}$}}s^{\prime} and u\mathrel{\raisebox{-2.0pt}{$\xrightarrow{\alpha\mid q}$}}u^{\prime} and p\neq q , we can derive a contradiction by case analysis on the transition of m , similar to condition 2. • Condition 5: when s\mathrel{\raisebox{-2.0pt}{$\xrightarrow{\alpha\mid p}$}}s^{\prime} and u\mathrel{\raisebox{-2.0pt}{$\xrightarrow{\alpha\mid p}$}}u^{\prime} , we will show m\mathrel{\raisebox{-2.0pt}{$\xrightarrow{\alpha\mid p}$}}m^{\prime} , by case analysis on the transition of m : – if m\mathrel{\resizebox{}{}{{\hbox{\hskip 0.0pt\raise-5.0pt\hbox{{$\xRightarrow{\alpha}$}}}}}}{\mathbf{ret}} , then because s\mathrel{\raisebox{-2.0pt}{$\xrightarrow{\alpha\mid p}$}}s^{\prime} and (s,m)\in R_{1} , contradicting condition 1 for R_{1} ; – if m\lightning^{\alpha} , then because s\mathrel{\raisebox{-2.0pt}{$\xrightarrow{\alpha\mid p}$}}s^{\prime} and (s,m)\in R_{1} , a contradiction can be derived via condition 2; – if m\mathrel{\raisebox{-2.0pt}{$\xrightarrow{\alpha\mid q}$}}m^{\prime} , and p\neq q , then because s\mathrel{\raisebox{-2.0pt}{$\xrightarrow{\alpha\mid p}$}}s^{\prime} and (s,m)\in R_{1} , a contradiction cna be derived via condition 4; Therefore the only possible transition is m\mathrel{\raisebox{-2.0pt}{$\xrightarrow{\alpha\mid p}$}}m^{\prime} , and by condition 5 for both R_{1} and R_{2} , we conclude (s^{\prime},m^{\prime})\in R_{1}^{\prime} and (m^{\prime},u^{\prime})\in R_{2}^{\prime} . Then, by definition of relation composition, (s^{\prime},u^{\prime})\in R_{1}^{\prime}\fatsemi R_{2}^{\prime} . Theorem 0.A.3 The transitive closure \mathsf{trans} is compatible with \rightarrowtail^{\mathrm{false}} : R\rightarrowtail^{\mathrm{false}}R^{\prime}\qquad\text{implies}\qquad\mathsf{trans}(R)\rightarrowtail^{\mathrm{false}}\mathsf{trans}(R^{\prime}) Proof Recall that \mathsf{trans}(R) is defined as \bigcup\{R^{n}\mid n\in\mathbb{N},n\geq 1\} . where R^{1}\triangleq R and R^{k+1}\triangleq R\fatsemi R^{k} . Because \rightarrowtail^{\mathrm{false}} preserves relation composition, we can show that R^{n}\rightarrowtail^{\mathrm{false}}R^{n} for all n\geq 1 by a simple induction. And we can derive the desired result by the following chain of implications: \displaystyle\forall n\geq 1,R^{n}\rightarrowtail^{\mathrm{false}}R^{n} simple induction implies \displaystyle\forall n\geq 1,R^{n}\rightarrowtail^{\mathrm{false}}\mathsf{trans}(R) Theorem 0.A.1 , R^{n}\subseteq\mathsf{trans}(R) implies \displaystyle\bigcup_{n\geq 1}R^{n}\rightarrowtail^{\mathrm{false}}\mathsf{trans}(R) implies \displaystyle\mathsf{trans}(R)\rightarrowtail^{\mathrm{false}}\mathsf{trans}(R) definition of \mathsf{trans} Corollary 1 (Compatiblity of Equivalence Closure) Because the refexive closure \mathsf{ref} , symmetric closure \mathsf{sym} , and transitive closure \mathsf{trans} are compatible with the progression \rightarrowtail^{\mathrm{false}} , then the equivalence closure e=\mathsf{ref}\circ\mathsf{sym}\circ\mathsf{sym} is also compatible. More concretely R\rightarrowtail^{\mathrm{false}}e(R) implies R is contained in an invariant of \rightarrowtail^{\mathrm{false}} . The first proof we give is bisimulation version of the algorithm, where the checked condition can be represented as R\rightarrowtail^{\mathrm{false}}R^{\prime} . This version is easier to prove because, by definition, R is a bisimulation relation if and only if R\rightarrowtail^{\mathrm{false}}R , that is when R is an invariant of \rightarrowtail^{\mathrm{false}} . Indeed, if P is false, then condition (2)-(4) will be false when their premises are true; thus the pair s,u either both return (condition (1)) or both transition and execute the same action (condition (5)). Additionally, the optimization from lines 4-7 will never be invoked. Theorem 0.A.4 (Correctness of Infinite-trace Equivalence) When the knownDead and isDead is replaced by constant false function, then {\textsc{equiv}}(s,u) will always terminate if the input automata are finite, and {\textsc{equiv}}(s,u) will return true if and only if s and u are bisimilar. Proof We denote all pairs of the inputs for function union during the program execution as R\subseteq S\times U . Recall that union-find generates the least equivalence relation from all the inputs of union , which we denote as e(R) . We note that e(R) is an equivalence relation on the disjoint union S+U , and this relation coincide with the equivalence of representatives: e(R)=\{(s,u)\mid{\textsc{rep}}(s)={\textsc{rep}}(u)\}. We first obtain termination: because the state sets S and U are finite, thus so is S\times U . Then notice if (s,u)\notin e(R) , then s,u is sent into union on line 3, making (s,u)\in R\subseteq e(R) before the recursive call on line 13 in Figure 5 . Therefore, at each recursive call of equiv , the size of the finite set (S\times U)\setminus e(R) will decrease. As for the correctness, we will construct an inductive invariant for the program, i.e. a triple that holds for the program if it holds for all recursive calls. For readability, we will split the invariant into two cases (formally, the two invariants translates to the conjunction of two implications): the first case is when the return is true; the second is when it is false. First we focus on the case when {\textsc{equiv}}(s,u)=\mathrm{true} . We claim the following post condition holds under the precondition R_{0}=R , where R_{0} is the auxiliary variable to record the starting R : (s,u)\in R\text{ and }(R\setminus R_{0})\rightarrowtail^{\mathrm{false}}e(R). Thus, if the start R_{0} is empty, i.e. starting from an empty union-find object, then we obtain R\rightarrowtail^{\mathrm{false}}e(R) at the end of the execution. Because R is an invariant of \rightarrowtail^{\mathrm{false}} if and only if R is a bisimulation; and equivalence e is compatible with \rightarrowtail^{\mathrm{false}} ( Corollary 1 ), then the ending condition R\rightarrowtail^{\mathrm{false}}e(R) implies (s,u)\in R is in a bisimulation between S and U . We proceed to sketch the proof of the above inductive invariant when {\textsc{equiv}}(s,u)=\mathrm{true} . We let R_{1}=R_{0}\cup\{(s,u)\} , then the following condition is a loop invariant for the for-all loop on lines 8-13: (s,u)\in R\text{ and }(R\setminus R_{1})\rightarrowtail^{\mathrm{false}}e(R)\text{ and }\forall\alpha\in\Lambda,(s,u)\rightarrowtail_{\alpha}e(R), where \Lambda is the explored atoms in the loop. After the loop finishes, \Lambda will just be \mathbf{At} , thus we can obtain the following conclusion: (s,u)\in R\text{ and }(R\setminus R_{1})\rightarrowtail^{\mathrm{false}}e(R)\text{ and }(s,u)\rightarrowtail^{\mathrm{false}}e(R). Because R_{1}=R_{0}\cup\{(s,u)\} , we obtain our conclusion: (s,u)\in R\text{ and }(R\setminus R_{0})\rightarrowtail^{\mathrm{false}}e(R). Second, we consider the case when {\textsc{equiv}}(s,u)=\mathrm{false} . We show the invariant that s\nsim u in the post-condition, which implies s and u are not bisimilar. We note that since knownDead and isDead are replaced with constant false function, therefore in order for {\textsc{equiv}}(s,u)=\mathrm{false} , there exists an atom s.t. at least one of the following is true: • one of s or u accepts, but not the other; • one of s or u transitions, but the other transitions; • s\mathrel{\raisebox{-2.0pt}{$\xrightarrow{\alpha\mid p}$}}s^{\prime} and u\mathrel{\raisebox{-2.0pt}{$\xrightarrow{\alpha\mid q}$}}u^{\prime} , but either p\neq q or {\textsc{equiv}}(s^{\prime},u^{\prime})=\mathrm{false} . By the inductive invariant, {\textsc{equiv}}(s^{\prime},u^{\prime})=\mathrm{false} implies s^{\prime}\nsim u^{\prime} . It is not hard to see if any of the condition above is violated, then s,u violates the condition of the bisimulation. In other word, if s\sim u then the relation \sim cannot be a bisimulation, concluding the desired post-condition s\nsim u . 0.A.3 Correctness of the Algorithm for Finite-trace Equivalence Unfortunately, the correctness of the finite-trace semantics case is not as easy as the bisimulation (or infinite-trace) case, mainly for the following two reasons. First, since we no longer explicitly construct a bisimulation with our algorithm, it is hard to demonstrate every invariant R identifies a bisimulation on normalized coalgebra, which is at the core of the correctness proof of 39 . In particular, to show every invariant of \rightarrowtail^{{\textsc{isDead}}} is a bisimulation on the normalized coalgebra, we will need to show s^{\prime} and u^{\prime} in the last condition have the same liveness; yet, we only know (s^{\prime},u^{\prime})\in R . Second, we will need to use the up-to technique to show that if R\rightarrowtail^{{\textsc{isDead}}}e(R) implies R is in an invariant. Yet, as we have shown in Example 2 , transitive closure, and thus equivalence closure, is not compatible with \rightarrowtail^{{\textsc{isDead}}} . Perhaps quite surprisingly, the easiest way to mitigate both of these problems is to work directly with trace equivalence instead of bisimulation on normalized coalgebra. Indeed, by reasoning about trace, it gives us a strong enough induction hypothesis to prove both that trace equivalence is the maximal invaraint, and the transitive closure \mathsf{trans} is sound (called “correct” by 32 ) with respect to \rightarrowtail^{{\textsc{isDead}}} . Before we prove our core result, we will first recall some common lemma around traces in GKAT automata. Lemma 2 A state s is live if and only if it has at least one trace. Proof If s is live, then there exists a chain to a accepting state s_{n} : s\mathrel{\raisebox{-2.0pt}{$\xrightarrow{\alpha_{1}\mid p_{1}}$}}s_{1}\mathrel{\raisebox{-2.0pt}{$\xrightarrow{\alpha_{2}\mid p_{2}}$}}\dots\mathrel{\raisebox{-2.0pt}{$\xrightarrow{\alpha_{n}\mid p_{n}}$}}s_{n}\mathrel{\resizebox{}{}{{\hbox{\hskip 0.0pt\raise-5.0pt\hbox{{$\xRightarrow{\alpha}$}}}}}}{\mathbf{ret}}, Then by an induction argument, we can show that the trace \alpha_{1}p_{1}\alpha_{2}p_{2}\dots\alpha_{n}p_{n}\alpha is a trace in \llbracket s\rrbracket . In the reverse direction, if we have a trace \alpha_{1}p_{1}\alpha_{2}p_{2}\dots\alpha_{n}p_{n}\alpha\in\llbracket s\rrbracket , then a path to accepting state can be recovered by computing the transitions on \alpha_{1},\alpha_{2},\alpha_{3} and so on: s\mathrel{\raisebox{-2.0pt}{$\xrightarrow{\alpha_{1}\mid p_{1}}$}}s_{1}\mathrel{\raisebox{-2.0pt}{$\xrightarrow{\alpha_{2}\mid p_{2}}$}}\dots\mathrel{\raisebox{-2.0pt}{$\xrightarrow{\alpha_{n}\mid p_{n}}$}}s_{n}\mathrel{\resizebox{}{}{{\hbox{\hskip 0.0pt\raise-5.0pt\hbox{{$\xRightarrow{\alpha}$}}}}}}{\mathbf{ret}}, which implies that s is live. Lemma 3 (Trace Determinacy [ 40 ] ) Given a state s and a starting atom \alpha , there exists at most one trace that starts with \alpha in \llbracket s\rrbracket . Remark 8 The general construction outlined by 5 does not easily apply in this situation, because (1) we work with GKAT automata, instead of a bialgebra; (2) as we have mentioned in the beginning of this sub-section, it is hard to show that every invariant is a bisimulation. Finally, equivalence closure is compatible with progressions defined by 5 , yet we have shown in Example 2 , transitive closure, and thus equivalence closure, is not compatible with our progression \rightarrowtail^{{\textsc{isDead}}} . We will then prove several core theorems that powers our correctness proof. Specifically, we show that trace equivalence is the largest invariant of \rightarrowtail^{{\textsc{isDead}}} and transitive closure \mathsf{trans} is sound 1 1 1 named “correct” by 32 , we call it “sound” to avoid confusion with the “correctness” of our algorithm with respect to \rightarrowtail^{{\textsc{isDead}}} . Interestingly, both of these results can be derived by the following lemma. Lemma 4 Consider two relation R,R^{\prime}\subseteq S\times U on two GKAT automata S and U , if for all traces w : \forall(s,u)\in R,w\in\llbracket s\rrbracket\text{ iff }w\in\llbracket u\rrbracket\qquad\text{implies}\qquad\forall(s,u)\in R^{\prime},w\in\llbracket s\rrbracket\text{ iff }w\in\llbracket u\rrbracket then R\rightarrowtail^{{\textsc{isDead}}}R^{\prime} and (s,u)\in R implies \llbracket s\rrbracket=\llbracket u\rrbracket . Proof We will show that for any pair of states (s,u)\in R and any trace w , w\in\llbracket s\rrbracket if and only if w\in\llbracket u\rrbracket , by induction on the length of w . • If w is a single atom \alpha , then by the first condition, we got the following chain of implications: \alpha\in\llbracket s\rrbracket\quad\text{iff}\quad s\mathrel{\resizebox{}{}{{\hbox{\hskip 0.0pt\raise-5.0pt\hbox{{$\xRightarrow{\alpha}$}}}}}}{\mathbf{ret}}\quad\text{iff}\quad u\mathrel{\resizebox{}{}{{\hbox{\hskip 0.0pt\raise-5.0pt\hbox{{$\xRightarrow{\alpha}$}}}}}}{\mathbf{ret}}\quad\text{iff}\quad\alpha\in\llbracket u\rrbracket. • If w is \alpha p\cdot w^{\prime}\in\llbracket s\rrbracket , then we know that s\mathrel{\raisebox{-2.0pt}{$\xrightarrow{\alpha\mid p}$}}s^{\prime} for some p\in\Sigma , s^{\prime}\in S and w^{\prime}\in\llbracket s^{\prime}\rrbracket . By Lemma 2 , s^{\prime} is a live state. By induction hypothesis, for all (s^{\prime},u^{\prime})\in R , w^{\prime}\in\llbracket s^{\prime}\rrbracket iff w^{\prime}\in\llbracket u^{\prime}\rrbracket . Finally, by the implication in the premise, for all (s^{\prime},u^{\prime})\in R^{\prime} , w^{\prime}\in\llbracket s^{\prime}\rrbracket iff w^{\prime}\in\llbracket u^{\prime}\rrbracket . We show \alpha p\cdot w\in\llbracket u\rrbracket by case analysis on the transition of u with atom \alpha : – if u\mathrel{\resizebox{}{}{{\hbox{\hskip 0.0pt\raise-5.0pt\hbox{{$\xRightarrow{\alpha}$}}}}}}{\mathbf{ret}} , then by the condition 1: s\mathrel{\resizebox{}{}{{\hbox{\hskip 0.0pt\raise-5.0pt\hbox{{$\xRightarrow{\alpha}$}}}}}}{\mathbf{ret}} , violating s\mathrel{\raisebox{-2.0pt}{$\xrightarrow{\alpha\mid p}$}}s^{\prime} ; – if u\lightning^{\alpha} , then by the condition 2, s^{\prime} is dead, violating our conclusion that s^{\prime} is live; – if u\mathrel{\raisebox{-2.0pt}{$\xrightarrow{\alpha\mid q}$}}u^{\prime} and p\neq q , then by condition 4, s^{\prime} is dead; again violating our conclusion that s^{\prime} is live. Thus, the only possible transition u can take under \alpha is u\mathrel{\raisebox{-2.0pt}{$\xrightarrow{\alpha\mid p}$}}u^{\prime} . By condition 5, (s^{\prime},u^{\prime})\in R^{\prime} ; then because w^{\prime}\in\llbracket s^{\prime}\rrbracket iff w^{\prime}\in\llbracket u^{\prime}\rrbracket , concluding that \alpha p\cdot w\in\llbracket u\rrbracket . The fact that \alpha p\cdot w\in\llbracket u\rrbracket implies \alpha p\cdot w\in\llbracket s\rrbracket can be shown by symmetry. Lemma 5 (Invariant Implies Traces Equivalence) If R\rightarrowtail^{{\textsc{isDead}}}R then every pair of states in R are trace-equivalent: for all (s,u)\in R,\llbracket s\rrbracket=\llbracket u\rrbracket . Proof We first note the implication in Lemma 4 holds. Indeed, \forall(s,u)\in R,w\in\llbracket s\rrbracket\text{ iff }w\in\llbracket u\rrbracket\qquad\text{implies}\qquad\forall(s,u)\in R,w\in\llbracket s\rrbracket\text{ iff }w\in\llbracket u\rrbracket Then by Lemma 4 , we conclude that \llbracket s\rrbracket=\llbracket u\rrbracket Lemma 6 (Trace Equivalence is an Invariant) Let R_{\equiv} be the trace equivalence relation: R_{\equiv}\triangleq\{(s,u)\mid(s,u)\in S\times U,\llbracket s\rrbracket=\llbracket u\rrbracket\}\ ,\qquad\text{then}\qquad R_{\equiv}\rightarrowtail^{{\textsc{isDead}}}R_{\equiv}. Proof To show all the conditions for R_{\equiv}\rightarrowtail^{{\textsc{isDead}}}R_{\equiv} are satisfied, we take any pair of trace equivalence states (s,u)\in R and atom \alpha\in\mathbf{At} , we case analysis whether there exists a trace starting with \alpha in \llbracket s\rrbracket and \llbracket u\rrbracket : • If there is no trace that starts with \alpha in both \llbracket s\rrbracket and \llbracket u\rrbracket , then s and u either reject \alpha or transition to a dead state via \alpha : – if both rejects, then it satisfies all the condition; – if one reject and the other transitions to a dead state, then it also satisfies all the conditions; in particular, this case is mentioned in conditions 2 and 3. – if both transition to dead states s^{\prime} and u^{\prime} , then because s^{\prime} and u^{\prime} are dead, hence have no trace ( Lemma 2 ), thus trace equivalent (s^{\prime},u^{\prime})\in R_{\equiv} . • If there is a trace \alpha in \llbracket s\rrbracket and \llbracket u\rrbracket , then by definition s\mathrel{\resizebox{}{}{{\hbox{\hskip 0.0pt\raise-5.0pt\hbox{{$\xRightarrow{\alpha}$}}}}}}{\mathbf{ret}} and u\mathrel{\resizebox{}{}{{\hbox{\hskip 0.0pt\raise-5.0pt\hbox{{$\xRightarrow{\alpha}$}}}}}}{\mathbf{ret}} , satisfying all the five conditions. • If there is a trace \alpha p\cdot w in \llbracket s\rrbracket and \llbracket u\rrbracket , then there exists states s^{\prime} and u^{\prime} : s\mathrel{\raisebox{-2.0pt}{$\xrightarrow{\alpha\mid p}$}}s^{\prime}\qquad\text{and}\qquad u\mathrel{\raisebox{-2.0pt}{$\xrightarrow{\alpha\mid p}$}}u^{\prime}\ . By definition of the trace semantics, we can obtain the following equivalences: w\in\llbracket s^{\prime}\rrbracket\iff\alpha p\cdot w\in\llbracket s\rrbracket\quad\text{and}\quad w\in\llbracket u^{\prime}\rrbracket\iff\alpha p\cdot w\in\llbracket u\rrbracket\ . Finally, we show that \llbracket s\rrbracket=\llbracket u\rrbracket , which conclude that this case also satsifies all the conditions in Definition 6 : \displaystyle w\in\llbracket s^{\prime}\rrbracket\iff\alpha p\cdot w\in\llbracket s\rrbracket\iff\alpha p\cdot w\in\llbracket u\rrbracket\iff\alpha w\in\llbracket u\rrbracket Notice that these are the only cases we need to worry about since (s,u)\in R_{\equiv} , implying \llbracket s\rrbracket=\llbracket u\rrbracket . Thus, we reach our desired conclusion: R_{\equiv}\rightarrowtail^{{\textsc{isDead}}}R_{\equiv} When combining Lemmas 6 and 5 , we obtain that trace equivalence is indeed the maximal invariant that we are looking for. Theorem 0.A.5 (Trace Equivalence is The Maximal Invariant) Given two automata over state sets S and U , then the trace equivalence relation R_{\equiv} : R_{\equiv}\triangleq\{(s,u)\mid(s,u)\in S\times U,\llbracket s\rrbracket=\llbracket u\rrbracket\}, is the maximal invariant, i.e. R_{\equiv}\rightarrowtail^{{\textsc{isDead}}}R_{\equiv} and for all R\subseteq S\times U , R\rightarrowtail^{{\textsc{isDead}}}R\implies R\subseteq R_{\equiv} . Proof R_{\equiv} is an invariant by Lemma 6 Then we prove that R_{\equiv} is maximal. Take any invariant R\rightarrowtail^{{\textsc{isDead}}}R , by Lemma 5 , every pair (s,u)\in R is trace equivalent: \llbracket s\rrbracket=\llbracket u\rrbracket . Therefore, R is contained with in R_{\equiv} : R\subseteq R_{\equiv} It is important that our property of interest, trace equivalence is the maximal invariant, as it allows us to apply the up-to technique [ 32 ] . In particular, we will require the up-to technique with equivalence closure e to prove our algorithm being sound, since we utilize a union-find object in the algorithm to keep trace of the explored states. This optimization enlarges the resulting states of a progression by the equivalence closure. Unfortunately, transitive closure \mathsf{trans} and thus equivalence closure e is not compatible with \rightarrowtail^{{\textsc{isDead}}} . We will show a weaker notion next, that is \mathsf{trans} is “sound” (called “correct” by 32 ): although a sound function is safe to use in an up-to proof, but unlike compatible function, composition of sound function is not necessary still sound. However, post-composing a sound function with a compatible function, still yields a sound Function [ 32 , Theorem 1.7] . This result is enough for us to derive the soundness of the equivalence closure e to be used in the up-to technique, which is crucial for the correctness of our algorithm. Theorem 0.A.6 The transitive closure \mathsf{trans} is sound with respect to \rightarrowtail^{{\textsc{isDead}}} . Proof We claim that it suffices to show that R\rightarrowtail^{{\textsc{isDead}}}\mathsf{trans}(R) implies that for all (s,u)\in R , \llbracket s\rrbracket=\llbracket u\rrbracket . First, we show the above claim indeed implies soundness as defined by 32 , which is \nu(m_{\rightarrowtail}\circ\mathsf{trans})\subseteq\nu(m_{\rightarrowtail}) , where m_{\rightarrowtail}(R^{\prime})\triangleq\bigcup\{R\mid R\rightarrowtail^{{\textsc{isDead}}}R^{\prime}\}\ ;\qquad\nu(f)=\bigcup\{R\mid R\subseteq f(R)\}\ . We prove this fact mostly by unfolding the definitions. Recalling a theorem by 32 , the following is true for all f R\subseteq m_{\rightarrowtail}\circ f(R)\qquad\iff\qquad R\rightarrowtail^{{\textsc{isDead}}}f(R) which means \nu(m_{\rightarrowtail}\circ\mathsf{trans}) is the largest R s.t. R\rightarrowtail^{{\textsc{isDead}}}\mathsf{trans}(R) ; and \nu(m_{\rightarrowtail}) is the largest invariant R\rightarrowtail^{{\textsc{isDead}}}R , which is just trace equivalence R_{\equiv} by Theorem 0.A.5 . Hence, \nu(m_{\rightarrowtail}\circ\mathsf{trans})\subseteq\nu(m_{\rightarrowtail}) simply means that the every R s.t. R\rightarrowtail^{{\textsc{isDead}}}\mathsf{trans}(R) is contained within R_{\equiv} , i.e. for all (s,u)\in R , \llbracket s\rrbracket=\llbracket u\rrbracket . Then to prove that R\rightarrowtail^{{\textsc{isDead}}}\mathsf{trans}(R) implies for all (s,u)\in R , \llbracket s\rrbracket=\llbracket u\rrbracket , we only need to use Lemma 4 , and show that fix any trace w , \forall(s,u)\in R,w\in\llbracket s\rrbracket\iff w\in\llbracket u\rrbracket implies \forall(s,u)\in\mathsf{trans}(R),w\in\llbracket s\rrbracket\iff\llbracket u\rrbracket . Recall that (s,u)\in\mathsf{trans}(R) if and only if there exists a sequence of m_{i} s.t. s\mathrel{R}m_{1}\mathrel{R}m_{2}\mathrel{R}\cdots\mathrel{R}m_{n}\mathrel{R}u\ . Thus, by induction on the length of above chain, we can show that w\in\llbracket s\rrbracket if and only if w\in\llbracket u\rrbracket . Finally, by Lemma 4 , R\rightarrowtail^{{\textsc{isDead}}}\mathsf{trans}(R) implies (s,u)\in R implies \llbracket s\rrbracket=\llbracket u\rrbracket , which then implies that \mathsf{trans} is sound with respect to \rightarrowtail^{{\textsc{isDead}}} . Corollary 2 (Soundness of Equivalence Closure) We recall that for any sound function f , R\rightarrowtail^{{\textsc{isDead}}}f(R) implies R is in the maximal invariant of \rightarrowtail^{{\textsc{isDead}}} , which is trace equivalence. Because \mathsf{trans} is sound and post-composition of sound function with compatible function gives sound functions, thus e=\mathsf{ref}\circ\mathsf{sym}\circ\mathsf{trans} is sound with respect to \rightarrowtail^{{\textsc{isDead}}} . In other word, R\rightarrowtail^{{\textsc{isDead}}}e(R)\qquad\implies\qquad\forall(s,u)\in R,\llbracket s\rrbracket=\llbracket u\rrbracket. Remark 9 To be completely formal, we will need to reason in a different automaton. For example, let R_{\equiv}^{\prime} be the equivalence relation over A_{S} and A_{U} with state sets S and U respectively, whereas e(R) is a relation over the disjoint union S+U and itself. In this case, R_{\equiv}^{\prime} is not necessarily contained in e(R) even when R is an invariant. However, we can parallel compose (a.k.a. coproduct) two automata over state sets S and U , this yields an automaton over state set S+U . The state in the coproduct automata will transition according to the original automata: \zeta(s,\alpha)\triangleq\begin{cases}\zeta_{S}(s,\alpha)&s\in S\\ \zeta_{U}(u,\alpha)&s\in U\end{cases}, where \zeta_{S} and \zeta_{U} are the transition function of the original automata; therefore the trace of each state also coincides with the original trace. Then the trace equivalence relation R_{\equiv} over the coproduct automata and itself is indeed the greatest invariant of \rightarrowtail^{{\textsc{isDead}}} , hence contains the equivalence closure of any invariant R over the coproduct automata and e(R) . Finally, we have all the tools to prove that the algorithm is sound and complete for trace equivalence, which is the second part of Theorem 3.1 Theorem 0.A.7 (Correctness of Finite-Trace Equivalence) {\textsc{equiv}}(s,u) will always terminate if the input automata are finite, and {\textsc{equiv}}(s,u) will return true if and only if s and u are bisimilar. Proof We split the proof into termination and partial correctness. First, we show the termination of the algorithm. Recall that isDead is a DFS on the finite state sets; and knownDead are checking inclusion of the cached dead states, therefore both functions always terminate. We can construct the same termination metric as the proof of Theorem 0.A.4 , (S\times U)\setminus e(R) . Indeed, by observing the algorithm in Figure 5 , we realize that if s,u\notin e(R) then on line 3, we will send them into the function union . After the union (s,u)\in R\subseteq e(R) , which means that (S\times U)\setminus e(R) will decrease before the recursive call on line 13. We then proceed with the partial correctness proof. First, we recall that the notation R\rightarrowtail^{{\textsc{isDead}}}R^{\prime} for two relation R,R^{\prime}\in S\times U when R transition to R^{\prime} following all the conditions in Figure 5 (see the formal definition of progression in Definition 6 ). Like the proof of Theorem 0.A.4 , we split the inductive invariants into two cases for readability. And we also use the relation R to denote all the inputs that have been sent into the union function. Let e(R) be the least equivalence generated by R on the disjoint union of S and U . And we recall that this least equivalence coincide with the equivalence of representatives in the union-find object, e(R)=\{(s,u)\mid{\textsc{rep}}(s)={\textsc{rep}}(u)\}. First, we focus on the case where the output {\textsc{equiv}}(s,u)=\mathrm{true} . Unlike the previous proofs, we will need to take into account of the optimization performed on lines 4-7. We assert the following invariant for the recursion: given the precondition R_{0}=R , where R_{0} is an auxiliary variable to keep track of the starting R , then the following post-condition can be derived: {\textsc{isDead}}(s)\text{ and }{\textsc{isDead}}(u)\quad\text{or}\quad(s,u)\in R\text{ and }(R\setminus R_{0})\rightarrowtail^{{\textsc{isDead}}}e(R). Indeed, if either {\textsc{knownDead}}(s) or {\textsc{knownDead}}(u) is true, then it means both s and u are dead, reaching the condition {\textsc{isDead}}(s)\text{ and }{\textsc{isDead}}(u) . If neither of these are true, we let R_{1}\triangleq R_{0}\cup\{(s,u)\} ; we construct the following invariant for the for-all loop on line 8-13: (s,u)\in R\text{ and }(R\setminus R_{1})\rightarrowtail^{{\textsc{isDead}}}e(R)\text{ and }\forall\alpha\in\Lambda,\{(s,u)\}\rightarrowtail^{{\textsc{isDead}}}_{\alpha}e(R), where \Lambda is all the explored atoms. Then at the end of the loop \Lambda will just be \mathbf{At} , therefore, we derive (s,u)\in R\text{ and }(R\setminus R_{1})\rightarrowtail^{{\textsc{isDead}}}e(R)\text{ and }\{(s,u)\}\rightarrowtail^{{\textsc{isDead}}}e(R), which gives us the desired post-condition R\rightarrowtail^{{\textsc{isDead}}}e(R) and (s,u)\in R , because R\setminus R_{0}=R\setminus R_{1}\cup\{(s,u)\} . Then for the case where {\textsc{equiv}}(s,u)=\mathrm{false} , we prove the invariant that under the precondition true, we can derive the post-condition \llbracket s\rrbracket\neq\llbracket u\rrbracket . This result is a direct consequence of Lemma 6 : if {\textsc{equiv}}(s,u)=\mathrm{false} , then one of the following will be true: • One of s and u is dead, but the other is not. Then by Lemma 2 , one of them will have trace, whereas the other don’t, hence they are clearly not trace equivalent. • there exists \alpha s.t. (s,u)\not\rightarrowtail^{{\textsc{isDead}}}_{\alpha}R_{\equiv} , then by Lemma 6 , s and u are not trace equivalent. Finally, combining the proof of Theorem 0.A.4 and Theorem 0.A.7 , we obtain the proof of the correctness for the non-symbolic algorithm. Proof (Proof of Theorem 3.1 ) Each item is proven by Theorem 0.A.4 and Theorem 0.A.7 respectively. Appendix 0.B Correctness of the Symbolic Algorithm To prove the correctness of the symbolic notation, we first set some notation for symbolic progression , which is characterizes the checks performed on the symbolic algorithm in Figure 7 . Definition 7 (Notation for Symbolic Progression) Given two symbolic GKAT automata over state space S and U respectively, we write R\mathrel{\hbox to13.72pt{\vbox to5.42pt{\pgfpicture\makeatletter\hbox{\hskip 1.16873pt\lower-2.71245pt\hbox to0.0pt{\lxSVG@begingroup@{_scopebegin} \lxSVG@begingroup@{stroke} \lxSVG@begingroup@{fill} \lxSVG@setlinewidth{\the\pgflinewidth}\lxSVG@begingroup@{stroke-width} \lx@inpgf@ignorespaces\nullfont\lxSVG@begingroup@{_scopebegin} \lxSVG@closescope \hbox to0.0pt{\lxSVG@begingroup@{_scopebegin} {}{{}}{} {}{}\lxSVG@begingroup@{_scopebegin} \lxSVG@setlinewidth{\the\pgflinewidth}\lxSVG@begingroup@{stroke-width} \lx@inpgf@ignorespaces{}{{ {{{\lx@inpgf@ignorespaces}} \lxSVG@setlinewidth{\the\pgflinewidth}\lx@inpgf@ignorespaces\lxSVG@setdash{0.0pt}\lx@inpgf@ignorespaces\lxSVG@roundcap\lx@inpgf@ignorespaces\lxSVG@roundjoin\lx@inpgf@ignorespaces{\lx@inpgf@ignorespaces} {\lx@inpgf@ignorespaces}{\lx@inpgf@ignorespaces}{\lx@inpgf@ignorespaces} {\lx@inpgf@ignorespaces}{\lx@inpgf@ignorespaces}{\lx@inpgf@ignorespaces} \lxSVG@stroke}} }{}{}{{}}{{ {{{\lx@inpgf@ignorespaces}} {{\lx@inpgf@ignorespaces}} \lxSVG@setlinewidth{\the\pgflinewidth}\lx@inpgf@ignorespaces\lxSVG@setdash{0.0pt}\lx@inpgf@ignorespaces\lxSVG@roundcap\lx@inpgf@ignorespaces\lxSVG@roundjoin\lx@inpgf@ignorespaces{\lx@inpgf@ignorespaces} {\lx@inpgf@ignorespaces}{\lx@inpgf@ignorespaces}{\lx@inpgf@ignorespaces} {\lx@inpgf@ignorespaces}{\lx@inpgf@ignorespaces}{\lx@inpgf@ignorespaces} \lxSVG@stroke}} }{}{}{{}}\lxSVG@stroke\lxSVG@drawpath@unclipped{M 1.55 0 L 12.71 0}{fill:none} \lxSVG@begingroup@{_scopebegin} {\lxSVG@setlinewidth{\pgfinnerlinewidth}\lxSVG@begingroup@{stroke-width} \lxSVG@begingroup@{stroke} \lxSVG@stroke\lxSVG@drawpath@unclipped{M 1.55 0 L 12.71 0}{fill:none} }\lxSVG@closescope {{}{{}}{}{}{{}}{{{\lx@inpgf@ignorespaces}}{{{\lx@inpgf@ignorespaces}}{\lxSVG@begingroup@{_scopebegin} \lxSVG@transformcm{-1.0}{0.0}{0.0}{-1.0}{1.11748pt}{0.0pt}\lxSVG@begingroup@{transform} \lxSVG@begingroup@{_scopebegin} \lxSVG@begingroup@{stroke-width} \lxSVG@begingroup@{stroke-dasharray,stroke-dashoffset} \lxSVG@begingroup@{stroke-linecap} \lxSVG@begingroup@{stroke-linejoin} \lxSVG@drawpath@unclipped{M 1.8 3.55 C 0.92 1.68 -1.42 0.07 -2.76 0 C -1.42 -0.07 0.92 -1.68 1.8 -3.55}{fill:none} \lxSVG@closescope \lxSVG@closescope }}{{\lx@inpgf@ignorespaces}}}}{{}{{}}{}{}{{}}{{{\lx@inpgf@ignorespaces}}{{{\lx@inpgf@ignorespaces}}{\lxSVG@begingroup@{_scopebegin} \lxSVG@transformcm{1.0}{0.0}{0.0}{1.0}{9.18533pt}{0.0pt}\lxSVG@begingroup@{transform} \lxSVG@begingroup@{_scopebegin} \lxSVG@begingroup@{stroke-width} \lxSVG@begingroup@{stroke-dasharray,stroke-dashoffset} \lxSVG@begingroup@{stroke-linecap} \lxSVG@begingroup@{stroke-linejoin} \lxSVG@drawpath@unclipped{M -1.8 3.55 C -0.92 1.68 1.42 0.07 2.76 0 C 1.42 -0.07 -0.92 -1.68 -1.8 -3.55}{fill:none} \lxSVG@closescope \lxSVG@closescope }}{{\lx@inpgf@ignorespaces}}}}\lx@inpgf@ignorespaces\lxSVG@closescope \lxSVG@closescope {\lx@inpgf@ignorespaces}{\lx@inpgf@ignorespaces}{\lx@inpgf@ignorespaces}\hss}\lxSVG@discardpath\lxSVG@closescope \hss}}\lxSVG@closescope\endpgfpicture}}}^{P}R^{\prime} for a predicate P on the disjoint union S+U , when R transitions according to the conditions from line 9-13 in Figure 7 : for all (s,u)\in R , • \bigvee\epsilon(s)\equiv\bigvee\epsilon(u) under axioms of Boolean algebra; • if s\mathrel{\raisebox{-2.0pt}{$\xrightarrow{b\mid p}$}}s^{\prime} and b\land\rho(u)\not\equiv 0 , then P(s^{\prime}) ; • if u\mathrel{\raisebox{-2.0pt}{$\xrightarrow{b\mid p}$}}u^{\prime} and b\land\rho(u)\not\equiv 0 , then P(u^{\prime}) ; • if s\mathrel{\raisebox{-2.0pt}{$\xrightarrow{b\mid p}$}}s^{\prime} , u\mathrel{\raisebox{-2.0pt}{$\xrightarrow{a\mid q}$}}u^{\prime} , b\land a\not\equiv 0 , and p\neq q , then P(s^{\prime}) and P(u^{\prime}) ; • if s\mathrel{\raisebox{-2.0pt}{$\xrightarrow{b\mid p}$}}s^{\prime} , u\mathrel{\raisebox{-2.0pt}{$\xrightarrow{a\mid p}$}}u^{\prime} , and b\land a\not\equiv 0 , then (s^{\prime},u^{\prime})\in R^{\prime} . In the case of computing trace equivalence, the P will just be dead state detection isDead ; and in the case of computing bisimulation equivalence, P will be the constant false predicate. We first prove a correspondence theorem, to show that the symbolic progression exactly correspond to the non-symbolic progression ( Definition 6 ) on its concretization. Theorem 0.B.1 (Correspondence) Take any two relation over the state sets of two symbolic GKAT automata R,R^{\prime} , the following correspondence holds: R\mathrel{\hbox to13.72pt{\vbox to5.42pt{\pgfpicture\makeatletter\hbox{\hskip 1.16873pt\lower-2.71245pt\hbox to0.0pt{\lxSVG@begingroup@{_scopebegin} \lxSVG@begingroup@{stroke} \lxSVG@begingroup@{fill} \lxSVG@setlinewidth{\the\pgflinewidth}\lxSVG@begingroup@{stroke-width} \lx@inpgf@ignorespaces\nullfont\lxSVG@begingroup@{_scopebegin} \lxSVG@closescope \hbox to0.0pt{\lxSVG@begingroup@{_scopebegin} {}{{}}{} {}{}\lxSVG@begingroup@{_scopebegin} \lxSVG@setlinewidth{\the\pgflinewidth}\lxSVG@begingroup@{stroke-width} \lx@inpgf@ignorespaces{}{}{}{}{{}}{}{}{}{{}}\lxSVG@stroke\lxSVG@drawpath@unclipped{M 1.55 0 L 12.71 0}{fill:none} \lxSVG@begingroup@{_scopebegin} {\lxSVG@setlinewidth{\pgfinnerlinewidth}\lxSVG@begingroup@{stroke-width} \lxSVG@begingroup@{stroke} \lxSVG@stroke\lxSVG@drawpath@unclipped{M 1.55 0 L 12.71 0}{fill:none} }\lxSVG@closescope {{}{{}}{}{}{{}}{{{\lx@inpgf@ignorespaces}}{{{\lx@inpgf@ignorespaces}}{\lxSVG@begingroup@{_scopebegin} \lxSVG@transformcm{-1.0}{0.0}{0.0}{-1.0}{1.11748pt}{0.0pt}\lxSVG@begingroup@{transform} \lxSVG@begingroup@{_scopebegin} \lxSVG@begingroup@{stroke-width} \lxSVG@begingroup@{stroke-dasharray,stroke-dashoffset} \lxSVG@begingroup@{stroke-linecap} \lxSVG@begingroup@{stroke-linejoin} \lxSVG@drawpath@unclipped{M 1.8 3.55 C 0.92 1.68 -1.42 0.07 -2.76 0 C -1.42 -0.07 0.92 -1.68 1.8 -3.55}{fill:none} \lxSVG@closescope \lxSVG@closescope }}{{\lx@inpgf@ignorespaces}}}}{{}{{}}{}{}{{}}{{{\lx@inpgf@ignorespaces}}{{{\lx@inpgf@ignorespaces}}{\lxSVG@begingroup@{_scopebegin} \lxSVG@transformcm{1.0}{0.0}{0.0}{1.0}{9.18533pt}{0.0pt}\lxSVG@begingroup@{transform} \lxSVG@begingroup@{_scopebegin} \lxSVG@begingroup@{stroke-width} \lxSVG@begingroup@{stroke-dasharray,stroke-dashoffset} \lxSVG@begingroup@{stroke-linecap} \lxSVG@begingroup@{stroke-linejoin} \lxSVG@drawpath@unclipped{M -1.8 3.55 C -0.92 1.68 1.42 0.07 2.76 0 C 1.42 -0.07 -0.92 -1.68 -1.8 -3.55}{fill:none} \lxSVG@closescope \lxSVG@closescope }}{{\lx@inpgf@ignorespaces}}}}\lx@inpgf@ignorespaces\lxSVG@closescope \lxSVG@closescope {\lx@inpgf@ignorespaces}{\lx@inpgf@ignorespaces}{\lx@inpgf@ignorespaces}\hss}\lxSVG@discardpath\lxSVG@closescope \hss}}\lxSVG@closescope\endpgfpicture}}}^{P}R^{\prime} if and only if R\rightarrowtail^{P}R^{\prime} in their concretizations. Proof By unfolding the definition of concretization, we obtain the following implications: \displaystyle s\mathrel{\resizebox{}{}{{\hbox{\hskip 0.0pt\raise-5.0pt\hbox{{$\xRightarrow{b}$}}}}}}{\mathbf{ret}} \displaystyle\text{ implies }s\mathrel{\resizebox{}{}{{\hbox{\hskip 0.0pt\raise-5.0pt\hbox{{$\xRightarrow{\alpha}$}}}}}}{\mathbf{ret}}\text{ for all $\alpha\leq b$, in the concrete automata}; \displaystyle s\mathrel{\raisebox{-2.0pt}{$\xrightarrow{b\mid p}$}}s^{\prime} \displaystyle\text{ implies }s\mathrel{\raisebox{-2.0pt}{$\xrightarrow{\alpha\mid p}$}}s^{\prime}\text{ for all $\alpha\leq b$, in the concrete automata}. First, assuming R\mathrel{\hbox to13.72pt{\vbox to5.42pt{\pgfpicture\makeatletter\hbox{\hskip 1.16873pt\lower-2.71245pt\hbox to0.0pt{\lxSVG@begingroup@{_scopebegin} \lxSVG@begingroup@{stroke} \lxSVG@begingroup@{fill} \lxSVG@setlinewidth{\the\pgflinewidth}\lxSVG@begingroup@{stroke-width} \lx@inpgf@ignorespaces\nullfont\lxSVG@begingroup@{_scopebegin} \lxSVG@closescope \hbox to0.0pt{\lxSVG@begingroup@{_scopebegin} {}{{}}{} {}{}\lxSVG@begingroup@{_scopebegin} \lxSVG@setlinewidth{\the\pgflinewidth}\lxSVG@begingroup@{stroke-width} \lx@inpgf@ignorespaces{}{}{}{}{{}}{}{}{}{{}}\lxSVG@stroke\lxSVG@drawpath@unclipped{M 1.55 0 L 12.71 0}{fill:none} \lxSVG@begingroup@{_scopebegin} {\lxSVG@setlinewidth{\pgfinnerlinewidth}\lxSVG@begingroup@{stroke-width} \lxSVG@begingroup@{stroke} \lxSVG@stroke\lxSVG@drawpath@unclipped{M 1.55 0 L 12.71 0}{fill:none} }\lxSVG@closescope {{}{{}}{}{}{{}}{{{\lx@inpgf@ignorespaces}}{{{\lx@inpgf@ignorespaces}}{\lxSVG@begingroup@{_scopebegin} \lxSVG@transformcm{-1.0}{0.0}{0.0}{-1.0}{1.11748pt}{0.0pt}\lxSVG@begingroup@{transform} \lxSVG@begingroup@{_scopebegin} \lxSVG@begingroup@{stroke-width} \lxSVG@begingroup@{stroke-dasharray,stroke-dashoffset} \lxSVG@begingroup@{stroke-linecap} \lxSVG@begingroup@{stroke-linejoin} \lxSVG@drawpath@unclipped{M 1.8 3.55 C 0.92 1.68 -1.42 0.07 -2.76 0 C -1.42 -0.07 0.92 -1.68 1.8 -3.55}{fill:none} \lxSVG@closescope \lxSVG@closescope }}{{\lx@inpgf@ignorespaces}}}}{{}{{}}{}{}{{}}{{{\lx@inpgf@ignorespaces}}{{{\lx@inpgf@ignorespaces}}{\lxSVG@begingroup@{_scopebegin} \lxSVG@transformcm{1.0}{0.0}{0.0}{1.0}{9.18533pt}{0.0pt}\lxSVG@begingroup@{transform} \lxSVG@begingroup@{_scopebegin} \lxSVG@begingroup@{stroke-width} \lxSVG@begingroup@{stroke-dasharray,stroke-dashoffset} \lxSVG@begingroup@{stroke-linecap} \lxSVG@begingroup@{stroke-linejoin} \lxSVG@drawpath@unclipped{M -1.8 3.55 C -0.92 1.68 1.42 0.07 2.76 0 C 1.42 -0.07 -0.92 -1.68 -1.8 -3.55}{fill:none} \lxSVG@closescope \lxSVG@closescope }}{{\lx@inpgf@ignorespaces}}}}\lx@inpgf@ignorespaces\lxSVG@closescope \lxSVG@closescope {\lx@inpgf@ignorespaces}{\lx@inpgf@ignorespaces}{\lx@inpgf@ignorespaces}\hss}\lxSVG@discardpath\lxSVG@closescope \hss}}\lxSVG@closescope\endpgfpicture}}}^{P}R^{\prime} , we prove some conditions in R\rightarrowtail^{P}R^{\prime} as examples: let (s,u)\in R , 1. if s\mathrel{\resizebox{}{}{{\hbox{\hskip 0.0pt\raise-5.0pt\hbox{{$\xRightarrow{\alpha}$}}}}}}{\mathbf{ret}} in the concrete automata, then there exists b s.t. s\mathrel{\resizebox{}{}{{\hbox{\hskip 0.0pt\raise-5.0pt\hbox{{$\xRightarrow{b}$}}}}}}{\mathbf{ret}} and \alpha\leq b . Because \bigvee\varepsilon(s)\equiv\bigvee\varepsilon(u) , therefore there exists \alpha\leq a and u\mathrel{\resizebox{}{}{{\hbox{\hskip 0.0pt\raise-5.0pt\hbox{{$\xRightarrow{a}$}}}}}}{\mathbf{ret}} , which then implies u\mathrel{\resizebox{}{}{{\hbox{\hskip 0.0pt\raise-5.0pt\hbox{{$\xRightarrow{\alpha}$}}}}}}{\mathbf{ret}} in the concrete automaton with states U . Thus, we have proven s\mathrel{\resizebox{}{}{{\hbox{\hskip 0.0pt\raise-5.0pt\hbox{{$\xRightarrow{\alpha}$}}}}}}{\mathbf{ret}} implies u\mathrel{\resizebox{}{}{{\hbox{\hskip 0.0pt\raise-5.0pt\hbox{{$\xRightarrow{\alpha}$}}}}}}{\mathbf{ret}} , and the reverse direction can be obtained by symmetry. 2. Assume s\mathrel{\raisebox{-2.0pt}{$\xrightarrow{\alpha\mid p}$}}s^{\prime} and u\lightning^{\alpha} in the automata. By definition of concretization, there exists b s.t. \alpha\leq b and s\mathrel{\raisebox{-2.0pt}{$\xrightarrow{b\mid p}$}}s^{\prime} . Additionally, \alpha\in\rho(u) . This means \mathrel{\raisebox{-2.0pt}{$\xrightarrow{b\mid p}$}}s^{\prime} and \rho(u)\land b\not\equiv 0 , because R\mathrel{\hbox to13.72pt{\vbox to5.42pt{\pgfpicture\makeatletter\hbox{\hskip 1.16873pt\lower-2.71245pt\hbox to0.0pt{\lxSVG@begingroup@{_scopebegin} \lxSVG@begingroup@{stroke} \lxSVG@begingroup@{fill} \lxSVG@setlinewidth{\the\pgflinewidth}\lxSVG@begingroup@{stroke-width} \lx@inpgf@ignorespaces\nullfont\lxSVG@begingroup@{_scopebegin} \lxSVG@closescope \hbox to0.0pt{\lxSVG@begingroup@{_scopebegin} {}{{}}{} {}{}\lxSVG@begingroup@{_scopebegin} \lxSVG@setlinewidth{\the\pgflinewidth}\lxSVG@begingroup@{stroke-width} \lx@inpgf@ignorespaces{}{}{}{}{{}}{}{}{}{{}}\lxSVG@stroke\lxSVG@drawpath@unclipped{M 1.55 0 L 12.71 0}{fill:none} \lxSVG@begingroup@{_scopebegin} {\lxSVG@setlinewidth{\pgfinnerlinewidth}\lxSVG@begingroup@{stroke-width} \lxSVG@begingroup@{stroke} \lxSVG@stroke\lxSVG@drawpath@unclipped{M 1.55 0 L 12.71 0}{fill:none} }\lxSVG@closescope {{}{{}}{}{}{{}}{{{\lx@inpgf@ignorespaces}}{{{\lx@inpgf@ignorespaces}}{\lxSVG@begingroup@{_scopebegin} \lxSVG@transformcm{-1.0}{0.0}{0.0}{-1.0}{1.11748pt}{0.0pt}\lxSVG@begingroup@{transform} \lxSVG@begingroup@{_scopebegin} \lxSVG@begingroup@{stroke-width} \lxSVG@begingroup@{stroke-dasharray,stroke-dashoffset} \lxSVG@begingroup@{stroke-linecap} \lxSVG@begingroup@{stroke-linejoin} \lxSVG@drawpath@unclipped{M 1.8 3.55 C 0.92 1.68 -1.42 0.07 -2.76 0 C -1.42 -0.07 0.92 -1.68 1.8 -3.55}{fill:none} \lxSVG@closescope \lxSVG@closescope }}{{\lx@inpgf@ignorespaces}}}}{{}{{}}{}{}{{}}{{{\lx@inpgf@ignorespaces}}{{{\lx@inpgf@ignorespaces}}{\lxSVG@begingroup@{_scopebegin} \lxSVG@transformcm{1.0}{0.0}{0.0}{1.0}{9.18533pt}{0.0pt}\lxSVG@begingroup@{transform} \lxSVG@begingroup@{_scopebegin} \lxSVG@begingroup@{stroke-width} \lxSVG@begingroup@{stroke-dasharray,stroke-dashoffset} \lxSVG@begingroup@{stroke-linecap} \lxSVG@begingroup@{stroke-linejoin} \lxSVG@drawpath@unclipped{M -1.8 3.55 C -0.92 1.68 1.42 0.07 2.76 0 C 1.42 -0.07 -0.92 -1.68 -1.8 -3.55}{fill:none} \lxSVG@closescope \lxSVG@closescope }}{{\lx@inpgf@ignorespaces}}}}\lx@inpgf@ignorespaces\lxSVG@closescope \lxSVG@closescope {\lx@inpgf@ignorespaces}{\lx@inpgf@ignorespaces}{\lx@inpgf@ignorespaces}\hss}\lxSVG@discardpath\lxSVG@closescope \hss}}\lxSVG@closescope\endpgfpicture}}}^{P}R^{\prime} , we obtained P(b) . Then assume R\rightarrowtail^{P}R^{\prime} , we will prove some condition in R\mathrel{\hbox to13.72pt{\vbox to5.42pt{\pgfpicture\makeatletter\hbox{\hskip 1.16873pt\lower-2.71245pt\hbox to0.0pt{\lxSVG@begingroup@{_scopebegin} \lxSVG@begingroup@{stroke} \lxSVG@begingroup@{fill} \lxSVG@setlinewidth{\the\pgflinewidth}\lxSVG@begingroup@{stroke-width} \lx@inpgf@ignorespaces\nullfont\lxSVG@begingroup@{_scopebegin} \lxSVG@closescope \hbox to0.0pt{\lxSVG@begingroup@{_scopebegin} {}{{}}{} {}{}\lxSVG@begingroup@{_scopebegin} \lxSVG@setlinewidth{\the\pgflinewidth}\lxSVG@begingroup@{stroke-width} \lx@inpgf@ignorespaces{}{}{}{}{{}}{}{}{}{{}}\lxSVG@stroke\lxSVG@drawpath@unclipped{M 1.55 0 L 12.71 0}{fill:none} \lxSVG@begingroup@{_scopebegin} {\lxSVG@setlinewidth{\pgfinnerlinewidth}\lxSVG@begingroup@{stroke-width} \lxSVG@begingroup@{stroke} \lxSVG@stroke\lxSVG@drawpath@unclipped{M 1.55 0 L 12.71 0}{fill:none} }\lxSVG@closescope {{}{{}}{}{}{{}}{{{\lx@inpgf@ignorespaces}}{{{\lx@inpgf@ignorespaces}}{\lxSVG@begingroup@{_scopebegin} \lxSVG@transformcm{-1.0}{0.0}{0.0}{-1.0}{1.11748pt}{0.0pt}\lxSVG@begingroup@{transform} \lxSVG@begingroup@{_scopebegin} \lxSVG@begingroup@{stroke-width} \lxSVG@begingroup@{stroke-dasharray,stroke-dashoffset} \lxSVG@begingroup@{stroke-linecap} \lxSVG@begingroup@{stroke-linejoin} \lxSVG@drawpath@unclipped{M 1.8 3.55 C 0.92 1.68 -1.42 0.07 -2.76 0 C -1.42 -0.07 0.92 -1.68 1.8 -3.55}{fill:none} \lxSVG@closescope \lxSVG@closescope }}{{\lx@inpgf@ignorespaces}}}}{{}{{}}{}{}{{}}{{{\lx@inpgf@ignorespaces}}{{{\lx@inpgf@ignorespaces}}{\lxSVG@begingroup@{_scopebegin} \lxSVG@transformcm{1.0}{0.0}{0.0}{1.0}{9.18533pt}{0.0pt}\lxSVG@begingroup@{transform} \lxSVG@begingroup@{_scopebegin} \lxSVG@begingroup@{stroke-width} \lxSVG@begingroup@{stroke-dasharray,stroke-dashoffset} \lxSVG@begingroup@{stroke-linecap} \lxSVG@begingroup@{stroke-linejoin} \lxSVG@drawpath@unclipped{M -1.8 3.55 C -0.92 1.68 1.42 0.07 2.76 0 C 1.42 -0.07 -0.92 -1.68 -1.8 -3.55}{fill:none} \lxSVG@closescope \lxSVG@closescope }}{{\lx@inpgf@ignorespaces}}}}\lx@inpgf@ignorespaces\lxSVG@closescope \lxSVG@closescope {\lx@inpgf@ignorespaces}{\lx@inpgf@ignorespaces}{\lx@inpgf@ignorespaces}\hss}\lxSVG@discardpath\lxSVG@closescope \hss}}\lxSVG@closescope\endpgfpicture}}}^{P}R^{\prime} as examples: let (s,u)\in R 1. take any \alpha\leq\bigvee\varepsilon(s) , then there exists a b\in\varepsilon(s) , s.t. \alpha\leq b , which implies s\mathrel{\resizebox{}{}{{\hbox{\hskip 0.0pt\raise-5.0pt\hbox{{$\xRightarrow{\alpha}$}}}}}}{\mathbf{ret}} in the concretization. Because s\mathrel{\resizebox{}{}{{\hbox{\hskip 0.0pt\raise-5.0pt\hbox{{$\xRightarrow{\alpha}$}}}}}}{\mathbf{ret}} iff u\mathrel{\resizebox{}{}{{\hbox{\hskip 0.0pt\raise-5.0pt\hbox{{$\xRightarrow{\alpha}$}}}}}}{\mathbf{ret}} , there exists u\mathrel{\resizebox{}{}{{\hbox{\hskip 0.0pt\raise-5.0pt\hbox{{$\xRightarrow{a}$}}}}}}{\mathbf{ret}} where \alpha\leq a , implying \alpha\leq\bigvee\varepsilon(u) . Because atoms are truth assignments, and we just proved \alpha\leq\bigvee\varepsilon(s) implies \alpha\leq\bigvee\varepsilon(u) , this means \bigvee\varepsilon(s)\leq\bigvee\varepsilon(u) in Boolean algebra; and the reverse direction \bigvee\varepsilon(s)\geq\bigvee\varepsilon(u) is shown by symmetric argument. 2. Assume s\mathrel{\raisebox{-2.0pt}{$\xrightarrow{b\mid p}$}}s^{\prime} and b\land\rho(u)\not\equiv 0 , then there exists an atom \alpha s.t. \alpha\leq b and \alpha\leq\rho(u) . By definition of concretization, s\mathrel{\raisebox{-2.0pt}{$\xrightarrow{\alpha\mid p}$}}s^{\prime} and u\lightning^{\alpha} . Because R\rightarrowtail^{P}R^{\prime} , therefore we reached P(s^{\prime}) . All the other cases follows exactly the same pattern as the listed case, therefore we opt to omit them in this paper. Proof (Proof of Theorem 3.2 ) The proof essentially by reducing to Theorems 0.A.7 and 0.A.4 , where we show that we can construct similar loop invariants with \mathrel{\hbox to13.72pt{\vbox to5.42pt{\pgfpicture\makeatletter\hbox{\hskip 1.16873pt\lower-2.71245pt\hbox to0.0pt{\lxSVG@begingroup@{_scopebegin} \lxSVG@begingroup@{stroke} \lxSVG@begingroup@{fill} \lxSVG@setlinewidth{\the\pgflinewidth}\lxSVG@begingroup@{stroke-width} \lx@inpgf@ignorespaces\nullfont\lxSVG@begingroup@{_scopebegin} \lxSVG@closescope \hbox to0.0pt{\lxSVG@begingroup@{_scopebegin} {}{{}}{} {}{}\lxSVG@begingroup@{_scopebegin} \lxSVG@setlinewidth{\the\pgflinewidth}\lxSVG@begingroup@{stroke-width} \lx@inpgf@ignorespaces{}{}{}{}{{}}{}{}{}{{}}\lxSVG@stroke\lxSVG@drawpath@unclipped{M 1.55 0 L 12.71 0}{fill:none} \lxSVG@begingroup@{_scopebegin} {\lxSVG@setlinewidth{\pgfinnerlinewidth}\lxSVG@begingroup@{stroke-width} \lxSVG@begingroup@{stroke} \lxSVG@stroke\lxSVG@drawpath@unclipped{M 1.55 0 L 12.71 0}{fill:none} }\lxSVG@closescope {{}{{}}{}{}{{}}{{{\lx@inpgf@ignorespaces}}{{{\lx@inpgf@ignorespaces}}{\lxSVG@begingroup@{_scopebegin} \lxSVG@transformcm{-1.0}{0.0}{0.0}{-1.0}{1.11748pt}{0.0pt}\lxSVG@begingroup@{transform} \lxSVG@begingroup@{_scopebegin} \lxSVG@begingroup@{stroke-width} \lxSVG@begingroup@{stroke-dasharray,stroke-dashoffset} \lxSVG@begingroup@{stroke-linecap} \lxSVG@begingroup@{stroke-linejoin} \lxSVG@drawpath@unclipped{M 1.8 3.55 C 0.92 1.68 -1.42 0.07 -2.76 0 C -1.42 -0.07 0.92 -1.68 1.8 -3.55}{fill:none} \lxSVG@closescope \lxSVG@closescope }}{{\lx@inpgf@ignorespaces}}}}{{}{{}}{}{}{{}}{{{\lx@inpgf@ignorespaces}}{{{\lx@inpgf@ignorespaces}}{\lxSVG@begingroup@{_scopebegin} \lxSVG@transformcm{1.0}{0.0}{0.0}{1.0}{9.18533pt}{0.0pt}\lxSVG@begingroup@{transform} \lxSVG@begingroup@{_scopebegin} \lxSVG@begingroup@{stroke-width} \lxSVG@begingroup@{stroke-dasharray,stroke-dashoffset} \lxSVG@begingroup@{stroke-linecap} \lxSVG@begingroup@{stroke-linejoin} \lxSVG@drawpath@unclipped{M -1.8 3.55 C -0.92 1.68 1.42 0.07 2.76 0 C 1.42 -0.07 -0.92 -1.68 -1.8 -3.55}{fill:none} \lxSVG@closescope \lxSVG@closescope }}{{\lx@inpgf@ignorespaces}}}}\lx@inpgf@ignorespaces\lxSVG@closescope \lxSVG@closescope {\lx@inpgf@ignorespaces}{\lx@inpgf@ignorespaces}{\lx@inpgf@ignorespaces}\hss}\lxSVG@discardpath\lxSVG@closescope \hss}}\lxSVG@closescope\endpgfpicture}}} . Then by the correspondence theorem, these loop invariants can be unfolded into the loop invariants in Theorems 0.A.7 and 0.A.4 in the concrete automata, essentially reduced the correctness of the symbolic algorithm to the correctness of the non-symbolic ones. We take the hardest case where we show that the symbolic {\textsc{equiv}}(s,u)=\mathrm{true} then \llbracket s\rrbracket=\llbracket u\rrbracket , where recall that the trace semantics of a symbolic automata coincide with its concretization. We assert the following induction invariant when {\textsc{equiv}}(s,u)=\mathrm{true} : {\textsc{isDead}}(s)\text{ and }{\textsc{isDead}}(u)\quad\text{or}\quad(s,u)\in e(R)\text{ and }(R\setminus R_{0})\mathrel{\hbox to13.72pt{\vbox to5.42pt{\pgfpicture\makeatletter\hbox{\hskip 1.16873pt\lower-2.71245pt\hbox to0.0pt{\lxSVG@begingroup@{_scopebegin} \lxSVG@begingroup@{stroke} \lxSVG@begingroup@{fill} \lxSVG@setlinewidth{\the\pgflinewidth}\lxSVG@begingroup@{stroke-width} \lx@inpgf@ignorespaces\nullfont\lxSVG@begingroup@{_scopebegin} \lxSVG@closescope \hbox to0.0pt{\lxSVG@begingroup@{_scopebegin} {}{{}}{} {}{}\lxSVG@begingroup@{_scopebegin} \lxSVG@setlinewidth{\the\pgflinewidth}\lxSVG@begingroup@{stroke-width} \lx@inpgf@ignorespaces{}{}{}{}{{}}{}{}{}{{}}\lxSVG@stroke\lxSVG@drawpath@unclipped{M 1.55 0 L 12.71 0}{fill:none} \lxSVG@begingroup@{_scopebegin} {\lxSVG@setlinewidth{\pgfinnerlinewidth}\lxSVG@begingroup@{stroke-width} \lxSVG@begingroup@{stroke} \lxSVG@stroke\lxSVG@drawpath@unclipped{M 1.55 0 L 12.71 0}{fill:none} }\lxSVG@closescope {{}{{}}{}{}{{}}{{{\lx@inpgf@ignorespaces}}{{{\lx@inpgf@ignorespaces}}{\lxSVG@begingroup@{_scopebegin} \lxSVG@transformcm{-1.0}{0.0}{0.0}{-1.0}{1.11748pt}{0.0pt}\lxSVG@begingroup@{transform} \lxSVG@begingroup@{_scopebegin} \lxSVG@begingroup@{stroke-width} \lxSVG@begingroup@{stroke-dasharray,stroke-dashoffset} \lxSVG@begingroup@{stroke-linecap} \lxSVG@begingroup@{stroke-linejoin} \lxSVG@drawpath@unclipped{M 1.8 3.55 C 0.92 1.68 -1.42 0.07 -2.76 0 C -1.42 -0.07 0.92 -1.68 1.8 -3.55}{fill:none} \lxSVG@closescope \lxSVG@closescope }}{{\lx@inpgf@ignorespaces}}}}{{}{{}}{}{}{{}}{{{\lx@inpgf@ignorespaces}}{{{\lx@inpgf@ignorespaces}}{\lxSVG@begingroup@{_scopebegin} \lxSVG@transformcm{1.0}{0.0}{0.0}{1.0}{9.18533pt}{0.0pt}\lxSVG@begingroup@{transform} \lxSVG@begingroup@{_scopebegin} \lxSVG@begingroup@{stroke-width} \lxSVG@begingroup@{stroke-dasharray,stroke-dashoffset} \lxSVG@begingroup@{stroke-linecap} \lxSVG@begingroup@{stroke-linejoin} \lxSVG@drawpath@unclipped{M -1.8 3.55 C -0.92 1.68 1.42 0.07 2.76 0 C 1.42 -0.07 -0.92 -1.68 -1.8 -3.55}{fill:none} \lxSVG@closescope \lxSVG@closescope }}{{\lx@inpgf@ignorespaces}}}}\lx@inpgf@ignorespaces\lxSVG@closescope \lxSVG@closescope {\lx@inpgf@ignorespaces}{\lx@inpgf@ignorespaces}{\lx@inpgf@ignorespaces}\hss}\lxSVG@discardpath\lxSVG@closescope \hss}}\lxSVG@closescope\endpgfpicture}}}^{{\textsc{isDead}}}e(R), where R is all the previous inputs of union , R_{0} is the starting value of R for equiv , and e(R) is the smallest equivalence relation that contains R . Verifying the soundness of the induction invariant of the symbolic algorithm is more straightforward as there is no loop, but the argument is eactly the same as Theorem 0.A.7 . Thus, when starting with an empty union-find object, R_{0} will be empty, thus we case analysis on the post condition: • if both s and u are dead, then by Lemma 2 , both \llbracket s\rrbracket and \llbracket u\rrbracket are empty, hence equal; • if (R)\mathrel{\hbox to13.72pt{\vbox to5.42pt{\pgfpicture\makeatletter\hbox{\hskip 1.16873pt\lower-2.71245pt\hbox to0.0pt{\lxSVG@begingroup@{_scopebegin} \lxSVG@begingroup@{stroke} \lxSVG@begingroup@{fill} \lxSVG@setlinewidth{\the\pgflinewidth}\lxSVG@begingroup@{stroke-width} \lx@inpgf@ignorespaces\nullfont\lxSVG@begingroup@{_scopebegin} \lxSVG@closescope \hbox to0.0pt{\lxSVG@begingroup@{_scopebegin} {}{{}}{} {}{}\lxSVG@begingroup@{_scopebegin} \lxSVG@setlinewidth{\the\pgflinewidth}\lxSVG@begingroup@{stroke-width} \lx@inpgf@ignorespaces{}{}{}{}{{}}{}{}{}{{}}\lxSVG@stroke\lxSVG@drawpath@unclipped{M 1.55 0 L 12.71 0}{fill:none} \lxSVG@begingroup@{_scopebegin} {\lxSVG@setlinewidth{\pgfinnerlinewidth}\lxSVG@begingroup@{stroke-width} \lxSVG@begingroup@{stroke} \lxSVG@stroke\lxSVG@drawpath@unclipped{M 1.55 0 L 12.71 0}{fill:none} }\lxSVG@closescope {{}{{}}{}{}{{}}{{{\lx@inpgf@ignorespaces}}{{{\lx@inpgf@ignorespaces}}{\lxSVG@begingroup@{_scopebegin} \lxSVG@transformcm{-1.0}{0.0}{0.0}{-1.0}{1.11748pt}{0.0pt}\lxSVG@begingroup@{transform} \lxSVG@begingroup@{_scopebegin} \lxSVG@begingroup@{stroke-width} \lxSVG@begingroup@{stroke-dasharray,stroke-dashoffset} \lxSVG@begingroup@{stroke-linecap} \lxSVG@begingroup@{stroke-linejoin} \lxSVG@drawpath@unclipped{M 1.8 3.55 C 0.92 1.68 -1.42 0.07 -2.76 0 C -1.42 -0.07 0.92 -1.68 1.8 -3.55}{fill:none} \lxSVG@closescope \lxSVG@closescope }}{{\lx@inpgf@ignorespaces}}}}{{}{{}}{}{}{{}}{{{\lx@inpgf@ignorespaces}}{{{\lx@inpgf@ignorespaces}}{\lxSVG@begingroup@{_scopebegin} \lxSVG@transformcm{1.0}{0.0}{0.0}{1.0}{9.18533pt}{0.0pt}\lxSVG@begingroup@{transform} \lxSVG@begingroup@{_scopebegin} \lxSVG@begingroup@{stroke-width} \lxSVG@begingroup@{stroke-dasharray,stroke-dashoffset} \lxSVG@begingroup@{stroke-linecap} \lxSVG@begingroup@{stroke-linejoin} \lxSVG@drawpath@unclipped{M -1.8 3.55 C -0.92 1.68 1.42 0.07 2.76 0 C 1.42 -0.07 -0.92 -1.68 -1.8 -3.55}{fill:none} \lxSVG@closescope \lxSVG@closescope }}{{\lx@inpgf@ignorespaces}}}}\lx@inpgf@ignorespaces\lxSVG@closescope \lxSVG@closescope {\lx@inpgf@ignorespaces}{\lx@inpgf@ignorespaces}{\lx@inpgf@ignorespaces}\hss}\lxSVG@discardpath\lxSVG@closescope \hss}}\lxSVG@closescope\endpgfpicture}}}^{{\textsc{isDead}}}e(R) , then by correspondence of the symbolic and concrete automata, we have (R)\rightarrowtail^{{\textsc{isDead}}}e(R) , which implies e(R) is an invariant. Because (s,u)\in e(R) , therefore s and u are trace equivalent. Appendix 0.C Application: Decision Procedure for GKAT In Sections 2 and 3 , we presented decision procedures for GKAT automata and symbolic GKAT automata. We now want to apply these algorithms to expressions directly and therefore need algorithms to compile expressions to automata. Although the procedure to generate GKAT automata from GKAT and CF-GKAT expressions has been presented in previous works [ 39 , 38 , 52 ] , we need an algorithm to generate symbolic GKAT automata in order to take advantage of the on-the-fly symbolic algorithm in Figure 7 . In this section, we will focus on the foundational system of GKAT , and explain how to generate symbolic GKAT automata from GKAT expressions. In the next section, we will then define a separate compilation procedure for CF-GKAT , whose operational semantics is also presented as GKAT automata [ 52 ] but with additional structures, like non-local control flows, that make the compilation procedure more complex and requiring extra steps that are non-trival. These two compilation procedures together will bridge the gap to reusing of the symbolic equivalence checking algorithm in Figure 7 for both systems. The syntax of GKAT largely mimics that of the imperative programs, except it abstracts away the meaning of the primitive actions and the tests of the program to enable a rich variety of semantics [ 39 , 38 ] . Formally, GKAT expressions over a finite set of primitive tests T and a finite set of primitive actions \Sigma is defined as follows: \displaystyle\mathsf{BExp}\ni b,c \displaystyle\triangleq 0\mid 1\mid b\land c\mid b\lor c\mid\overline{b} \displaystyle\textsf{GKAT}\ni e,f \displaystyle\triangleq b\mid p\in\Sigma\mid e\fatsemi f\mid e+_{b}f\mid e^{(b)} e+_{b}f and e^{(b)} are the compact notations for \texttt{if}~b~\texttt{then}~e~\texttt{else}~f and \texttt{while}~b~\texttt{do}~e . The operational semantics of a GKAT expression is defined as a GKAT automaton, and the trace equivalence of the generated GKAT automata corresponds to the trace equivalence of the original GKAT expression [ 39 , 38 ] . This result enables us to determine trace equivalence of GKAT expressions by combining the efficient algorithm presented in Figure 5 with existing automata generation processes like Thompson’s construction and derivatives. \frac{\quad}{p\mathrel{\raisebox{-2.0pt}{$\xrightarrow{1\mid p}$}}1}\frac{\quad}{b\mathrel{\resizebox{}{}{{\hbox{\hskip 0.0pt\raise-5.0pt\hbox{{$\xRightarrow{b}$}}}}}}{\mathbf{ret}}}\frac{e\mathrel{\resizebox{}{}{{\hbox{\hskip 0.0pt\raise-2.0pt\hbox{{$\xhookrightarrow{a}$}}}}}}r}{e+_{b}f\mathrel{\resizebox{}{}{{\hbox{\hskip 0.0pt\raise-2.0pt\hbox{{$\xhookrightarrow{b\land a}$}}}}}}r}\frac{f\mathrel{\resizebox{}{}{{\hbox{\hskip 0.0pt\raise-2.0pt\hbox{{$\xhookrightarrow{a}$}}}}}}r}{e+_{b}f\mathrel{\resizebox{}{}{{\hbox{\hskip 0.0pt\raise-2.0pt\hbox{{$\xhookrightarrow{b\land a}$}}}}}}r}\frac{e\mathrel{\raisebox{-2.0pt}{$\xrightarrow{b\mid p}$}}e^{\prime}}{e\fatsemi f\mathrel{\raisebox{-2.0pt}{$\xrightarrow{b\mid p}$}}e^{\prime}\fatsemi f}\frac{e\mathrel{\resizebox{}{}{{\hbox{\hskip 0.0pt\raise-5.0pt\hbox{{$\xRightarrow{b}$}}}}}}{\mathbf{ret}}\quad f\mathrel{\resizebox{}{}{{\hbox{\hskip 0.0pt\raise-2.0pt\hbox{{$\xhookrightarrow{a}$}}}}}}r}{e\fatsemi f\mathrel{\resizebox{}{}{{\hbox{\hskip 0.0pt\raise-2.0pt\hbox{{$\xhookrightarrow{b\land a}$}}}}}}r}\frac{\quad}{e^{(b)}\mathrel{\resizebox{}{}{{\hbox{\hskip 0.0pt\raise-5.0pt\hbox{{$\xRightarrow{\overline{b}}$}}}}}}{\mathbf{ret}}}\frac{e\mathrel{\raisebox{-2.0pt}{$\xrightarrow{a\mid p}$}}e^{\prime}}{e^{(b)}\mathrel{\raisebox{-2.0pt}{$\xrightarrow{b\land a\mid p}$}}e^{\prime}\fatsemi e^{(b)}} Figure 12 : Symbolic Derivatives for GKAT However, to effectively utilize the on-the-fly symbolic decision procedure in Figure 7 , we will need to devise an algorithm to generate symbolic GKAT automata directly from GKAT expressions. This process is given by symbolic derivatives , which generates a transition system on-the-fly, with states being GKAT expressions (denoted as GKAT ): \displaystyle\varepsilon \displaystyle:\textsf{GKAT}\to\mathcal{P}({\mathsf{BExp}}), \displaystyle\delta \displaystyle:\textsf{GKAT}\to\mathcal{P}({\mathsf{BExp}\times\textsf{GKAT}\times\Sigma}). Indeed, this transition system defines the operational semantics for GKAT expressions. Concretely, symbolic derivatives for GKAT are given in Figure 12 , where we use the notation e\mathrel{\resizebox{}{}{{\hbox{\hskip 0.0pt\raise-2.0pt\hbox{{$\xhookrightarrow{b}$}}}}}}r to say that e under condition b will reach result r , where r ranges over \{{\mathbf{ret}}\}+\Sigma\times\textsf{GKAT} . Intuitively, a rule with e\mathrel{\resizebox{}{}{{\hbox{\hskip 0.0pt\raise-2.0pt\hbox{{$\xhookrightarrow{b}$}}}}}}r can be split into a return rule e\mathrel{\resizebox{}{}{{\hbox{\hskip 0.0pt\raise-5.0pt\hbox{{$\xRightarrow{b}$}}}}}}{\mathbf{ret}} and a transition rule e\mathrel{\raisebox{-2.0pt}{$\xrightarrow{b\mid p}$}}e^{\prime} . As an example, the following rule for sequencing can be soundly split as follows: \frac{e\mathrel{\resizebox{}{}{{\hbox{\hskip 0.0pt\raise-5.0pt\hbox{{$\xRightarrow{b}$}}}}}}{\mathbf{ret}}\quad f\mathrel{\resizebox{}{}{{\hbox{\hskip 0.0pt\raise-2.0pt\hbox{{$\xhookrightarrow{a}$}}}}}}r}{e\fatsemi f\mathrel{\resizebox{}{}{{\hbox{\hskip 0.0pt\raise-2.0pt\hbox{{$\xhookrightarrow{b\land a}$}}}}}}r}\quad\lx@xy@svg{\hbox{\raise 2.5pt\hbox{\kern 3.0pt\hbox{\ignorespaces\ignorespaces\ignorespaces\hbox{\vtop{\halign{\entry@#!@&&\entry@@#!@\cr&\crcr}}}\ignorespaces{\hbox{\kern-3.0pt\raise 0.0pt\hbox{\hbox{\kern 0.0pt\raise 0.0pt\hbox{\hbox{\kern 3.0pt\raise-2.5pt\hbox{$\textstyle{{}\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$}}}}}}}\ignorespaces\ignorespaces\ignorespaces{}\ignorespaces\ignorespaces{\hbox{\lx@xy@drawsquiggles@}}\ignorespaces{\hbox{\kern 27.0pt\raise 0.0pt\hbox{\hbox{\kern 0.0pt\raise 0.0pt\hbox{\lx@xy@tip{1}\lx@xy@tip{-1}}}}}}\ignorespaces\ignorespaces{\hbox{\lx@xy@drawsquiggles@}}\ignorespaces{\hbox{\lx@xy@drawsquiggles@}}{\hbox{\kern 27.0pt\raise 0.0pt\hbox{\hbox{\kern 0.0pt\raise 0.0pt\hbox{\hbox{\kern 3.0pt\raise-2.5pt\hbox{$\textstyle{}$}}}}}}}\ignorespaces}}}}\ignorespaces\quad\frac{e\mathrel{\resizebox{}{}{{\hbox{\hskip 0.0pt\raise-5.0pt\hbox{{$\xRightarrow{b}$}}}}}}{\mathbf{ret}}\quad f\mathrel{\resizebox{}{}{{\hbox{\hskip 0.0pt\raise-5.0pt\hbox{{$\xRightarrow{a}$}}}}}}{\mathbf{ret}}}{e\fatsemi f\mathrel{\resizebox{}{}{{\hbox{\hskip 0.0pt\raise-5.0pt\hbox{{$\xRightarrow{b\land a}$}}}}}}{\mathbf{ret}}}\quad\frac{e\mathrel{\resizebox{}{}{{\hbox{\hskip 0.0pt\raise-5.0pt\hbox{{$\xRightarrow{b}$}}}}}}{\mathbf{ret}}\quad f\mathrel{\raisebox{-2.0pt}{$\xrightarrow{a\mid p}$}}f^{\prime}}{e\fatsemi f\mathrel{\raisebox{-2.0pt}{$\xrightarrow{b\land a\mid p}$}}f^{\prime}} With the operational semantics defined by derivatives, we can construct a symbolic GKAT automaton \langle e\rangle for any expression e , where the states are the reachable expressions by taking the derivatives of e , and the start state is the 1+_{b}p 1 {\mathbf{ret}} {\mathbf{ret}} b 1 \overline{b}\mid p (1+_{b}p)^{(c)} {\mathbf{ret}} \overline{c} c\land\overline{b}\mid p \langle 1+_{b}p\rangle: \langle(1+_{b}p)^{(c)}\rangle: expression e . Then by running the algorithm in Figure 7 on symbolic automata \langle e\rangle and \langle f\rangle , we can decide the trace equivalence of the expressions e and f . As an example, We compute the derivative for expression (1+_{b}p)^{(c)} . There is only one rule that leads to the (immediate) termination of while loops: when the loop condition c is unsatisfied: e^{(c)}\mathrel{\resizebox{}{}{{\hbox{\hskip 0.0pt\raise-5.0pt\hbox{{$\xRightarrow{\overline{c}}$}}}}}}{\mathbf{ret}} . For the transition case, the loop e^{(c)} only transition to e^{\prime}\fatsemi e^{(c)} when the body e transition to e^{\prime} . Since only p branch of 1+_{b}p will transition: p\mathrel{\raisebox{-2.0pt}{$\xrightarrow{1\mid p}$}}1 ; we obtain 1+_{b}p\mathrel{\raisebox{-2.0pt}{$\xrightarrow{\overline{b}\mid p}$}}1 and (1+_{b}p)^{(c)}\mathrel{\raisebox{-2.0pt}{$\xrightarrow{c\land\overline{b}\land 1\mid p}$}}1\fatsemi e^{(c)} . Finally, because c\land b\land 1\equiv c\land b and 1\fatsemi e^{(c)}\equiv e^{(c)} , we optimize the derivative of (1+_{b}p)^{(c)} : \displaystyle\varepsilon((1+_{b}p)^{(c)}) \displaystyle=\{\overline{c}\}\ , \displaystyle\delta((1+_{b}p)^{c}) \displaystyle=\{(c\land\overline{b},(1+_{b}p)^{(c)},p)\}\ . Notice the atoms satisfying c\land b will neither terminate nor transition, which means they silently diverge, or formally, are rejected by the state (1+_{b}p)^{(c)} . Appendix 0.D Omitted proofs in Section 4 \frac{\frac{\frac{(x\mapsto 3,e)\mathrel{\raisebox{-2.0pt}{$\xrightarrow{\overline{b}\land a\mid p}$}}(x\mapsto 3,\texttt{skip})}{(x\mapsto 3,e\vartriangleleft e^{(x\neq 2)})\mathrel{\raisebox{-2.0pt}{$\xrightarrow{\overline{b}\land a\mid p}$}}(x\mapsto 3,\texttt{skip}\vartriangleleft e^{(x\neq 2)})}}{(x\mapsto 3,e\vartriangleleft e^{(x\neq 2)})\mathrel{\raisebox{-2.0pt}{$\xrightarrow{\overline{b}\land a\mid p}$}}(x\mapsto 3,e^{(x\neq 2)})}\quad\textsc{Left=$e^{(x\neq 2)}\equiv\texttt{skip}\vartriangleleft e^{(x\neq 2)}$}}{(x\mapsto 3,e^{(x\neq 2)})\mathrel{\raisebox{-2.0pt}{$\xrightarrow{\overline{b}\land a\mid p}$}}(x\mapsto 3,e^{(x\neq 2)})}\frac{\frac{(x\mapsto 3,e)\mathrel{\resizebox{}{}{{\hbox{\hskip 0.0pt\raise-5.0pt\hbox{{$\xRightarrow{b}$}}}}}}{\mathbf{acc}~(x\mapsto 4)}\hskip 8.19447pt\frac{\frac{\frac{(x\mapsto 4,e)\mathrel{\raisebox{-2.0pt}{$\xrightarrow{a\mid p}$}}(x\mapsto 4,\texttt{skip})}{(x\mapsto 4,e\vartriangleleft e^{(x\neq 2)})\mathrel{\raisebox{-2.0pt}{$\xrightarrow{a\mid p}$}}(x\mapsto 4,\texttt{skip}\vartriangleleft e^{(x\neq 2)})}}{(x\mapsto 4,e\vartriangleleft e^{(x\neq 2)})\mathrel{\raisebox{-2.0pt}{$\xrightarrow{a\mid p}$}}(x\mapsto 4,e^{(x\neq 2)})}\hskip 7.3612pt\textsc{Left=$e^{(x\neq 2)}\equiv\texttt{skip}\vartriangleleft e^{(x\neq 2)}$}}{(x\mapsto 4,e^{(x\neq 2)})\mathrel{\raisebox{-2.0pt}{$\xrightarrow{a\mid p}$}}(x\mapsto 4,e^{(x\neq 2)})}}{(x\mapsto 3,e\vartriangleleft e^{(x\neq 2)})\mathrel{\raisebox{-2.0pt}{$\xrightarrow{b\land a\mid p}$}}(x\mapsto 4,e^{(x\neq 2)})}}{(x\mapsto 3,e^{(x\neq 2)})\mathrel{\raisebox{-2.0pt}{$\xrightarrow{b\land a\mid p}$}}(x\mapsto 4,e^{(x\neq 2)})} Figure 13 : The derivation of the outgoing transitions for (x\mapsto 3,e^{x\neq 2}) , where e^{x\neq 2} is from Figure 9(a) . We also include the standard optimization e^{x\neq 2}\equiv\texttt{skip}\vartriangleleft e^{x\neq 2} , which removes skip , in the derivation. Proof (Proof for Theorem 4.1 ) Before we start the formal proof, we would like to note that \mathrm{accu}_{\mathrm{res},\mathrm{con}} can also be characterized as the least fixpoint of the following equation: \mathrm{accu}_{\mathrm{res},\mathrm{con}}(n)\triangleq\mathrm{res}(n)\cup\bigcup\{h(r)\mid(h,n^{\prime})\in\mathrm{con}(n),r\in\mathrm{accu}_{\mathrm{res},\mathrm{con}}(n^{\prime})\}. Hence, the Scott-continuity of the function in the above fixpoint equation will imply \mathrm{accu} can be approximated from below by the Kleene’s fixpoint theorem. However, we opt to present our current proof, since it is closer to our implementation. We design an algorithm to explicitly compute the result of \mathrm{accu}_{\mathrm{res},\mathrm{con}}(n) by keeping track of an axillary variable M , which keeps track of the explored n\in N : \displaystyle\mathrm{accu}^{\prime}_{\mathrm{res},\mathrm{con}}(n,M) \displaystyle\triangleq\begin{cases}\emptyset&\text{if }n\in M\\ \begin{aligned} \mathrm{res}(n)\cup\{h(r)\mid{}&(n^{\prime},h)\in\mathrm{con}(n)\text{ and }\\ {}&r\in\mathrm{accu}^{\prime}_{\mathrm{res},\mathrm{con}}(n^{\prime},M\cup\{n\})\}\end{aligned}&\text{otherwise}\end{cases} \displaystyle\mathrm{accu}_{\mathrm{res},\mathrm{con}}(n) \displaystyle=\mathrm{accu}^{\prime}_{\mathrm{res},\mathrm{con}}(n,\emptyset). The algorithm will terminate because the size of N\setminus M decrease for each recursive call. If r\in\mathrm{res}(n) , then we say that r\in\mathrm{accu}^{\prime}_{\mathrm{res},\mathrm{con}}(n,M) is computable in 1 call of \mathrm{accu}^{\prime} ; and if r\in\mathrm{accu}^{\prime}_{\mathrm{res},\mathrm{con}}(n^{\prime},M\cup\{n\}) is computable in k calls of \mathrm{accu}^{\prime} , we say h(r)\in\mathrm{accu}^{\prime}_{\mathrm{res},\mathrm{con}}(n^{\prime},M) is computable in k+1 calls of \mathrm{accu}^{\prime} . Since every call decreases the size of N\setminus M , then r\in\mathrm{accu}^{\prime}_{\mathrm{res},\mathrm{con}}(n^{\prime},\emptyset) if and only if it can be computed within |N\setminus\emptyset|=|N| calls. Then we can prove that if r\in\mathrm{accu}_{\mathrm{res},\mathrm{con}}(n) is derivable with proof of size k if and only if r can be computed with exactly k call of \mathrm{accu}^{\prime}_{\mathrm{res},\mathrm{con}} . • If k=1 , then \displaystyle r\in\mathrm{accu}_{\mathrm{res},\mathrm{con}}(n)\text{ is derivable in 1 step} \displaystyle\iff r\in\mathrm{res}(n) \displaystyle\iff r\in\mathrm{accu}^{\prime}_{\mathrm{res},\mathrm{con}}(n,\emptyset)\text{ is computable in 1 call}. • If r\in\mathrm{accu}_{\mathrm{res},\mathrm{con}}(n) can be derived using a derivation of size k+1 . Then let (n^{\prime},h)=\mathrm{con}(n) and r^{\prime}\in\mathrm{accu}(n^{\prime}) is derivable in k step, s.t. r=h(r^{\prime}) . \displaystyle r\in\mathrm{accu}_{\mathrm{res},\mathrm{con}}(n)\text{ derivable in $k+1$ step} \displaystyle\iff r=h(r^{\prime})\text{ where }(n^{\prime},h)=\mathrm{con}(n)\text{ and }r^{\prime}\in\mathrm{accu}(n^{\prime})\text{is derivable in $k$ steps} \displaystyle\iff r=h(r^{\prime})\text{ where }(n^{\prime},h)=\mathrm{con}(n)\text{ and }r^{\prime}\in\mathrm{accu}(n^{\prime})\text{is computable in $k$ calls} \displaystyle\iff r\in\mathrm{accu}^{\prime}_{\mathrm{res},\mathrm{con}}(n,\emptyset)\text{ in $k+1$ call}. Proof (Proof for Theorem 4.2 ) The 2 equivalences are proven separately by induction. First to prove \delta(\pi,e^{(b)})=\mathrm{accu}(\mathrm{res}_{\delta},\mathrm{con}_{\delta},\pi) , we begin in the forward direction, i.e., we show that for all b,p , \sigma and f such that there is (\pi,e^{(b)})\mathrel{\raisebox{-2.0pt}{$\xrightarrow{b\mid p}$}}(\sigma,f) , there is (b,(\sigma,f),p)\in\mathrm{accu}(\mathrm{res}_{\delta},\mathrm{con}_{\delta},\pi) . The proof proceeds by induction on the derivation of (\pi,e^{(b)})\mathrel{\raisebox{-2.0pt}{$\xrightarrow{b\mid p}$}}(\sigma,f) . It is clear by the rules of Figure 8 that there are only two cases to consider: \frac{\frac{(\pi,e)\mathrel{\raisebox{-2.0pt}{$\xrightarrow{a\mid p}$}}(\pi^{\prime},e^{\prime})}{(\pi,e\vartriangleleft e^{(b)})\mathrel{\raisebox{-2.0pt}{$\xrightarrow{a\mid p}$}}(\pi^{\prime},e^{\prime}\vartriangleleft e^{(b)})}}{(\pi,e^{(b)})\mathrel{\raisebox{-2.0pt}{$\xrightarrow{b[\pi]\land a\mid p}$}}(\pi^{\prime},e^{\prime}\vartriangleleft e^{(b)})}\quad(1) \frac{\frac{(\pi,e)\mathrel{\resizebox{}{}{{\hbox{\hskip 0.0pt\raise-5.0pt\hbox{{$\xRightarrow{a}$}}}}}}{c}\hskip 7.3612ptc\in\{{\mathbf{acc}~\pi^{\prime}},{\mathbf{cont}~\pi^{\prime}}\}\hskip 7.3612pt(\pi^{\prime},e^{(b)})\mathrel{\raisebox{-2.0pt}{$\xrightarrow{d\mid p}$}}(\sigma,f)}{(\pi,e\vartriangleleft e^{(b)})\mathrel{\raisebox{-2.0pt}{$\xrightarrow{a\land d\mid p}$}}(\sigma,f)}}{(\pi,e^{(b)})\mathrel{\raisebox{-2.0pt}{$\xrightarrow{b[\pi]\land a\land d\mid p}$}}(\sigma,f)}\quad(2) In case (1), from the definition of \mathrm{res}_{\delta} , we immediately have: \frac{(\pi,e)\mathrel{\raisebox{-2.0pt}{$\xrightarrow{a\mid p}$}}(\pi^{\prime},e^{\prime})}{(b[\pi]\land a,(\pi^{\prime},e^{\prime}\vartriangleleft e^{(b)}),p)\in\mathrm{res}_{\delta}(\pi)} which shows that (b[\pi]\land a,(\pi^{\prime},e^{\prime}\vartriangleleft e^{(b)}),p)\in\mathrm{accu}(\mathrm{res}_{\delta},\mathrm{con}_{\delta},\pi) . In case (2), from the premises (\pi,e)\mathrel{\resizebox{}{}{{\hbox{\hskip 0.0pt\raise-5.0pt\hbox{{$\xRightarrow{a}$}}}}}}{c} and c\in\{{\mathbf{acc}~\pi^{\prime}},{\mathbf{cont}~\pi^{\prime}}\} obtained from inversion, we have (\pi^{\prime},\langle b[\pi]\land a|)\in\mathrm{con}_{\delta}(\pi) . Furthermore, from the induction hypothesis, we know that (d,(\sigma,f),p)\in\mathrm{accu}(\mathrm{res}_{\delta},\mathrm{con}_{\delta},\pi^{\prime}) . This means that the following holds: \frac{(\pi^{\prime},\langle b[\pi]\land a|)\in\mathrm{con}_{\delta}(\pi)\hskip 9.24994pt(d,(\sigma,f),p)\in\mathrm{accu}(\mathrm{res}_{\delta},\mathrm{con}_{\delta},\pi^{\prime})}{(b[\pi]\land a\land d,(\sigma,f),p)\in\mathrm{accu}(\mathrm{res}_{\delta},\mathrm{con}_{\delta},\pi)} which concludes the proof of the forward direction. To prove the reverse direction, we need to show that for all (b_{0},(\sigma,f),p)\in\mathrm{accu}(\mathrm{res}_{\delta},\mathrm{con}_{\delta},\pi) , there is (\pi,e^{(b)})\mathrel{\raisebox{-2.0pt}{$\xrightarrow{b_{0}\mid p}$}}(\sigma,f) . By induction on the derivation of (b_{0},(\sigma,f),p)\in\mathrm{accu}(\mathrm{res}_{\delta},\mathrm{con}_{\delta},\pi) , we have the following cases to consider: \frac{(b,(\sigma,f),p)\in\mathrm{res}_{\delta}(\pi)}{(b,(\sigma,f),p)\in\mathrm{accu}(\mathrm{res}_{\delta},\mathrm{con}_{\delta},\pi)}(1)\frac{(\pi^{\prime},h)\in\mathrm{con}_{\delta}(\pi)\quad r\in\mathrm{accu}(\mathrm{res}_{\delta},\mathrm{con}_{\delta},\pi^{\prime})}{h(r)\in\mathrm{accu}(\mathrm{res}_{\delta},\mathrm{con}_{\delta},\pi)}(2) In case (1), by inversion on (b_{0},(\sigma,f),p)\in\mathrm{res}_{\delta}(\pi) we have: \frac{(\pi,e)\mathrel{\raisebox{-2.0pt}{$\xrightarrow{a\mid p}$}}(\pi^{\prime},e^{\prime})}{(b[\pi]\land a,(\pi^{\prime},e^{\prime}\vartriangleleft e^{(b)}),p)\in\mathrm{res}_{\delta}(\pi)} and b_{0}=b[\pi]\land a , \sigma=\pi^{\prime} , f=e^{\prime}\vartriangleleft e^{(b)} . Now from the rules of Figure 8 , we can derive the transition (\pi,e^{(b)})\mathrel{\raisebox{-2.0pt}{$\xrightarrow{b[\pi]\land a\mid p}$}}(\pi^{\prime},e^{\prime}\vartriangleleft e^{(b)}) which is just (\pi,e^{(b)})\mathrel{\raisebox{-2.0pt}{$\xrightarrow{b_{0}\mid p}$}}(\sigma,f) . In case (2), we have h(r)=(b_{0},(\sigma,f),p) by assumption. Inverting (\pi^{\prime},h)\in\mathrm{con}_{\delta}(\pi) we have: \frac{(\pi,e)\mathrel{\resizebox{}{}{{\hbox{\hskip 0.0pt\raise-5.0pt\hbox{{$\xRightarrow{a}$}}}}}}{c}\quad c\in\{{\mathbf{acc}~\pi^{\prime}},{\mathbf{cont}~\pi^{\prime}}\}}{(\pi^{\prime},\langle b[\pi]\land a|\in\mathrm{con}_{\delta}(\pi))} and h=\langle b[\pi]\land a| . Let r=(d,(\sigma^{\prime},f^{\prime}),p^{\prime})\in\mathrm{accu}(\mathrm{res}_{\delta},\mathrm{con}_{\delta},\pi^{\prime}) . By h(r)=(b_{0},(\sigma,f),p) we have b_{0}=b[\pi]\land a\land d , \sigma=\sigma^{\prime} , f=f^{\prime} , and p=p^{\prime} . From the induction hypothesis, we know that there is transition (\pi^{\prime},e^{(b)})\mathrel{\raisebox{-2.0pt}{$\xrightarrow{d\mid p}$}}(\sigma,f) . The rules of Figure 8 then allow us to derive the transition (\pi,e^{(b)})\mathrel{\raisebox{-2.0pt}{$\xrightarrow{b[\pi]\land a\land b\mid p}$}}(\sigma,f) which concludes the proof of the reverse direction. We now begin proving the second equivalence \varepsilon(\pi,e^{(b)})=\mathrm{accu}(\mathrm{res}_{\varepsilon},\mathrm{con}_{\varepsilon},\pi) . In the forward direction, we show that for all (\pi,e^{(b)})\mathrel{\resizebox{}{}{{\hbox{\hskip 0.0pt\raise-4.0pt\hbox{{$\xRightarrow{b_{0}}$}}}}}}c_{0} , we have (b_{0},c_{0})\in\mathrm{accu}(\mathrm{res}_{\varepsilon},\mathrm{con}_{\varepsilon},\pi) . By induction on the derivation of (\pi,e^{(b)})\mathrel{\resizebox{}{}{{\hbox{\hskip 0.0pt\raise-4.0pt\hbox{{$\xRightarrow{b_{0}}$}}}}}}c_{0} , the only cases to consider are: \frac{\hskip 9.24994pt}{(\pi,e^{(b)})\mathrel{\resizebox{}{}{{\hbox{\hskip 0.0pt\raise-3.425pt\hbox{{$\xRightarrow{\neg b[\pi]}$}}}}}}{{\mathbf{acc}~\pi}}}\frac{(\pi,e)\mathrel{\resizebox{}{}{{\hbox{\hskip 0.0pt\raise-5.0pt\hbox{{$\xRightarrow{a}$}}}}}}{\mathbf{brk}~\pi^{\prime}}}{(\pi,e^{(b)})\mathrel{\resizebox{}{}{{\hbox{\hskip 0.0pt\raise-3.425pt\hbox{{$\xRightarrow{b[\pi]\land a}$}}}}}}{{\mathbf{acc}~\pi^{\prime}}}}\frac{(\pi,e)\mathrel{\resizebox{}{}{{\hbox{\hskip 0.0pt\raise-5.0pt\hbox{{$\xRightarrow{a}$}}}}}}{c}\hskip 9.24994ptc={\mathbf{ret}}\text{ or }c={\mathbf{jmp}~(l,\pi^{\prime})}}{(\pi,e^{(b)})\mathrel{\resizebox{}{}{{\hbox{\hskip 0.0pt\raise-3.425pt\hbox{{$\xRightarrow{b[\pi]\land a}$}}}}}}{c}}\frac{(\pi,e)\mathrel{\resizebox{}{}{{\hbox{\hskip 0.0pt\raise-5.0pt\hbox{{$\xRightarrow{a}$}}}}}}{c}\hskip 9.24994ptc={\mathbf{acc}~\pi^{\prime}}\text{ or }{\mathbf{cont}~\pi^{\prime}}\hskip 9.24994pt(\pi^{\prime},e^{(b)})\mathrel{\resizebox{}{}{{\hbox{\hskip 0.0pt\raise-5.0pt\hbox{{$\xRightarrow{d}$}}}}}}{c_{0}}}{(\pi,e^{(b)})\mathrel{\resizebox{}{}{{\hbox{\hskip 0.0pt\raise-3.425pt\hbox{{$\xRightarrow{b[\pi]\land a\land d}$}}}}}}{c_{0}}} The first 3 cases are trivial as they all belong in \mathrm{res}_{\varepsilon}(\pi) , and by extension \mathrm{accu}(\mathrm{res}_{\varepsilon},\mathrm{con}_{\varepsilon},\pi) , via the following rules: \frac{\hskip 9.24994pt}{(\neg b[\pi],{\mathbf{acc}~\pi})\in\mathrm{res}_{\varepsilon}(\pi)}\frac{(\pi,e)\mathrel{\resizebox{}{}{{\hbox{\hskip 0.0pt\raise-5.0pt\hbox{{$\xRightarrow{a}$}}}}}}{\mathbf{brk}~\pi^{\prime}}}{(b[\pi]\land a,{\mathbf{acc}~\pi^{\prime}})\in\mathrm{res}_{\varepsilon}(\pi)}\frac{(\pi,e)\mathrel{\resizebox{}{}{{\hbox{\hskip 0.0pt\raise-5.0pt\hbox{{$\xRightarrow{a}$}}}}}}{c}\hskip 9.24994ptc={\mathbf{ret}}\text{ or }c={\mathbf{jmp}~(l,\pi^{\prime})}}{(b[\pi]\land a,c)\in\mathrm{res}_{\varepsilon}(\pi)} From the first 2 premises of the 4th case, we can derive (\pi^{\prime},\langle b[\pi]\land a|)\in\mathrm{con}_{\varepsilon}(\pi) by definition of \mathrm{con}_{\varepsilon} . Applying the induction hypothesis on (\pi^{\prime},e^{(b)})\mathrel{\resizebox{}{}{{\hbox{\hskip 0.0pt\raise-5.0pt\hbox{{$\xRightarrow{d}$}}}}}}c_{0} gives us (d,c_{0})\in\mathrm{accu}(\mathrm{res}_{\varepsilon},\mathrm{con}_{\varepsilon},\pi^{\prime}) . The \mathrm{accu} rule then allows us to derive: \frac{(\pi^{\prime},\langle b[\pi]\land a|)\in\mathrm{con}_{\varepsilon}(\pi)\hskip 9.24994pt(d,c_{0})\in\mathrm{accu}(\mathrm{res}_{\varepsilon},\mathrm{con}_{\varepsilon},\pi^{\prime})}{(b[\pi]\land a\land d,c_{0})\in\mathrm{accu}(\mathrm{res}_{\varepsilon},\mathrm{con}_{\varepsilon},\pi)} which concludes the proof of the forward direction. To prove the reverse direction, we need to show that for all (b_{0},c_{0})\in\mathrm{accu}(\mathrm{res}_{\varepsilon},\mathrm{con}_{\varepsilon},\pi) , there is (\pi,e^{(b)})\mathrel{\resizebox{}{}{{\hbox{\hskip 0.0pt\raise-4.0pt\hbox{{$\xRightarrow{b_{0}}$}}}}}}c_{0} . By induction on the derivation of (b_{0},c_{0})\in\mathrm{accu}(\mathrm{res}_{\varepsilon},\mathrm{con}_{\varepsilon},\pi) , we have the following cases to consider: \frac{(b_{0},c_{0})\in\mathrm{res}_{\varepsilon}(\pi)}{(b_{0},c_{0})\in\mathrm{accu}(\mathrm{res}_{\varepsilon},\mathrm{con}_{\varepsilon},\pi)}(1)\frac{(\pi^{\prime},h)\in\mathrm{con}_{\varepsilon}(\pi)\hskip 9.24994ptr\in\mathrm{accu}(\mathrm{res}_{\varepsilon},\mathrm{con}_{\varepsilon},\pi^{\prime})}{h(r)\in\mathrm{accu}(\mathrm{res}_{\varepsilon},\ con_{\varepsilon},\pi)}(2) Similarly to the forward direction, case (1) is trivial as inversion on the proof of (b_{0},c_{0})\in\mathrm{res}_{\varepsilon}(\pi) yields the following cases: \frac{\hskip 9.24994pt}{(\neg b[\pi],{\mathbf{acc}~\pi})\in\mathrm{res}_{\varepsilon}(\pi)}\frac{(\pi,e)\mathrel{\resizebox{}{}{{\hbox{\hskip 0.0pt\raise-5.0pt\hbox{{$\xRightarrow{a}$}}}}}}{\mathbf{brk}~\pi^{\prime}}}{(b[\pi]\land a,{\mathbf{acc}~\pi^{\prime}})\in\mathrm{res}_{\varepsilon}(\pi)}\frac{(\pi,e)\mathrel{\resizebox{}{}{{\hbox{\hskip 0.0pt\raise-5.0pt\hbox{{$\xRightarrow{a}$}}}}}}{c_{0}}\hskip 9.24994ptc_{0}={\mathbf{ret}}\text{ or }c_{0}={\mathbf{jmp}~(l,\pi^{\prime})}}{(b[\pi]\land a,c_{0})\in\mathrm{res}_{\varepsilon}(\pi)} which allow us to derive (\pi,e^{(b)})\mathrel{\resizebox{}{}{{\hbox{\hskip 0.0pt\raise-3.25pt\hbox{{$\xRightarrow{\neg b[\pi]}$}}}}}}{\mathbf{acc}~\pi} , (\pi,e^{(b)})\mathrel{\resizebox{}{}{{\hbox{\hskip 0.0pt\raise-3.25pt\hbox{{$\xRightarrow{b[\pi]\land a}$}}}}}}{\mathbf{acc}~\pi^{\prime}} and (\pi,e^{(b)})\mathrel{\resizebox{}{}{{\hbox{\hskip 0.0pt\raise-3.25pt\hbox{{$\xRightarrow{b[\pi]\land a}$}}}}}}c_{0} respectively. In case (2), we have h(r)=(b_{0},c_{0}) by assumption. Inverting (\pi^{\prime},h)\in\mathrm{con}_{\varepsilon}(\pi) we have: \frac{(\pi,e)\mathrel{\resizebox{}{}{{\hbox{\hskip 0.0pt\raise-5.0pt\hbox{{$\xRightarrow{a}$}}}}}}{c}\hskip 9.24994ptc={\mathbf{acc}~\pi^{\prime}}\text{ or }{\mathbf{cont}~\pi^{\prime}}}{(\pi^{\prime},\langle b[\pi]\land a|)\in\mathrm{con}_{\varepsilon}(\pi)} and h=\langle b[\pi]\land a| . Let r=(d,c^{\prime})\in\mathrm{accu}(\mathrm{res}_{\varepsilon},\mathrm{con}_{\varepsilon},\pi^{\prime}) . From the induction hypothesis, we have (\pi^{\prime},e^{(b)})\mathrel{\resizebox{}{}{{\hbox{\hskip 0.0pt\raise-5.0pt\hbox{{$\xRightarrow{d}$}}}}}}c^{\prime} and: \frac{(\pi,e)\mathrel{\resizebox{}{}{{\hbox{\hskip 0.0pt\raise-5.0pt\hbox{{$\xRightarrow{a}$}}}}}}{c}\hskip 9.24994ptc={\mathbf{acc}~\pi^{\prime}}\text{ or }{\mathbf{cont}~\pi^{\prime}}\hskip 9.24994pt(\pi^{\prime},e^{(b)})\mathrel{\resizebox{}{}{{\hbox{\hskip 0.0pt\raise-5.0pt\hbox{{$\xRightarrow{d}$}}}}}}{c^{\prime}}}{(\pi,e^{(b)})\mathrel{\resizebox{}{}{{\hbox{\hskip 0.0pt\raise-3.425pt\hbox{{$\xRightarrow{b[\pi]\land a\land d}$}}}}}}{c^{\prime}}} Because (b_{0},c_{0})=h(r)=(b[\pi]\land a\land d,c^{\prime}) , there is (\pi,e^{(b)})\mathrel{\resizebox{}{}{{\hbox{\hskip 0.0pt\raise-4.0pt\hbox{{$\xRightarrow{b_{0}}$}}}}}}c_{0} which concludes the proof. Expressing the \varepsilon of while-loops . Similar to the \delta case, we unfold the proof rules for e\vartriangleleft e^{(b)} and extract all the premise that can lead to e^{(b)}\mathrel{\resizebox{}{}{{\hbox{\hskip 0.0pt\raise-5.0pt\hbox{{$\xRightarrow{a}$}}}}}}c for some condition a\in\mathsf{BExp} and continuation c\in C ; we omit the middle step (\pi,e\vartriangleleft e^{(b)})\mathrel{\resizebox{}{}{{\hbox{\hskip 0.0pt\raise-5.0pt\hbox{{$\xRightarrow{a}$}}}}}}c : \frac{\quad}{(\pi,e^{(b)})\mathrel{\resizebox{}{}{{\hbox{\hskip 0.0pt\raise-3.25pt\hbox{{$\xRightarrow{\neg b[\pi]}$}}}}}}{{\mathbf{acc}~\pi}}}\frac{(\pi,e)\mathrel{\resizebox{}{}{{\hbox{\hskip 0.0pt\raise-5.0pt\hbox{{$\xRightarrow{a}$}}}}}}{\mathbf{brk}~\pi^{\prime}}}{(\pi,e^{(b)})\mathrel{\resizebox{}{}{{\hbox{\hskip 0.0pt\raise-3.25pt\hbox{{$\xRightarrow{b[\pi]\land a}$}}}}}}{{\mathbf{acc}~\pi^{\prime}}}}\frac{(\pi,e)\mathrel{\resizebox{}{}{{\hbox{\hskip 0.0pt\raise-5.0pt\hbox{{$\xRightarrow{a}$}}}}}}{c}\quad c={\mathbf{ret}}\text{ or }c={\mathbf{jmp}~(l,\pi^{\prime})}}{(\pi,e^{(b)})\mathrel{\resizebox{}{}{{\hbox{\hskip 0.0pt\raise-3.25pt\hbox{{$\xRightarrow{b[\pi]\land a}$}}}}}}{c}}\frac{(\pi,e)\mathrel{\resizebox{}{}{{\hbox{\hskip 0.0pt\raise-5.0pt\hbox{{$\xRightarrow{a}$}}}}}}{c}\quad c={\mathbf{acc}~\pi^{\prime}}\text{ or }{\mathbf{cont}~\pi^{\prime}}\quad(\pi^{\prime},e^{(b)})\mathrel{\resizebox{}{}{{\hbox{\hskip 0.0pt\raise-5.0pt\hbox{{$\xRightarrow{d}$}}}}}}{c^{\prime}}}{(\pi,e^{(b)})\mathrel{\resizebox{}{}{{\hbox{\hskip 0.0pt\raise-3.25pt\hbox{{$\xRightarrow{b[\pi]\land a\land d}$}}}}}}{c^{\prime}}} We notice that the first three rules compute elements in \varepsilon(\pi,e^{(b)}) directly from \varepsilon(\pi,e) ; the final rule will compute the elements in \varepsilon(\pi,e^{(b)}) inductively from \varepsilon(\pi^{\prime},e^{(b)}) , and the resulting condition d is guarded by b[\pi]\land a . Thus, the first three rules are converted into rules for \mathrm{res}_{\varepsilon} and the final rule is converted into a rule for \mathrm{con}_{\varepsilon} : \frac{\quad}{(\neg b[\pi],{\mathbf{acc}~\pi})\in\mathrm{res}_{\varepsilon}(\pi)}\frac{(\pi,e)\mathrel{\resizebox{}{}{{\hbox{\hskip 0.0pt\raise-5.0pt\hbox{{$\xRightarrow{a}$}}}}}}{\mathbf{brk}~\pi^{\prime}}}{(b[\pi]\land a,{\mathbf{acc}~\pi^{\prime}})\in\mathrm{res}_{\varepsilon}(\pi)}\frac{(\pi,e)\mathrel{\resizebox{}{}{{\hbox{\hskip 0.0pt\raise-5.0pt\hbox{{$\xRightarrow{a}$}}}}}}{c}\quad c={\mathbf{ret}}\text{ or }c={\mathbf{jmp}~(l,\pi^{\prime})}}{(b[\pi]\land a,c)\in\mathrm{res}_{\varepsilon}(\pi)}\frac{(\pi,e)\mathrel{\resizebox{}{}{{\hbox{\hskip 0.0pt\raise-5.0pt\hbox{{$\xRightarrow{a}$}}}}}}c\quad c={\mathbf{acc}~\pi^{\prime}}\text{ or }c={\mathbf{cont}~\pi^{\prime}}}{(\pi^{\prime},\langle b[\pi]\land a|)\in\mathrm{con}_{\varepsilon}(\pi)} Proof (Proof for Theorem 4.3 ) We define \mathrm{res}_{\varepsilon} , \mathrm{con}_{\varepsilon} , \mathrm{res}_{\delta} , \mathrm{con}_{\delta} , via the following inference rules: let l ranges over all the labels in e , and \sigma,\sigma^{\prime} ranges over all indicator states, \frac{(\sigma,f)\mathrel{\resizebox{}{}{{\hbox{\hskip 0.0pt\raise-5.0pt\hbox{{$\xRightarrow{a}$}}}}}}{c}\quad c\neq{\mathbf{jmp}~l,\sigma^{\prime}}}{(a,c)\in\mathrm{res}_{\varepsilon}(\sigma,f)}\frac{(\sigma,f)\mathrel{\resizebox{}{}{{\hbox{\hskip 0.0pt\raise-5.0pt\hbox{{$\xRightarrow{a}$}}}}}}{{\mathbf{jmp}~l,\sigma^{\prime}}}}{((\sigma^{\prime},e_{l}),\langle a|)\in\mathrm{con}_{\varepsilon}(\sigma,f)}\frac{(\sigma,f)\mathrel{\raisebox{-2.0pt}{$\xrightarrow{a\mid p}$}}(\sigma^{\prime},f^{\prime})}{(a,(\sigma^{\prime},f^{\prime}),p)\in\mathrm{res}_{\delta}(\sigma,f)}\frac{(\sigma,f)\mathrel{\resizebox{}{}{{\hbox{\hskip 0.0pt\raise-5.0pt\hbox{{$\xRightarrow{a}$}}}}}}{{\mathbf{jmp}~l,\sigma^{\prime}}}}{((\sigma^{\prime},e_{l}),\langle a|)\in\mathrm{con}_{\delta}(\sigma,f)} We then show respective \mathrm{accu} computes the accepting \varepsilon and transition function \delta in jump resolution: \displaystyle\varepsilon(\pi,f) \displaystyle=\mathrm{accu}(\mathrm{res}_{\varepsilon},\mathrm{con}_{\varepsilon},(\pi,f)) \displaystyle\delta(\pi,f) \displaystyle=\mathrm{accu}(\mathrm{res}_{\delta},\mathrm{con}_{\delta},(\pi,f)) via induction on the size of the derivation. First to prove \varepsilon(\sigma,f)=\mathrm{accu}(\mathrm{res}_{\varepsilon},\mathrm{con}_{\varepsilon},(\sigma,f)) , in the forward direction, we must show that for all (\sigma,f)\mathrel{\resizebox{}{}{{\hbox{\hskip 0.0pt\raise-4.0pt\hbox{{$\xRightarrow{b_{0}}$}}}}}}{c} in \langle\pi,e\rangle\!\downarrow , there is (b_{0},c)\in\mathrm{accu}(\mathrm{res}_{\varepsilon},\mathrm{con}_{\varepsilon},(\sigma,f)) . By induction on the derivation of (\sigma,f)\mathrel{\resizebox{}{}{{\hbox{\hskip 0.0pt\raise-4.0pt\hbox{{$\xRightarrow{b_{0}}$}}}}}}{c} in \langle\pi,e\rangle\!\downarrow , there are 2 cases to consider: \frac{(\sigma,f)\mathrel{\resizebox{}{}{{\hbox{\hskip 0.0pt\raise-5.0pt\hbox{{$\xRightarrow{a}$}}}}}}c\text{ in }\langle\pi,e\rangle\hskip 9.24994ptc\neq{\mathbf{jmp}~l,\sigma^{\prime}}}{(\sigma,f)\mathrel{\resizebox{}{}{{\hbox{\hskip 0.0pt\raise-5.0pt\hbox{{$\xRightarrow{a}$}}}}}}c\text{ in }\langle\pi,e\rangle\!\downarrow}(1)\par\frac{(\sigma,f)\mathrel{\resizebox{}{}{{\hbox{\hskip 0.0pt\raise-5.0pt\hbox{{$\xRightarrow{a}$}}}}}}{{\mathbf{jmp}~l,\sigma^{\prime}}}\text{ in }\langle\pi,e\rangle\hskip 9.24994pt(\sigma^{\prime},e_{l})\mathrel{\resizebox{}{}{{\hbox{\hskip 0.0pt\raise-5.0pt\hbox{{$\xRightarrow{b}$}}}}}}r\text{ in }\langle\pi,e\rangle\!\downarrow}{(\sigma,f)\mathrel{\resizebox{}{}{{\hbox{\hskip 0.0pt\raise-5.0pt\hbox{{$\xRightarrow{a\land b}$}}}}}}r\text{ in }\langle\pi,e\rangle\!\downarrow}(2) In case (1), by definition of \mathrm{res}_{\varepsilon} , we have (a,c)\in\mathrm{res}_{\varepsilon}(\sigma,f) which immediately gives us (a,c)\in\mathrm{accu}(\mathrm{res}_{\varepsilon},\mathrm{con}_{\varepsilon},(\sigma,f)) . In case (2), the first premise gives us ((\sigma^{\prime},e_{l}),\langle a|)\in\mathrm{con}_{\varepsilon}(\sigma,f) by definition of \mathrm{con}_{\varepsilon} . The induction hypothesis applied to the second premise gives us (b,r)\in\mathrm{accu}(\mathrm{res}_{\varepsilon},\mathrm{con}_{\varepsilon},(\sigma^{\prime},e_{l})) . The \mathrm{accu} rule then allows us to derive: \frac{((\sigma^{\prime},e_{l}),\langle a|)\in\mathrm{con}_{\varepsilon}(\sigma,f)\hskip 9.24994pt(b,r)\in\mathrm{accu}(\mathrm{res}_{\varepsilon},\mathrm{con}_{\varepsilon},(\sigma^{\prime},e_{l}))}{(a\land b,r)\in\mathrm{accu}(\mathrm{res}_{\varepsilon},\mathrm{con}_{\varepsilon},(\sigma,f))} which concludes the proof of the forward direction. To prove the reverse direction, we need to show that for all (b_{0},c)\in\mathrm{accu}(\mathrm{res}_{\varepsilon},\mathrm{con}_{\varepsilon},(\sigma,f)) , there is (\sigma,f)\mathrel{\resizebox{}{}{{\hbox{\hskip 0.0pt\raise-4.0pt\hbox{{$\xRightarrow{b_{0}}$}}}}}}{c} in \langle\pi,e\rangle\!\downarrow . By induction on the derivation of (b_{0},c)\in\mathrm{accu}(\mathrm{res}_{\varepsilon},\mathrm{con}_{\varepsilon},(\sigma,f)) , the cases to consider are: \frac{(b_{0},c)\in\mathrm{res}_{\varepsilon}(\sigma,f)}{(b_{0},c)\in\mathrm{accu}(\mathrm{res}_{\varepsilon},\mathrm{con}_{\varepsilon},(\sigma,f))}(1)\frac{(n,h)\in\mathrm{con}_{\varepsilon}(\sigma,f)\hskip 9.24994ptr\in\mathrm{accu}(\mathrm{res}_{\varepsilon},\mathrm{con}_{\varepsilon},n)}{h(r)\in\mathrm{accu}(\mathrm{res}_{\varepsilon},\mathrm{con}_{\varepsilon},(\sigma,f))}(2) In case (1), inversion on (b_{0},c)\in\mathrm{res}_{\varepsilon}(\sigma,f) gives us: \frac{(\sigma,f)\mathrel{\resizebox{}{}{{\hbox{\hskip 0.0pt\raise-5.0pt\hbox{{$\xRightarrow{a}$}}}}}}{c}\text{ in }\langle\pi,e\rangle\hskip 9.24994ptc\neq{\mathbf{jmp}~l,\sigma^{\prime}}}{(a,c)\in\mathrm{res}_{\varepsilon}(\sigma,f)} which allows us to derive (\sigma,f)\mathrel{\resizebox{}{}{{\hbox{\hskip 0.0pt\raise-5.0pt\hbox{{$\xRightarrow{a}$}}}}}}{c} in \langle\pi,e\rangle\!\downarrow . In case (2), inversion of the first premise gives us: \frac{(\sigma,f)\mathrel{\resizebox{}{}{{\hbox{\hskip 0.0pt\raise-5.0pt\hbox{{$\xRightarrow{a}$}}}}}}{{\mathbf{jmp}~l,\sigma^{\prime}}}\text{ in }\langle\pi,e\rangle}{((\sigma^{\prime},e_{l}),\langle a|)\in\mathrm{con}_{\varepsilon}(\sigma,f)} where n=(\sigma^{\prime},e_{l}) and h=\langle a| . Let r=(b,c^{\prime})\in\mathrm{accu}(\mathrm{res}_{\varepsilon},\mathrm{con}_{\varepsilon},(\sigma^{\prime},e_{l})) . The induction hypothesis applied to the second premise gives us (\sigma^{\prime},e_{l})\mathrel{\resizebox{}{}{{\hbox{\hskip 0.0pt\raise-5.0pt\hbox{{$\xRightarrow{b}$}}}}}}{c^{\prime}} in \langle\pi,e\rangle\!\downarrow . We can now derive: \frac{(\sigma,f)\mathrel{\resizebox{}{}{{\hbox{\hskip 0.0pt\raise-5.0pt\hbox{{$\xRightarrow{a}$}}}}}}{{\mathbf{jmp}~l,\sigma^{\prime}}}\text{ in }\langle\pi,e\rangle\hskip 9.24994pt(\sigma^{\prime},e_{l})\mathrel{\resizebox{}{}{{\hbox{\hskip 0.0pt\raise-5.0pt\hbox{{$\xRightarrow{b}$}}}}}}{c^{\prime}}\text{ in }\langle\pi,e\rangle\!\downarrow}{(\sigma,f)\mathrel{\resizebox{}{}{{\hbox{\hskip 0.0pt\raise-5.0pt\hbox{{$\xRightarrow{a\land b}$}}}}}}{c^{\prime}}\text{ in }\langle\pi,e\rangle\!\downarrow} which concludes the proof of the reverse direction. We now begin proving the second equivalence \delta(\sigma,f)=\mathrm{accu}(\mathrm{res}_{\delta},\mathrm{con}_{\delta},(\sigma,f)) . In the forward direction, we must show that for all (\sigma,f)\mathrel{\raisebox{-2.0pt}{$\xrightarrow{b_{0}\mid p}$}}(\sigma^{\prime},f^{\prime}) in \langle\pi,e\rangle\!\downarrow , there is (b_{0},(\sigma^{\prime},f^{\prime}),p)\in\mathrm{accu}(\mathrm{res}_{\delta},\mathrm{con}_{\delta},(\sigma,f)) . We proceed by induction on the derivation of (\sigma,f)\mathrel{\raisebox{-2.0pt}{$\xrightarrow{b_{0}\mid p}$}}(\sigma^{\prime},f^{\prime}) in \langle\pi,e\rangle\!\downarrow . There are 2 cases to consider: \frac{(\sigma,f)\mathrel{\raisebox{-2.0pt}{$\xrightarrow{b\mid p}$}}(\sigma^{\prime},f^{\prime})\text{ in }\langle\pi,e\rangle}{(\sigma,f)\mathrel{\raisebox{-2.0pt}{$\xrightarrow{b\mid p}$}}(\sigma^{\prime},f^{\prime})\text{ in }\langle\pi,e\rangle\!\downarrow}(1)\frac{(\sigma,f)\mathrel{\resizebox{}{}{{\hbox{\hskip 0.0pt\raise-5.0pt\hbox{{$\xRightarrow{a}$}}}}}}{{\mathbf{jmp}~l,\sigma^{\prime}}}\text{ in }\langle\pi,e\rangle\hskip 9.24994pt(\sigma^{\prime},e_{l})\mathrel{\raisebox{-2.0pt}{$\xrightarrow{b\mid p}$}}(\sigma^{\prime\prime},f^{\prime})\text{ in }\langle\pi,e\rangle\!\downarrow}{(\sigma,f)\mathrel{\raisebox{-2.0pt}{$\xrightarrow{a\land b\mid p}$}}(\sigma^{\prime\prime},f^{\prime})\text{ in }\langle\pi,e\rangle\!\downarrow}(2) In case (1), by definition of \mathrm{res}_{\delta} , we have (b,(\sigma^{\prime},f^{\prime}),p)\in\mathrm{res}_{\delta}(\sigma,f) which immediately gives us (b,(\sigma^{\prime},f^{\prime}),p)\in\mathrm{accu}(\mathrm{res}_{\delta},\mathrm{con}_{\delta},(\sigma,f)) . In case (2), the first premise gives us ((\sigma^{\prime},e_{l}),\langle a|)\in\mathrm{con}_{\delta}(\sigma,f) by definition of \mathrm{con}_{\delta} . The induction hypothesis applied to the second premise gives us (b,(\sigma^{\prime\prime},f^{\prime}),p)\in\mathrm{accu}(\mathrm{res}_{\delta},\mathrm{con}_{\delta},(\sigma^{\prime},e_{l})) . The \mathrm{accu} rule then allows us to derive: \frac{((\sigma^{\prime},e_{l}),\langle a|)\in\mathrm{con}_{\delta}(\sigma,f)\hskip 9.24994pt(b,(\sigma^{\prime\prime},f^{\prime}),p)\in\mathrm{accu}(\mathrm{res}_{\delta},\mathrm{con}_{\delta},(\sigma^{\prime},e_{l}))}{(a\land b,(\sigma^{\prime\prime},f^{\prime}),p)\in\mathrm{accu}(\mathrm{res}_{\delta},\mathrm{con}_{\delta},(\sigma,f))} which concludes the proof of the forward direction. To prove the reverse, we need to show that for all (b_{0},(\sigma^{\prime},f^{\prime}),p)\in\mathrm{accu}(\mathrm{res}_{\delta},\mathrm{con}_{\delta},(\sigma,f)) , there is (\sigma,f)\mathrel{\raisebox{-2.0pt}{$\xrightarrow{b_{0}\mid p}$}}(\sigma^{\prime},f^{\prime}) in \langle\pi,e\rangle\!\downarrow . By induction on the derivation of (b_{0},(\sigma^{\prime},f^{\prime}),p)\in\mathrm{accu}(\mathrm{res}_{\delta},\mathrm{con}_{\delta},(\sigma,f)) , the cases to consider are: \frac{(b_{0},(\sigma^{\prime},f^{\prime}),p)\in\mathrm{res}_{\delta}(\sigma,f)}{(b_{0},(\sigma^{\prime},f^{\prime}),p)\in\mathrm{accu}(\mathrm{res}_{\delta},\mathrm{con}_{\delta},(\sigma,f))}(1)\frac{(n,h)\in\mathrm{con}_{\delta}(\sigma,f)\hskip 9.24994ptr\in\mathrm{accu}(\mathrm{res}_{\delta},\mathrm{con}_{\delta},n)}{h(r)\in\mathrm{accu}(\mathrm{res}_{\delta},\mathrm{con}_{\delta},(\sigma,f))}(2) In case (1), inversion on (b_{0},(\sigma^{\prime},f^{\prime}),p)\in\mathrm{res}_{\delta}(\sigma,f) gives us: \frac{(\sigma,f)\mathrel{\raisebox{-2.0pt}{$\xrightarrow{b_{0}\mid p}$}}(\sigma^{\prime},f^{\prime})\text{ in }\langle\pi,e\rangle}{(b_{0},(\sigma^{\prime},f^{\prime}),p)\in\mathrm{res}_{\delta}(\sigma,f)} which immediately gives us (\sigma,f)\mathrel{\raisebox{-2.0pt}{$\xrightarrow{b_{0}\mid p}$}}(\sigma^{\prime},f^{\prime}) in \langle\pi,e\rangle\!\downarrow . In case (2), inversion of the first premise gives us: \frac{(\sigma,f)\mathrel{\resizebox{}{}{{\hbox{\hskip 0.0pt\raise-5.0pt\hbox{{$\xRightarrow{a}$}}}}}}{{\mathbf{jmp}~l,\sigma^{\prime\prime}}}\text{ in }\langle\pi,e\rangle}{((\sigma^{\prime\prime},e_{l}),\langle a|)\in\mathrm{con}_{\delta}(\sigma,f)} where n=(\sigma^{\prime\prime},e_{l}) and h=\langle a| . Let r=(b,(\sigma^{\prime},f^{\prime}),p)\in\mathrm{accu}(\mathrm{res}_{\delta},\mathrm{con}_{\delta},(\sigma^{\prime},e_{l})) . The induction hypothesis applied to the second premise gives us (\sigma^{\prime\prime},e_{l})\mathrel{\raisebox{-2.0pt}{$\xrightarrow{b\mid p}$}}(\sigma^{\prime},f^{\prime}) in \langle\pi,e\rangle\!\downarrow . We can now derive: \frac{(\sigma,f)\mathrel{\resizebox{}{}{{\hbox{\hskip 0.0pt\raise-5.0pt\hbox{{$\xRightarrow{a}$}}}}}}{{\mathbf{jmp}~l,\sigma^{\prime\prime}}}\text{ in }\langle\pi,e\rangle\hskip 9.24994pt(\sigma^{\prime\prime},e_{l})\mathrel{\raisebox{-2.0pt}{$\xrightarrow{b\mid p}$}}(\sigma^{\prime},f^{\prime})\text{ in }\langle\pi,e\rangle\!\downarrow}{(\sigma,f)\mathrel{\raisebox{-2.0pt}{$\xrightarrow{a\land b\mid p}$}}(\sigma^{\prime},f^{\prime})\text{ in }\langle\pi,e\rangle\!\downarrow} Because (b_{0},(\sigma^{\prime},f^{\prime}),p)=h(r)=(a\land b,(\sigma^{\prime},f^{\prime}),p) , there is (\sigma,f)\mathrel{\raisebox{-2.0pt}{$\xrightarrow{b_{0}\mid p}$}}(\sigma^{\prime},f^{\prime}) in \langle\pi,e\rangle\!\downarrow which concludes the proof.