Introduction
Model Learning , also known as Active Automata Learning (AAL) [7 , 44 , 55 ] , uses tests to infer automata models that represent the dynamic behavior of software or hardware components. Models obtained by AAL have proven useful for many purposes, such as analyzing security protocols [22 , 23 , 45 , 50 ] [28], mining APIs [6 ] , supporting model-based testing [30 , 52 , 57 ] and conformance testing [4 ] . Efficient AAL algorithms have been developed [7 , 33 , 35 , 44 , 54 ] and implemented [36 ] , supported by various domain-specific optimizations. However, their scope is limited to finite state machine (FSM) models, such as Mealy machines.
For many analysis tasks, however, it is crucial for models to also be able to describe data flow , including constraints on data parameters that are passed between the component and its environment, as well as the mutual influence between dynamic behavior and data flow. For instance, models of protocol components should describe how different values of sequence numbers, identifiers, etc. influence and are influenced by dynamic behavior. This has motivated several approaches for extending AAL to Extended Finite State Machine (EFSM) models. Some approaches reduce the problem to inferring FSMs by employing manually supplied abstractions on the data domain [3 , 5 ] ; this requires insight into the control/data dependencies of the System Under Learning (SUL). Other approaches extend AAL for finite state models by allowing transitions to contain predicates over rich data domains, but cannot generate state variables to model data dependencies between consecutive interactions [16 , 39 ] . Finally, there exist extensions to EFSM models with state variables and guards from a fixed theory, such as Register Automata (RA) [1 , 2 , 13 , 14 , 34 ] , automata which can express relations between data parameters. RA models have uncovered bugs in e.g., TCP implementations [19 , 20 ] , but the learning algorithms that these works used do not scale well, especially with increasing numbers of registers.
This work aims to improve the scalability of state-of-the-art RA learning algorithms. The main challenge is reducing the number of tests that are performed. In typical RA learning algorithms, tests are sequences of actions (e.g., protocol messages or API calls) of form u v uv uv , composed from a prefix u u u and a suffix v v v . When learning FSMs, such tests are used to determine whether prefixes u u u and u ′ u' u ′ can be distinguished by the SUL’s reaction to u v uv uv and u ′ v u'v u ′ v for some v v v . In RA learning, such tests must also detect dependencies between data parameters in the prefix u u u and the suffix v v v . Such dependencies are inferred by varying the data parameters in v v v to examine how the choice of parameters in u u u affect the SUL’s reaction to the composition u v uv uv . These dependencies are then used to infer state variables and guards on outgoing transitions from u u u ; prefixes that are separated by differences in these dependencies will lead to different control states in the learned RA. For instance, if the SUL reacts differently to a ( 1 ) b ( 1 ) a(1)b(1) a ( 1 ) b ( 1 ) and a ( 1 ) b ( 2 ) a(1)b(2) a ( 1 ) b ( 2 ) , it is inferred that the parameter of a a a must be remembered in a state variable; if it also does not distinguish c ( 1 ) b ( 1 ) c(1)b(1) c ( 1 ) b ( 1 ) from c ( 1 ) b ( 2 ) c(1)b(2) c ( 1 ) b ( 2 ) , then a ( 1 ) a(1) a ( 1 ) and c ( 1 ) c(1) c ( 1 ) must lead to different control locations. A main scalability problem is that in a naïve approach, the number of tests for inferring dependencies grows exponentially with the length of the suffix. The S L λ SL^\lambda S L λ algorithm [14 , 15 ] , the current state-of-the-art in RA learning, addressed this by (i) reducing the number of tested prefix-suffix combinations by employing a classification tree [35 , 37 ] , (ii) preferring shorter suffixes over longer ones [33 ] , and (iii) employing a simple scheme for restricting the range of values considered in suffixes. These techniques achieve significant performance improvements over S L λ SL^\lambda S L λ [13 ] , the previous state-of-the-art algorithm. However, the restriction scheme of S L λ SL^\lambda S L λ is simplistic; suffix parameters can be restricted only if they have no dependencies to any prefix parameter. In SULs which exhibit many data dependencies, this causes a large subset of suffixes to be unrestricted, potentially causing an exponential blow-up in the number of tests.
This paper introduces S L ≡ λ SL^\lambda_{\equiv} S L ≡ λ , an extension of S L λ SL^\lambda S L λ optimized for inferring RA models with equality relations between values of data parameters. In addition to the simple restrictions that S L λ SL^\lambda S L λ comes with, S L ≡ λ SL^\lambda_{\equiv} S L ≡ λ also allows to restrict parameters to be equal to one or more prefix values by using information gained about dependencies between suffix parameters and prefix values. For example, if it is detected that a ( 1 ) a(1) a ( 1 ) and a ( 1 ) a ( 2 ) a(1)a(2) a ( 1 ) a ( 2 ) are separated by b ( 1 ) b ( 1 ) b(1)b(1) b ( 1 ) b ( 1 ) then S L ≡ λ SL^\lambda_{\equiv} S L ≡ λ restricts the data parameters to these values (1 and 1) also when investigating whether another prefix, e.g., a ( 1 ) a ( 2 ) a ( 3 ) a(1)a(2)a(3) a ( 1 ) a ( 2 ) a ( 3 ) , can be distinguished from a ( 1 ) a(1) a ( 1 ) or a ( 1 ) a ( 2 ) a(1)a(2) a ( 1 ) a ( 2 ) . This allows S L = λ SL^\lambda_{=} S L = λ to separate locations using only one test in most cases, in contrast to the seventeen tests that S L λ SL^\lambda S L λ would use, corresponding to the possible inequivalent instantiations of the parameters of b ( p 1 ) b ( p 2 ) b(p_1)b(p_2) b ( p 1 ) b ( p 2 ) after the prefix a ( 1 ) a ( 2 ) a ( 3 ) a(1)a(2)a(3) a ( 1 ) a ( 2 ) a ( 3 ) .
We present the S L = λ SL^\lambda_{=} S L = λ algorithm in detail (Section 4), and prove (§ 5 ) that S L = λ SL^\lambda_{=} S L = λ , when presented with a data language L \mathcal{L} L of finite index, is guaranteed to infer a minimal (in the number of locations) RA which accepts L \mathcal{L} L .
We have implemented S L = λ SL^\lambda_{=} S L = λ as a new algorithm in RALib [12 ] , a library for RA learning which comes with implementations of S L ∗ SL^* S L ∗ [13 ] and S L λ SL^\lambda S L λ [14 , 15 ] . Our performance evaluation (§ 6 ), on a variety of benchmarks, including experiments to learn models for five DTLS server implementations, shows that S L = λ SL^\lambda_{=} S L = λ uses fewer tests than the other two algorithms, both during model construction and in total, and scales much better than them as SULs increase in size.
Related Work. AAL has been researched for almost four decades; see [31 , 32 ] for overviews. Applications of AAL include generation of behavioral models for software [48 , 51 ] , e.g. for network protocol implementations [22 , 45 ] , security analyses and model checking [3 , 21 , 24 ] , testing [41 , 49 ] , and formal analyses of systems [55 ] . Learning beyond FSMs has been investigated for many models aside from register automata. For example, algorithms have been presented for workflow Petri nets [18 ] , data automata [26 ] , generic nondeterministic transition systems [56 ] , symbolic automata [16 , 40 ] , NetKAT programs [42 ] , automata with timers [10 , 53 ] , sub-classes of timed automata [27 ] , session automata [9 ] , and procedural systems [25 ] .
Several algorithms combine learning algorithms for FSMs with various approaches for inferring symbolic data constraints: Daikon [17 ] has been combined with state merging for passive learning [38 ] ; FSM learners have been combined with a bespoke inference of data constraints [19 ] , or with genetic programming [29 ] . One approach for learning EFSMs combines an FSM learner with a manually created abstraction module that maps symbolic RA transitions to a finite alphabet [1 , 2 ] . Another approach for inferring registers is to extend the learning model with memorability queries that directly provide registers [8 ] .
The previous approaches do not tackle the problem of inferring registers from only membership and equality queries. Approaches that address this problem include that of Sakamoto [47 ] , which presented the first AAL algorithm for a version of register automata, called finite memory automata, that was never implemented. More closely related to our work are the RA learning algorithms [13 , 14 ] implemented in RALib. Compared to these algorithms, and to S L λ SL^\lambda S L λ in particular, we employ more fine-grained restrictions, which result in significant performance improvements and better scalability, as we demonstrate in § 6 .
Main Ideas
In this section, we introduce the main ideas behind the S L = λ SL^\lambda_{=} S L = λ algorithm and how it differs from S L λ SL^\lambda S L λ . As an illustrating example, we will use the data language L P ( n ) \mathcal{L}_{P(n)} L P ( n ) , which assumes a data domain N \mathbb{N} N of natural numbers and the single action a. In the context of L P ( n ) \mathcal{L}_{P(n)} L P ( n ) , a data symbol is a term of form a(d), where the parameter d is a natural number, and a data word (or word ) is a finite sequence of data symbols. A data language L \mathcal{L} L is a set of data words, such that membership in L \mathcal{L} L depends only on the equalities and inequalities between its parameters; put differently, if the word w is in L \mathcal{L} L then any bijection on N \mathbb{N} N applied to w is also in L \mathcal{L} L . The language L P ( n ) \mathcal{L}_{P(n)} L P ( n ) contains words of length at most n in which the parameters form a palindrome. In the following, we will consider L P ( 3 ) \mathcal{L}_{P(3)} L P ( 3 ) ; for example, a(5)a(5) and a(3)a(1)a(3) are in L P ( 3 ) \mathcal{L}_{P(3)} L P ( 3 ) , but a(5)a(7) and a(3)a(1)a(2) are not.
The task of AAL is to learn an acceptor for L P ( 3 ) \mathcal{L}_{P(3)} L P ( 3 ) in a black-box scenario, i.e., knowing only the alphabet { a } \{a\} { a } and the data domain, by asking two kinds of queries: A membership query (MQ) asks whether a word w is in L P ( 3 ) \mathcal{L}_{P(3)} L P ( 3 ) ; it can be realized by a simple test. An equivalence query (EQ) asks whether a hypothesis H \mathcal{H} H accepts L P ( 3 ) \mathcal{L}_{P(3)} L P ( 3 ) ; it is answered either by yes or by a counterexample , i.e., a word on which L ( H ) \mathcal{L}(\mathcal{H}) L ( H ) and L P ( 3 ) \mathcal{L}_{P(3)} L P ( 3 ) disagree; Typically, a sequence of MQs is used to construct H \mathcal{H} H , which is then subject to validation by an EQ; if a counterexample is found, hypothesis construction is resumed, etc., until convergence.
An acceptor for L P ( 3 ) \mathcal{L}_{P(3)} L P ( 3 ) , in the form of a register automaton is shown in Figure 1 . This RA can be the output of an AAL algorithm. It has four accepting locations (l 0 l_0 l 0 , l 1 l_1 l 1 , l 2 l_2 l 2 , and l 3 l_3 l 3 ) and two rejecting locations (l 4 l_4 l 4 and a sink location, not shown). Each location is labeled by its set of active registers (e.g., { x 1 } \{x_1\} { x 1 } in l 2 l_2 l 2 ). Each transition is labeled by a parameterized data symbol a(p), a guard (to right), and an assignment to registers (bottom). The guard is a boolean combination of equalities and negated equalities between p and registers. The RA processes a data word by considering its data symbols one by one, starting in the initial location l 0 l_0 l 0 . When in a location l i l_i l i and seeing a symbol a(d), it (i) matches the parameterized data symbol a(p) with a(d) (essentially assigning d to p) (ii) selects an outgoing transition from l i l_i l i whose guard evaluates to true when p is assigned d, (iii) performs that transition’s assignment to registers, and (iv) moves to its target location. The accepting locations l 0 l_0 l 0 and l 1 l_1 l 1 are reached on words of length zero and one, respectively. The accepting location l 2 l_2 l 2 is reached on inputs a(d 1 d_1 d 1 )a(d 2 d_2 d 2 ) of length two where d 1 = d 2 d_1=d_2 d 1 = d 2 whereas the rejecting location l 4 l_4 l 4 corresponds to inputs a(d 1 d_1 d 1 )a(d 2 d_2 d 2 ) where d 1 ≠ d 2 d_1\ne d_2 d 1 = d 2 , and l 3 l_3 l 3 corresponds to inputs a(d 1 d_1 d 1 )a(d 2 d_2 d 2 )a(d 3 d_3 d 3 ) where d 1 = d 3 d_1=d_3 d 1 = d 3 . In locations l 1 l_1 l 1 , l 2 l_2 l 2 and l 4 l_4 l 4 register x 1 x_1 x 1 stores the parameter of the first symbol in the word.
Figure 1. Register automaton accepting language L P ( 3 ) \mathcal{L}_{P(3)} L P ( 3 ) .
Classical AAL algorithms that learn DFAs [7 , 44 ] maintain an expanding set of words, S p S_p S p , called short prefixes , and an expanding set of words, called suffixes , which induce an equivalence relation ≡ \equiv ≡ on prefixes, defined by u ≡ u ′ u \equiv u' u ≡ u ′ iff u v ∈ L ⇔ u ′ v ∈ L uv \in\mathcal{L} \Leftrightarrow u'v \in\mathcal{L} uv ∈ L ⇔ u ′ v ∈ L for all suffixes v v v . This allows equivalence classes of prefixes to represent locations in the automaton which is constructed. Generalizations of AAL for learning RAs similarly represent locations by equivalence classes of data words: a location l l l can be represented by the data words that reach l l l . However, the equivalence on prefixes cannot be defined as in the DFA case. Instead of suffixes, S L λ SL^\lambda S L λ maintains a set of symbolic suffixes , each of which is a parameterized word, i.e., a word where data values are replaced by parameters p 1 , … , p m p_1,\ldots,p_m p 1 , … , p m . For a prefix u u u , say a ( 0 ) a(0) a ( 0 ) , and symbolic suffix v v v , say a ( p 1 ) a(p_1) a ( p 1 ) , membership in L \mathcal{L} L of words of the form u v uv uv depends on how the symbolic parameters in v v v are instantiated. In S L λ SL^\lambda S L λ this dependency is represented by a function L [ u , v ] \mathcal{L}[u,v] L [ u , v ] with arguments x 1 x_1 x 1 (representing the first data value of u u u ) and the symbolic parameter p 1 p_1 p 1 which expresses how membership depends on the relation between the data values of u u u and the values that instantiate parameters of v v v . Letting + + + stand for accept and − - − for reject , we have for u = a ( 0 ) u=a(0) u = a ( 0 ) and v = a ( p 1 ) v=a(p_1) v = a ( p 1 ) that L [ u , v ] ( x 1 , p 1 ) \mathcal{L}[u,v](x_1,p_1) L [ u , v ] ( x 1 , p 1 ) is + + + iff x 1 = p 1 x_1=p_1 x 1 = p 1 and − - − otherwise. We can then generalize the equivalence ≡ \equiv ≡ to the setting with data by defining prefixes u , u ′ u,u' u , u ′ to be equivalent if L [ u , v ] \mathcal{L}[u,v] L [ u , v ] and L [ u ′ , v ] \mathcal{L}[u',v] L [ u ′ , v ] are equivalent modulo permutations of registers x 1 , x 2 , … x_1,x_2,\ldots x 1 , x 2 , … for all symbolic suffixes v v v .
Functions of form L [ u , v ] \mathcal{L}[u,v] L [ u , v ] are generated by so-called tree queries , which perform membership queries for all possible combinations of equalities and negated equalities between data values in u u u and parameters in v v v . Generating L [ a ( 0 ) , a ( p 1 ) ] \mathcal{L}[a(0),a(p_1)] L [ a ( 0 ) , a ( p 1 )] requires two MQs, say a ( 0 ) a ( 0 ) a(0)a(0) a ( 0 ) a ( 0 ) and a ( 0 ) a ( 1 ) a(0)a(1) a ( 0 ) a ( 1 ) , corresponding to equality and negated equality between the data values in the prefix and in the suffix. In general, the number of induced MQs increases exponentially with the number of parameters in the suffix, and polynomially with the number of parameters in the prefix. Thus, generating L [ a ( 0 ) , a ( p 1 ) a ( p 2 ) ] \mathcal{L}[a(0),a(p_1)a(p_2)] L [ a ( 0 ) , a ( p 1 ) a ( p 2 )] requires five MQs (a ( 0 ) a ( 0 ) a ( 0 ) a(0)a(0)a(0) a ( 0 ) a ( 0 ) a ( 0 ) , a ( 0 ) a ( 0 ) a ( 1 ) a(0)a(0)a(1) a ( 0 ) a ( 0 ) a ( 1 ) , a ( 0 ) a ( 1 ) a ( 0 ) a(0)a(1)a(0) a ( 0 ) a ( 1 ) a ( 0 ) , a ( 0 ) a ( 1 ) a ( 1 ) a(0)a(1)a(1) a ( 0 ) a ( 1 ) a ( 1 ) , and a ( 0 ) a ( 1 ) a ( 2 ) a(0)a(1)a(2) a ( 0 ) a ( 1 ) a ( 2 ) ), whereas L [ a ( 0 ) , a ( p 1 ) a ( p 2 ) a ( p 3 ) ] \mathcal{L}[a(0),a(p_1)a(p_2)a(p_3)] L [ a ( 0 ) , a ( p 1 ) a ( p 2 ) a ( p 3 )] requires fifteen MQs.
The goal of S L = λ SL^\lambda_{=} S L = λ is to improve on the performance of S L λ SL^\lambda S L λ by reducing, as much as possible, the number of MQs needed for constructing functions of form L [ u , v ] \mathcal{L}[u,v] L [ u , v ] . This is done by reducing the number of data values that need be considered by restricting the parameters in v v v . A restriction limits the relationships that should be considered between a parameter in v v v to the other parameters in u u u and v v v . As an example, for L [ a ( 0 ) , a ( p 1 ) a ( p 2 ) ] \mathcal{L}[a(0),a(p_1)a(p_2)] L [ a ( 0 ) , a ( p 1 ) a ( p 2 )] , a restriction on p 2 p_2 p 2 can be of the form (i) fresh (p 2 p_2 p 2 ), meaning that the value of p 2 p_2 p 2 must be different from all preceding values in u u u and the suffix, (ii) p 2 = p 1 p_2=p_1 p 2 = p 1 , meaning that the value of p 2 p_2 p 2 must be equal to that of p 1 p_1 p 1 , or (iii) p 2 = x 1 p_2=x_1 p 2 = x 1 , meaning that the value of p 2 p_2 p 2 must be equal to the first data value in the prefix; this restriction can be applied only if some previously applied suffix has detected that the first data value of u u u must be saved in a register x 1 x_1 x 1 . Which restrictions to apply depends on the purpose for which L [ u , v ] \mathcal{L}[u,v] L [ u , v ] is constructed: this can be to (i) demonstrate that u u u is not equivalent to some other prefix(es), (ii) discover a new guard and outgoing transition from u u u , or (iii) discover a new register in the location represented by u u u . For an example of purpose (i), in Figure 1 the locations l 2 l_2 l 2 and l 3 l_3 l 3 , represented by prefixes u = a ( 0 ) a ( 0 ) u = a(0)a(0) u = a ( 0 ) a ( 0 ) and u ′ = a ( 0 ) a ( 0 ) a ( 0 ) u' = a(0)a(0)a(0) u ′ = a ( 0 ) a ( 0 ) a ( 0 ) , respectively, are separated by v = a ( p 1 ) v = a(p_1) v = a ( p 1 ) , since L [ u , v ] ( x 1 , p 1 ) \mathcal{L}[u,v](x_1,p_1) L [ u , v ] ( x 1 , p 1 ) is + iff x 1 = p 1 x_1 = p_1 x 1 = p 1 and − otherwise, whereas L [ u ′ , v ] = − \mathcal{L}[u',v] = - L [ u ′ , v ] = − . They are also separated by a ( p 1 ) a(p_1) a ( p 1 ) under the restriction p 1 = x 1 p_1 = x_1 p 1 = x 1 since u a ( 0 ) ∈ L P ( 3 ) ua(0) \in\mathcal{L}P(3) u a ( 0 ) ∈ L P ( 3 ) while u ′ a ( 0 ) ∉ L P ( 3 ) u'a(0) \notin\mathcal{L}P(3) u ′ a ( 0 ) ∈ / L P ( 3 ) , but not under the restriction f r e s h ( p 1 ) fresh(p_1) f r es h ( p 1 ) since both u a ( 1 ) ∉ L P ( 3 ) ua(1) \notin\mathcal{L}P(3) u a ( 1 ) ∈ / L P ( 3 ) and u ′ a ( 1 ) ∉ L P ( 3 ) u'a(1) \notin\mathcal{L}P(3) u ′ a ( 1 ) ∈ / L P ( 3 ) . In this case, the restriction p 1 = x 1 p_1 = x_1 p 1 = x 1 saves only one MQ for the purpose of separating u u u from u ′ u' u ′ . In other cases, the savings can be substantial, as we show below.
Consider the short prefixes u = a ( 0 ) u = a(0) u = a ( 0 ) and u ′ = a ( 0 ) a ( 0 ) u' = a(0)a(0) u ′ = a ( 0 ) a ( 0 ) . These are separated by the symbolic suffix v = a ( p 1 ) a ( p 2 ) v = a(p_1)a(p_2) v = a ( p 1 ) a ( p 2 ) , since L [ u , v ] ( x 1 , p 1 , p 2 ) \mathcal{L}[u,v](x_1,p_1,p_2) L [ u , v ] ( x 1 , p 1 , p 2 ) is + iff x 1 = p 2 x_1 = p_2 x 1 = p 2 and − otherwise, whereas L [ u ′ , v ] ( x 1 , p 1 , p 2 ) = − \mathcal{L}[u',v](x_1,p_1,p_2) = - L [ u ′ , v ] ( x 1 , p 1 , p 2 ) = − . We often represent such functions as symbolic decision trees (SDTs) of a certain form. Figures 2c and 2d show the SDTs for L [ u , v ] \mathcal{L}[u,v] L [ u , v ] and L [ u ′ , v ] \mathcal{L}[u',v] L [ u ′ , v ] . For each of u u u and u ′ u' u ′ , S L λ SL^\lambda S L λ makes five MQs to construct these decision trees, one for each of the relevant combination values of suffix parameters, shown in Figs. 2a and 2b. For example, the blue path in Fig. 2a corresponds to the test a ( 0 ) a ( 0 ) a ( 0 ) a(0)a(0)a(0) a ( 0 ) a ( 0 ) a ( 0 ) . We also see that to separate u u u and u ′ u' u ′ , it suffices to compare only the blue tests in Figs. 2a and 2b. This is because, no matter how the other tests turn out, the corresponding constructed SDTs will be different. In the suffix v v v , we can therefore restrict p 1 p_1 p 1 and p 2 p_2 p 2 in a ( p 1 ) a ( p 2 ) a(p_1)a(p_2) a ( p 1 ) a ( p 2 ) to both be equal to x 1 x_1 x 1 and construct corresponding SDTs from only one MQ. The constructed SDTs will both have only one path labeled t r u e t r u e true\ true t r u e t r u e , but for u u u it will lead to accept and for u ′ u' u ′ to reject. The restriction separates u u u and u ′ u' u ′ with only one MQ for each of u u u and u ′ u' u ′ , compared to five in the unrestricted case. A restricted suffix that induces only one membership query is called atomic. In fact, all suffixes used by S L = λ SL^\lambda_{=} S L = λ for separating locations are atomic. We here note that the restriction in this example can be applied only if the register x 1 x_1 x 1 has already been detected; this can be done by the unrestricted suffix a ( p 1 ) a(p_1) a ( p 1 ) , which induces two MQs (a ( 0 ) a ( 0 ) a(0)a(0) a ( 0 ) a ( 0 ) and a ( 0 ) a ( 1 ) a(0)a(1) a ( 0 ) a ( 1 ) ) that detect the necessity of remembering the data value of u u u in a register.
The suffix a ( p 1 ) a(p_1) a ( p 1 ) is used to discover guards after the prefix a ( 0 ) a(0) a ( 0 ) since the SDT constructed from the tests a ( 0 ) a ( 0 ) a(0)a(0) a ( 0 ) a ( 0 ) and a ( 0 ) a ( 1 ) a(0)a(1) a ( 0 ) a ( 1 ) has two branches separated by the guards p 1 = x 1 p_1 = x_1 p 1 = x 1 and p 1 ≠ x 1 p_1 \ne x_1 p 1 = x 1 . In general, to discover guards using a suffix like a ( p 1 ) a(p_1) a ( p 1 ) , the parameter p 1 p_1 p 1 must be allowed to range over the data values in the prefix and also to an additional fresh data value, since these data values correspond to different potential guards.
Main Concepts
In this section, we first review background concepts on data languages and register automata and then introduce symbolic decision trees used in S L = λ SL^\lambda_{=} S L = λ . We assume an infinite domain D D D of data values and a set Σ \Sigma Σ of actions , each with an arity that denotes how many parameters it takes from D D D . For simplicity, we assume that all actions have arity 1; our techniques can be extended to handle actions with arbitrary arities. A data symbol is a term of form α ( d ) \alpha(d) α ( d ) , where α \alpha α is an action and d ∈ D d \in D d ∈ D is a data value. A data word (or simply word ) is a finite sequence of data symbols. The concatenation of two words u u u and v v v is denoted u v uv uv ; we then refer to u u u as a prefix and v v v as a suffix . For a word w = α 1 ( d 1 ) … α n ( d n ) w = \alpha_1(d_1) \ldots\alpha_n(d_n) w = α 1 ( d 1 ) … α n ( d n ) , let V a l s ( w ) Vals(w) V a l s ( w ) denote the set of data values that occur in w w w , and let ∣ w ∣ |w| ∣ w ∣ denote the number of data symbols in w w w . Two words w = α 1 ( d 1 ) … α n ( d n ) w = \alpha_1(d_1) \ldots\alpha_n(d_n) w = α 1 ( d 1 ) … α n ( d n ) and w ′ = α 1 ( d 1 ′ ) … α n ( d n ′ ) w' = \alpha_1(d'_1) \ldots\alpha_n(d'_n) w ′ = α 1 ( d 1 ′ ) … α n ( d n ′ ) are indistinguishable , denoted w ≈ w ′ w \approx w' w ≈ w ′ , if d i = d j ⇔ d i ′ = d j ′ d_i = d_j \Leftrightarrow d'_i = d'_j d i = d j ⇔ d i ′ = d j ′ for all indices i , j ∈ 1 … n i, j \in1 \ldots n i , j ∈ 1 … n . A data language L L L is a set of data words such that w ∈ L ⇔ w ′ ∈ L w \in L \Leftrightarrow w' \in L w ∈ L ⇔ w ′ ∈ L whenever w ≈ w ′ w \approx w' w ≈ w ′ .
Register Automata. We assume a set of registers x 1 , x 2 , … x_1, x_2, \ldots x 1 , x 2 , … , and a set of formal parameters p , p 1 , p 2 , … p, p_1, p_2, \ldots p , p 1 , p 2 , … . A parameterized symbol is a term of form α ( p ) \alpha(p) α ( p ) , where α \alpha α is an action and p p p a formal parameter . Given a parameterized symbol p p p and a set X \mathcal{X} X of registers, a guard over p p p and X \mathcal{X} X is a constraint, either of form p = x i p = x_i p = x i for x i ∈ X x_i \in\mathcal{X} x i ∈ X , or of form ⋀ x i ∈ X p ≠ x i \bigwedge_{x_i \in X} p \ne x_i ⋀ x i ∈ X p = x i for some X ⊆ X X \subseteq\mathcal{X} X ⊆ X . We will sometimes use the term else-guard when referring to a guard of the second form. Note that an else-guard is true in case X X X is the empty set. An assignment is a parallel update of registers with values from registers or the formal parameter p p p . We represent it as a mapping π \pi π from { x i 1 , … , x i m } \{x_{i_1}, \ldots, x_{i_m}\} { x i 1 , … , x i m } to { x j 1 , … , x j n } ∪ { p } \{x_{j_1}, \ldots, x_{j_n}\} \cup\{p\} { x j 1 , … , x j n } ∪ { p } , meaning that the value π ( x i k ) \pi(x_{i_k}) π ( x i k ) is assigned to x i k x_{i_k} x i k , for k = 1 , … , m k = 1, \ldots, m k = 1 , … , m . In multiple-assignment notation, this would be written x i 1 , … , x i m : = π ( x i 1 ) , … , π ( x i m ) x_{i_1}, \ldots, x_{i_m} := \pi(x_{i_1}), \ldots, \pi(x_{i_m}) x i 1 , … , x i m := π ( x i 1 ) , … , π ( x i m ) .
Definition 1. A register automaton is a tuple A = ( L , l 0 , X , Γ , λ ) \mathcal{A} = (L, l_0, \mathcal{X}, \Gamma, \lambda) A = ( L , l 0 , X , Γ , λ ) , where
L L L is a finite set of locations, with l 0 ∈ L l_0 \in L l 0 ∈ L as the initial location,
X \mathcal{X} X maps each location l ∈ L l \in L l ∈ L to a finite set X ( l ) \mathcal{X}(l) X ( l ) of registers,
Γ \Gamma Γ is a finite set of transitions, each of form ⟨ l , α ( p ) , g , π , l ′ ⟩ \langle l, \alpha(p), g, \pi, l' \rangle ⟨ l , α ( p ) , g , π , l ′ ⟩ , where
l ∈ L l \in L l ∈ L is a source location and l ′ ∈ L l' \in L l ′ ∈ L is a target location,
α ( p ) \alpha(p) α ( p ) is a parameterized symbol,
g g g , the guard, is a guard over p p p and X ( l ) \mathcal{X}(l) X ( l ) .
π \pi π (the assignment) is a mapping from X ( l ′ ) \mathcal{X}(l') X ( l ′ ) to X ( l ) ∪ { p } \mathcal{X}(l) \cup\{p\} X ( l ) ∪ { p } , and
λ \lambda λ maps each l ∈ L l \in L l ∈ L to { + , − } \{+,-\} { + , − } , where + + + denotes accept and − - − reject.
A state of a RA A = ( L , l 0 , X , Γ , λ ) \mathcal{A}=(L,l_0,\mathcal{X},\Gamma,\lambda) A = ( L , l 0 , X , Γ , λ ) is a pair ⟨ l , μ ⟩ \langle l,\mu\rangle ⟨ l , μ ⟩ where l ∈ L l\in L l ∈ L and μ \mu μ is a valuation over X ( l ) \mathcal{X}(l) X ( l ) , i.e., a mapping from X ( l ) \mathcal{X}(l) X ( l ) to D \mathcal{D} D . A step of A \mathcal{A} A , denoted ⟨ l , μ ⟩ → α ( d ) ⟨ l ′ , μ ′ ⟩ \langle l,\mu\rangle\xrightarrow{\alpha(d)} \langle l',\mu'\rangle ⟨ l , μ ⟩ α ( d ) ⟨ l ′ , μ ′ ⟩ , transfers the state of A \mathcal{A} A from ⟨ l , μ ⟩ \langle l,\mu\rangle ⟨ l , μ ⟩ to ⟨ l ′ , μ ′ ⟩ \langle l',\mu'\rangle ⟨ l ′ , μ ′ ⟩ on input of the data symbol α ( d ) \alpha(d) α ( d ) if there is a transition ⟨ l , α ( p ) , g , π , l ′ ⟩ ∈ Γ \langle l,\alpha(p),g,\pi,l'\rangle\in\Gamma ⟨ l , α ( p ) , g , π , l ′ ⟩ ∈ Γ such that (i) μ ⊨ g [ d / p ] \mu\models g[d/p] μ ⊨ g [ d / p ] , i.e., d d d satisfies the guard g g g under the valuation μ \mu μ , and (ii) μ ′ \mu' μ ′ is defined by μ ′ ( x i ) = μ ( x j ) \mu'(x_i)=\mu(x_j) μ ′ ( x i ) = μ ( x j ) if π ( x i ) = x j \pi(x_i)=x_j π ( x i ) = x j , otherwise μ ′ ( x i ) = d \mu'(x_i)=d μ ′ ( x i ) = d if π ( x i ) = p \pi(x_i)=p π ( x i ) = p . A run of A \mathcal{A} A over a data word w = α ( d 1 ) … α ( d n ) w=\alpha(d_1)\ldots\alpha(d_n) w = α ( d 1 ) … α ( d n ) is a sequence of steps of A \mathcal{A} A
⟨ l 0 , μ 0 ⟩ → α 1 ( d 1 ) ⟨ l 1 , μ 1 ⟩ ⋯ ⟨ l n − 1 , μ n − 1 ⟩ → α n ( d n ) ⟨ l n , μ n ⟩ \langle l_0,\mu_0\rangle\xrightarrow{\alpha_1(d_1)} \langle l_1,\mu_1\rangle\ \cdots\ \langle l_{n-1},\mu_{n-1}\rangle\xrightarrow{\alpha_n(d_n)} \langle l_n,\mu_n\rangle ⟨ l 0 , μ 0 ⟩ α 1 ( d 1 ) ⟨ l 1 , μ 1 ⟩ ⋯ ⟨ l n − 1 , μ n − 1 ⟩ α n ( d n ) ⟨ l n , μ n ⟩
where the initial valuation μ 0 \mu_0 μ 0 is empty. The run is accepting if λ ( l n ) = + \lambda(l_n)=+ λ ( l n ) = + and rejecting if λ ( l n ) = − \lambda(l_n)=- λ ( l n ) = − . The word w w w is accepted (rejected) by A \mathcal{A} A under μ 0 \mu_0 μ 0 if A \mathcal{A} A has an accepting (rejecting) run over w w w from ⟨ l 0 , μ 0 ⟩ \langle l_0,\mu_0\rangle ⟨ l 0 , μ 0 ⟩ . Define the language L ( A ) L(\mathcal{A}) L ( A ) as the set of words accepted by A \mathcal{A} A . We require register automata to be deterministic , meaning that outgoing transitions from a location are mutually exclusive.
Restricted Suffixes. Let u u u be a data word α 1 ( d 1 ) … α k ( d k ) \alpha_1(d_1)\ldots\alpha_k(d_k) α 1 ( d 1 ) … α k ( d k ) . Define the potential of u u u , denoted p o t ( u ) pot(u) p o t ( u ) , as the set of positions of first occurrences of data values in u u u . For instance, if u u u is α 1 ( 5 ) α 2 ( 9 ) α 3 ( 5 ) α 4 ( 3 ) \alpha_1(5)\alpha_2(9)\alpha_3(5)\alpha_4(3) α 1 ( 5 ) α 2 ( 9 ) α 3 ( 5 ) α 4 ( 3 ) , then p o t ( u ) pot(u) p o t ( u ) is { 1 , 2 , 4 } \{1,2,4\} { 1 , 2 , 4 } . Let p o t r e g s ( u ) potregs(u) p o t r e g s ( u ) be the set of registers x l x_l x l with l ∈ p o t ( u ) l\in pot(u) l ∈ p o t ( u ) . A u u u -guard is a guard over p p p and p o t r e g s ( u ) potregs(u) p o t r e g s ( u ) . For a data word u u u , let μ u : p o t r e g s ( u ) → V a l s ( u ) \mu_u:potregs(u)\to Vals(u) μ u : p o t r e g s ( u ) → V a l s ( u ) be defined by μ u ( x i ) = d i \mu_u(x_i)=d_i μ u ( x i ) = d i for i ∈ p o t ( u ) i\in pot(u) i ∈ p o t ( u ) . We sometimes write ( u , d ) ⊨ g (u,d)\models g ( u , d ) ⊨ g for μ u ⊨ g [ d / p ] \mu_u\models g[d/p] μ u ⊨ g [ d / p ] , i.e., that the data value d d d satisfies the u u u -guard g g g after the prefix u u u . To each u u u -guard g g g is assigned a unique representative data value , denoted d u g d_u^g d u g , defined as (i) μ u ( x i ) \mu_u(x_i) μ u ( x i ) for a guard g g g of form p = x i p=x_i p = x i , and (ii) some data value not in u u u for an else-guard g g g ; for a given u u u , the representative value d u g d_u^g d u g should be the same for all else-guards g g g . In the S L = λ SL^\lambda_= S L = λ algorithm, whenever we need a one-symbol extension, of form u α ( d ) u\alpha(d) uα ( d ) , of a prefix u u u to satisfy a specific guard g g g , we always choose d d d as d u g d_u^g d u g .
A symbolic suffix is a word in which data values are replaced by formal parameters p 1 , … , p m p_1,\ldots,p_m p 1 , … , p m , i.e., it is of form α 1 ′ ( p 1 ) ⋯ α m ′ ( p m ) \alpha'_1(p_1)\cdots\alpha'_m(p_m) α 1 ′ ( p 1 ) ⋯ α m ′ ( p m ) . For a prefix u u u and a set X ⊆ p o t r e g s ( u ) \mathcal{X}\subseteq potregs(u) X ⊆ p o t r e g s ( u ) of registers, a X \mathcal{X} X -restricted suffix is of form α 1 ′ ( p 1 ∣ ϕ 1 ) ⋯ α m ′ ( p m ∣ ϕ m ) \alpha'_1(p_1\mid\phi_1)\cdots\alpha'_m(p_m\mid\phi_m) α 1 ′ ( p 1 ∣ ϕ 1 ) ⋯ α m ′ ( p m ∣ ϕ m ) , where α 1 ′ ( p 1 ) ⋯ α m ′ ( p m ) \alpha'_1(p_1)\cdots\alpha'_m(p_m) α 1 ′ ( p 1 ) ⋯ α m ′ ( p m ) is a symbolic suffix and each ϕ j \phi_j ϕ j is a restriction on which values are allowed for p j p_j p j . It is of one of the following forms:
fresh ( p j ) (p_j) ( p j ) , meaning that the value of p j p_j p j must be different from all preceding values in u u u and the suffix,
p j = x l p_j=x_l p j = x l , where x l ∈ X x_l\in\mathcal{X} x l ∈ X , meaning that the value of p j p_j p j must be equal to the value μ u ( x l ) \mu_u(x_l) μ u ( x l ) of x l x_l x l under the valuation μ u \mu_u μ u ,
p j = p j ′ p_j=p_{j'} p j = p j ′ , where j ′ < j j'<j j ′ < j , i.e., p j ′ p_{j'} p j ′ is an earlier parameter of the suffix, meaning that the value of p j p_j p j must be equal to that of p j ′ p_{j'} p j ′ ,
unmapped ( p j ) (p_j) ( p j ) , meaning that the value of p j p_j p j is either fresh (i.e., different from all preceding values in u u u and the suffix) or equal to a data value in V a l s ( u ) Vals(u) V a l s ( u ) but not equal to μ u ( x l ) \mu_u(x_l) μ u ( x l ) for any x l ∈ X x_l\in\mathcal{X} x l ∈ X , or
a disjunction of restrictions of the above forms.
A restricted suffix, where each parameter has a restriction of one of the first three forms is called atomic , since a corresponding tree query requires exactly one membership query. We here remark that previous works [14 , 34 ] used only the two types of restrictions: f r e s h ( p j ) \mathit{fresh}(p_j) fresh ( p j ) and p j = p j ′ p_j = p_{j'} p j = p j ′ .
For a prefix u = α 1 ( d 1 ) … α k ( d k ) u = \alpha_1(d_1)\ldots\alpha_k(d_k) u = α 1 ( d 1 ) … α k ( d k ) and restricted suffix z = α 1 ′ ( p 1 ) … α m ′ ( p m ) z = \alpha'_1(p_1)\ldots\alpha'_m(p_m) z = α 1 ′ ( p 1 ) … α m ′ ( p m ) , membership in L \mathcal{L} L of words of the form u z uz u z depends on how the symbolic parameters in v \boldsymbol{v} v are instantiated. In S L = λ \mathrm{SL}^{\lambda}_{=} SL = λ this dependency is represented by a function L [ u , z ] ( x 1 , … , x k , p 1 , … , p m ) \mathcal{L}[u,z](x_1,\ldots,x_k,p_1,\ldots,p_m) L [ u , z ] ( x 1 , … , x k , p 1 , … , p m ) over parameters x 1 , … , x k x_1,\ldots,x_k x 1 , … , x k and p 1 , … , p m p_1,\ldots,p_m p 1 , … , p m , where x i x_i x i represents the i i i th data value d i d_i d i of u u u and p j p_j p j represents the j j j th symbolic parameter of z z z . L [ u , z ] \mathcal{L}[u,z] L [ u , z ] should satisfy the criterion that
for all d 1 ′ , … , d m ′ d'_1,\ldots,d'_m d 1 ′ , … , d m ′ that satisfy the restriction of z z z (with p j p_j p j representing d j ′ d'_j d j ′ )
L [ u , z ] ( d 1 , … , d k , d 1 ′ , … , d m ′ ) = + \mathcal{L}[u,z](d_1,\ldots,d_k,d'_1,\ldots,d'_m) = + L [ u , z ] ( d 1 , … , d k , d 1 ′ , … , d m ′ ) = + iff u α 1 ′ ( d 1 ′ ) … α m ′ ( d m ′ ) ∈ L u\alpha'_1(d'_1)\ldots\alpha'_m(d'_m) \in\mathcal{L} u α 1 ′ ( d 1 ′ ) … α m ′ ( d m ′ ) ∈ L , and
L [ u , z ] ( d 1 , … , d k , d 1 ′ , … , d m ′ ) = − \mathcal{L}[u,z](d_1,\ldots,d_k,d'_1,\ldots,d'_m) = - L [ u , z ] ( d 1 , … , d k , d 1 ′ , … , d m ′ ) = − iff u α 1 ′ ( d 1 ′ ) … α m ′ ( d m ′ ) ∉ L u\alpha'_1(d'_1)\ldots\alpha'_m(d'_m) \notin\mathcal{L} u α 1 ′ ( d 1 ′ ) … α m ′ ( d m ′ ) ∈ / L .
We illustrate on the example in Figure 2 . Let u = a ( 0 ) u = a(0) u = a ( 0 ) and z = a ( p 1 ∣ ϕ 1 ) a ( p 2 ∣ ϕ 2 ) z = a(p_1\mid\phi_1)a(p_2\mid\phi_2) z = a ( p 1 ∣ ϕ 1 ) a ( p 2 ∣ ϕ 2 ) . If ϕ 1 = ϕ 2 = t r u e \phi_1 = \phi_2 = \mathit{true} ϕ 1 = ϕ 2 = true then L [ u , z ] \mathcal{L}[u,z] L [ u , z ] is + + + iff p 2 = x 1 p_2 = x_1 p 2 = x 1 and − - − otherwise; if ϕ 1 \phi_1 ϕ 1 is true and ϕ 2 \phi_2 ϕ 2 is p 2 = x 1 p_2 = x_1 p 2 = x 1 then L [ u , z ] \mathcal{L}[u,z] L [ u , z ] is + + + ; if ϕ 1 \phi_1 ϕ 1 is p 1 = x 1 p_1 = x_1 p 1 = x 1 and ϕ 2 \phi_2 ϕ 2 is p 2 = x 1 p_2 = x_1 p 2 = x 1 then L [ u , z ] \mathcal{L}[u,z] L [ u , z ] is + + + .
Figure 2. Used tests and SDTs for L [ a ( 0 ) , v ] \mathcal{L}[a(0),v] L [ a ( 0 ) , v ] and L [ a ( 0 ) a ( 0 ) , v ] \mathcal{L}[a(0)a(0),v] L [ a ( 0 ) a ( 0 ) , v ] with v = a ( p 1 ) a ( p 2 ) v = a(p_1)a(p_2) v = a ( p 1 ) a ( p 2 ) .
Symbolic Decision Trees. Since S L = λ \mathrm{SL}^{\lambda}_{=} SL = λ is intended to construct register automata, we find it natural to represent functions of form L [ u , z ] \mathcal{L}[u,z] L [ u , z ] in the form of tree-shaped “mini-RAs”, which we define as a symbolic decision trees (SDTs) of a certain form. For a prefix u = α 1 ( d 1 ) … α k ( d k ) u = \alpha_1(d_1)\ldots\alpha_k(d_k) u = α 1 ( d 1 ) … α k ( d k ) and a X \mathcal{X} X -restricted suffix z = α 1 ′ ( p 1 ∣ ϕ 1 ) ⋯ α m ′ ( p m ∣ ϕ m ) z = \alpha'_1(p_1\mid\phi_1)\cdots\alpha'_m(p_m\mid\phi_m) z = α 1 ′ ( p 1 ∣ ϕ 1 ) ⋯ α m ′ ( p m ∣ ϕ m ) , a ( u , z ) (u,z) ( u , z ) -path is a sequence g 1 ⋯ g m g_1\cdots g_m g 1 ⋯ g m where each guard g j g_j g j is of one of the following forms: (i) p j = x l p_j = x_l p j = x l , where x l ∈ potregs ( u ) x_l \in\operatorname{potregs}(u) x l ∈ potregs ( u ) , (ii) p j = p j ′ p_j = p_{j'} p j = p j ′ , where j ′ < j j' < j j ′ < j , i.e., p j ′ p_{j'} p j ′ is an earlier parameter of the suffix, or (iii) a conjunction of negations of guards of the two preceding forms. Note that t r u e \mathit{true} true is included in the allowed guards of form (iii). We often write g g g for g 1 ⋯ g m g_1\cdots g_m g 1 ⋯ g m .
An important principle is that the purpose of g j g_j g j is to distinguish among the data values allowed by ϕ j \phi_j ϕ j , and not to distinguish data values allowed by ϕ j \phi_j ϕ j from data values not allowed by ϕ j \phi_j ϕ j . Thus, if ϕ j \phi_j ϕ j is of one of form f r e s h ( p j ) \mathit{fresh}(p_j) fresh ( p j ) , p j = x l p_j = x_l p j = x l , or p j = p j ′ p_j = p_{j'} p j = p j ′ , then g j g_j g j must be t r u e \mathit{true} true . In general, the guard g j g_j g j can only use registers x l x_l x l or previous parameters p j ′ p_{j'} p j ′ whose values are allowed by the corresponding restriction ϕ j \phi_j ϕ j . A ( u , z ) (u,z) ( u , z ) -tree T T T is a mapping from a set Dom ( T ) \operatorname{Dom}(T) Dom ( T ) of ( u , z ) (u,z) ( u , z ) -paths to { + , − } \{+,-\} { + , − } . It represents the function with parameters x 1 , … , x k x_1,\ldots,x_k x 1 , … , x k (for the data values in a prefix) and p 1 , … , p m p_1,\ldots,p_m p 1 , … , p m (for the data values of a suffix), which maps a tuple of values of x 1 , … , x k x_1,\ldots,x_k x 1 , … , x k and p 1 , … , p m p_1,\ldots,p_m p 1 , … , p m to T ( g 1 ⋯ g m ) T(g_1\cdots g_m) T ( g 1 ⋯ g m ) whenever these values satisfy all guards g 1 , … , g m g_1,\ldots,g_m g 1 , … , g m . For a language L \mathcal{L} L it can be shown, using a generalization of the techniques for SDT-construction [11 ] that for each u u u and z z z there is a unique minimal ( u , z ) (u,z) ( u , z ) -tree T T T which represents L [ u , z ] \mathcal{L}[u,z] L [ u , z ] . The construction of minimal SDTs is rather straightforward; the basic principle is to introduce equality guards only when necessary. Figure 2 c and Figure 2 d show two SDTs that have been constructed from the information obtained in the tests in Figure 2 a and Figure 2 b, respectively.
S L = λ \mathrm{SL}^{\lambda}_{=} SL = λ generates ( u , z ) (u,z) ( u , z ) -trees L [ u , z ] \mathcal{L}[u,z] L [ u , z ] through so-called tree queries , which perform membership queries for values of the data parameters p 1 , … , p m p_1,\ldots,p_m p 1 , … , p m that cover all equivalence classes of ≈ \approx ≈ that satisfy the restriction of z z z . The results of these MQs are then organized into an SDT with leaves labeled accept or reject .
From L [ u , z ] \mathcal{L}[u,z] L [ u , z ] , we can extract registers that must be remembered in the location reached by the prefix u u u as the registers that occur in some guard in L [ u , z ] \mathcal{L}[u,z] L [ u , z ] . Let mem Z ( u ) \operatorname{mem}_{Z}(u) mem Z ( u ) , the set of memorable parameters, denote the set of registers that occur in some guard in L [ u , z ] \mathcal{L}[u,z] L [ u , z ] . Intuitively, if x i x_i x i is a memorable parameter, then the i t h i^{\mathrm{th}} i th data value in u u u will be remembered in the register x i x_i x i in the location reached by u u u . For example, for the SDT in Figure 2 c, after the prefix a ( 0 ) a(0) a ( 0 ) , the register x 1 x_1 x 1 is memorable, and will store the first data value 0 the prefix. For a set Z Z Z of restricted suffixes, define mem Z ( u ) \operatorname{mem}_{Z}(u) mem Z ( u ) as ⋃ z ∈ Z mem z ( u ) \bigcup_{z\in Z}\operatorname{mem}_{z}(u) ⋃ z ∈ Z mem z ( u ) .
For a prefix u u u and restricted suffix z z z whose first action is α \alpha α , let G { z } ( u , α ) \mathcal{G}_{\{z\}}(u,\alpha) G { z } ( u , α ) denote the initial guards in the ( u , z ) (u,z) ( u , z ) -tree L [ u , z ] \mathcal{L}[u,z] L [ u , z ] , with p 1 p_1 p 1 replaced by p p p . Intuitively, since these initial guards are necessary for separating data values that are processed differently by L \mathcal{L} L , they must also appear in any acceptor for L \mathcal{L} L . For a set Z Z Z , let G Z ( u , α ) \mathcal{G}_{Z}(u,\alpha) G Z ( u , α ) denote the set of conjunctions of guards in G { z } ( u , α ) \mathcal{G}_{\{z\}}(u,\alpha) G { z } ( u , α ) for restricted suffixes z ∈ Z z\in Z z ∈ Z whose first action is α \alpha α .
Equivalence. Two ( u , z ) (u,z) ( u , z ) -trees, T T T and T ′ T' T ′ , are equivalent denoted T ≡ T ′ T\equiv T' T ≡ T ′ , if Dom ( T ) = Dom ( T ′ ) \operatorname{Dom}(T)=\operatorname{Dom}(T') Dom ( T ) = Dom ( T ′ ) and T ( g ‾ ) = T ′ ( g ‾ ) T(\overline{g})=T'(\overline{g}) T ( g ) = T ′ ( g ) for each g ‾ ∈ Dom ( T ) \overline{g}\in\operatorname{Dom}(T) g ∈ Dom ( T ) . If γ \gamma γ is a mapping from X \mathcal{X} X to a set of registers, we extend γ \gamma γ to a mapping from X \mathcal{X} X -restricted suffixes and from ( u , z ) (u,z) ( u , z ) -paths in the natural way. For a decision tree T T T , we define γ ( T ) \gamma(T) γ ( T ) as the decision tree defined by Dom ( γ ( T ) ) = { γ ( g ‾ ) : g ‾ ∈ Dom ( T ) } \operatorname{Dom}(\gamma(T))=\{\gamma(\overline{g}):\overline{g}\in\operatorname{Dom}(T)\} Dom ( γ ( T )) = { γ ( g ) : g ∈ Dom ( T )} and γ ( T ) ( γ ( g ‾ ) ) = T ( g ‾ ) \gamma(T)(\gamma(\overline{g}))=T(\overline{g}) γ ( T ) ( γ ( g )) = T ( g ) . For a set Z Z Z of restricted suffixes, let u ≃ γ Z u ′ u\mathrel{\simeq_{\gamma}^{Z}}u' u ≃ γ Z u ′ denote that γ \gamma γ is a bijection from mem Z ( u ) \operatorname{mem}_{Z}(u) mem Z ( u ) to mem γ ( Z ) ( u ′ ) \operatorname{mem}_{\gamma(Z)}(u') mem γ ( Z ) ( u ′ ) such that γ ( L [ u , z ] ) ≡ L [ u ′ , γ ( z ) ] \gamma(\mathcal{L}[u,z])\equiv\mathcal{L}[u',\gamma(z)] γ ( L [ u , z ]) ≡ L [ u ′ , γ ( z )] for each z ∈ Z z\in Z z ∈ Z . Let u ≃ Z u ′ u\mathrel{\simeq_{Z}}u' u ≃ Z u ′ denote that u ≃ γ Z u ′ u\mathrel{\simeq_{\gamma}^{Z}}u' u ≃ γ Z u ′ for some γ \gamma γ . Note that in general, when u ≃ Z u ′ u\mathrel{\simeq_{Z}}u' u ≃ Z u ′ , there can be several such bijections.
Definition 2. We define a data language L \mathcal{L} L to have finite index if it partitions the set of data words into a finite number of equivalence classes w.r.t. ≃ Z \mathrel{\simeq_{Z}} ≃ Z . □ \square □
Here Z \mathcal{Z} Z denotes the set of all restricted suffixes. Definition 2 is a natural generalization of the concept of regular languages to the setting of data languages.
The S L = λ SL_{\mathord{=}}^{\lambda} S L = λ Learning Algorithm
In this section, we present the S L = λ SL_{\mathord{=}}^{\lambda} S L = λ algorithm. Like other AAL algorithms, S L = λ SL_{\mathord{=}}^{\lambda} S L = λ alternates between hypothesis construction and hypothesis validation. During hypothesis construction, MQs are performed to obtain information which is maintained in a classification tree C T CT C T , described in § 4.1 . The information gathering aims to establish a set of closedness and consistency properties of C T CT C T , using rules described in § 4.2 . When these properties have been established, the C T CT C T is used to construct a hypothesis H \mathcal{H} H (§ 4.3 ), which is then validated with an EQ to determine whether H \mathcal{H} H accepts L \mathcal{L} L . If yes, learning concludes and H \mathcal{H} H is returned. If no, the EQ responds with a counterexample , which is then analyzed, as described in § 4.4 , to determine how H \mathcal{H} H can be refined. As a result of the analysis, new information is added to C T CT C T . Thereafter, the rule-based machinery of § 4.2 resumes to re-establish closedness and consistency of C T CT C T , after which a new, refined hypothesis is constructed. This cycle continues until S L = λ SL_{\mathord{=}}^{\lambda} S L = λ constructs a hypothesis which accepts L \mathcal{L} L , which is then returned.
Algorithm 1: Operations on the classification tree
Function Sift ( u , N ) \operatorname{Sift}(u,N) Sift ( u , N ) is
if N N N is a leaf then U ← U [ u ↦ N ] \mathcal{U}\leftarrow\mathcal{U}[u\mapsto N] U ← U [ u ↦ N ]
else
if N N N has child N ′ N' N ′ with rp ( N ′ ) ≃ z ( N ′ ) u \operatorname{rp}(N')\simeq_{z(N')}u rp ( N ′ ) ≃ z ( N ′ ) u then Sift ( u , N ′ ) \operatorname{Sift}(u,N') Sift ( u , N ′ )
else
Create new leaf N n e w N^{new} N n e w as child of N N N with rp ( N n e w ) = u \operatorname{rp}(N^{new})=u rp ( N n e w ) = u
Sift ( u , N n e w ) \operatorname{Sift}(u,N^{new}) Sift ( u , N n e w )
Function Expand ( u ) \operatorname{Expand}(u) Expand ( u ) is
if u ∉ U u\notin U u ∈ / U then Sift ( u , root ( C T ) ) \operatorname{Sift}(u,\operatorname{root}(CT)) Sift ( u , root ( C T ))
S p ← S p ∪ { u } S_p\leftarrow S_p\cup\{u\} S p ← S p ∪ { u }
for α ∈ Σ \alpha\in\Sigma α ∈ Σ do Sift ( u α ( d u g ) , root ( C T ) ) \operatorname{Sift}(u\alpha(d_u^g),\operatorname{root}(CT)) Sift ( uα ( d u g ) , root ( C T )) for each g ∈ G ( u , α ) g\in\mathcal{G}(u,\alpha) g ∈ G ( u , α )
Function Refine ( N , z ) \operatorname{Refine}(N,z) Refine ( N , z ) is
Replace N N N by an inner node N ′ N' N ′ with z ( N ′ ) = z z(N')=z z ( N ′ ) = z and rp ( N ′ ) = rp ( N ) \operatorname{rp}(N')=\operatorname{rp}(N) rp ( N ′ ) = rp ( N )
for u ∈ U − 1 ( N ) u\in\mathcal{U}^{-1}(N) u ∈ U − 1 ( N ) do Sift ( u , N ′ ) \operatorname{Sift}(u,N') Sift ( u , N ′ )
Data Structures
During hypothesis construction, S L = λ SL^\lambda_= S L = λ maintains: (i) a prefix-closed set S p S_p S p of short prefixes , representing locations, (ii) a set of one-symbol extensions of the prefixes in S p S_p S p , representing transitions; we use U U U , called the set of prefixes , to represent the union of S p S_p S p and this set, and (iii) a suffix-closed set Z Z Z of restricted suffixes.
The sets U U U and Z Z Z are maintained in a classification tree C T CT C T , which is designed to represent how the suffixes in Z Z Z partition the set U U U into equivalence classes corresponding to locations. The classification tree is a rooted tree, consisting of nodes connected by edges. Each leaf is labeled by a subset of U U U ; we let U \mathcal{U} U denote the mapping, which maps each prefix u ∈ U u\in U u ∈ U to the classification tree leaf where it is contained. Thus, if N N N is a leaf node, U − 1 ( N ) \mathcal{U}^{-1}(N) U − 1 ( N ) is the set of prefixes labeling N N N . Each node, both inner and leaf node, is labeled by a representative prefix , denoted rp ( N ) \operatorname{rp}(N) rp ( N ) , which is chosen as the prefix that was first labeling N N N . Each inner node of C T CT C T is labeled by a potregs ( rp ( N ) ) \operatorname{potregs}(\operatorname{rp}(N)) potregs ( rp ( N )) -restricted suffix, denoted z ( N ) z(N) z ( N ) . The inverse, i.e., the inner node labeled by a suffix z z z , is denoted N ( z ) N(z) N ( z ) . Figure 3 shows a classification tree which can be generated by S L = λ SL^\lambda_= S L = λ when learning an acceptor for L P ( 3 ) \mathcal{L}_{\mathcal{P}(3)} L P ( 3 ) (such as the one in Figure 1 ). Its leaves correspond (from left to right) to the locations l 4 l_4 l 4 , the sink, l 2 l_2 l 2 , l 1 l_1 l 1 , l 3 l_3 l 3 , and l 0 l_0 l 0 of Figure 1 , respectively.
Figure 3. Classification tree for L P ( 3 ) \mathcal{L}_{P(3)} L P ( 3 ) (accepted by the RA in Figure 1 ). The representative prefix for each leaf is underlined. Each inner node is labeled by its restricted suffix (inside) and representative prefix (above).
The insertion of a new prefix u u u into the classification tree C T CT C T is performed by function Sift \operatorname{Sift} Sift (cf. Algorithm 1). It traverses C T CT C T from the root downwards; from each node N N N it chooses the outgoing branch labeled by the SDT that reflects how suffixes are classified after u u u and remembers how the registers of that SDT correspond to the registers of u u u . This allows to maintain, at each internal node N N N , a mapping denoted ρ u N \rho_u^N ρ u N , from the registers of u u u that have been discovered so far to the corresponding registers of rp ( N ) \operatorname{rp}(N) rp ( N ) . At node N N N , Sift \operatorname{Sift} Sift then constructs the SDT obtained by applying the restricted suffix z ( N ) z(N) z ( N ) to u u u , after first replacing the registers in z ( N ) z(N) z ( N ) by the corresponding ones of u u u using the mapping ( ρ u N ) − 1 (\rho_u^N)^{-1} ( ρ u N ) − 1 , i.e., constructing L [ u , ( ρ u N ) − 1 ( z ( N ) ) ] \mathcal{L}[u,(\rho_u^N)^{-1}(z(N))] L [ u , ( ρ u N ) − 1 ( z ( N ))] . It thereafter checks whether r p ( N ′ ) ≃ Z ( N ′ ) u rp(N') \simeq_{Z(N')} u r p ( N ′ ) ≃ Z ( N ′ ) u for any child N ′ N' N ′ of N N N ; here Z ( N ) Z(N) Z ( N ) denotes the set of suffixes of all ancestors of N N N after remapping their registers to those of r p ( N ) rp(N) r p ( N ) . If so, it continues the traversal at N ′ N' N ′ , otherwise a new child of N N N is created as a leaf N n e w N^{new} N n e w with r p ( N n e w ) = u rp(N^{new}) = u r p ( N n e w ) = u and U \mathcal{U} U is updated to reflect that u u u has been sifted to N n e w N^{new} N n e w . For example, when u = a ( 0 ) a ( 0 ) u = \mathrm{a}(0)\mathrm{a}(0) u = a ( 0 ) a ( 0 ) is sifted into the classification tree in Figure 3 , we find that u ≃ { ϵ } ϵ u \simeq_{\{\epsilon\}} \epsilon u ≃ { ϵ } ϵ , so u u u is sifted to the right child node of the root. Then, u u u is sifted to the left branches of the nodes labeled by z 1 = a ( p 1 ∣ f r e s h ( p 1 ) ) z_1 = \mathrm{a}(p_1|\mathit{fresh}(p_1)) z 1 = a ( p 1 ∣ fresh ( p 1 )) and z 2 = a ( p 1 ∣ u n m a p p e d ( p 1 ) ) z_2 = \mathrm{a}(p_1|\mathit{unmapped}(p_1)) z 2 = a ( p 1 ∣ unmapped ( p 1 )) , since u ≃ { z 1 , z 2 } a ( 0 ) u \simeq_{\{z_1,z_2\}} \mathrm{a}(0) u ≃ { z 1 , z 2 } a ( 0 ) . In z 3 = a ( p 1 ∣ p 1 = x 1 ) a ( p 2 ∣ p 2 = x 1 ) z_3 = \mathrm{a}(p_1|p_1 = x_1)\mathrm{a}(p_2|p_2 = x_1) z 3 = a ( p 1 ∣ p 1 = x 1 ) a ( p 2 ∣ p 2 = x 1 ) , the register x 1 x_1 x 1 refers to a ( 0 ) \mathrm{a}(0) a ( 0 ) , the representative prefix of N ( z 3 ) N(z_3) N ( z 3 ) . Thus, when sifting u u u through N ( z 3 ) N(z_3) N ( z 3 ) , x 1 x_1 x 1 must be mapped to the corresponding register ( ρ u N ( z 3 ) ) − 1 ( x 1 ) (\rho_u^{N(z_3)})^{-1}(x_1) ( ρ u N ( z 3 ) ) − 1 ( x 1 ) of u u u , which, in this case, is also x 1 x_1 x 1 (as revealed by L [ u , z 2 ] \mathcal{L}[u,z_2] L [ u , z 2 ] ). Since u ̸ ≃ { z 3 } a ( 0 ) u \not\simeq_{\{z_3\}} \mathrm{a}(0) u ≃ { z 3 } a ( 0 ) , a new leaf is created for u u u , with u u u as representative prefix.
We note that constructing an SDT for a prefix u u u and restricted suffix z z z often requires that the registers appearing in z z z first be remapped to correspond with those of u u u . To simplify notation, we will henceforth often omit such remappings; this is not a real problem since they can be inferred from the context in C T CT C T . Thus, if u ≃ Z u ′ u \simeq_Z u' u ≃ Z u ′ for some set Z Z Z and z z z is an X X X -restricted suffix, where X X X is a set of registers of u u u , then we can write L [ u ′ , z ] \mathcal{L}[u',z] L [ u ′ , z ] to denote L [ u ′ , γ ( z ) ] \mathcal{L}[u',\gamma(z)] L [ u ′ , γ ( z )] . Furthermore, when applying the restricted suffix z ( N ) z(N) z ( N ) to u u u , since the registers z ( N ) z(N) z ( N ) are those of r p ( N ) rp(N) r p ( N ) , they have to be remapped to those of u u u by ( ρ u N ) − 1 (\rho_u^N)^{-1} ( ρ u N ) − 1 . We will then write L [ u , N ] \mathcal{L}[u,N] L [ u , N ] to denote L [ u , ( ρ u N ) − 1 ( z ( N ) ) ] \mathcal{L}[u,(\rho_u^N)^{-1}(z(N))] L [ u , ( ρ u N ) − 1 ( z ( N ))] . We will also use ρ u \rho_u ρ u as a shorthand for ρ u N \rho_u^N ρ u N when N = U ( u ) N = \mathcal{U}(u) N = U ( u ) .
The Sift function ensures that the prefixes that label a leaf node N N N are all in the same equivalence class of ≃ Z ( N ) \simeq_{Z(N)} ≃ Z ( N ) . When N N N is a leaf node with u ∈ U − 1 ( N ) u \in\mathcal{U}^{-1}(N) u ∈ U − 1 ( N ) we will use Z ( u ) Z(u) Z ( u ) as a shorthand for Z ( U ( u ) ) Z(\mathcal{U}(u)) Z ( U ( u )) . Two prefixes that label different leaves, N N N and N ′ N' N ′ , are guaranteed to be inequivalent, since they are separated by the restricted suffix of lca ( N , N ′ ) \operatorname{lca}(N,N') lca ( N , N ′ ) , where lca ( N , N ′ ) \operatorname{lca}(N,N') lca ( N , N ′ ) is the lowest common ancestor node of N N N and N ′ N' N ′ . We will also use G ( u , α ) \mathcal{G}(u,\alpha) G ( u , α ) as a shorthand for G Z ( u ) ( u , α ) \mathcal{G}_{Z(u)}(u,\alpha) G Z ( u ) ( u , α ) .
The Core Algorithm
The core of the S L ≡ λ \mathrm{SL}^{\lambda}_{\equiv} SL ≡ λ algorithm, shown in Algorithm 2, initializes the classification tree to consist of one root node, for the empty suffix (which classifies words as accepted or rejected); U \mathcal{U} U and S p S_p S p are empty (line 1). It then sifts the empty prefix ϵ \epsilon ϵ , thereby entering it into U \mathcal{U} U (line 2). Thereafter, Algorithm 2 repeats the main loop in which C T CT C T is checked for a number of properties that must be satisfied. These properties fall into two categories; closedness and consistency . Closedness properties ensure that new prefixes are added to C T CT C T when new locations and transitions are detected, and that registers are maintained in transitions. Let us describe the actions of Algorithm 2 for location and transition closedness; the description of Register Closedness appears later, after the consistency properties. Location Closedness is satisfied if each leaf contains a short prefix in S p S_p S p . Whenever a leaf N N N does not contain a short prefix in S p S_p S p (line 4), one of its prefixes u u u is chosen for inclusion in S p S_p S p by calling Expand ( u ) (u) ( u ) (defined in Algorithm 1), which makes u u u a short prefix, and for each initial guard g ∈ G ( u , α ) g \in\mathcal{G}(u,\alpha) g ∈ G ( u , α ) forms one-symbol extensions of form u α ( d u g ) u\alpha(d_u^g) uα ( d u g ) , which are entered into C T CT C T by sifting.
Transition Closedness is satisfied if for each short prefix u u u , action α \alpha α , and initial guard g ∈ G ( u , α ) g \in\mathcal{G}(u,\alpha) g ∈ G ( u , α ) , the extension u α ( d u g ) u\alpha(d_u^g) uα ( d u g ) , using the representative data value d u g d_u^g d u g , is in U U U . If not satisfied, the missing u α ( d u g ) u\alpha(d_u^g) uα ( d u g ) is added to U U U by sifting (lines 6-7).
Let us now describe the consistency properties, which ensure that transitions and register assignments are consistent across C T CT C T . For example, a leaf may contain multiple short prefixes with one-symbol extensions that are inequivalent, thereby violating location consistency Such a leaf must be split when a suffix which separates the two short prefixes can be formed. Similarly, a leaf may contain multiple inequivalent one-symbol extensions satisfying the same guard thereby violating transition consistency, which necessitates splitting the guard by a separating suffix. Splitting is performed by the function Refine , shown in Algorithm 1, which takes a leaf node N N N and a restricted suffix z z z . Refine replaces N N N by a new node N ′ N' N ′ labeled by z z z (line 13 of Algorithm 1) and sifts each prefix u u u in N N N ; this results in one or several of the following: (i) splitting N N N into several equivalence classes which become children of N ′ N' N ′ , (ii) refining the initial guards of N N N , (iii) extending the set of registers in the location represented by N N N , or (iv) reducing the set of symmetries between registers in that location. Before calling Refine , the suffix z z z is restricted as much as possible to limit the number of incurred MQs. We introduce the function Prune which, given two SDTs T 1 T_1 T 1 and T 2 T_2 T 2 , returns a path that separates them, i.e., a path g ˉ = g ˉ 1 ∧ g ˉ 2 \bar{g} = \bar{g}_1 \land\bar{g}_2 g ˉ = g ˉ 1 ∧ g ˉ 2 , with g ˉ 1 ∈ Dom ( T 1 ) \bar{g}_1 \in\operatorname{Dom}(T_1) g ˉ 1 ∈ Dom ( T 1 ) and g ˉ 2 ∈ Dom ( T 2 ) \bar{g}_2 \in\operatorname{Dom}(T_2) g ˉ 2 ∈ Dom ( T 2 ) , such that g ˉ 1 ∧ g ˉ 2 \bar{g}_1 \land\bar{g}_2 g ˉ 1 ∧ g ˉ 2 is satisfiable and T 1 ( g ˉ 1 ) ≠ T 2 ( g ˉ 2 ) T_1(\bar{g}_1) \ne T_2(\bar{g}_2) T 1 ( g ˉ 1 ) = T 2 ( g ˉ 2 ) . Let ∩ \cap ∩ be an operator such that z ∩ g ˉ z \cap\bar{g} z ∩ g ˉ combines a restricted suffix z = α 1 ( p 1 ∣ φ 1 ) ⋯ α m ( p m ∣ φ m ) z = \alpha_1(p_1 \mid\varphi_1) \cdots\alpha_m(p_m \mid\varphi_m) z = α 1 ( p 1 ∣ φ 1 ) ⋯ α m ( p m ∣ φ m ) with the path g ˉ = g 1 ⋯ g m \bar{g} = g_1 \cdots g_m g ˉ = g 1 ⋯ g m to form the restricted suffix α 1 ( p 1 ∣ φ 1 ∧ g 1 ) ⋯ α m ( p m ∣ φ m ∧ g m ) \alpha_1(p_1 \mid\varphi_1 \land g_1) \cdots\alpha_m(p_m \mid\varphi_m \land g_m) α 1 ( p 1 ∣ φ 1 ∧ g 1 ) ⋯ α m ( p m ∣ φ m ∧ g m ) . Finally, we let α ( p 1 ∣ φ α ) ⋅ z \alpha(p_1 \mid\varphi_\alpha) \cdot z α ( p 1 ∣ φ α ) ⋅ z denote the restricted suffix z z z prepended by the symbol α ( p 1 ∣ φ α ) \alpha(p_1 \mid\varphi_\alpha) α ( p 1 ∣ φ α ) . We can now describe the actions for location and transition consistency.
Algorithm 2: The S L λ SL^{\lambda} S L λ Algorithm for Learning Register Automata
Initialize C T CT C T as root node r o o t ( C T ) root(CT) r oo t ( C T ) with suffix ϵ \epsilon ϵ and U ← ∅ U \leftarrow\emptyset U ← ∅ , S p ← ∅ S_p \leftarrow\emptyset S p ← ∅
S i f t ( ϵ , r o o t ( C T ) ) Sift(\epsilon, root(CT)) S i f t ( ϵ , r oo t ( C T ))
HYP: repeat ▷ Check closedness
if exists leaf N N N for which U − 1 ( N ) ∩ S p = ∅ U^{-1}(N) \cap S_p = \emptyset U − 1 ( N ) ∩ S p = ∅ then // location
E x p a n d ( u ) Expand(u) E x p an d ( u ) for some u ∈ U − 1 ( N ) u \in U^{-1}(N) u ∈ U − 1 ( N )
if u ∈ S p u \in S_p u ∈ S p and g ∈ G ( u , α ) g \in G(u,\alpha) g ∈ G ( u , α ) but u α ( d u g ) ∉ U u\alpha(d_u^g) \notin U uα ( d u g ) ∈ / U then // transition
S i f t ( u α ( d u g ) , r o o t ( C T ) ) Sift(u\alpha(d_u^g), root(CT)) S i f t ( uα ( d u g ) , r oo t ( C T ))
if m e m { z } ( u α ( d ) ) ⊈ m e m Z ( u ) ( u ) ∪ { x ∣ u ∣ + 1 } mem_{\{z\}}(u\alpha(d)) \not\subseteq mem_{Z(u)}(u)\cup\{x_{|u|+1}\} m e m { z } ( uα ( d )) ⊆ m e m Z ( u ) ( u ) ∪ { x ∣ u ∣ + 1 } for some z ∈ Z ( u α ( d ) ) z \in Z(u\alpha(d)) z ∈ Z ( uα ( d )) then // register
R e f i n e ( U ( u ) , α ( p 1 ∣ ϕ α ) ⋅ z ) Refine(U(u),\alpha(p_1\mid\phi_\alpha)\cdot z) R e f in e ( U ( u ) , α ( p 1 ∣ ϕ α ) ⋅ z ) where ϕ α \phi_\alpha ϕ α is if d = d u t r u e d=d_u^{true} d = d u t r u e then f r e s h ( p 1 ) fresh(p_1) f r es h ( p 1 ) elif d = μ u ( x l ) d=\mu_u(x_l) d = μ u ( x l ) then p 1 = x l p_1=x_l p 1 = x l else u n m a p p e d ( p 1 ) unmapped(p_1) u nma pp e d ( p 1 ) ▷ Check consistency
if u , u ′ ∈ U − 1 ( N ) ∩ S p u,u' \in U^{-1}(N)\cap S_p u , u ′ ∈ U − 1 ( N ) ∩ S p with u ≃ Z ( N ) u ′ u \simeq_{Z(N)} u' u ≃ Z ( N ) u ′ for leaf N N N with U ( u α ( d u g ) ) ≠ U ( u ′ α ( d u ′ γ ( g ) ) ) U(u\alpha(d_u^g))\ne U(u'\alpha(d_{u'}^{\gamma(g)})) U ( uα ( d u g )) = U ( u ′ α ( d u ′ γ ( g ) )) where g ∈ G ( u , α ) g\in G(u,\alpha) g ∈ G ( u , α ) and γ ( g ) ∈ G ( u ′ , α ) \gamma(g)\in G(u',\alpha) γ ( g ) ∈ G ( u ′ , α ) then // location
R e f i n e ( N , α ( p 1 ∣ ϕ α ) ⋅ ( z ( N ′ ) ∩ P r u n e ( L [ u α ( d u g ) , N ′ ] , L [ u ′ α ( d u ′ γ ( g ) ) , N ′ ] ) ) ) Refine(N,\alpha(p_1\mid\phi_\alpha)\cdot(z(N')\cap Prune(\mathcal{L}[u\alpha(d_u^g),N'],\mathcal{L}[u'\alpha(d_{u'}^{\gamma(g)}),N']))) R e f in e ( N , α ( p 1 ∣ ϕ α ) ⋅ ( z ( N ′ ) ∩ P r u n e ( L [ uα ( d u g ) , N ′ ] , L [ u ′ α ( d u ′ γ ( g ) ) , N ′ ])))
where N ′ = l c a ( u α ( d u g ) , u ′ α ( d u ′ γ ( g ) ) ) N'=lca(u\alpha(d_u^g),u'\alpha(d_{u'}^{\gamma(g)})) N ′ = l c a ( uα ( d u g ) , u ′ α ( d u ′ γ ( g ) )) and
ϕ α \phi_\alpha ϕ α is if g g g is p 1 = x l p_1=x_l p 1 = x l then p 1 = x l p_1=x_l p 1 = x l else f r e s h ( p 1 ) fresh(p_1) f r es h ( p 1 )
if U ( u α ( d ) ) ≠ U ( u α ( d u t r u e ) ) U(u\alpha(d))\ne U(u\alpha(d_u^{true})) U ( uα ( d )) = U ( uα ( d u t r u e )) with d ≠ d u g d\ne d_u^g d = d u g for all g ∈ G ( u , α ) g\in G(u,\alpha) g ∈ G ( u , α ) then // transition(a)
R e f i n e ( U ( u ) , α ( p 1 ∣ ϕ α ) ⋅ ( z ( N ′ ) ∩ P r u n e ( L [ u α ( d ) , N ′ ] , L [ u α ( d u t r u e ) , N ′ ] ) ) ) Refine(U(u),\alpha(p_1\mid\phi_\alpha)\cdot(z(N')\cap Prune(\mathcal{L}[u\alpha(d),N'],\mathcal{L}[u\alpha(d_u^{true}),N']))) R e f in e ( U ( u ) , α ( p 1 ∣ ϕ α ) ⋅ ( z ( N ′ ) ∩ P r u n e ( L [ uα ( d ) , N ′ ] , L [ uα ( d u t r u e ) , N ′ ])))
where N ′ = l c a ( u α ( d ) , u α ( d u t r u e ) ) N'=lca(u\alpha(d),u\alpha(d_u^{true})) N ′ = l c a ( uα ( d ) , uα ( d u t r u e )) and
ϕ α \phi_\alpha ϕ α is if d = μ u ( x l ) d=\mu_u(x_l) d = μ u ( x l ) then ( f r e s h ( p 1 ) ∨ p 1 = x l ) (fresh(p_1)\lor p_1=x_l) ( f r es h ( p 1 ) ∨ p 1 = x l ) else u n m a p p e d ( p 1 ) unmapped(p_1) u nma pp e d ( p 1 )
if U ( u α ( d ) ) = U ( u α ( d u t r u e ) ) U(u\alpha(d))=U(u\alpha(d_u^{true})) U ( uα ( d )) = U ( uα ( d u t r u e )) with d ≠ d u g d\ne d_u^g d = d u g for all g ∈ G ( u , α ) g\in G(u,\alpha) g ∈ G ( u , α ) but u α ( d u t r u e ) ̸ ≃ { z } u α ( d ) u\alpha(d_u^{true})\not\simeq_{\{z\}}u\alpha(d) uα ( d u t r u e ) ≃ { z } uα ( d ) for some z ∈ Z ( u α ( d ) ) z\in Z(u\alpha(d)) z ∈ Z ( uα ( d )) then // transition(b)
R e f i n e ( U ( u ) , α ( p 1 ∣ ϕ α ) ⋅ ( z ∩ P r u n e ( L [ u α ( d ) , N ( z ) ] , L [ u α ( d u t r u e ) , N ( z ) ] ) ) ) Refine(U(u),\alpha(p_1\mid\phi_\alpha)\cdot(z\cap Prune(\mathcal{L}[u\alpha(d),N(z)],\mathcal{L}[u\alpha(d_u^{true}),N(z)]))) R e f in e ( U ( u ) , α ( p 1 ∣ ϕ α ) ⋅ ( z ∩ P r u n e ( L [ uα ( d ) , N ( z )] , L [ uα ( d u t r u e ) , N ( z )])))
where ϕ α \phi_\alpha ϕ α is if d = μ u ( x l ) d=\mu_u(x_l) d = μ u ( x l ) then ( f r e s h ( p 1 ) ∨ p 1 = x l ) (fresh(p_1)\lor p_1=x_l) ( f r es h ( p 1 ) ∨ p 1 = x l ) else u n m a p p e d ( p 1 ) unmapped(p_1) u nma pp e d ( p 1 )
if u ≃ Z ( u ) u u\simeq_{Z(u)}u u ≃ Z ( u ) u but u α ( d ) ̸ ≃ Z ( u α ( d ) ) [ x ∣ u ∣ + 1 ↦ x ∣ u ∣ + 1 ] ∘ γ u α ( d ) u\alpha(d)\not\simeq_{Z(u\alpha(d))}^{[x_{|u|+1}\mapsto x_{|u|+1}]\circ\gamma}u\alpha(d) uα ( d ) ≃ Z ( uα ( d )) [ x ∣ u ∣ + 1 ↦ x ∣ u ∣ + 1 ] ∘ γ uα ( d ) then // register
R e f i n e ( U ( u ) , α ( p 1 ∣ ϕ α ) ⋅ ( z ( N ) ∩ P r u n e ( L [ u α ( d ) , N ] , γ ( L [ u α ( d ) , N ] ) ) ) ) Refine(U(u),\alpha(p_1\mid\phi_\alpha)\cdot(z(N)\cap Prune(\mathcal{L}[u\alpha(d),N],\gamma(\mathcal{L}[u\alpha(d),N])))) R e f in e ( U ( u ) , α ( p 1 ∣ ϕ α ) ⋅ ( z ( N ) ∩ P r u n e ( L [ uα ( d ) , N ] , γ ( L [ uα ( d ) , N ]))))
where N = U ( u α ( d ) ) N=U(u\alpha(d)) N = U ( uα ( d )) and ϕ α \phi_\alpha ϕ α is if d = d u t r u e d=d_u^{true} d = d u t r u e then f r e s h ( p 1 ) fresh(p_1) f r es h ( p 1 ) elif d = μ u ( x l ) d=\mu_u(x_l) d = μ u ( x l ) then p 1 = x l p_1=x_l p 1 = x l else u n m a p p e d ( p 1 ) unmapped(p_1) u nma pp e d ( p 1 )
until closed and consistent
H ← H y p o t h e s i s ( C T ) H \leftarrow Hypothesis(CT) H ← H y p o t h es i s ( C T )
if ∃ w ∈ Σ + \exists w\in\Sigma^+ ∃ w ∈ Σ + s.t. H ( w ) ≠ L ( w ) H(w)\ne L(w) H ( w ) = L ( w ) then { A n a l y z e ( w ) ; g o t o H Y P } \{Analyze(w); goto\ HYP\} { A na l y z e ( w ) ; g o t o H Y P } else return H H H
L o c a t i o n C o n s i s t e n c y Location\ Consistency L oc a t i o n C o n s i s t e n cy is satisfied if all short prefixes in the same leaf N N N have equivalent one-symbol extensions. If this property is not satisfied, i.e., for two short prefixes u u u , u ′ u' u ′ in N N N we have U ( u α ( d u g ) ) ≠ U ( u ′ α ( d u ′ γ ( g ) ) ) U(u\alpha(d_u^g))\ne U(u'\alpha(d_{u'}^{\gamma(g)})) U ( uα ( d u g )) = U ( u ′ α ( d u ′ γ ( g ) )) where g ∈ G ( u , α ) g\in G(u,\alpha) g ∈ G ( u , α ) and γ ( g ) ∈ G ( u ′ , α ) \gamma(g)\in G(u',\alpha) γ ( g ) ∈ G ( u ′ , α ) are equivalent guards (line 10), then the leaf N N N must be split by a suitable atomic suffix z ′ z' z ′ . This is done as follows. Let N ′ = l c a ( u α ( d u g ) , u ′ α ( d u ′ γ ( g ) ) ) N'=lca(u\alpha(d_u^g),u'\alpha(d_{u'}^{\gamma(g)})) N ′ = l c a ( uα ( d u g ) , u ′ α ( d u ′ γ ( g ) )) be the node whose suffix z ( N ′ ) z(N') z ( N ′ ) separates the two extended prefixes; then P r u n e ( L [ u α ( d u g ) , N ′ ] , L [ u ′ α ( d u ′ γ ( g ) ) , N ′ ] ) Prune(\mathcal{L}[u\alpha(d_u^g),N'],\mathcal{L}[u'\alpha(d_{u'}^{\gamma(g)}),N']) P r u n e ( L [ uα ( d u g ) , N ′ ] , L [ u ′ α ( d u ′ γ ( g ) ) , N ′ ]) extracts a path g ˉ \bar{g} g ˉ which separates them. The path g ˉ \bar{g} g ˉ is used to strengthen the restrictions of z ( N ′ ) z(N') z ( N ′ ) into z ( N ′ ) ∩ g ˉ z(N')\cap\bar{g} z ( N ′ ) ∩ g ˉ , which always results in an atomic suffix, which is then prepended by a symbol α ( p 1 ∣ ϕ α ) \alpha(p_1\mid\phi_\alpha) α ( p 1 ∣ ϕ α ) to form the sought restricted suffix z ′ z' z ′ ; here ϕ α \phi_\alpha ϕ α is chosen to reflect the guard g g g , i.e., if g g g is an equality guard p = x l p=x_l p = x l then ϕ α \phi_\alpha ϕ α is p 1 = x l p_1=x_l p 1 = x l , otherwise (if g g g is an else-guard) ϕ α \phi_\alpha ϕ α is fresh ( p 1 ) \operatorname{fresh}(p_1) fresh ( p 1 ) . Finally, the leaf N N N is split by a call R e f i n e ( N , z ′ ) \mathit{Refine}(N,z') Refine ( N , z ′ ) (line 11). We illustrate by the example in Figure 4 with u = a ( 0 ) u=\mathrm{a}(0) u = a ( 0 ) and u ′ = a ( 0 ) a ( 0 ) u'=\mathrm{a}(0)\mathrm{a}(0) u ′ = a ( 0 ) a ( 0 ) (shown in blue and teal , respectively). Their extensions u a ( 0 ) u\mathrm{a}(0) u a ( 0 ) and u ′ a ( 0 ) u'\mathrm{a}(0) u ′ a ( 0 ) are inequivalent, separated by the suffix a ( p 1 ∣ unmapped ( p 1 ) ) \mathrm{a}(p_1\mid\operatorname{unmapped}(p_1)) a ( p 1 ∣ unmapped ( p 1 )) . From their corresponding SDTs, P r u n e \mathit{Prune} Prune extracts the path p 1 = x 1 p_1=x_1 p 1 = x 1 which leads to accept for u u u and to reject for u ′ u' u ′ . This path is used to refine a ( p 1 ∣ unmapped ( p 1 ) ) \mathrm{a}(p_1\mid\operatorname{unmapped}(p_1)) a ( p 1 ∣ unmapped ( p 1 )) to a ( p 1 ∣ p 1 = x 1 ) \mathrm{a}(p_1\mid p_1=x_1) a ( p 1 ∣ p 1 = x 1 ) , to which we prepend a ( p 1 ∣ p 1 = x 1 ) \mathrm{a}(p_1\mid p_1=x_1) a ( p 1 ∣ p 1 = x 1 ) , since the one-symbol extensions of u u u and u ′ u' u ′ are performed using the equality guard p = x 1 p=x_1 p = x 1 , resulting in the atomic suffix z ′ = a ( p 1 ∣ p 1 = x 1 ) a ( p 2 ∣ p 2 = x 1 ) z'=\mathrm{a}(p_1\mid p_1=x_1)\mathrm{a}(p_2\mid p_2=x_1) z ′ = a ( p 1 ∣ p 1 = x 1 ) a ( p 2 ∣ p 2 = x 1 ) . The call R e f i n e ( N , z ′ ) \mathit{Refine}(N,z') Refine ( N , z ′ ) will split the leaf of a ( 0 ) \mathrm{a}(0) a ( 0 ) into two leaves: one for a ( 0 ) \mathrm{a}(0) a ( 0 ) and one for a ( 0 ) a ( 0 ) \mathrm{a}(0)\mathrm{a}(0) a ( 0 ) a ( 0 ) , as in Figure 3 .
Figure 4. Illustration of location consistency using an intermediate classification tree for the acceptor in Figure 1 .
Transition Consistency is satisfied if for each short prefix u u u and action α \alpha α , there is a one-to-one correspondence between one-symbol extensions u α ( d ) ∈ U u\alpha(d)\in U uα ( d ) ∈ U and guards g ∈ G ( u , α ) g\in\mathcal{G}(u,\alpha) g ∈ G ( u , α ) . If transition consistency is not satisfied, then there is an extension u α ( d ) u\alpha(d) uα ( d ) such that d d d is not representative for any guard in G ( u , α ) \mathcal{G}(u,\alpha) G ( u , α ) ; this implies that d d d is the l t h l^{\mathit{th}} l th data value in u u u for some l l l , but we have not yet applied a suffix z ′ z' z ′ such that L [ u , z ′ ] L[u,z'] L [ u , z ′ ] has an initial guard p 1 = x l p_1=x_l p 1 = x l . Transition Consistency comes in two versions: (i) transition(a) where u α ( d ) u\alpha(d) uα ( d ) and u α ( d u t r u e ) u\alpha(d_u^{\mathit{true}}) uα ( d u true ) appear in different leaves (line 14), and (ii) transition(b) where u α ( d ) u\alpha(d) uα ( d ) and u α ( d u t r u e ) u\alpha(d_u^{\mathit{true}}) uα ( d u true ) appear in the same leaf but are not equivalent under the identity mapping i d \mathbf{id} id between registers (line 18). In both cases, the new guard is found by adding a suffix z ′ z' z ′ to U ( u ) U(u) U ( u ) , formed by prepending a symbol α ( p 1 ∣ ϕ α ) \alpha(p_1\mid\phi_\alpha) α ( p 1 ∣ ϕ α ) to a suffix z z z , made atomic analogously to location consistency, that reveals the inconsistency. In contrast to location consistency, the suffix z ′ z' z ′ is not atomic; if d d d is equal to a memorable data value of u u u , then the suffix z ′ z' z ′ will incur two MQs during sifting; else it will incur ( k + 1 ) (k+1) ( k + 1 ) MQs, where k k k is the number of unmapped data values in u u u .
Register Consistency For some short prefix u u u with memorable values mem Z ( u ) ( u ) \operatorname{mem}_{Z(u)}(u) mem Z ( u ) ( u ) , there may be symmetries in L [ u , z ] \mathcal{L}[u,z] L [ u , z ] for some z ∈ Z ( u ) z\in Z(u) z ∈ Z ( u ) , i.e., for some nontrivial permutation γ \gamma γ on mem Z ( u ) ( u ) \operatorname{mem}_{Z(u)}(u) mem Z ( u ) ( u ) we have u ≅ Z ( u ) γ u u\cong^{\gamma}_{Z(u)}u u ≅ Z ( u ) γ u . It may be that this symmetry does not exist in the canonical acceptor for L \mathcal{L} L , but we did not yet add a suffix that disproves it. Register consistency checks for the existence of such suffixes by comparing symmetries in u u u and its continuations u α ( d ) u\alpha(d) uα ( d ) . If γ \gamma γ is a symmetry on memorable data values of u u u , but not on those of an extension u α ( d ) u\alpha(d) uα ( d ) (line 21), we construct a suffix that breaks the symmetry γ \gamma γ also for u u u (line 23).
Finally, let us now describe the register closedness property.
Register Closedness is satisfied if each register x l x_l x l that is memorable for a one-symbol extension u α ( d ) u\alpha(d) uα ( d ) of a short prefix u u u is also memorable for u u u . Register closedness allows us to correlate registers of u u u and u α ( d ) u\alpha(d) uα ( d ) , even if u u u and u α ( d ) u\alpha(d) uα ( d ) are in different leaves. If this property is not satisfied (line 8), a suffix z ∈ Z ( u α ( d ) ) z \in Z(u\alpha(d)) z ∈ Z ( uα ( d )) that reveals a missing register is prepended by a symbol α ( p 1 ∣ φ α ) \alpha(p_1\mid\varphi_\alpha) α ( p 1 ∣ φ α ) and added to Z ( u ) Z(u) Z ( u ) with a call to R e f i n e ( U ( u ) , α ( p 1 ∣ φ α ) ⋅ z ) Refine(U(u),\alpha(p_1\mid\varphi_\alpha)\cdot z) R e f in e ( U ( u ) , α ( p 1 ∣ φ α ) ⋅ z ) . The restriction φ α \varphi_\alpha φ α is chosen according to the relation between d d d and data values of u u u , i.e., if d d d is fresh then φ α \varphi_\alpha φ α is f r e s h ( p 1 ) fresh(p_1) f r es h ( p 1 ) , if d = μ u ( x l ) d=\mu_u(x_l) d = μ u ( x l ) where x l x_l x l is a memorable register of u u u then φ α \varphi_\alpha φ α is p 1 = x l p_1=x_l p 1 = x l , otherwise (if d d d is unmapped in u u u ) φ α \varphi_\alpha φ α is u n m a p p e d ( p 1 ) unmapped(p_1) u nma pp e d ( p 1 ) .
Hypothesis Construction
We can construct a hypothesis from a closed and consistent classification tree. Location closedness ensures that every short prefix corresponds to a location; transition closedness ensures that every extended prefix corresponds to a transition; register closedness ensures that registers exist for all memorable data values in relevant locations. Location consistency, transition consistency, and register consistency ensure that we can construct a unique deterministic register automaton even though there may exist multiple short prefixes for one location and symmetries between memorable data values.
Definition 3 (Hypothesis). Let C T CT C T be a closed and consistent classification tree. Then the hypothesis automaton H ( C T ) \mathcal{H}(CT) H ( C T ) is the RA ( L , l 0 , X , Γ , λ ) (L,l_0,\mathcal{X},\Gamma,\lambda) ( L , l 0 , X , Γ , λ ) , where
L L L is the set of leaves of C T CT C T , and l 0 l_0 l 0 is the leaf containing the empty prefix ϵ \epsilon ϵ ,
X \mathcal{X} X maps each location l ∈ L l \in L l ∈ L to m e m Z ( u ) ( u ) mem_{Z(u)}(u) m e m Z ( u ) ( u ) ; here and below we let u u u be r p ( l ) rp(l) r p ( l ) ,
λ ( l ) = + \lambda(l)=+ λ ( l ) = + if the leaf l l l is in the accepting subtree of the root, else λ ( l ) = − \lambda(l)=- λ ( l ) = − ,
for each location l l l , each action α \alpha α , and guard g g g in G Z ( u ) ( u , α ) \mathcal{G}_{Z(u)}(u,\alpha) G Z ( u ) ( u , α ) , there is a transition ⟨ l , α ( p ) , g , π , l ′ ⟩ \langle l,\alpha(p),g,\pi,l'\rangle ⟨ l , α ( p ) , g , π , l ′ ⟩ , where
l ′ = U ( u α ( d u g ) ) l'=\mathcal{U}(u\alpha(d_u^g)) l ′ = U ( uα ( d u g )) is the target location; let u ′ u' u ′ be r p ( l ′ ) rp(l') r p ( l ′ ) , and
π : m e m Z ( u ′ ) ( u ′ ) → ( m e m Z ( u ) ( u ) ∪ { p } ) \pi:mem_{Z(u')}(u')\to(mem_{Z(u)}(u)\cup\{p\}) π : m e m Z ( u ′ ) ( u ′ ) → ( m e m Z ( u ) ( u ) ∪ { p }) is defined as [ x ∣ u ∣ + 1 ↦ p ] ∘ γ − 1 [x_{|u|+1}\mapsto p]\circ\gamma^{-1} [ x ∣ u ∣ + 1 ↦ p ] ∘ γ − 1 for some γ \gamma γ with u α ( d u g ) ∼ Z ( u α ( d u g ) ) u ′ u\alpha(d_u^g)\sim_{Z(u\alpha(d_u^g))}u' uα ( d u g ) ∼ Z ( uα ( d u g )) u ′ .
Counterexample Analysis
When an equivalence query returns a counterexample w w w over which H \mathcal{H} H has a misclassifying initialized run
⟨ l 0 , μ 0 ⟩ → α 1 ( d 1 ) ⟨ l 1 , μ 1 ⟩ ⋯ ⟨ l n − 1 , μ n − 1 ⟩ → α n ( d n ) ⟨ l n , μ n ⟩ \langle l_0,\mu_0\rangle\xrightarrow{\alpha_1(d_1)} \langle l_1,\mu_1\rangle\ \cdots\ \langle l_{n-1},\mu_{n-1}\rangle\xrightarrow{\alpha_n(d_n)} \langle l_n,\mu_n\rangle ⟨ l 0 , μ 0 ⟩ α 1 ( d 1 ) ⟨ l 1 , μ 1 ⟩ ⋯ ⟨ l n − 1 , μ n − 1 ⟩ α n ( d n ) ⟨ l n , μ n ⟩
Algorithm 3: Analyze Counterexample
1 Function Analyze(w) where w = α(d₁) ··· α(dₙ) is
2 Let ⟨l₀, μ₀⟩ \xrightarrow{α₁(d₁)} ⟨l₁, μ₁⟩ ··· ⟨lₙ₋₁, μₙ₋₁⟩ \xrightarrow{αₙ(dₙ)} ⟨lₙ, μₙ⟩ be a misclassifying run
3 for n ≥ i ≥ 1 do
4 Let ⟨lᵢ₋₁, αᵢ(p), gᵢ, πᵢ, lᵢ⟩ be a transition inducing ⟨lᵢ₋₁, μᵢ₋₁⟩ \xrightarrow{αᵢ(dᵢ)} ⟨lᵢ, μᵢ⟩
(implying that μᵢ₋₁ ⊨ gᵢ[dᵢ/p] and rp(lᵢ₋₁)αᵢ(dᵣₚ(lᵢ₋₁)) ∈ U⁻¹(lᵢ))
5 forall uᵢ₋₁ ∈ (U⁻¹(lᵢ₋₁) ∩ Sₚ) do
6 forall l ∈ potmatch(w₁:ᵢ₋₁, dᵢ, uᵢ₋₁, μᵢ₋₁ ◦ ρᵤᵢ₋₁) s.t. dᵢ′ = μᵤᵢ₋₁(xₗ) and
zᵢ = potsuff(w₁:ᵢ, wᵢ₊₁:ₙ, uᵢ₋₁αᵢ(dᵢ′), [x|uᵢ₋₁|+1 ↦ wᵢ] ◦ μᵢ₋₁ ◦ ρᵤᵢ₋₁)
implies uᵢ₋₁αᵢ(dᵢ′) ≄_{zᵢ} uᵢ₋₁αᵢ(dᵤᵢ₋₁ᵢᵗʳᵘᵉ) do
7 Sift(uᵢ₋₁αᵢ(dᵢ′), root(CT)); return
8 forall dᵢ′ with lᵢ = U(uᵢ₋₁αᵢ(dᵢ′)) do
9 if there is no uᵢ ∈ (U⁻¹(lᵢ) ∩ Sₚ) s.t. uᵢ₋₁αᵢ(dᵢ′) ≃_{zᵢ} uᵢ where
zᵢ = potsuff(w₁:ᵢ, wᵢ₊₁:ₙ, uᵢ₋₁αᵢ(dᵢ′), [x|uᵢ₋₁|+1 ↦ wᵢ] ◦ μᵢ₋₁ ◦ ρᵤᵢ₋₁)
for some ρ̂ᵢ which agrees with ρᵤᵢ₋₁αᵢ(dᵢ′) ◦ (ρᵤᵢ)⁻¹ on the
intersection of their domains then
10 Expand(uᵢ₋₁αᵢ(dᵢ′)); return
we process it as shown in Algorithm 3. Since each leaf can contain several short prefixes, the above run corresponds to several possible sequences of short prefixes, u 0 , u 1 , … , u n u_0, u_1, \ldots, u_n u 0 , u 1 , … , u n , with l i = U ( u i ) l_i = U(u_i) l i = U ( u i ) for i = 0 , … , n i = 0, \ldots, n i = 0 , … , n . Algorithm 3 analyzes the i i i th transition in each such sequence; it is of form ⟨ l i − 1 , μ i − 1 ⟩ → α i ( d i ) ⟨ l i , μ i ⟩ \langle l_{i-1}, \mu_{i-1}\rangle\xrightarrow{\alpha_i(d_i)} \langle l_i, \mu_i\rangle ⟨ l i − 1 , μ i − 1 ⟩ α i ( d i ) ⟨ l i , μ i ⟩ and corresponds to the one-symbol extension r p ( l i − 1 ) α i ( d r p ( l i − 1 ) g i ) rp(l_{i-1})\alpha_i(d_{rp(l_{i-1})}^{g_i}) r p ( l i − 1 ) α i ( d r p ( l i − 1 ) g i ) in C T CT C T . Its objective is to find, for some index i i i from n n n down to 1, a one-symbol extension u i − 1 α i ( d i ′ ) u_{i-1}\alpha_i(d_i') u i − 1 α i ( d i ′ ) of a short prefix u i − 1 ∈ U − 1 ( l i − 1 ) u_{i-1} \in U^{-1}(l_{i-1}) u i − 1 ∈ U − 1 ( l i − 1 ) , which either (i) is new (not yet in U U U ) and inequivalent to u i − 1 α i ( d u i − 1 t r u e ) u_{i-1}\alpha_i(d_{u_{i-1}}^{\mathrm{true}}) u i − 1 α i ( d u i − 1 true ) , or (ii) is in l i l_i l i but inequivalent to all short prefixes in l i l_i l i . In both cases, “inequivalent” will be shown using a restricted suffix z i z_i z i which “covers” the suffix w i + 1 : n w_{i+1:n} w i + 1 : n of the counterexample. In Algorithm 3, the function p o t m a t c h ( w 1 : i − 1 , d i , u i − 1 , μ i − 1 ∘ ρ u i − 1 ) potmatch(w_{1:i-1}, d_i, u_{i-1}, \mu_{i-1} \circ\rho_{u_{i-1}}) p o t ma t c h ( w 1 : i − 1 , d i , u i − 1 , μ i − 1 ∘ ρ u i − 1 ) at line 6 returns the set of positions in u i − 1 u_{i-1} u i − 1 whose data values can match the i i i th data value d i d_i d i in the counterexample. Similarly, the function p o t s u f f ( w 1 : i , w i + 1 : n , u i − 1 α i ( d i ′ ) , [ x ∣ u i − 1 ∣ + 1 ↦ w i ] ∘ μ i − 1 ∘ ρ u i − 1 ) potsuff(w_{1:i}, w_{i+1:n}, u_{i-1}\alpha_i(d_i'), [x_{|u_{i-1}|+1} \mapsto w_i] \circ\mu_{i-1} \circ\rho_{u_{i-1}}) p o t s u f f ( w 1 : i , w i + 1 : n , u i − 1 α i ( d i ′ ) , [ x ∣ u i − 1 ∣ + 1 ↦ w i ] ∘ μ i − 1 ∘ ρ u i − 1 ) at lines 6 and 9 returns a suffix restricted to include values that need be considered when comparing SDTs. They are explained in detail in Section B.
Algorithm 3 considers each short prefix u i − 1 ∈ U − 1 ( l i − 1 ) u_{i-1} \in U^{-1}(l_{i-1}) u i − 1 ∈ U − 1 ( l i − 1 ) , and makes two checks.
New Transition. If d i d_i d i is in V a l s ( w 1 : i − 1 ) Vals(w_{1:i-1}) V a l s ( w 1 : i − 1 ) , then Algorithm 3 considers all d i ′ = μ u i − 1 ( x l ) d_i' = \mu_{u_{i-1}}(x_l) d i ′ = μ u i − 1 ( x l ) with l l l in p o t m a t c h ( w 1 : i − 1 , d i , u i − 1 , μ i − 1 ∘ ρ u i − 1 ) potmatch(w_{1:i-1}, d_i, u_{i-1}, \mu_{i-1} \circ\rho_{u_{i-1}}) p o t ma t c h ( w 1 : i − 1 , d i , u i − 1 , μ i − 1 ∘ ρ u i − 1 ) such that u i − 1 α i ( d i ′ ) u_{i-1}\alpha_i(d_i') u i − 1 α i ( d i ′ ) is not in U U U . If, letting z i z_i z i be p o t s u f f ( w 1 : i , w i + 1 : n , u i − 1 α i ( d i ′ ) , [ x i ↦ w i ] ∘ μ i − 1 ) potsuff(w_{1:i}, w_{i+1:n}, u_{i-1}\alpha_i(d_i'), [x_i \mapsto w_i] \circ\mu_{i-1}) p o t s u f f ( w 1 : i , w i + 1 : n , u i − 1 α i ( d i ′ ) , [ x i ↦ w i ] ∘ μ i − 1 ) we have u i − 1 α i ( d i ′ ) ̸ ≃ { z i } u i − 1 α i ( d u i − 1 t r u e ) u_{i-1}\alpha_i(d_i') \not\simeq_{\{z_i\}} u_{i-1}\alpha_i(d_{u_{i-1}}^{\mathrm{true}}) u i − 1 α i ( d i ′ ) ≃ { z i } u i − 1 α i ( d u i − 1 true ) then u i − 1 α i ( d i ′ ) u_{i-1}\alpha_i(d_i') u i − 1 α i ( d i ′ ) will be sifted. The sifting will eventually result in a new guard p = x l p = x_l p = x l from l i − 1 l_{i-1} l i − 1 .
New Location. A one-symbol extension u i − 1 α i ( d i ′ ) u_{i-1}\alpha_i(d_i') u i − 1 α i ( d i ′ ) in l i l_i l i is inequivalent to any short prefix in l i l_i l i . In this case, we make u i − 1 α i ( d i ′ ) u_{i-1}\alpha_i(d_i') u i − 1 α i ( d i ′ ) a new short prefix, and expand it.
If neither case applies, we continue with the next index. Since the run is misclassifying, one of the cases will apply for some index.
Correctness and Complexity
In this short section, we state the main correctness theorem for S L = λ SL^{\lambda}_{=} S L = λ (its proof and supporting lemmata appear in Appendix § 12 ), and briefly discuss its complexity.
Theorem 1 (Correctness). S L = λ SL^{\lambda}_{=} S L = λ infers a minimal (in the number of locations) RA for data language L \mathcal{L} L of finite index using a finite number of membership queries and equivalence queries.
For an analysis of the complexity in terms of the number of MQs and EQs that may have to be performed for inferring an RA, we note that S L = λ SL^{\lambda}_{=} S L = λ and S L λ SL^{\lambda} S L λ have the same basic structure. S L = λ SL^{\lambda}_{=} S L = λ improves on S L λ SL^{\lambda} S L λ by using context information to reduce the number of MQs required for the construction of each SDT. However, in the worst case, the restrictions used by S L = λ SL^{\lambda}_{=} S L = λ are equivalent to those of S L λ SL^{\lambda} S L λ . Hence, the worst-case complexity for S L = λ SL^{\lambda}_{=} S L = λ is the same as for S L λ SL^{\lambda} S L λ [15 ] . Still, our evaluation in § 6 shows that in practice, S L = λ SL^{\lambda}_{=} S L = λ uses (significantly) fewer tests than S L λ SL^{\lambda} S L λ and scales much better as SULs increase in size.
Evaluation
We have implemented S L = λ SL^{\lambda}_{=} S L = λ in RALib , a publicly available tool for learning register automata. RALib comes with implementations of the S L ∗ SL^{*} S L ∗ and S L λ SL^{\lambda} S L λ algorithms.
Our evaluation comprises four kinds of experiments; two of them (1 and 3 in the list below) are from the artifact [46 ] of the S L λ SL^{\lambda} S L λ paper, and the other two (2 and 4) are new. The experiments are: (1) Learning small models from the Automata Wiki [43 ] in order to establish a baseline comparison of S L = λ SL^{\lambda}_{=} S L = λ against S L ∗ SL^{*} S L ∗ and S L λ SL^{\lambda} S L λ . (2) Comparing S L λ SL^{\lambda} S L λ and S L = λ SL^{\lambda}_{=} S L = λ on our running example: an implementation of L P ( n ) \mathcal{L}_{P(n)} L P ( n ) , accepting palindromes of length at most n n n (4 ≤ n ≤ 14 4 \le n \le14 4 ≤ n ≤ 14 ). (3) Measuring the scalability of S L λ SL^{\lambda} S L λ and S L = λ SL^{\lambda}_{=} S L = λ on 24 consecutive hypotheses of increasing size generated when learning the DTLS server implementation of Mbed TLS 2.26.0. (4) Learning RA models of five widely-used DTLS server implementations in a black-box setting, using the epoch field as a data parameter. To control this experiment and make it fair, we use an a priori known single counterexample (completing a DTLS handshake), and stop learning when the models contain it. We have submitted an artifact for reproduction of our results.
RALib is implemented in Java 21. The machine we used for our experiments is a Dell server with two Intel(R) Xeon(R) Platinum 8168 CPUs (2.70GHz) running Debian 13.5. The machine has 192 GB of RAM. For one experiment instance (L P ( n ) \mathcal{L}_{P(n)} L P ( n ) for n = 14 n = 14 n = 14 ), we had to allocate a JVM heap of 150 GB to obtain results. For all other experiments, learning generally uses much less memory, and the default JVM configuration suffices.
(1) Results on Automata Wiki models. Table 1 displays the results of this experiment. For every model, we report its complexity (in number of locations ∣ Q ∣ \lvert Q\rvert ∣ Q ∣ , transitions ∣ Γ ∣ \lvert\Gamma\rvert ∣ Γ ∣ , registers ∣ X ∣ \lvert X\rvert ∣ X ∣ , and constants ∣ C ∣ \lvert C\rvert ∣ C ∣ ) and, for each learning algorithm, the number of tests (or unique MQs)1 . We notice that S L λ SL^\lambda S L λ and S L = λ SL^\lambda_= S L = λ consistently outperform S L ∗ SL^* S L ∗ , using substantially fewer tests. We also see that S L = λ SL^\lambda_= S L = λ performs similarly or better than S L λ SL^\lambda S L λ . In one case (abp-output), S L = λ SL^\lambda_= S L = λ exhibits a significant improvement.
Table 1. Results on Synthetic Models from Automata Wiki.
Most of these benchmarks do not feature the types of system behavior that showcase the advantages of S L = λ SL^\lambda_= S L = λ over S L λ SL^\lambda S L λ . The restrictions added by S L = λ SL^\lambda_= S L = λ mainly pay off when a data dependency discovered during learning remains relevant as learning continues. If we look at fifo7, for instance, the dependency of values pushed to the queue is relevant only when the value is popped. Afterwards, there is no further reference to the value that was popped. This similarly holds for abp-receiver3, login, and sip, where the relevance of data dependencies is greatly diminished once the reason for the relevance is revealed (i.e., when a suffix can be formed that reveals a data value to be memorable). This is in contrast to abp-output, wherein a specific register acts as a “gateway”, allowing progress through protocol states only when passing a check for equality with said register.
(2) Results on L P ( n ) \mathcal{L}_{P(n)} L P ( n ) . Table 2 shows results obtained for languages accepting palindromes up to size n n n , where n n n takes even values from 4 to 14. This benchmark is synthetic but quite challenging. For each algorithm and model, the table displays similar measurements to Table 1 , but also shows ratios between tests, during construction and in total, needed by S L = λ SL^\lambda_= S L = λ and S L λ SL^\lambda S L λ . × \times × marks experiments that did not complete due to running out of memory even though we used a JVM heap of 150 GB for L P ( 14 ) \mathcal{L}_{P(14)} L P ( 14 ) . S L = λ SL^\lambda_= S L = λ needs the fewest tests on all models, while S L ∗ SL^* S L ∗ is the worst performer, needing approximately three times as many total tests as S L λ SL^\lambda S L λ , which comes second. Observe that the gap between S L = λ SL^\lambda_= S L = λ and S L λ SL^\lambda S L λ widens with growing n n n : when n n n is 4, S L = λ SL^\lambda_= S L = λ needs 79% the total tests of S L λ SL^\lambda S L λ , when n n n is 12 it needs a mere 28%. S L = λ SL^\lambda_= S L = λ also proves to be the most memory-efficient algorithm, being the only one not to run out of memory when n n n is 14.
Table 2. Results on L P ( n ) \mathcal{L}_P(n) L P ( n ) ; ✗ denotes out of memory; ratio is S L = λ / S L λ SL^\lambda_{=}/SL^\lambda S L = λ / S L λ .
(3) Results on DTLS models. Figure 5 shows results obtained for learning hypotheses of increasing complexity of the DTLS server of Mbed TLS 2.26.0. Here, for each algorithm, we show how the number of tests scales with the number of transitions in the model. As in the L P ( n ) \mathcal{L}_P(n) L P ( n ) experiments, the results indicate clearly that the number of tests grows much more rapidly for S L λ SL^\lambda S L λ than for S L = λ SL^\lambda_{=} S L = λ . Similarly to abp-output, the detected data dependency remains relevant as learning continues. In DTLS, once the correct value for the echo field is identified, the value must be reused by several actions (messages) of the protocol in order to complete a handshake. This characteristic allows S L = λ SL^\lambda_{=} S L = λ to restrict suffix parameters to be equal to this value, greatly reducing the number of tests needed. We note that this characteristic occurs naturally in many other stateful network protocols, such as TCP, where an identifier (e.g., port number) is stored and must be reused repeatedly across the protocol interaction.
Figure 5. Number of tests for inferring models of the Mbed TLS 2.26.0 server.
Results on DTLS implementations
Table 3 shows results obtained from learning five DTLS server implementations. For each algorithm, included are the number of accepting locations and transitions in the learned model, the number of tests and the learning time (in minutes) with corresponding ratios between S L λ SL^\lambda S L λ and S L = λ SL^\lambda_{=} S L = λ . Inclusion of size metrics is motivated by the fact that different learning algorithms can produce models which differ in size. (Recall that our black-box equivalence setup employs a single counterexample.) In producing a hypothesis which fits this counterexample, learning algorithms might unearth a different number of neighboring locations. The table shows S L = λ SL^\lambda_{=} S L = λ to be performing substantially better than S L λ SL^\lambda S L λ : it reduces learning time and tests from slightly over a third to under a fifth. This improvement comes at no cost to model quality: both algorithms learn models of identical size for all systems. S L ∗ SL^* S L ∗ is able to learn marginally larger models for the last three implementations, but this comes at a significant performance cost: S L ∗ SL^* S L ∗ generally trails S L λ SL^\lambda S L λ , and is vastly behind S L = λ SL^\lambda_{=} S L = λ , which reduces learning time and test count by a factor of five to eight.
Table 3. Results on learning RA models of DTLS servers; ratio is S L = λ / S L λ SL^{\lambda}_{=}/SL^{\lambda} S L = λ / S L λ .
Conclusion
We have presented S L = λ SL^{\lambda}_{=} S L = λ , a tree-based algorithm for RA learning. In comparison to previous algorithms, S L = λ SL^{\lambda}_{=} S L = λ reduces the number of membership queries needed for inferring RA models by aggressively restricting the ranges of data parameters in suffixes. The restrictions are derived by analyzing which data values must be considered to distinguish locations or transitions, or to detect new registers.
There are several directions for future work, including to develop (i) analogous restriction policies for RA learning algorithms for other theories or classes of systems, (ii) passive algorithms for RA learning, and (iii) more efficient strategies for identifying counterexamples in equivalence queries.
Acknowledgments. This research was partially funded by grants 2023-05363 and 2024-05748 from the Swedish Research Council (Vetenskapsrådet), and by the Knut and Alice Wallenberg Foundation through project UPDATE.
Data-Availability Statement The implementation of S L = λ SL^{\lambda}_{=} S L = λ that we have used for all experiments is included in RALib 0.2.
Disclosure of Interests. The authors have no competing interests to declare that are relevant to the content of this paper.
References
In these appendices, we include
Section A: Explanation of details in S L ≡ λ SL^{\lambda}_{\equiv} S L ≡ λ that could not fit into Section 4. Section B: More information on the functions appearing in Algorithm 3. Section C: Proof of Theorem 1.
The S L ≡ λ SL^{\lambda}_{\equiv} S L ≡ λ Learning Algorithm in Detail
In this appendix, we give a detailed explanation of the S L ≡ λ SL^{\lambda}_{\equiv} S L ≡ λ algorithm. As stated in Section 4, the core of S L ≡ λ SL^{\lambda}_{\equiv} S L ≡ λ , shown in Algorithm 2, initializes the data structures U U U and S p S_p S p to ∅ \varnothing ∅ and then sifts ϵ \epsilon ϵ , entering it into U U U . Thereafter, it enters the main loop and checks whether the closedness and consistency properties are satisfied. Recall that if a property is not satisfied, S L ≡ λ SL^{\lambda}_{\equiv} S L ≡ λ performs a corrective update, which consists of one of the following:
expanding a prefix u ∈ U ∖ S p u \in U \setminus S_p u ∈ U ∖ S p (in the case of location closedness),
sifting a prefix into C T CT C T (in the case of transition closedness), or
refining a leaf N N N by replacing it with a new inner node and then sifting each prefix in N N N (in the cases of register closedness and consistency properties).
For the latter corrective action, the new inner node replacing N N N contains a restricted suffix that is always formed by prepending another restricted suffix labeling some node in C T CT C T with some symbol α ( p 1 ∣ ϕ α ) \alpha(p_1 \mid\phi_{\alpha}) α ( p 1 ∣ ϕ α ) . Note that the corrective actions for the consistency properties all require C T CT C T to be register closed. Below, we describe in greater detail how these restricted suffixes are formed.
Register Closedness
Let us begin with register closedness. Recall from Section 4 that register closedness is satisfied if each register x l x_l x l that is memorable for a one-symbol extension u α ( d ) u\alpha(d) uα ( d ) of a short prefix u u u is also memorable for u u u . Register closedness allows us to correlate registers of u u u and u α ( d ) u\alpha(d) uα ( d ) , even if u u u and u α ( d ) u\alpha(d) uα ( d ) are in different leaves. If this property is not satisfied (line 8), a restricted suffix z ′ z' z ′ revealing the missing register(s) is added to the suffixes of u u u . This suffix is formed by prepending a suffix z z z for which mem { z } ( u α ( d ) ) ⊈ mem Z ( u ) ( u ) \operatorname{mem}_{\{z\}}(u\alpha(d)) \not\subseteq\operatorname{mem}_{Z(u)}(u) mem { z } ( uα ( d )) ⊆ mem Z ( u ) ( u ) by the symbol α ( p 1 ∣ ϕ α ) \alpha(p_1 \mid\phi_{\alpha}) α ( p 1 ∣ ϕ α ) , as stated in Section 4.
Note, however, that this property has two notable exceptions. The first is if l = ∣ u ∣ + 1 l = |u| + 1 l = ∣ u ∣ + 1 , in which case x l x_l x l is clearly not a register of u u u . The second exception is a bit more subtle. Recall that when a data value d d d is stored in a register x l x_l x l , the index l l l will always be the index of the first occurrence of d d d in the prefix. This means that when d = μ u α ( d ) ( x l ) d = \mu_{u\alpha(d)}(x_l) d = μ uα ( d ) ( x l ) for l ≤ ∣ u ∣ l \le|u| l ≤ ∣ u ∣ , a guard p j = x l p_j = x_l p j = x l is indistinguishable from a guard p j = x ∣ u ∣ + 1 p_j = x_{|u|+1} p j = x ∣ u ∣ + 1 . If a guard p j = x l p_j = x_l p j = x l in L [ u α ( d ) , z ] L[u\alpha(d), z] L [ uα ( d ) , z ] is truly p j = x ∣ u ∣ + 1 p_j = x_{|u|+1} p j = x ∣ u ∣ + 1 then L [ u , z ′ ] L[u,z'] L [ u , z ′ ] for a one-symbol extension z ′ z' z ′ of z z z would not contain a guard on x l x_l x l , and therefore x l ∉ mem { z ′ } ( u ) x_l \notin\operatorname{mem}_{\{z'\}}(u) x l ∈ / mem { z ′ } ( u ) . We refer to such a register x l x_l x l as a phantom register of z z z . To check for potential phantom registers, we include the one-symbol extension z ′ z' z ′ in the check for the register closedness property (line 8 of Algorithm 2).
As an example of a phantom register, consider the language L S L P L_{SLP} L S L P for a session login protocol where a client may register a session with a server and then login to that session. The client registers a session identifier i i i with Register ( i ) \operatorname{Register}(i) Register ( i ) , after which it may login to the session with Login ( i ) \operatorname{Login}(i) Login ( i ) . The server acknowledges the login with Ack ( i ) \operatorname{Ack}(i) Ack ( i ) and no further login attempts can be made thereafter. However, the server will also acknowledge a login attempt with an invalid identifier. An acceptor for this protocol is shown in Figure 7 . For z = Ack ( p 1 ∣ unmapped ( p 1 ) ) z = \operatorname{Ack}(p_1 \mid\operatorname{unmapped}(p_1)) z = Ack ( p 1 ∣ unmapped ( p 1 )) the SDT L [ Register ( 0 ) Login ( 0 ) , z ] \mathcal{L}[\operatorname{Register}(0)\operatorname{Login}(0),z] L [ Register ( 0 ) Login ( 0 ) , z ] , shown in Figure 6 , contains the guard p 1 = x 1 p_1 = x_1 p 1 = x 1 which would appear to indicate that x 1 x_1 x 1 is memorable. However, L [ Register ( 0 ) Login ( d ′ ) , z ] = + \mathcal{L}[\operatorname{Register}(0)\operatorname{Login}(d'),z] = + L [ Register ( 0 ) Login ( d ′ ) , z ] = + for p 1 = d ′ p_1 = d' p 1 = d ′ for all d ′ d' d ′ , including 0, the actual guard should really be p 1 = x 2 p_1 = x_2 p 1 = x 2 . The register x 1 x_1 x 1 is therefore a phantom register of z z z .
Figure 7. Register automaton accepting language L S L P L_{SLP} L S L P .
Figure 6. Decision tree for L [ Register ( 0 ) Login ( 0 ) , Ack ( p 1 ∣ unmapped ( p 1 ) ) ] \mathcal{L}[\operatorname{Register}(0)\operatorname{Login}(0),\operatorname{Ack}(p_1\mid\operatorname{unmapped}(p_1))] L [ Register ( 0 ) Login ( 0 ) , Ack ( p 1 ∣ unmapped ( p 1 ))] .
Note that a register x l x_l x l being a phantom register does not mean that x l x_l x l is not memorable in u u u . In fact, a core concept of the S L = λ SL^\lambda_{=} S L = λ algorithm is that a one-symbol extension u α ( d ) u\alpha(d) uα ( d ) is only ever added to C T CT C T as a representative data value d u d_u d u for a guard g ∈ G { z } ( u , α ) g \in G_{\{z\}}(u,\alpha) g ∈ G { z } ( u , α ) for some suffix z z z . However, z z z need not necessarily be present in C T CT C T (see § 4.4 ). If x l ∈ m e m { z } ( u α ( d ) ) x_l \in mem_{\{z\}}(u\alpha(d)) x l ∈ m e m { z } ( uα ( d )) but x l ∉ m e m Z ( u ) ( u ) x_l \notin mem_{Z(u)}(u) x l ∈ / m e m Z ( u ) ( u ) , it just means that there is not yet a suffix z z z in C T CT C T that acts as a witness to x l x_l x l being memorable in u u u . In our example, the suffix Login ( p 1 ∣ unmapped ( p 1 ) ) Ack ( p 2 ∣ p 2 = p 1 ) Login ( p 3 ∣ fresh ( p 3 ) ) \operatorname{Login}(p_1\mid\operatorname{unmapped}(p_1))\operatorname{Ack}(p_2\mid p_2=p_1)\operatorname{Login}(p_3\mid\operatorname{fresh}(p_3)) Login ( p 1 ∣ unmapped ( p 1 )) Ack ( p 2 ∣ p 2 = p 1 ) Login ( p 3 ∣ fresh ( p 3 )) would reveal that x 1 x_1 x 1 is memorable in Register ( 0 ) \operatorname{Register}(0) Register ( 0 ) .
For the sake of simplicity, the pseudocode for the register closedness case in Algorithm 2 hides the necessary steps for handling phantom registers. First, note that it is not, in general, possible to determine whether a register x l x_l x l is a phantom register from analysis of L [ u α ( d ) , z ] \mathcal{L}[u\alpha(d),z] L [ uα ( d ) , z ] alone. We must therefore add a check to line 8 for whether L [ u , z ] \mathcal{L}[u,z] L [ u , z ] contains a guard on x l x_l x l . If it does not, then x l x_l x l is a phantom register, so register closedness does not apply. Secondly, if there are multiple suffixes z z z revealing new non-phantom registers, we choose the one whose node is highest in C T CT C T (i.e., closest to the root). This allows us to easily determine whether a register x l x_l x l in the restrictions of z z z is a phantom register; if x l ∉ m e m Z ( u ) ( u ) x_l \notin mem_{Z(u)}(u) x l ∈ / m e m Z ( u ) ( u ) then it must be a phantom register, since there would otherwise exist a node above N ( z ) N(z) N ( z ) revealing x l x_l x l to be memorable, which contradicts that N ( z ) N(z) N ( z ) is the highest node revealing non-phantom registers.
Finally, the ⋅ \cdot ⋅ operator for prepending a restricted suffix by a symbol α ( p 1 ∣ ϕ α ) \alpha(p_1\mid\phi_\alpha) α ( p 1 ∣ ϕ α ) hides functionality for safely transferring the restrictions ϕ \phi ϕ of z z z to z ′ z' z ′ . Note that we cannot directly use the restrictions of ϕ \phi ϕ , partly due to the potential presence of phantom registers, but also because the u n m a p p e d ( p j ) unmapped(p_j) u nma pp e d ( p j ) restriction is non-monotonic, i.e., a register that is unmapped for an inner node N N N need not be unmapped for a successor N ′ N' N ′ . The restrictions ϕ \phi ϕ must first be adapted, as follows. Let N = N ( z ) N=N(z) N = N ( z ) . For j = 1 , … , ∣ ϕ ∣ j=1,\ldots,|\phi| j = 1 , … , ∣ ϕ ∣ , we let ϕ j ′ \phi'_j ϕ j ′ be the disjunction of the following:
f r e s h ( p j + 1 ) fresh(p_{j+1}) f r es h ( p j + 1 ) if ϕ j \phi_j ϕ j contains f r e s h ( p j ) fresh(p_j) f r es h ( p j ) or u n m a p p e d ( p j ) unmapped(p_j) u nma pp e d ( p j ) ,
p j + 1 = x l p_{j+1}=x_l p j + 1 = x l if x l x_l x l is a memorable register of u u u and either L [ u α ( d ) , N ] \mathcal{L}[u\alpha(d),N] L [ uα ( d ) , N ] contains a guard p j = x l p_j=x_l p j = x l or ϕ j \phi_j ϕ j contains the restriction p j = ρ u α ( d ) N ( x l ) p_j=\rho^{N}_{u\alpha(d)}(x_l) p j = ρ uα ( d ) N ( x l ) ,
p j + 1 = p j ′ p_{j+1}=p_{j'} p j + 1 = p j ′ , where p j ′ p_{j'} p j ′ is a prior suffix value (i.e., j ′ < j j'<j j ′ < j ), if either L [ u α ( d ) , N ] \mathcal{L}[u\alpha(d),N] L [ uα ( d ) , N ] contains a guard p j = p j ′ p_j=p_{j'} p j = p j ′ or ϕ j \phi_j ϕ j contains the restriction p j = p j ′ p_j=p_{j'} p j = p j ′ ,
u n m a p p e d ( p j + 1 ) unmapped(p_{j+1}) u nma pp e d ( p j + 1 ) if L [ u α ( d ) , N ] \mathcal{L}[u\alpha(d),N] L [ uα ( d ) , N ] contains a guard p j = x l p_j=x_l p j = x l where x l ∉ m e m Z ( u ) ( u ) x_l\notin mem_Z(u)(u) x l ∈ / m e m Z ( u ) ( u ) and l < ∣ u ∣ + 1 l<|u|+1 l < ∣ u ∣ + 1 (i.e., x l x_l x l is an unmapped register of u u u ),
p j + 1 = p 1 p_{j+1}=p_1 p j + 1 = p 1 if ϕ j \phi_j ϕ j contains the restriction p j = x l p_j=x_l p j = x l with x l ∉ m e m Z ( u ) ( u ) x_l\notin mem_Z(u)(u) x l ∈ / m e m Z ( u ) ( u ) ,
p j + 1 = p 1 p_{j+1}=p_1 p j + 1 = p 1 if L [ u α ( d ) , N ] \mathcal{L}[u\alpha(d),N] L [ uα ( d ) , N ] contains a guard p j = x l p_j=x_l p j = x l where l = ∣ u ∣ + 1 l=|u|+1 l = ∣ u ∣ + 1 (i.e., x l x_l x l is not a register of u u u ) or d = μ u ( x l ) d=\mu_u(x_l) d = μ u ( x l ) (i.e., x l x_l x l is a potential phantom register).
The general idea behind these rules is that the restrictions ϕ ′ \phi' ϕ ′ of z ′ z' z ′ should cover every possible path of L [ u α ( d ) , N ] \mathcal{L}[u\alpha(d),N] L [ uα ( d ) , N ] . Guards (or restrictions) on a register x l x_l x l that is already memorable in u u u (rule 2), guards (or restrictions) on a prior suffix parameter (rule 3), and any f r e s h fresh f r es h restrictions (rule 1) can be safely transferred to ϕ ′ \phi' ϕ ′ . Any guard on a register of u u u that is not yet known to be memorable is one of the missing registers that z ′ z' z ′ should reveal, inducing an u n m a p p e d unmapped u nma pp e d restriction (rule 4). If there is a guard (or restriction) on a register x ∣ u ∣ + 1 x_{|u|+1} x ∣ u ∣ + 1 corresponding to d d d , then x ∣ u ∣ + 1 x_{|u|+1} x ∣ u ∣ + 1 should be translated to the parameter p 1 p_1 p 1 (rules 5 and 6). This includes potential phantom registers, since we can not know a priori whether a register x l x_l x l is a phantom register. (Note that if x l x_l x l is a potential phantom register, i.e., l < ∣ u ∣ + 1 l<|u|+1 l < ∣ u ∣ + 1 and d = μ u ( x l ) d=\mu_u(x_l) d = μ u ( x l ) , then it will also be an unmapped data value of u u u , so ϕ j ′ \phi'_j ϕ j ′ will include the disjunct u n m a p p e d ( p j + 1 ) unmapped(p_{j+1}) u nma pp e d ( p j + 1 ) due to rule 4.)
Extending Suffixes for the Consistency Properties
Recall from Section 4 that for any consistency property that is not satisfied, we add a new inner node labeled by an atomically (or k k k -atomically, with k ≤ ∣ u ∣ k\leq|u| k ≤ ∣ u ∣ , in the case of transition consistency) labeled suffix z ′ z' z ′ to C T CT C T . The suffix z ′ z' z ′ is formed by prepending a suffix z z z in C T CT C T , that has been made atomic, by a symbol α ( p 1 ∣ ϕ α ) \alpha(p_1\mid\phi_\alpha) α ( p 1 ∣ ϕ α ) . In this section, we will describe how to form such a suffix z ′ z' z ′ in more detail. We will use location consistency as the context; the other consistency properties are resolved in a similar manner (as described in Section 4).
Recall that location consistency is satisfied if all pairs of short prefixes u , u ′ u,u' u , u ′ such that u ≃ Z ( u ) γ u ′ u\mathrel{\simeq^{\gamma}_{Z(u)}}u' u ≃ Z ( u ) γ u ′ (implying that U ( u ) = U ( u ′ ) \mathcal{U}(u)=\mathcal{U}(u') U ( u ) = U ( u ′ ) ) have equivalent extensions. If it is not satisfied, then there is some guard g ∈ G ( u , α ) g\in\mathcal{G}(u,\alpha) g ∈ G ( u , α ) such that U ( u α ( d u ( g ) ) ) ≠ U ( u ′ α ( d u ′ ( g ) ) ) \mathcal{U}(u\alpha(d^{(g)}_u))\ne\mathcal{U}(u'\alpha(d^{(g)}_{u'})) U ( uα ( d u ( g ) )) = U ( u ′ α ( d u ′ ( g ) )) . To resolve this inconsistency, the leaf containing u u u (and u ′ u' u ′ ) must be split by a suitable atomic suffix z ′ \mathbf{z}' z ′ . For the sake of simplicity, we will let d \mathbf{d} d denote d u q d^{q}_{u} d u q and d ′ \mathbf{d}' d ′ denote d u ′ γ ( g ˉ ) d^{\gamma(\bar{g})}_{u'} d u ′ γ ( g ˉ ) .
Table 4.
As explained in Section 4, the first step in forming z ′ \mathbf{z}' z ′ is to find a path g ˉ \bar{g} g ˉ that separates L [ u α ( d ) , N ] \mathcal{L}[u\alpha(\mathbf{d}),N] L [ uα ( d ) , N ] and L [ u ′ α ( d ′ ) , N ] \mathcal{L}[u'\alpha(\mathbf{d}'),N] L [ u ′ α ( d ′ ) , N ] , where N N N is a common ancestor of the two extensions (i.e., z ( N ) \mathbf{z}(N) z ( N ) separates u α ( d ) u\alpha(\mathbf{d}) uα ( d ) and u ′ α ( d ′ ) u'\alpha(\mathbf{d}') u ′ α ( d ′ ) ). We do this with a call to the Prune \operatorname{Prune} Prune method, shown in Algorithm 4. Note that the only difference between the definition in Section 4 and Algorithm 4 is that the latter definition shows how registers are remapped between T 1 T_{1} T 1 and T 2 T_{2} T 2 .
The next step is use g ˉ \bar{g} g ˉ to strengthen the restrictions of the suffix z ( N ) \mathbf{z}(N) z ( N ) . Let α 1 ( p 1 ∣ ϕ 1 ) ⋯ α m ( p m ∣ ϕ m ) \alpha_{1}(p_{1} \mid\phi_{1}) \cdots\alpha_{m}(p_{m} \mid\phi_{m}) α 1 ( p 1 ∣ ϕ 1 ) ⋯ α m ( p m ∣ ϕ m ) denote z ( N ) \mathbf{z}(N) z ( N ) . We define the operator ∩ u α ( d ) \underset{u\alpha(\mathbf{d})}{\cap} uα ( d ) ∩ such that z ( N ) ∩ u α ( d ) g ˉ \mathbf{z}(N) \underset{u\alpha(\mathbf{d})}{\cap} \bar{g} z ( N ) uα ( d ) ∩ g ˉ combines the restrictions of z \mathbf{z} z with g ˉ \bar{g} g ˉ to form an atomically restricted suffix α 1 ( p 1 ∣ ϕ 1 ′ ) ⋯ α m ( p m ∣ ϕ m ′ ) \alpha_{1}(p_{1} \mid\phi'_{1}) \cdots\alpha_{m}(p_{m} \mid\phi'_{m}) α 1 ( p 1 ∣ ϕ 1 ′ ) ⋯ α m ( p m ∣ ϕ m ′ ) . For j = 1 , … , m j = 1,\ldots,m j = 1 , … , m we let ϕ j ′ \phi'_{j} ϕ j ′ be
p j = ρ u ( x l ) p_{j} = \rho_{u}(x_{l}) p j = ρ u ( x l ) if g j g_{j} g j is p j = x l p_{j} = x_{l} p j = x l or if ϕ j \phi_{j} ϕ j contains the restriction p j = ρ u α ( d ) N ( x l ) p_{j} = \rho^{N}_{u\alpha(\mathbf{d})}(x_{l}) p j = ρ uα ( d ) N ( x l ) ,
p j = p j ′ p_{j} = p_{j'} p j = p j ′ , where p j ′ p_{j'} p j ′ is a prior suffix parameter (i.e., j ′ < j j' < j j ′ < j ), if g j g_{j} g j is p j = p j ′ p_{j} = p_{j'} p j = p j ′ or ϕ j \phi_{j} ϕ j contains the restriction p j = p j ′ p_{j} = p_{j'} p j = p j ′ , and
fresh ( p j ) \operatorname{fresh}(p_{j}) fresh ( p j ) otherwise.
In a nutshell, each ϕ j ′ \phi'_{j} ϕ j ′ is chosen such that ϕ j ′ \phi'_{j} ϕ j ′ satisfies g j ∧ ϕ j g_{j} \land\phi_{j} g j ∧ ϕ j . Note that any register in ϕ j ′ \phi'_{j} ϕ j ′ is remapped to rp ( U ( u ) ) \operatorname{rp}(U(u)) rp ( U ( u )) . It is this remapping that allows us to map the registers of a prefix to those used in restrictions, using the ρ u α ( d ) N \rho^{N}_{u\alpha(\mathbf{d})} ρ uα ( d ) N bijection.
Finally, we prepend z ( N ) ∩ u α ( d ) g ˉ \mathbf{z}(N) \underset{u\alpha(\mathbf{d})}{\cap} \bar{g} z ( N ) uα ( d ) ∩ g ˉ by the symbol ϕ α \phi_{\alpha} ϕ α . Let z \mathbf{z} z denote z ( N ) ∩ u α ( d ) g ˉ \mathbf{z}(N) \underset{u\alpha(\mathbf{d})}{\cap} \bar{g} z ( N ) uα ( d ) ∩ g ˉ . We define the operator ⋅ \cdot ⋅ such that α ( p 1 ∣ ϕ α ) ⋅ z \alpha(p_{1} \mid\phi_{\alpha}) \cdot\mathbf{z} α ( p 1 ∣ ϕ α ) ⋅ z is the restricted suffix α ( p 1 ∣ ϕ α ) α 1 ( p 2 ∣ ϕ 1 ′ ′ ) ⋯ α m ( p m + 1 ∣ ϕ m ′ ′ ) \alpha(p_{1} \mid\phi_{\alpha})\alpha_{1}(p_{2} \mid\phi''_{1}) \cdots\alpha_{m}(p_{m+1} \mid\phi''_{m}) α ( p 1 ∣ ϕ α ) α 1 ( p 2 ∣ ϕ 1 ′′ ) ⋯ α m ( p m + 1 ∣ ϕ m ′′ ) . Each ϕ j ′ ′ \phi''_{j} ϕ j ′′ is ϕ j ′ \phi'_{j} ϕ j ′ (where ϕ j ′ \phi'_{j} ϕ j ′ is the restriction for the j th j^{\text{th}} j th parameter of z \mathbf{z} z ) with the following modifications:
p j p_{j} p j is replaced with p j + 1 p_{j+1} p j + 1 ,
p j ′ p_{j'} p j ′ , where j ′ < j j' < j j ′ < j , is replaced by p j ′ + 1 p_{j'+1} p j ′ + 1 ,
x ∣ u ∣ + 1 x_{|u|+1} x ∣ u ∣ + 1 is replaced by p 1 p_{1} p 1 , and
if p j + 1 p_{j+1} p j + 1 is of form p j + 1 = x l p_{j+1} = x_{l} p j + 1 = x l where x l x_{l} x l is a register not in mem Z ( u ) ( u ) \operatorname{mem}_{Z(u)}(u) mem Z ( u ) ( u ) , then x l x_{l} x l is replaced with p 1 p_{1} p 1 .
The first three modifications simply shift the suffix parameters of ϕ 1 ′ , … , ϕ m ′ \phi'_{1},\ldots,\phi'_{m} ϕ 1 ′ , … , ϕ m ′ and the register x ∣ u ∣ + 1 x_{|u|+1} x ∣ u ∣ + 1 of α ( d ) \alpha(\mathbf{d}) α ( d ) , “one step to the right”. The fourth modification is there to handle any phantom registers in ϕ 1 ′ , … , ϕ m ′ \phi'_{1},\ldots,\phi'_{m} ϕ 1 ′ , … , ϕ m ′ . Since we require C T CT C T to be register closed before doing any of the checks for the consistency properties,
Algorithm 5: The full $SL^{\lambda}$ Algorithm for Learning Register Automata
1 Initialize $CT$ as root node $root(CT)$ with suffix $\epsilon$ and $U \leftarrow \emptyset$, $S_p \leftarrow \emptyset$
2 $Sift(\epsilon,root(CT))$
3 HYP: repeat
▷ Check closedness
4 if exists leaf $N$ for which $U^{-1}(N) \cap S_p = \emptyset$ then // location
5 $Expand(u)$ for some $u \in U^{-1}(N)$
6 if $u \in S_p$ and $g \in G(u,\alpha)$ but $u\alpha(d_u^g) \notin U$ then // transition
7 $Sift(u\alpha(d_u^g),root(CT))$
8 if $mem_{\{z\}}(u\alpha(d)) \not\subseteq mem_{Z(u)}(u)\cup\{x_{|u|+1}\}$ for some $z \in Z(u\alpha(d))$ then // register
9 $Refine(U(u),\alpha(p_1\mid\phi_\alpha)\cdot z)$ where $\phi_\alpha$ is if $d=d_u^{true}$ then $fresh(p_1)$
elif $d=\mu_u(x_l)$ then $p_1=x_l$ else $unmapped(p_1)$
▷ Check consistency
10 if $u,u' \in U^{-1}(N)\cap S_p$ with $u \simeq_{Z(N)} u'$ for leaf $N$ with
$U(u\alpha(d_u^g)) \ne U(u'\alpha(d_{u'}^{\gamma(g)}))$ then // location
11 $Refine(N,\alpha(p_1\mid\phi_\alpha)\cdot
(z^{(N)}_{u\alpha(d_u^g)} \cap
Prune(\mathcal{L}[u\alpha(d_u^g),N'],\mathcal{L}[u'\alpha(d_{u'}^{\gamma(g)}),N'])))$
12 where $N'=lca(u\alpha(d_u^g),u'\alpha(d_{u'}^{\gamma(g)}))$ and
13 $\phi_\alpha$ is if $g$ is $p_1=x_l$ then $p_1=x_l$ else $fresh(p_1)$
14 if $U(u\alpha(d))\ne U(u\alpha(d_u^{true}))$ with $d\ne d_u^g$ for all $g\in G(u,\alpha)$ then // transition(a)
15 $Refine(U(u),\alpha(p_1\mid\phi_\alpha)\cdot
(z^{(N')}_{u\alpha(d)}\cap
Prune(\mathcal{L}[u\alpha(d),N'],\mathcal{L}[u\alpha(d_u^{true}),N']))$
16 where $N'=lca(u\alpha(d),u\alpha(d_u^{true}))$ and
17 $\phi_\alpha$ is if $d=\mu_u(x_l)$ then $(fresh(p_1)\vee p_1=x_l)$ else $unmapped(p_1)$
18 if $U(u\alpha(d))=U(u\alpha(d_u^{true}))$ with $d\ne d_u^g$ for all $g\in G(u,\alpha)$ but
$u\alpha(d_u^{true})\not\simeq_{\{z\}}u\alpha(d)$ for some $z\in Z(u\alpha(d))$ then // transition(b)
19 $Refine(U(u),\alpha(p_1\mid\phi_\alpha)\cdot
(z^{u\alpha(d)}\cap
Prune(\mathcal{L}[u\alpha(d),N(z)],\mathcal{L}[u\alpha(d_u^{true}),N(z)])))$
20 where $\phi_\alpha$ is if $d=\mu_u(x_l)$ then $(fresh(p_1)\vee p_1=x_l)$ else $unmapped(p_1)$
21 if $u\simeq_{Z(u)}u$ but $u\alpha(d)\not\simeq_{Z(u\alpha(d))}u\alpha(d)$ then // register
22 $Refine(U(u),\alpha(p_1\mid\phi_\alpha)\cdot
(z^{(N)}_{u\alpha(d)}\cap Prune(\mathcal{L}[u\alpha(d),N],\gamma(\mathcal{L}[u\alpha(d),N]))))$
23 where $N=U(u\alpha(d))$ and $\phi_\alpha$ is if $d=d_u^{true}$ then $fresh(p_1)$ elif $d=\mu_u(x_l)$
then $p_1=x_l$ else $unmapped(p_1)$
24 until closed and consistent
25 $\mathcal{H}\leftarrow Hypothesis(CT)$
26 if $\exists w\in\Sigma^+$ s.t. $\mathcal{H}(w)\ne\mathcal{L}(w)$ then $\{Analyze(w); goto\ HYP\}$ else return $\mathcal{H}$
we can guarantee that the registers of u u u and non-phantom registers of u α ( d ) u\alpha(d) uα ( d ) can be correlated. Hence, if a register x l x_l x l in ϕ 1 ′ , … , ϕ m ′ \phi'_1,\ldots,\phi'_m ϕ 1 ′ , … , ϕ m ′ is not in m e m Z ( u ) ( u ) mem_{Z(u)}(u) m e m Z ( u ) ( u ) then x l x_l x l must be a phantom register and therefore refers to the data value d d d (at position ∣ u ∣ + 1 |u|+1 ∣ u ∣ + 1 ) so should be replaced by p 1 p_1 p 1 .
The complete algorithm, without any of the hidden features, is shown in Algorithm 5.
Details in Algorithm 3
Let us define the functions p o t m a t c h potmatch p o t ma t c h and p o t s u f f potsuff p o t s u f f in more detail. First, define a mapping μ i : p o t r e g s ( r p ( l i ) ) → V a l s ( w 1 : i ) \mu_i : potregs(rp(l_i)) \to Vals(w_{1:i}) μ i : p o t r e g s ( r p ( l i )) → V a l s ( w 1 : i ) to be position-injective if there is an injective mapping h : p o t r e g s ( r p ( l i ) ) → { 1 , … , i } h : potregs(rp(l_i)) \to\{1,\ldots,i\} h : p o t r e g s ( r p ( l i )) → { 1 , … , i } such that μ i ( x l ) = d h ( x l ) \mu_i(x_l) = d_{h(x_l)} μ i ( x l ) = d h ( x l ) (recall that d j d_j d j is the data value at position j j j in w w w ). Intuitively, a valuation is position-injective if it is injective when regarded as a mapping from registers to positions in a word. A basic property of mappings that occur in runs of form shown at the beginning of § 4.4 is that each valuation μ i \mu_i μ i is position-injective. This allows us to define the following restrictions during counterexample analysis.
For a data word w ′ w' w ′ , data value d d d , prefix u u u , and position-injective mapping μ \mu μ from p o t ( u ) pot(u) p o t ( u ) to V a l s ( w ′ ) Vals(w') V a l s ( w ′ ) , we define p o t m a t c h ( w ′ , d , u , μ ) potmatch(w',d,u,\mu) p o t ma t c h ( w ′ , d , u , μ ) , as the positions l l l in p o t ( u ) pot(u) p o t ( u ) such that there is a position-injective extension ν : p o t ( u ) ↦ V a l s ( w ′ ) \nu: pot(u) \mapsto Vals(w') ν : p o t ( u ) ↦ V a l s ( w ′ ) of μ \mu μ which maps the l t h l^{\mathrm{th}} l th data value in u u u to d d d . If d ∉ V a l s ( w ′ ) d \notin Vals(w') d ∈ / V a l s ( w ′ ) then p o t m a t c h ( w ′ , d , u , μ ) = ∅ potmatch(w',d,u,\mu) = \varnothing p o t ma t c h ( w ′ , d , u , μ ) = ∅ . Otherwise, p o t m a t c h ( w ′ , d , u , μ ) potmatch(w',d,u,\mu) p o t ma t c h ( w ′ , d , u , μ ) is the union of
the indices l l l such that x l x_l x l is a register in D o m ( μ ) Dom(\mu) D o m ( μ ) with μ ( x l ) = d \mu(x_l) = d μ ( x l ) = d , and
all indices l l l in p o t ( u ) pot(u) p o t ( u ) with x l ∉ D o m ( μ ) x_l \notin Dom(\mu) x l ∈ / D o m ( μ ) in the case that there are more occurrences of d d d in w ′ w' w ′ than in R a n ( μ ) Ran(\mu) R an ( μ ) (e.g., if d ∉ R a n ( μ ) d \notin Ran(\mu) d ∈ / R an ( μ ) ).
Intuitively, p o t m a t c h ( w ′ , d , u , μ ) potmatch(w',d,u,\mu) p o t ma t c h ( w ′ , d , u , μ ) denotes the indices l l l of u u u such that if a hypothesis reaches ⟨ u , μ ⟩ \langle u,\mu\rangle ⟨ u , μ ⟩ after a run over w ′ w' w ′ , then there is a position-injective extension ν \nu ν of μ \mu μ under which d d d will satisfy the guard p = x l p = x_l p = x l . This implies that possible guards p = x l p = x_l p = x l that may be relevant when checking the equivalence properties at lines Algorithm 3 or 9 of Algorithm 3 are given by p o t m a t c h ( w ′ , d , u , μ ) potmatch(w',d,u,\mu) p o t ma t c h ( w ′ , d , u , μ ) .
Let us assume that a run of the hypothesis over w 1 : i w_{1:i} w 1 : i reaches ⟨ u , μ ⟩ \langle u,\mu\rangle ⟨ u , μ ⟩ . Then we define p o t s u f f ( w 1 : i , w i + 1 : n , u , μ ) potsuff(w_{1:i},w_{i+1:n},u,\mu) p o t s u f f ( w 1 : i , w i + 1 : n , u , μ ) as the restricted suffix z i = α i + 1 ( p 1 ∣ ϕ 1 ) ⋯ α n ( p n − 1 ∣ ϕ n − 1 ) \mathbf{z}_i = \alpha_{i+1}(p_1\mid\phi_1)\cdots\alpha_n(p_{n-1}\mid\phi_{n-1}) z i = α i + 1 ( p 1 ∣ ϕ 1 ) ⋯ α n ( p n − 1 ∣ ϕ n − 1 ) , where each ϕ j \phi_j ϕ j is a disjunction of (i) f r e s h ( p j ) fresh(p_j) f r es h ( p j ) , (ii) p j = x l p_j = x_l p j = x l for l ∈ p o t m a t c h ( w 1 : i , d i + j , u , μ ) l \in potmatch(w_{1:i},d_{i+j},u,\mu) l ∈ p o t ma t c h ( w 1 : i , d i + j , u , μ ) , and (iii) p j = p j ′ p_j = p_{j'} p j = p j ′ for each prior parameter p j ′ p_{j'} p j ′ in the suffix such that d i + j = d i + j ′ d_{i+j} = d_{i+j'} d i + j = d i + j ′ .
Proof of Theorem 1
To prove Theorem 1, we will first prove the following invariants, each in a separate lemma, establishing correspondences between C T CT C T and L \mathcal{L} L after each round of counterexample analysis.
S L λ ^ SL_{\hat{\lambda}} S L λ ^ correctly partitions U U U into equivalence classes induced by the suffixes in Z Z Z .
If u , u ′ ∈ S p u,u' \in S_p u , u ′ ∈ S p and U ( u ) = U ( u ′ ) U(u) = U(u') U ( u ) = U ( u ′ ) , then there exists a suffix separating u u u and u ′ u' u ′ .
For any short prefix u ∈ S p u \in S_p u ∈ S p , α ∈ Σ \alpha\in\Sigma α ∈ Σ and g ∈ G Z ( u ) ( u , α ) g \in G_{Z(u)}(u,\alpha) g ∈ G Z ( u ) ( u , α ) , for each u α ( d ) u\alpha(d) uα ( d ) in U ( u α ( d g ) ) U(u\alpha(d^g)) U ( uα ( d g )) , there is a u u u -guard g ′ g' g ′ and restricted suffix z \mathbf{z} z such that – d d d is d g d^g d g , and – u α ( d ) ̸ ≡ z u α ( d ′ ) u\alpha(d) \not\equiv_{\mathbf{z}} u\alpha(d') uα ( d ) ≡ z uα ( d ′ ) for all d ′ d' d ′ different from d d d with u α ( d ′ ) u\alpha(d') uα ( d ′ ) in U ( u α ( d g ) ) U(u\alpha(d^g)) U ( uα ( d g )) .
We begin with the first lemma, which loosely states that two prefixes in C T CT C T are equivalent w.r.t. the restricted suffixes used to sift them if and only if they are in the same leaf.
Lemma 1. Let N N N be a leaf, u ∈ U − 1 ( N ) u \in U^{-1}(N) u ∈ U − 1 ( N ) and u ′ ∈ U u' \in U u ′ ∈ U . Then u ′ ∈ U − 1 ( N ) u' \in U^{-1}(N) u ′ ∈ U − 1 ( N ) iff u ′ ≃ Z ( N ) u u' \simeq_{Z(N)} u u ′ ≃ Z ( N ) u .
Proof. We will prove that u ′ ∈ U − 1 ( N ) u' \in U^{-1}(N) u ′ ∈ U − 1 ( N ) iff u ′ ≃ Z ( N ) r p ( N ) u' \simeq_{Z(N)} rp(N) u ′ ≃ Z ( N ) r p ( N ) ; the proof of Lemma 1 follows from transitivity. Let N 0 , … , N k N_0,\ldots,N_k N 0 , … , N k be the k k k ancestors of N N N , ordered from the root to the immediate ancestor of N N N , and let N k + 1 N_{k+1} N k + 1 denote N N N . This means that Z ( N ) = { z ( N i ) : 0 ≤ i ≤ k } Z(N)=\{z(N_i): 0 \leq i \leq k\} Z ( N ) = { z ( N i ) : 0 ≤ i ≤ k } . From the definition of S i f t Sift S i f t , it follows that
r p ( N ) ≃ z ( N i ) r p ( N i + 1 ) , where 0 ≤ i ≤ k (1) rp(N) \simeq_{z(N_i)} rp(N_{i+1}), \text{ where } 0 \leq i \leq k \tag*{(1)} r p ( N ) ≃ z ( N i ) r p ( N i + 1 ) , where 0 ≤ i ≤ k (1)
We will first prove, by contradiction, that u ′ ∈ U − 1 ( N ) u' \in U^{-1}(N) u ′ ∈ U − 1 ( N ) implies u ′ ≃ Z ( N ) r p ( N ) u' \simeq_{Z(N)} rp(N) u ′ ≃ Z ( N ) r p ( N ) . Assume that u ′ ∈ U − 1 ( N ) u' \in U^{-1}(N) u ′ ∈ U − 1 ( N ) but u ′ ̸ ≃ Z ( N ) r p ( N ) u' \not\simeq_{Z(N)} rp(N) u ′ ≃ Z ( N ) r p ( N ) . Then, there must exist a node N i N_i N i with 0 ≤ i ≤ k 0 \leq i \leq k 0 ≤ i ≤ k such that u ′ ̸ ≃ z ( N i ) r p ( N ) u' \not\simeq_{z(N_i)} rp(N) u ′ ≃ z ( N i ) r p ( N ) . From Eq. (1) , it follows that u ′ ̸ ≃ z ( N i ) r p ( N i + 1 ) u' \not\simeq_{z(N_i)} rp(N_{i+1}) u ′ ≃ z ( N i ) r p ( N i + 1 ) . But that means, from the definition of S i f t Sift S i f t , that u ′ u' u ′ could not have been sifted to N i + 1 N_{i+1} N i + 1 . This contradicts, if i < k i < k i < k , the assumption that N i + 1 N_{i+1} N i + 1 is an ancestor of N N N , or, if i = k i = k i = k , the assumption that u ′ ∈ U − 1 ( N ) u' \in U^{-1}(N) u ′ ∈ U − 1 ( N ) .
We will now prove that u ′ ≃ Z ( N ) r p ( N ) u' \simeq_{Z(N)} rp(N) u ′ ≃ Z ( N ) r p ( N ) implies u ′ ∈ U − 1 ( N ) u' \in U^{-1}(N) u ′ ∈ U − 1 ( N ) , also with a proof by contradiction. Assume that u ′ ≃ Z ( N ) r p ( N ) u' \simeq_{Z(N)} rp(N) u ′ ≃ Z ( N ) r p ( N ) but u ′ ∉ U − 1 ( N ) u' \notin U^{-1}(N) u ′ ∈ / U − 1 ( N ) . From the definition of S i f t Sift S i f t , it follows that there must be a node N i N_i N i with 0 ≤ i ≤ k 0 \leq i \leq k 0 ≤ i ≤ k such that u ′ u' u ′ does not sift to N i + 1 N_{i+1} N i + 1 . In other words, there exists an i ∈ [ 0 , k ] i \in[0,k] i ∈ [ 0 , k ] such that u ′ ̸ ≃ z ( N i ) r p ( N i + 1 ) u' \not\simeq_{z(N_i)} rp(N_{i+1}) u ′ ≃ z ( N i ) r p ( N i + 1 ) . From Eq. (1) , it follows that u ′ ̸ ≃ z ( N i ) r p ( N ) u' \not\simeq_{z(N_i)} rp(N) u ′ ≃ z ( N i ) r p ( N ) , which contradicts the assumption that u ′ ≃ Z ( N ) r p ( N ) u' \simeq_{Z(N)} rp(N) u ′ ≃ Z ( N ) r p ( N ) . □ \square □
Next, we show that if there are two short prefixes in the same leaf, then there exists a restricted suffix (which may not yet be in C T CT C T ) that separates them.
Lemma 2. Let u , u ′ ∈ S p u,u' \in S_p u , u ′ ∈ S p with U ( u ) = U ( u ′ ) U(u)=U(u') U ( u ) = U ( u ′ ) . Then there exists a restricted suffix z ∉ Z ( u ) z \notin Z(u) z ∈ / Z ( u ) such that u ̸ ≃ { z } u ′ u \not\simeq_{\{z\}}u' u ≃ { z } u ′ .
Proof. A prefix is only added to S p S_p S p with a call to E x p a n d Expand E x p an d , which occurs in only two cases: (i) when resolving location closedness in Algorithm 2 (line 5), or (ii) when a new location is found in Algorithm 3 (line 10). Let u , u ′ ∈ S p u,u' \in S_p u , u ′ ∈ S p with U ( u ) = U ( u ′ ) U(u)=U(u') U ( u ) = U ( u ′ ) , and assume w.l.o.g. that u u u was added to S p S_p S p before u ′ u' u ′ . Since U ( u ′ ) ∩ S p U(u') \cap S_p U ( u ′ ) ∩ S p was not equal to ∅ \varnothing ∅ when u ′ u' u ′ was added to S p S_p S p , it can not be that u ′ u' u ′ was added in case (i), so u ′ u' u ′ must have been added in case (ii). Hence, there must exist a restricted suffix z z z such that u ′ ̸ ≃ { z } u u' \not\simeq_{\{z\}} u u ′ ≃ { z } u . Since U ( u ) = U ( u ′ ) U(u)=U(u') U ( u ) = U ( u ′ ) , by Lemma 1, u ≃ Z ( u ) u ′ u \simeq_{Z(u)} u' u ≃ Z ( u ) u ′ , which implies that z ∉ Z ( u ) z \notin Z(u) z ∈ / Z ( u ) . □ \square □
Next, we show that we never add any “unnecessary” transitions to H \mathcal{H} H . In other words, each extension u α ( d u g ) ∈ U u\alpha(d^g_u) \in U uα ( d u g ) ∈ U of a short prefix u ∈ S p u \in S_p u ∈ S p corresponds to some unique guard g g g induced by some restricted suffix.
Lemma 3. For any short prefix u ∈ S p u \in S_p u ∈ S p , α ∈ Σ \alpha\in\Sigma α ∈ Σ and u α ( d ) ∈ U u\alpha(d) \in U uα ( d ) ∈ U ,
(i) there is a u u u -guard g g g such that g g g is d u g d^g_u d u g , and
(ii) for any other u u u -guard g ′ g' g ′ with u α ( d u g ′ ) ∈ U u\alpha(d^{g'}_u) \in U uα ( d u g ′ ) ∈ U , we have either that g ∧ g ′ g \land g' g ∧ g ′ is unsatisfiable when registers are valued as in μ u \mu_u μ u or that there is a restricted suffix z z z such that u α ( d u g ) ̸ ≃ { z } i d u α ( d u g ′ ) u\alpha(d^g_u) \not\simeq^{\mathrm{id}}_{\{z\}} u\alpha(d^{g'}_u) uα ( d u g ) ≃ { z } id uα ( d u g ′ ) .
Proof. There exist only three cases where one-symbol extensions are added to C T CT C T :
In the call to Expand in Algorithm 1 (line 11).
When resolving transition closedness in Algorithm 2 (line 7).
When a new transition is discovered during counterexample analysis in Algorithm 3.
In case 1, one-symbol extensions u α ( d u g ) u\alpha(d^{g}_{u}) uα ( d u g ) are sifted for each g ∈ G Z ( u ) ( u , α ) g \in G_{Z(u)}(u,\alpha) g ∈ G Z ( u ) ( u , α ) . Note that since we never expand a prefix that is already short and U U U is prefix-closed, it follows that U U U does not contain any one-symbol extensions u α ( d ) u\alpha(d) uα ( d ) prior to sifting the one-symbol extensions u α ( d u g ) u\alpha(d^{g}_{u}) uα ( d u g ) . Since the one-symbol extensions u α ( d u g ) u\alpha(d^{g}_{u}) uα ( d u g ) are by construction all separated by some suffix, it follows that Lemma 3 is true.
In case 2, Lemma 3 is trivially true, since, in this case, a one-symbol extension u α ( d u g ) ∉ U u\alpha(d^{g}_{u}) \notin U uα ( d u g ) ∈ / U is sifted for some guard g ∈ G Z ( u ) ( u , α ) g \in G_{Z(u)}(u,\alpha) g ∈ G Z ( u ) ( u , α ) . If there is another guard g ′ ∈ G Z ( u ) ( u , α ) g' \in G_{Z(u)}(u,\alpha) g ′ ∈ G Z ( u ) ( u , α ) then it must be that u α ( d u g ) ̸ ≃ Z ( u ) i d u α ( d u g ′ ) u\alpha(d^{g}_{u}) \not\simeq^{\mathrm{id}}_{Z(u)} u\alpha(d^{g'}_{u}) uα ( d u g ) ≃ Z ( u ) id uα ( d u g ′ ) .
In case 3, using the notation of Algorithm 3, a one-symbol extension u i − 1 α i ( d i ′ ) u_{i-1}\alpha_i(d'_{i}) u i − 1 α i ( d i ′ ) is added to U U U by sifting, where u i − 1 ∈ S p u_{i-1} \in S_p u i − 1 ∈ S p , g i ∈ G Z ( u i − 1 ) ( u i − 1 , α i ) g_i \in G_{Z(u_{i-1})}(u_{i-1},\alpha_i) g i ∈ G Z ( u i − 1 ) ( u i − 1 , α i ) and g i ′ ∈ G { z i − 1 } ( u i − 1 , α i ) g'_i \in G_{\{z_{i-1}\}}(u_{i-1},\alpha_i) g i ′ ∈ G { z i − 1 } ( u i − 1 , α i ) for some restricted suffix z i − 1 z_{i-1} z i − 1 such that u i − 1 α i ( d i ′ ) ̸ ≃ { z i } i d u i − 1 α i ( d u i − 1 t r u e ) u_{i-1}\alpha_i(d'_i) \not\simeq^{\mathrm{id}}_{\{z_i\}} u_{i-1}\alpha_i(d^{\mathrm{true}}_{u_{i-1}}) u i − 1 α i ( d i ′ ) ≃ { z i } id u i − 1 α i ( d u i − 1 true ) for all d i ′ d'_i d i ′ such that d i ′ = μ u i − 1 ( x l ) d'_i = \mu_{u_{i-1}}(x_l) d i ′ = μ u i − 1 ( x l ) for l ∈ potmatch ( w 1 : i − 1 , d i , u i − 1 , μ i − 1 ∘ ρ u i − 1 ) l \in\operatorname{potmatch}(w_{1:i-1},d_i,u_{i-1},\mu_{i-1}\circ\rho_{u_{i-1}}) l ∈ potmatch ( w 1 : i − 1 , d i , u i − 1 , μ i − 1 ∘ ρ u i − 1 ) . Condition (i) of this lemma is trivially true, as d i ′ d'_i d i ′ is a representative data value for the guard p = x l p=x_l p = x l . For condition (ii), let N = U ( u i − 1 α i ( d u i − 1 g i ) ) N=U(u_{i-1}\alpha_i(d^{g_i}_{u_{i-1}})) N = U ( u i − 1 α i ( d u i − 1 g i )) . If u i − 1 α i ( d i ′ ) u_{i-1}\alpha_i(d'_i) u i − 1 α i ( d i ′ ) sifts to the node N N N , then it is separated from u i − 1 α i ( d u i − 1 t r u e ) u_{i-1}\alpha_i(d^{\mathrm{true}}_{u_{i-1}}) u i − 1 α i ( d u i − 1 true ) by construction. □ \square □
Note that, as a consequence of Lemma 3, S L ≡ λ SL^\lambda_{\equiv} S L ≡ λ never adds a one-symbol extension u α ( d u g ) u\alpha(d^{g}_{u}) uα ( d u g ) more than once. Since a representative data value d u g d^{g}_{u} d u g for a u u u -guard g g g is unique, it therefore follows from Lemma 3 that there is an upper bound on the number of one-symbol extensions in C T CT C T .
To prepare for proving that Algorithm 3 will make progress by finding a discrepancy, we first show that a run of H \mathcal{H} H over a word w w w , which does not exhibit any discrepancy of the forms that Algorithm 3 searches for, correctly classifies w w w .
Lemma 4. Let H \mathcal{H} H be a hypothesis formed from a closed and consistent C T CT C T . Let w = α 1 ( d 1 ) ⋯ α n ( d n ) w=\alpha_1(d_1)\cdots\alpha_n(d_n) w = α 1 ( d 1 ) ⋯ α n ( d n ) be a word, and let
⟨ l 0 , μ 0 ⟩ → α 1 ( d 1 ) ⟨ l 1 , μ 1 ⟩ ⋯ ⟨ l n − 1 , μ n − 1 ⟩ → α n ( d n ) ⟨ l n , μ n ⟩ \langle l_0,\mu_0\rangle\xrightarrow{\alpha_1(d_1)} \langle l_1,\mu_1\rangle\ \cdots\ \langle l_{n-1},\mu_{n-1}\rangle\xrightarrow{\alpha_n(d_n)} \langle l_n,\mu_n\rangle ⟨ l 0 , μ 0 ⟩ α 1 ( d 1 ) ⟨ l 1 , μ 1 ⟩ ⋯ ⟨ l n − 1 , μ n − 1 ⟩ α n ( d n ) ⟨ l n , μ n ⟩ be an initialized run of H \mathcal{H} H over w w w . Let the i t h i^{\mathrm{th}} i th step in the above run be derived from a transition ⟨ l i − 1 , α i ( p ) , g i , π i , l i ⟩ \langle l_{i-1},\alpha_i(p),g_i,\pi_i,l_i\rangle ⟨ l i − 1 , α i ( p ) , g i , π i , l i ⟩ in H \mathcal{H} H . If for each i = 1 , … , n i=1,\ldots,n i = 1 , … , n it is the case that for each u i − 1 ∈ ( U − 1 ( l i − 1 ) ∩ S p ) u_{i-1}\in(U^{-1}(l_{i-1})\cap S_p) u i − 1 ∈ ( U − 1 ( l i − 1 ) ∩ S p )
u i − 1 α i ( d i ′ ) ≃ { z i } i d u i − 1 α i ( d u i − 1 t r u e ) u_{i-1}\alpha_i(d'_i)\simeq^{\mathrm{id}}_{\{z_i\}}u_{i-1}\alpha_i(d^{\mathrm{true}}_{u_{i-1}}) u i − 1 α i ( d i ′ ) ≃ { z i } id u i − 1 α i ( d u i − 1 true ) for all l ∈ potmatch ( w 1 : i − 1 , d i , u i − 1 , μ i − 1 ∘ ρ u i − 1 ) l\in\operatorname{potmatch}(w_{1:i-1},d_i,u_{i-1},\mu_{i-1}\circ\rho_{u_{i-1}}) l ∈ potmatch ( w 1 : i − 1 , d i , u i − 1 , μ i − 1 ∘ ρ u i − 1 ) such that d i ′ = μ u i − 1 ( x l ) d'_i=\mu_{u_{i-1}}(x_l) d i ′ = μ u i − 1 ( x l ) , and
for each d i ′ d'_i d i ′ with l i = U ( u i − 1 α i ( d i ′ ) ) l_i=U(u_{i-1}\alpha_i(d'_i)) l i = U ( u i − 1 α i ( d i ′ )) there is some u i ∈ ( U − 1 ( l i ) ∩ S p ) u_i\in(U^{-1}(l_i)\cap S_p) u i ∈ ( U − 1 ( l i ) ∩ S p ) such that u i α i ( d i ′ ) ≃ { z i } γ i u i u_i\alpha_i(d'_i)\simeq^{\gamma_i}_{\{z_i\}}u_i u i α i ( d i ′ ) ≃ { z i } γ i u i for some γ i \gamma_i γ i which agrees with ρ ( u i − 1 α i ( d i ′ ) ) → u i \rho_{(u_{i-1}\alpha_i(d'_i))\to u_i} ρ ( u i − 1 α i ( d i ′ )) → u i on the intersection of their domains,
where z i = potsuff ( w 1 : i , w i + 1 : n , u i − 1 α i ( d i ′ ) , [ x ∣ u i − 1 ∣ + 1 ↦ w i ] ∘ μ i − 1 ∘ ρ u i − 1 ) z_i = \operatorname{potsuff}(w_{1:i}, w_{i+1:n}, u_{i-1}\alpha_i(d'_i), [x_{|u_{i-1}|+1} \mapsto w_i] \circ\mu_{i-1} \circ\rho_{u_{i-1}}) z i = potsuff ( w 1 : i , w i + 1 : n , u i − 1 α i ( d i ′ ) , [ x ∣ u i − 1 ∣ + 1 ↦ w i ] ∘ μ i − 1 ∘ ρ u i − 1 ) , then the above run of H \mathcal{H} H over w w w classifies w w w correctly.
In the last equivalence u i − 1 α i ( d i ) ≃ { z i } u i u_{i-1}\alpha_i(d_i) \simeq_{\{z_i\}} u_i u i − 1 α i ( d i ) ≃ { z i } u i , the mapping γ i \gamma_i γ i should be consistent with the already existing mapping between registers induced by Z ( r p ( l i ) ) \mathbf{Z}(rp(l_i)) Z ( r p ( l i )) .
For a restricted suffix z = α 1 ′ ( p 1 ∣ φ 1 ) ⋯ α m ′ ( p m ∣ φ m ) z = \alpha'_1(p_1 \mid\varphi_1) \cdots\alpha'_m(p_m \mid\varphi_m) z = α 1 ′ ( p 1 ∣ φ 1 ) ⋯ α m ′ ( p m ∣ φ m ) , we write φ ‾ \overline{\varphi} φ for φ 1 , … , φ m \varphi_1,\ldots,\varphi_m φ 1 , … , φ m . In the following proof, we regard a ( u , z ) (u,z) ( u , z ) -tree T T T together with a valuation μ \mu μ over potregs ( u ) \operatorname{potregs}(u) potregs ( u ) as a function ⟦ T ⟧ μ \llbracket T \rrbracket_\mu [ [ T ] ] μ whose domain is the set of tuples d ′ \mathbf{d}' d ′ such that μ ⊨ φ ‾ [ d ′ / p ‾ ] \mu\models\overline{\varphi}[\mathbf{d}'/\overline{p}] μ ⊨ φ [ d ′ / p ] (i.e., which satisfy all guards in the restriction φ ‾ \overline{\varphi} φ of z z z ), whose range is { + , − } \{+,-\} { + , − } , and which maps a tuple d ′ \mathbf{d}' d ′ in its domain to T ( g ‾ ) T(\overline{g}) T ( g ) whenever d ′ \mathbf{d}' d ′ satisfies all guards in g ‾ \overline{g} g .
Proof. Assume w.l.o.g. that w ∉ L w \notin L w ∈ / L . Assume that the initialized run of H \mathcal{H} H over w w w is as in the statement of the lemma, implying that for each i = 1 , … , n i=1,\ldots,n i = 1 , … , n we have μ i − 1 ⊨ g i [ d i / p ] \mu_{i-1} \models g_i[d_i/p] μ i − 1 ⊨ g i [ d i / p ] , and also μ i = μ i − 1 ∘ [ p ↦ d i ] ∘ π i \mu_i = \mu_{i-1} \circ[p \mapsto d_i] \circ\pi_i μ i = μ i − 1 ∘ [ p ↦ d i ] ∘ π i for i = 1 , … , n i=1,\ldots,n i = 1 , … , n . Assume that the conditions in the statement of the lemma hold. We will inductively construct a sequence u ^ 0 , u ^ 1 , … , u ^ n \hat{u}_0,\hat{u}_1,\ldots,\hat{u}_n u ^ 0 , u ^ 1 , … , u ^ n of short prefixes such that l i = U ( u ^ i ) l_i = U(\hat{u}_i) l i = U ( u ^ i ) for i = 0 , … , n i=0,\ldots,n i = 0 , … , n . For i = 0 , … , n i=0,\ldots,n i = 0 , … , n , we will write x ‾ i \overline{x}_i x i for the registers of u ^ i \hat{u}_i u ^ i and p ‾ i \overline{p}_i p i for p 1 , … , p n − i p_1,\ldots,p_{n-i} p 1 , … , p n − i . We will also construct a sequence κ 0 , κ 1 , … , κ n \kappa_0,\kappa_1,\ldots,\kappa_n κ 0 , κ 1 , … , κ n , where each κ i : mem z i ( u ^ i ) → Vals ( w 1 : i ) \kappa_i : \operatorname{mem}_{z_i}(\hat{u}_i) \to\operatorname{Vals}(w_{1:i}) κ i : mem z i ( u ^ i ) → Vals ( w 1 : i ) is consistent with μ i ∘ ρ u ^ i \mu_i \circ\rho_{\hat{u}_i} μ i ∘ ρ u ^ i . We let d ~ i \widetilde{d}_i d i be the tuple d i + j , … , d n d_{i+j},\ldots,d_n d i + j , … , d n . By induction, we will establish that for i = 0 , … , n i=0,\ldots,n i = 0 , … , n we have ⟦ L [ u ^ i , z i ] ⟧ κ i ( d ~ i ) = − \llbracket L[\hat{u}_i,z_i]\rrbracket_{\kappa_i}(\widetilde{d}_i) = - [ [ L [ u ^ i , z i ] ] ] κ i ( d i ) = − , i.e., that the SDT for the prefix u ^ i \hat{u}_i u ^ i and restricted suffix z i z_i z i under the valuation κ i \kappa_i κ i evaluates the tuple of suffix data values to − - − . By taking i i i as n n n , we conclude that the SDT L [ u ^ n , z n ] L[\hat{u}_n,z_n] L [ u ^ n , z n ] , whose domain contains only the empty path (for the empty suffix), is non-accepting, implying that the final location in the run, i.e., l n = U ( u ^ n ) l_n = U(\hat{u}_n) l n = U ( u ^ n ) , is non-accepting, thereby proving the lemma.
(Base case) We let u ^ 0 \hat{u}_0 u ^ 0 be the empty sequence and κ 0 \kappa_0 κ 0 be the empty valuation; then ⟦ L [ u ^ 0 , z 0 ] ⟧ κ 0 ( d ~ 0 ) = − \llbracket L[\hat{u}_0,z_0]\rrbracket_{\kappa_0}(\widetilde{d}_0) = - [ [ L [ u ^ 0 , z 0 ] ] ] κ 0 ( d 0 ) = − is trivially true, since the branches in L [ u 0 , z 0 ] L[u_0,z_0] L [ u 0 , z 0 ] correspond to entire words of length n n n , which are mapped to { + , − } \{+,-\} { + , − } in accordance with L L L .
(Inductive step) We assume ⟦ L [ u ^ i − 1 , z i − 1 ] ⟧ κ i − 1 ( d ~ i − 1 ) = − \llbracket L[\hat{u}_{i-1},z_{i-1}]\rrbracket_{\kappa_{i-1}}(\widetilde{d}_{i-1}) = - [ [ L [ u ^ i − 1 , z i − 1 ] ] ] κ i − 1 ( d i − 1 ) = − as inductive hypothesis; we must find u ^ i \hat{u}_i u ^ i and κ i \kappa_i κ i and establish that ⟦ L [ u ^ i , z i ] ⟧ κ i ( d ~ i ) = − \llbracket L[\hat{u}_i,z_i]\rrbracket_{\kappa_i}(\widetilde{d}_i) = - [ [ L [ u ^ i , z i ] ] ] κ i ( d i ) = − . Let the valuation ν i − 1 \nu_{i-1} ν i − 1 be the union of μ i − 1 ∘ ρ u ^ i − 1 \mu_{i-1} \circ\rho_{\hat{u}_{i-1}} μ i − 1 ∘ ρ u ^ i − 1 and κ i − 1 \kappa_{i-1} κ i − 1 ; this valuation exists since μ i − 1 ∘ ρ u ^ i − 1 \mu_{i-1} \circ\rho_{\hat{u}_{i-1}} μ i − 1 ∘ ρ u ^ i − 1 and κ i − 1 \kappa_{i-1} κ i − 1 are consistent, implying that ν i − 1 ⊨ g i [ d i / p ] \nu_{i-1} \models g_i[d_i/p] ν i − 1 ⊨ g i [ d i / p ] . Among the guards in G { z i − 1 } ( u ^ i − 1 , α i ) G_{\{z_{i-1}\}}(\hat{u}_{i-1},\alpha_i) G { z i − 1 } ( u ^ i − 1 , α i ) , choose g i ′ g'_i g i ′ such that κ i − 1 ⊨ g i ′ [ d i / p ] \kappa_{i-1} \models g'_i[d_i/p] κ i − 1 ⊨ g i ′ [ d i / p ] (such a g i ′ g'_i g i ′ can always be found), implying that ν i − 1 ⊨ g i ′ [ d i / p ] \nu_{i-1} \models g'_i[d_i/p] ν i − 1 ⊨ g i ′ [ d i / p ] . Thus, in L [ u ^ i − 1 , z i − 1 ] κ i − 1 L[\hat{u}_{i-1},z_{i-1}]_{\kappa_{i-1}} L [ u ^ i − 1 , z i − 1 ] κ i − 1 the data value d i d_i d i (i.e., the first in the tuple d ~ i − 1 \widetilde{d}_{i-1} d i − 1 ) may take the branch which corresponds to g i ′ g'_i g i ′ . From the construction of SDTs, it leads to L [ u ^ i − 1 α i ( d i ′ ) , z i ] L[\hat{u}_{i-1}\alpha_i(d'_i),z_i] L [ u ^ i − 1 α i ( d i ′ ) , z i ] , and by the inductive hypothesis we have
[ σ u ^ i − 1 ( L [ u ^ i − 1 α i ( d i ′ ) , z i ] ) ] κ i − 1 ( d ~ i − 1 ) = − [\sigma_{\hat{u}_{i-1}}(L[\hat{u}_{i-1}\alpha_i(d'_i),z_i])]_{\kappa_{i-1}}(\widetilde{d}_{i-1}) = - [ σ u ^ i − 1 ( L [ u ^ i − 1 α i ( d i ′ ) , z i ]) ] κ i − 1 ( d i − 1 ) = −
where σ k \sigma_k σ k transforms an SDT by replacing x k + 1 x_{k+1} x k + 1 by p 1 p_1 p 1 , and p j p_j p j by p j + 1 p_{j+1} p j + 1 for j = 1 , … , ( n − k − 1 ) j=1,\ldots,(n-k-1) j = 1 , … , ( n − k − 1 ) , i.e., σ k \sigma_k σ k performs the renamings to transform an SDT constructed with a prefix of length k + 1 k+1 k + 1 “one step backwards”. Let u ^ i \hat{u}_i u ^ i be a short prefix u i u_i u i that satisfies Condition 2, i.e. we have L [ u ^ i − 1 α i ( d i ′ ) , z i ] ≡ γ ^ i − 1 ( L [ u ^ i , z i ] ) L[\hat{u}_{i-1}\alpha_i(d'_i),z_i] \equiv\hat{\gamma}_i^{-1}(L[\hat{u}_i,z_i]) L [ u ^ i − 1 α i ( d i ′ ) , z i ] ≡ γ ^ i − 1 ( L [ u ^ i , z i ]) . Thus, defining κ i \kappa_i κ i by κ i = κ i − 1 ∘ σ ∣ u ^ i − 1 ∣ ∘ γ ^ i − 1 \kappa_i = \kappa_{i-1} \circ\sigma_{| \hat{u}_{i-1}|} \circ\hat{\gamma}_i^{-1} κ i = κ i − 1 ∘ σ ∣ u ^ i − 1 ∣ ∘ γ ^ i − 1 , we derive
⟦ L [ u ^ i , z i ] ⟧ κ i ( d ~ i ) = ⟦ σ ∣ u ^ i − 1 ∣ ∘ γ ^ i − 1 ( L [ u ^ i , z i ] ) ⟧ κ i ( d ~ i ) = ⟦ σ ∣ u ^ i − 1 ∣ ( L [ u ^ i − 1 α i ( d i ′ ) , z i − 1 ] ) ⟧ κ i − 1 ( d ~ i − 1 ) = − \begin{aligned}
\llbracket L[\hat{u}_i,z_i]\rrbracket_{\kappa_i}(\tilde{d}_i)
&= \llbracket\sigma_{|\hat{u}_{i-1}|} \circ\hat{\gamma}_i^{-1}(L[\hat{u}_i,z_i])\rrbracket_{\kappa_i}(\tilde{d}_i) \\
&= \llbracket\sigma_{|\hat{u}_{i-1}|}(L[\hat{u}_{i-1}\alpha_i(d'_i),z_{i-1}])\rrbracket_{\kappa_{i-1}}(\tilde{d}_{i-1}) \\
&= -
\end{aligned} [ [ L [ u ^ i , z i ] ] ] κ i ( d ~ i ) = [ [ σ ∣ u ^ i − 1 ∣ ∘ γ ^ i − 1 ( L [ u ^ i , z i ]) ] ] κ i ( d ~ i ) = [ [ σ ∣ u ^ i − 1 ∣ ( L [ u ^ i − 1 α i ( d i ′ ) , z i − 1 ]) ] ] κ i − 1 ( d ~ i − 1 ) = −
thereby completing the inductive step.
Based on Lemma 4 , we can now show that each round of counterexample analysis leads to either an additional short prefix or one-symbol extension being added to C T CT C T .
Lemma 5. Let C T CT C T be a closed and consistent classification tree. A counterexample always leads to introducing a new prefix (Case 1 of Algorithm 3) or a new short prefix (Case 2 of Algorithm 3) into C T CT C T .
Proof. Let H \mathcal{H} H be a hypothesis formed from C T CT C T and let w = α 1 ( d 1 ) … α n ( d n ) w = \alpha_1(d_1)\ldots\alpha_n(d_n) w = α 1 ( d 1 ) … α n ( d n ) be a word. Assume that there is a misclassifying run of H \mathcal{H} H over w w w and let
⟨ l 0 , μ 0 ⟩ → α 1 ( d 1 ) ⟨ l 1 , μ 1 ⟩ ⋯ ⟨ l n − 1 , μ n − 1 ⟩ → α n ( d n ) ⟨ l n , μ n ⟩ \langle l_0,\mu_0\rangle\xrightarrow{\alpha_1(d_1)} \langle l_1,\mu_1\rangle\ \cdots\ \langle l_{n-1},\mu_{n-1}\rangle\xrightarrow{\alpha_n(d_n)} \langle l_n,\mu_n\rangle ⟨ l 0 , μ 0 ⟩ α 1 ( d 1 ) ⟨ l 1 , μ 1 ⟩ ⋯ ⟨ l n − 1 , μ n − 1 ⟩ α n ( d n ) ⟨ l n , μ n ⟩ be such a misclassifying run. For i = 1 , … , n i = 1,\ldots,n i = 1 , … , n , let z i = A c t s ( w i + 1 : n ) z_i = Acts(w_{i+1:n}) z i = A c t s ( w i + 1 : n ) , and let the i i i th step in the above run be derived from a transition ⟨ l i − 1 , α i ( p ) , g i , π i , l i ⟩ \langle l_{i-1},\alpha_i(p),g_i,\pi_i,l_i\rangle ⟨ l i − 1 , α i ( p ) , g i , π i , l i ⟩ in H \mathcal{H} H . If analysis of w w w does not lead to the introduction of a new prefix or short prefix into C T CT C T , then for each i = 1 , … , n i = 1,\ldots,n i = 1 , … , n it must be the case that for each u i − 1 ∈ ( U − 1 ( l i − 1 ) ∩ S p ) u_{i-1} \in(U^{-1}(l_{i-1}) \cap S_p) u i − 1 ∈ ( U − 1 ( l i − 1 ) ∩ S p )
u i − 1 α i ( d i ′ ) ≃ { z i } u i − 1 α i ( d u i − 1 t r u e ) u_{i-1}\alpha_i(d'_i) \mathrel{\simeq_{\{z_i\}}} u_{i-1}\alpha_i(d^{\mathrm{true}}_{u_{i-1}}) u i − 1 α i ( d i ′ ) ≃ { z i } u i − 1 α i ( d u i − 1 true ) for all l ∈ p o t m a t c h ( w 1 : i − 1 , d i , u i − 1 , μ i − 1 ∘ ρ u i − 1 ) l \in potmatch(w_{1:i-1},d_i,u_{i-1},\mu_{i-1}\circ\rho_{u_{i-1}}) l ∈ p o t ma t c h ( w 1 : i − 1 , d i , u i − 1 , μ i − 1 ∘ ρ u i − 1 ) such that d i ′ = μ u i − 1 ( x l ) d'_i = \mu_{u_{i-1}}(x_l) d i ′ = μ u i − 1 ( x l ) , and
for each d i ′ d'_i d i ′ with l i = U ( u i − 1 α i ( d i ′ ) ) l_i = U(u_{i-1}\alpha_i(d'_i)) l i = U ( u i − 1 α i ( d i ′ )) there is some u i ∈ ( U − 1 ( l i ) ∩ S p ) u_i \in(U^{-1}(l_i)\cap S_p) u i ∈ ( U − 1 ( l i ) ∩ S p ) such that u i − 1 α i ( d i ′ ) ≃ { z i } u i u_{i-1}\alpha_i(d'_i) \mathrel{\simeq_{\{z_i\}}} u_i u i − 1 α i ( d i ′ ) ≃ { z i } u i for some γ ^ i \hat{\gamma}_i γ ^ i which agrees with ρ ( u i − 1 α i ( d i ′ ) ) ↦ u i \rho_{(u_{i-1}\alpha_i(d'_i))\mapsto u_i} ρ ( u i − 1 α i ( d i ′ )) ↦ u i on the intersection of their domains, where z i = p o t s u f f ( w 1 : i , w i + 1 : n , u i − 1 α i ( d i ′ ) , [ x ∣ u i − 1 ∣ + 1 ↦ w i ] ∘ μ i − 1 ∘ ρ u i − 1 ) z_i = potsuff(w_{1:i},w_{i+1:n},u_{i-1}\alpha_i(d'_i),[x_{|u_{i-1}|+1}\mapsto w_i]\circ\mu_{i-1}\circ\rho_{u_{i-1}}) z i = p o t s u f f ( w 1 : i , w i + 1 : n , u i − 1 α i ( d i ′ ) , [ x ∣ u i − 1 ∣ + 1 ↦ w i ] ∘ μ i − 1 ∘ ρ u i − 1 ) , then the above run of H \mathcal{H} H over w w w classifies w w w correctly.
It then follows from Lemma 4 that the above run of H \mathcal{H} H over w w w classifies w w w correctly, which contradicts the assumption that this is a misclassifying run.
We can now prove Theorem 1.
Proof. (of Theorem 1) Lemmas 4 and 5 show that if there exists a w ∈ Σ + w \in\Sigma^+ w ∈ Σ + such that H ( w ) ≠ L ( w ) \mathcal{H}(w) \ne\mathcal{L}(w) H ( w ) = L ( w ) then S L = λ SL^\lambda_{=} S L = λ will add a new short prefix or a new one-symbol extension to C T CT C T . Since, as Lemmas 1 to 3 show, S L = λ SL^\lambda_{=} S L = λ correctly classifies each short prefix and one-symbol extension, and the number of short prefixes and one-symbol extensions is bounded, this implies that eventually H ( w ) = L ( w ) \mathcal{H}(w) = \mathcal{L}(w) H ( w ) = L ( w ) for all w ∈ Σ + w \in\Sigma^+ w ∈ Σ + , at which point H \mathcal{H} H is, by definition, an acceptor of L \mathcal{L} L . Since each location in H \mathcal{H} H corresponds to a leaf of C T CT C T , it follows from Lemma 1 that the number of locations of H \mathcal{H} H is the same as the number of equivalence classes w.r.t. ≃ L \simeq_{\mathcal{L}} ≃ L , proving minimality.