Abstract:
A method of semantic translation of a class of diagrams to input/output-extended finite automata is provided. The method includes receiving a data representation of a diagram, said diagram comprising a plurality of blocks and said diagram being associated with a graphical modeling environment which defines semantics for executing the diagram, and processing, using a computing device, the data representation of the diagram to translate the diagram to an input/output-extended finite automata model.

Description:
CROSS-REFERENCE TO RELATED APPLICATIONS 
       [0001]    This application claims priority under 35 U.S.C. §119 of a provisional application Ser. No. 61/357,568 filed Jun. 23, 2010, and which application is hereby incorporated by reference in its entirety. 
     
    
     GRANT REFERENCE 
       [0002]    This invention was made with government support under Grant No. NSF-CCF-0811541 awarded by the National Science Foundation. The government has certain rights in the invention. 
     
    
     FIELD OF THE INVENTION 
       [0003]    The present invention relates to a semantic translation approach for diagrams associated with graphical modeling and simulation environments or tools. The semantic translation generates a model which may be used for further analysis such as test generation and formal verification. 
       BACKGROUND OF THE INVENTION 
       [0004]    Graphical modeling and simulation environments or tools allow users to construct and analyze models of processes or systems using diagrams. There are various examples of such tools commercially available. One such example is Simulink from The MathWorks, Inc. A further example of a graphical modeling and simulation environments is Lab VIEW, available from National Instruments Corporation. 
         [0005]    Typically, these diagrams describe computations or logic which can ultimately be implemented using application specific devices, computers, microcontrollers, FPGA, integrated circuits, or computing devices. The diagrams are built using elements or blocks which are interconnected. The diagrams are created within a graphical modeling environment which defines the semantics for executing the diagrams. Software systems or descriptions of hardware systems may then be produced which exhibit the behavior of the model or portions thereof. 
         [0006]    The Simulink diagrams can be simulated to generate sample-runs (runs on sample times) which provide a means for their validation. Other means of validation include testing and verification. In order to be able to test a Simulink diagram or verify an implementation of a Simulink diagram, it is desirable to translate such diagrams into a form amenable to automated test generation or verification. Thus the corresponding techniques and tools for such translation are needed. 
       BRIEF SUMMARY OF THE INVENTION 
       [0007]    Therefore, it is a primary object, feature, or advantage of the present invention to improve over the state of the art. 
         [0008]    It is a further object, feature, or advantage of the present invention to a semantic translation approach which is recursive. 
         [0009]    It is a still further object, feature, or advantage of the present invention to provide a semantic translation approach which is amenable to automated test generation and verification. 
         [0010]    It is a still further object, feature, or advantage of the present invention to provide a semantic translation approach which has no special restriction on the types of blocks. 
         [0011]    It is a still further object, feature, or advantage of the present invention to provide a semantic translation approach which is sound and complete. 
         [0012]    According to one aspect of the present invention, a method of semantic translation of a diagram associated with a graphical modeling environment into an input/output-extended finite automata (I/O-EFA) model is provided. The method includes receiving a representation of the diagram and processing the representation of the diagram with a computing device by (a) representing all atomic blocks in said diagram as a tuple, (b) representing the diagram using a connecting rule and a conditioning rule, (c) determining an order in which the blocks included inside the diagram are executed, (d) translating the atomic blocks into the I/O-EFA model using a first algorithm, and (e) translating for the connecting rule and the condition rule using a second algorithm and a third algorithm, respectively to thereby modify the I/O-EFA model. 
         [0013]    According to another aspect of the present invention, a computer-readable storage medium storing computer-executable instructions that are executed on a processing device is provided. The computer-executable instructions include instructions for receiving a data representation of a diagram, said diagram comprising a plurality of blocks and said diagram being associated with a graphical modeling environment which defines semantics for executing the diagram, and instructions for processing the data representation of the diagram to translate the diagram into an input/output-extended finite automata model. 
         [0014]    According to another aspect of the present invention, a method of semantic translation of a diagram into input/output-extended finite automata (I/O-EFA) model is provided. The method includes: representing atomic blocks in the diagram as a tuple; representing the diagram using a connecting-rule and a conditioning-rule; determining an order in which the atomic blocks of the diagram are executed; translating the atomic-blocks into an I/O-EFA model; and translating for the connecting-rule and the conditioning-rule to adjust the I/O-EFA model. The steps may be performed by a computing device. 
         [0015]    According to another aspect of the present invention, a method of translating a class of diagrams as input/output-extended finite automata is provided. The method includes receiving a data representation of a diagram, said diagram including a plurality of blocks and said diagram being associated with a graphical modeling environment which defines semantics for executing the diagram. The method further includes processing, using a computing device, the data representation of the diagram to translate the diagram into an input/output-extended finite automata model. 
     
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         [0016]      FIG. 1  is a simulink diagram of a counter. 
           [0017]      FIG. 2  is a multirate simulink diagram. 
           [0018]      FIG. 3  is a simulink diagram of bouncing ball. 
           [0019]      FIG. 4  is I/O-EFA model of atomic-block ψ. 
           [0020]      FIG. 5  is I/O-EFA model of system-block  ψ =Ψ/C. 
           [0021]      FIG. 6  is I/O-EFA model of Ψ 2 /C 2  of Example 2. 
           [0022]      FIG. 7  is I/O-EFA model of multirate Simulink diagram of Example 3. 
           [0023]      FIG. 8  is I/O-EFA model of system-block  ψ =ψ         θ. 
           [0024]      FIG. 9  is I/O-EFA model of Ψ 1  of Example 2. 
           [0025]      FIG. 10  is I/O-EFA model of counter of Example 2. 
           [0026]      FIG. 11  is I/O-EFA model of bouncing ball of Example 4. 
           [0027]      FIG. 12  is Simulation of counter of Example 2 and its I/O-EFA model in  FIG. 10 . 
           [0028]      FIG. 13  is Simulation of multirate Simulink diagram Example 3 and I/O-EFA model in  FIG. 7 . 
           [0029]      FIG. 14  is Simulation of bouncing ball of Example 4 and its I/O-EFA model in  FIG. 11 . 
       
    
    
     DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS 
     1. Introduction 
       [0030]    Although the present invention may be used with diagrams from any number of graphical environments, Simulink/Stateflow (S/S) diagrams are used as representative examples of such diagrams. Simulink/Stateflow (S/S) [2] diagrams are graphical representations of dynamical systems, and can capture both time-driven as well as event-driven dynamics of hybrid systems. Stateflow diagrams are used for representing and simulating event-driven dynamics. The S/S diagrams can be simulated to generate sample-runs (runs on sample times) which provide a means for their validation. Other means of validation include testing and verification. In order to be able to test a S/S diagram or verify an implementation of a S/S diagram, a model-based approach is desirable, where a model can be used for automated test generation or as a formal specification. 
         [0031]    Simulink blocks can be time-driven or non time-driven. A time-driven block, such as an Integrator block, represents the time-dependent mathematical relationships between its inputs and outputs. On the other hand, non time-driven block, such as a Stateflow block or a Discrete Event Subsystem block, may evolve upon the occurrence of events. Here, we focus on study the semantic translation of time-driven blocks, and for conciseness, we write “Simulink blocks” to mean only the “time-driven Simulink blocks”. 
         [0032]    We propose an approach for translating the behaviors of a Simulink diagram at (discrete) sample times to input/output-extended finite automata (I/O-EFA) [9, 15]. Note that a Simulink diagram can represent a hybrid system that combines event-driven discrete and time-dependent continuous behaviors, whereas I/O-EFA is a model of a reactive untimed infinite state system. Yet, since we are only interested in capturing the behaviors of a Simulink diagram at sample times, an I/O-EFA model (which is untimed) suffices. 
         [0033]    Simulink provides a library of blocks (such as transfer functions, discontinuities, math operations, logic and bit operations etc.), which can be interconnected in a hierarchical fashion to form an overall Simulink diagram. We consider the blocks in the Simulink library to be “atomic”, and formally define an atomic-block. Further we formulate two rules, namely connecting-rule and conditioning-rule, used in Simulink for building complex blocks by combining the simpler ones, and formally define a class of Simulink diagrams formed using these rules. This recursive view of defining the class of all Simulink diagrams leads to a recursive translation in form of I/O-EFA. 
         [0034]    In order to obtain an I/O-EFA model recursively, we first present an algorithm for translating an atomic-block to an I/O-EFA. Next for each rule of combining simpler Simulink diagrams to construct a complex Simulink diagram, we develop a corresponding rule for combining the I/O-EFA models of simpler Simulink diagrams to build the I/O-EFA model of the more complex Simulink diagram. 
         [0035]    We introduce the concept of a step of an I/O-EFA to emulate the computation of a Simulink diagram at a sample time. A sequence of steps, namely, a step-trajectory, generates outputs over a sequence of sample times. We show that the translation approach is sound and complete: The input-state-output behavior of the I/O-EFA, defined in terms of a step-trajectory, preserves the input-state-output behavior of the corresponding Simulink diagram at each sample time (assuming the same integration method for any of the continuous blocks with dynamics). 
         [0036]    Various aspects of the present invention include:
       The translation approach is recursive. Formal definitions of an atomic Simulink block and a class of Simulink diagrams formed using the identified connecting-rule and conditioning-rule are provided. These definitions can be used to create a more complex Simulink diagram from the simpler ones.   The model of I/O-EFA is amenable to automated test generation [10] or verification [14]. The model can be directly supplied to a test generation or verification tool that accepts I/O-EFA models or programming languages such as C/C++ or Java since an I/O-EFA model can be easily translated into these languages.   The translation approach has no special restriction on the types of Simulink blocks. The approach supports virtually all blocks in Simulink Library (in this patent we only consider time-driven blocks) provided that the block can be mathematically written as input-state-output functions over time. Also unlike [4], it does not require a clear separation between discrete and continuous dynamics for modeling hybrid systems. As an illustration, consider for example the bouncing ball example presented herein.   The translation approach is sound and complete: The input-state-output behavior of an I/O-EFA model, as defined in terms of a step-trajectory, preserves the input-state-output behavior of the corresponding Simulink diagram at each sample time (assuming the same integration method for any of the continuous blocks with dynamics).   The translation approach can handle the Simulink features such as multi-rate diagrams, sample times with initial offsets, variable-step simulation etc.   The translation approach is general in that it can be applied to other graphical modeling and simulation tools such as LabView.       
 
       2. I/O-EFA 
       [0043]    We present the notion of an input-output extended finite automaton (I/O-EFA) as a formal model of representation for a Simulink diagram. I/O-EFA is a model of a reactive untimed infinite state system in form of an automaton, extended with discrete variables such as inputs, outputs, and data. Using I/O-EFA as a model, many value-passing processes can be represented as finite graphs. An I/O-EFA consists of locations (i.e., symbolic-state), data (i.e., numeric-state), numeric-inputs, numeric-outputs, symbolic-inputs, symbolic-outputs, transitions, an initial location, initial data values, and a final location. The locations (symbolic-states) together with the data (numeric-states) form the state-space of a I/O-EFA. The locations are finite and form the vertices of the automaton graph. The edges of the graph represent transitions between the locations and are guarded by constraints over the data and the inputs. The occurrence of a transition triggers a data update and an output assignment. 
         [0000]    Definition 1 An input/output extended finite automaton (I/O-EFA) is a tuple 
         [0000]        P =( L,D,U,Y,Σ,Δ,l   0   ,D   0   ,l   m   ,E ) 
         [0000]    where
       L is the set of locations (symbolic-states),   D=D 1 × . . . ×D n  is the set of typed data (numeric-states),   U=U 1 × . . . ×U m  is the set of typed numeric-inputs,   Y=Y 1 × . . . ×Y p  is the set of typed numeric-outputs,   Σ is the set of symbolic-inputs,   Δ is the set of symbolic-outputs,   l 0 εL is the initial location,   D 0   ⊂ D is the set of initial-data values,   l m εL is the final location, and   E is the set of edges, and each eεE is a 7-tuple,
           e=(o e , t e , σ e , δ e , G e , f e , h e ), where
               o e εL is the origin location,   t e εL is the terminal location,   σ e εΣ∪{ε} is the symbolic-input,   δ e εΔ∪{ε} is the symbolic-output,   G e   ⊂ D×U is the enabling guard (a predicate),   f e : D×U→D is the data-update function,   h e : D×U→Y is the output-assignment function.   
               
               
 
         [0062]    Initially, P starts from the initial location l 0  and an initial data value d o εD 0 . While at a certain state (l,d)εL×D, a transition eεE such that o e =l is enabled if the input σ e  arrives, and the data d and input u are such that the guard G e (d,u) holds. Note when σ e =ε, the transition is enabled when only the guard G e (d,u) holds; on the other hand when G e (D,U)=True, then the transition is enabled when only σ e  arrives. An enabled transition can be executed. The execution of an enabled transition e at the state (o e ,d) causes P to transit to the location t e , the data value is updated to ƒ e (d,u), the output variable is assigned the value h e (d,u), and a discrete output δ e  is emitted. 
       3. Atomic-Blocks Minimal Simulink Diagrams 
       [0063]    Simulink provides a library of blocks, which can be used as minimal systems, and the corresponding Simulink diagrams will then be minimal Simulink diagrams. We refer to such blocks as atomic blocks. The atomic-blocks can be composed in a recursive fashion to construct more complex Simulink diagrams, and we discuss the rules of composition in the next section. 
         [0064]    An atomic-block can be stateful or stateless. A stateful block&#39;s output depends on the history of its inputs. An example of a stateful block is the Unit Delay block. On the other hand, the output of a stateless block depends only on its current inputs. An example of a stateless block is the Gain block, which simply outputs its input signal, multiplied with a constant called the gain. 
         [0065]    An atomic-block can be classified as continuous-time versus discrete-time, and is associated with a sample-period. For a continuous-time block, sample-period is the time between the instants when it is numerically simulated. For a discrete-time block, sample-period is the time between the instants when the corresponding discrete-time system evolves. 
         [0066]    An atomic-block can be defined as follows. 
         [0000]    Definition 2 An atomic Simulink block ψ can be represented as a tuple 
         [0000]      ( U   ψ   ,Y   ψ   ,D   ψ   ,D   0   ψ ,{( G   i   ψ   ,ƒ   i   ψ   ,h   i   ψ )} i=1   q     ψ   ,( T   ψ   ,T   o   ψ )), 
         [0000]    where
       U ψ =U 1   ψ × . . . ×U m     ψ     ψ  is the set of typed inputs,   Y ψ =Y 1   ψ × . . . ×Y p     ψ     ψ  is the set of typed outputs,   D ψ =D 1   ψ × . . . ×D n     ψ     ψ  is the set of typed data,   D 0   ψ   ⊂ D ψ  is the set of initial data conditions,   {(G i   ψ , ƒ i   ψ , h i   ψ )} i=1   q     ψ    is a set of triples, where
           G i   ψ   ⊂ D ψ ×U ψ  is a predicate representing an enabling guard, such that v i=1   q     ψ    G i =True,   ƒ i   ψ : D ψ ×U ψ →D ψ  is a data-update function,   h i   ψ : D ψ ×U ψ →Y ψ  is an output-assignment function.   
           T ψ  is the sample period and T 0   ψ  is an offset (it is assumed zero by default if unspecified).
 
Remark 1 The kth sampling time occurs at kT ψ +T o   ψ . The value of the input signal at the kth sampling time is denoted as u(k)=(u 1 (k), . . . , u m     ψ   (k))εU ψ , and similarly for other signals. At the kth sampling time, if the data d(k) and the input u(k)) are such that G i   ψ (d(k),u(k)) holds, the next data, d(k+1)=ƒ i   ψ (d(k),u(k)), is computed, and the output value is assigned to y(k)=h i   ψ (d(k),u(k)). Note that for continuous-time blocks, the data-update and output-assignment functions correspond to the ones obtained through discretization at sample times using an appropriate integration method. Simulink allows different kinds of sample period that include Discrete, Continuous, Inherited (−1), Constant (inf) and Triggered etc. Discrete sample periods are the only kind for which the evolution times of the corresponding system are known a priori. For blocks with other kinds of sample period, Simulink determines the evolution times of the corresponding system from the block&#39;s type or by its context within the model during the compilation phase of simulation. Given a Simulink diagram, the sample period of a non continuous-time block can be obtained from the get_param (object, ‘CompiledSampleTime’) command after compiling the diagram. The sample-period of a continuous-time block, which is used in discretization, can be chosen to be the greatest common divisor of all non continuous-time blocks using the following rule [3]: for 1≦i, j≦n,
       
 
         [0000]    
       
         
           
             
               T 
               ψ 
             
             = 
             
               { 
               
                 
                   
                     
                       
                         gcd 
                          
                         
                           ( 
                           
                             { 
                             
                               T 
                               
                                 ψ 
                                 i 
                               
                             
                             } 
                           
                           ) 
                         
                       
                     
                     
                       
                         
                           if 
                            
                           
                               
                           
                            
                           
                             T 
                             o 
                             
                               ψ 
                               i 
                             
                           
                         
                         = 
                         
                           T 
                           o 
                           
                             ψ 
                             j 
                           
                         
                       
                     
                   
                   
                     
                       
                         gcd 
                          
                         
                           ( 
                           
                             { 
                             
                               
                                 T 
                                 
                                   ψ 
                                   i 
                                 
                               
                               , 
                               
                                 T 
                                 o 
                                 
                                   ψ 
                                   i 
                                 
                               
                             
                             } 
                           
                           ) 
                         
                       
                     
                     
                       otherwise 
                     
                   
                 
                 , 
                 
                   
 
                 
                  
                 
                   
                     and 
                      
                     
                         
                     
                      
                     
                       T 
                       o 
                       ψ 
                     
                   
                   = 
                   
                     { 
                     
                       
                         
                           
                             T 
                             o 
                             
                               ψ 
                               i 
                             
                           
                         
                         
                           
                             
                               if 
                                
                               
                                   
                               
                                
                               
                                 T 
                                 o 
                                 
                                   ψ 
                                   i 
                                 
                               
                             
                             = 
                             
                               T 
                               o 
                               
                                 ψ 
                                 j 
                               
                             
                           
                         
                       
                       
                         
                           0 
                         
                         
                           
                             otherwise 
                             . 
                           
                         
                       
                     
                   
                 
               
             
           
         
       
     
         [0000]    Also note for a stateless atomic-block ψ, the set D ψ  is empty (and accordingly, there are no initial data conditions or data-update functions). 
         [0076]    The following example illustrates the Definition 2. 
       Example 1 
       [0077]    The Integrator block provides a continuous-time integration of the input signal. It models the relations, {dot over (d)}(t)=u(t) with d(0)=d 0 , and y(t)=d(t), where u is its input, d is its data, y is its output, t is the continuous-time variable, and d 0  is the initial data condition. Using Euler&#39;s Method the discretization is d(k+1)=d(k)+T ψ u(k). Thus, the Integrator block can be represented as: 
         [0000]      ( u,y,d,d   0 ,{(−, d ( k+ 1)= d ( k )+ T   ψ   u ( k ), y ( k )= d ( k ))},( T   ψ   ,T   0   ψ )),
 
         [0000]    where T ψ  is the sample-period and T 0   ψ  is an offset. 
         [0078]    Note that the Integrator block can be configured further by setting certain parameters to have a more complex behavior. An example is the Integrator block ψ 5  in  FIG. 3 . In Example 1 we did not include this much detail for the sake of simplicity of illustration. 
         [0079]    We introduce the following concepts for the computation of an atomic block over sample times. 
         [0000]    Definition 3 Given an atomic-block ψ and an input uεU ψ , we call the computation of the corresponding output yεY ψ  a step of ψ over u. y is called the output of a step of ψ over u. Given an input sequence {u(k)} k=0   K , a step-trajectory of ψ over {u(k)} k=0   K  is a sequence of steps of ψ, where the kth step (0≦k≦K) in the sequence is over the input u(k). Letting y(k) (0≦k≦K) denote the output of ψ over u(k), {y(k)} k=0   K  is called the output of step-trajectory of ψ over {u k } k=0   K . 
       4. System-Blocks Simulink Diagrams 
       [0080]    A Simulink diagram, also called a system-block, can be constructed by recursively composing atomic-blocks and other simpler system-blocks according to certain rules. The following two rules are the among the rules that Simulink uses for the construction of complex Simulink diagrams from the simpler ones:
       Connecting-rule: A certain input of one system-block can be connected to a certain output of another system-block. The connections over a set of system-blocks Ψ can be represented using a relation C ⊂ (Ψ×N) 2 , where N denotes the set of port numbers. A connection c=((ψ 1 ,i),(ψ 2 ,j))εC connects the output port i of system-block ψ 1  to an input port j of system-block ψ 2 . The “C-connected Ψ system” thus formed is denoted Ψ/C. Note a possible choice for connections is the “null-connection”, and {ψ}/=ψ.   Conditioning-rule: A system-block can be made conditionally executable when a certain guard condition over certain variables, called control-inputs, holds. Further the data may be reset when the guard condition holds, and the output may be reset when the guard condition is violated. Given a system-block ψ, a conditioning over ψ is a 5-tuple       
 
         [0000]      θ:=( U   θ   ,G   θ ,ƒ θ   ,h   θ ,( T   θ   ,T   o   θ )),
 
         [0000]    where
       U θ =U 1   θ × . . . ×U m     θ     θ  is the set of conditioning-inputs (also called control-inputs),   G θ   ⊂ U θ  is a condition (predicate) over U θ ,   ƒ θ : D ψ →D ψ  is a data-resetting function,   h θ : Y ψ →Y ψ  is an output-resetting function, and   T θ  is a sample-period, T o   θ  is an offset.
 
When G θ  holds, ψ computes, and otherwise, h θ  assigns the output. Also, when G ø  becomes true, the first computation of ψ is preceded by a data-update by ƒ θ . The “θ-conditioned ψ” system thus formed is denoted ψ         θ.
 
The conditioning-rule can be implemented by placing a system-block inside a certain Subsystem block (of Simulink Library) which can be configured to specify the conditioning parameters. Note a possible choice for conditioning is “null-conditioning”, denoted ⊥:=(−, True, id, id, ∞), in which case ψ         ⊥=ψ. (Here id denotes the identity function.)
       
 
         [0088]    Next we formally define the class of Simulink diagrams (also referred to as system-blocks) formed using the above rules. 
         [0000]    Definition 4 A certain class of Simulink diagrams (also referred to as system-blocks) is recursively defined as follows.
       1. ψ is an atomic-block, then ψ is a system-block.   2. Ψ is a set of system-blocks, C ⊂ (Ψ×N) 2  is a set of interconnections, then C-connected Ψ, denoted Ψ/C, is a system-block.   3. ψ is a system-block and θ is a conditioning over ψ, then θ-conditioned ψ, denoted ψ         θ, is a system-block.
 
Remark 2 For a system-block  ψ :=Ψ/C, we have:
   inputs U   ψ   =Π ∃((.,.),(ψ,i))εC U i   ψ ,   outputs Y   ψ   =Π ψεΨ Y ψ ,   data D   ψ   =Π ψεΨ D ψ ,   initial data D 0     ψ   =Π ψεΨ D ψ , and   sample-period, T   ψ    and offset T o     ψ    are obtained using the rule defined in Remark 1 over {T ψ , T o   ψ |ψεΨ}.
 
Note the above definition of T   ψ    ensures that each computation of each system-block ψεΨ coincides with some computation of the connected system-block  ψ  (i.e., no computation of any system-block is missed).
 
Similarly, for a system-block  ψ :=         θ we have:
   inputs U   ψ   =U ψ ×U θ ,   outputs Y   ψ   =Y ψ ,   data D   ψ   =D ψ ,   initial data D 0     ψ   =D 0   ψ     sample-period       
 
         [0000]    
       
         
           
             
               T 
               
                 ψ 
                 _ 
               
             
             = 
             
               { 
               
                 
                   
                     
                       
                         T 
                         θ 
                       
                     
                     
                       
                         if 
                          
                         
                             
                         
                          
                         
                           T 
                           θ 
                         
                          
                         
                             
                         
                          
                         specified 
                       
                     
                   
                   
                     
                       
                         T 
                         ψ 
                       
                     
                     
                       otherwise 
                     
                   
                 
                 , 
                 
                   
 
                 
                  
                 
                   
                     and 
                      
                     
                         
                     
                      
                     offset 
                      
                     
                         
                     
                      
                     
                       T 
                       o 
                       
                         ψ 
                         _ 
                       
                     
                   
                   = 
                   
                     { 
                     
                       
                         
                           
                             T 
                             o 
                             θ 
                           
                         
                         
                           
                             if 
                              
                             
                                 
                             
                              
                             
                               T 
                               θ 
                             
                              
                             
                                 
                             
                              
                             specified 
                           
                         
                       
                       
                         
                           
                             T 
                             o 
                             ψ 
                           
                         
                         
                           
                             otherwise 
                             . 
                           
                         
                       
                     
                   
                 
               
             
           
         
       
     
         [0000]    Note by the Simulink grammar, for a system-block  ψ :=ψ         θ, T θ  is either specified and in which case T   ψ    is inherited to be T θ , or is unspecified and in which case T   ψ    is inherited to be T ψ . Similarly for T o     ψ   . 
       Example 2 
       [0102]    Consider the Simulink diagram ψ of a counter shown in  FIG. 1 , where the Unit Delay block ψ 5  is a discrete-time atomic-block and the block ψ 1  is an Enabled Subsystem block. The output y 5  increases by 1 at each sample-period when the control input u is positive, and y 5  resets to its initial value when the control input u is not positive. The Saturation block ψ 2  limits the value of y 5  in the range between −0.5 and 7. The sample-period of ψ 5  is 0.01 seconds and others are either constant (inf) or inherited (−1). T o   ψ     5   =0 by default since unspecified. Using get_param command after compiling ψ, T ψ =T ψ     i   =0.01 for i=1, 2, 3, 4, 5. ψ belongs to the class of Simulink diagrams defined in Definition 4: 
         [0000]      ψ={ψ 1 ,ψ 2   }/C   1 ,
 
         [0000]    where
       ψ 1 =({ψ 3 , ψ 4 , ψ 5 }/C 2 )         θ, where
           C 2 ={((ψ 3 , •),(ψ 4 , •)), ((ψ 4 , •),(ψ 5 , •)), (ψ 5 , •),(ψ 4 , •))},   θ=(U θ , u θ (k)&gt;0, d(k)=d 0 , (y 3 (k), y 4 (k), y 5 (k))=(−, −, y 50 ), −)   
           C 1 ={((ψ 1 , •),(ψ 2 , •))}, and   ψ 2 , ψ 3 , ψ 4 , ψ 5  are atomic-blocks.
 
Note since we choose the Pulse type of the source block Pulse Generator to be Time based, ψ is a single-rate Simulink diagram. Thus the source block for generating the inputs and the sink block Scope for displaying the outputs are not considered as part of the Simulink diagram being translated, and hence not included in ψ. If the Pulse type of the source block is chosen to be Sample based and the sample time is different from 0.01, then ψ becomes a multirate Simulink diagram.
       
 
       Example 3 
       [0108]    Consider the multirate Simulink diagram ψ shown in  FIG. 2 , where blocks ψ 3  and ψ 7  are discrete-time blocks with sample-period of 0.01 and 0.025 seconds, respectively. The Zero-Order Hold block ψ 8  is also a discrete-time block that samples the incoming signal at 0.01. Blocks ψ 5  and ψ 6  are continuous-time blocks. The sample-periods of other blocks are either constant (inf) or inherited (−1). All offsets are 0 by default since unspecified. Thus, T ψ     i   =0.01 for i=1, 2, 3, 4, 8 and T ψ     7   =0.025. Since gcd(0.01, 0.025)=0.005, we opt to discretize ψ 5  and ψ 6  at a sample-period of 0.005. Then T ψ     5   =T ψ     6   =0.005, and also T ψ =0.005. 
         [0109]    ψ belongs to the class of Simulink diagrams defined in Definition 4: ψ=Ψ/C, where Ψ={ψ 1 , ψ 2 , ψ 3 , ψ 4 , ψ 5 , ψ 6 , ψ 7 , ψ 8 } and C is omitted. U=, D=D 3 ×D 5 ×D 6 ×D 7  with D 0 ={(0, 0, 0, 0)}. Note the sink block Scope for displaying the outputs is not considered as part of the Simulink diagram being translated, and hence not included in ψ. 
       Example 4 
       [0110]    Consider the Simulink diagram ψ of a bouncing ball shown in  FIG. 3 . ψ models a hybrid-system of a bouncing ball that is thrown up with an initial velocity of 15 m/s from an initial height of 10 m. y 5  (resp., y 2 ) is the position (resp., velocity) of the ball. ψ 2  and ψ 5  are continuous-time blocks. We have opted to discretize ψ 2  and ψ 5  at a sample period of 0.01. The sample-periods of other blocks are either constant (inf) or inherited (−1). Then T ψ =T ψ     i   =0.01 for 1, . . . , 7. ψ belongs to the class of Simulink diagrams defined in Definition 4: ψ=Ψ/C, 
         [0000]    where Ψ={ψ 1 , ψ 2 , ψ 3 , ψ 4 , ψ 5 , ψ 6 , ψ 7 } and C is omitted. U=, D=D 1 ×D 2  with D 0 ={(15, 10)}. 
       4.1 Sorted-Order 
       [0111]    When system-blocks are composed using the connecting-rule to form a more complex system-block, the input of one system-block becomes the output of another system-block. To respect the interdependency of the inputs/outputs, Simulink defines and uses the notion of an execution-order (which it refers as sorted-order) to determine the order in which the system-blocks included inside a connected system-block are executed. Note that the conditioning-rule does not require defining a sorted-order since it is applied to a single system-block. 
         [0112]    Given a system-block Ψ/C formed using the connecting-rule, the sorted-order of the system-blocks {ψεΨ} is given as an ordering function Ord: Ψ→N, where N is the set of natural numbers. The sorted-order induces a total-order over Ψ, i.e., for ψ, ψ′εΨ, Ord(ψ)=Ord(ψ′) if and only if ψ=ψ′. Accordingly ψεΨ is executed before ψ′εΨ if Ord(ψ)&lt;Ord(ψ′). The sorted-order value Ord(ψ) can be displayed, as part of a label ascribed to a system-block ψεΨ, by selecting the option Sorted Order from Simulink Block Displays menu. Assuming, without loss of generality of correctness of translation, that the Optimization on Conditional Execution Behaviors is turned off, the label ascribed to ψ has the format: Id(Ψ/C): Ord(ψ): {Id(ψ)}, where Id is a function that associates a certain identifier number to a system-block. The {Id(ψ)} part may be missing if ψ an atomic-block. Whenever we need to indicate the label ascribed to ψεΨ, we write it in the form: ψ [Id(Ψ/C): Ord(ψ){Id(ψ)}]. 
         [0113]    The notion of sorted-order is essential in defining the step of a system-block. 
         [0000]    Definition 5 Given a system-block ψ and an input uεU ψ , the step of ψ over u is recursively defined as follows:
       If ψ is an atomic-block, then the step of ψ over u is as defined in Definition 3.   If ψ=Ψ/C is a connected system-block, then for j min ≦j≦j max , where j min =min{Ord(ψ): ψεΨ} and j max =max{Ord(ψ): ψεΨ}, letting ψ j εΨ denote the system-block with Ord(ψ j )=j, a step of ψ over u is a sequence of steps, whose jth element is the step of ψ j εΨ over u j , the input of ψ j  as determined by the set of connections C.   If ψ=ψ         θ is a conditioned system-block, then a step of ψ over u is the step of ψ′ over u if G θ  holds, and otherwise it is the execution of the output-resetting function h θ . Also when G θ  becomes true, the first execution of the step of ψ′ over u is preceded by the execution of the data-resetting function ƒ θ .
 
Given an input sequence {u(k)} k=0   K , a step-trajectory of ψ over {u(k)} k=0   K  is a sequence of steps of ψ, where the kth step (0≦k≦K) in the sequence is over the input u(k). Letting y(k) (0≦k≦K) denote the output of ψ over u(k), {y(k)} k=0   K  is called the output of step-trajectory of ψ over {u k } k=0   K .
       
 
         [0117]    Note in the 2 nd  item of Definition 5, when kT ψ +T 0   ψ =k ψ     j   T ψ     j   +T o   ψ     j    a step of ψ j  is computed by h i   ψ     j    if G i   ψ     j    holds, and k ψ     j    increases when k increases; otherwise when kT ψ +T o   ψ ≠k ψ     j   T o   ψ +T o   ψ     j   , the output of ψ j  remains its previous value, and k ψ     j    remains unchanged when k increases. 
       Example 5 
       [0118]    Consider the Simulink diagram of ψ the counter shown in  FIG. 1  that was also discussed in Example 2, and its sorted-order displayed in  FIG. 1 . We have 
         [0000]      ψ=Ψ 1   /C   1 ={ψ 1 [0:1{1}],ψ 2 [0:2 ]}/C   1 ,
 
         [0000]      ψ 1 =(Ψ 2   /C   2 )         θ=({ψ 3 [1:0],ψ 4 [1:2],ψ 5 [1:1 ]}/C   2 )         θ.
 
         [0000]    Then according to Definition 5 we have:
       A step of ψ={ψ 1 , ψ 2 }/C 1  is a step of ψ 1  followed by a step of ψ 2  since Ord(ψ 1 )&lt;Ord(ψ 2 )=2.   A step of ψ 1 =({ψ 3 , ψ 4 , ψ 5 }/C 2 )         θ is obtained as follows: If G θ  holds, the sequence of steps of ψ 3 , ψ 5 , ψ 4  is executed since Ord(ψ 3 )=0&lt;Ord(ψ 5 )=1&lt;Ord(ψ 4 )=2; and otherwise, h θ  computes. Also when G θ  becomes true, the first execution of the sequence of steps of ψ 3 , ψ 5 , ψ 4  is preceded by the computation of ƒ θ .       
 
       Example 6 
       [0121]    Consider the multirate Simulink diagram ψ of  FIG. 2  that was also discussed in Example 3, and its sorted-order displayed in  FIG. 2 . It can be seen that 
         [0000]      ψ=ψ 1 [0:2],ψ 2 [0:6],ψ 3 [0:7],ψ 4 [0:8],ψ 5 [0:3],ψ 6 [0:4],ψ 7 [0:0],ψ 8 [0:5 ]}/C.  
 
         [0000]    It then follows that a step of ψ is the sequence of steps of ψ 7 , ψ 1 , ψ 5 , ψ 6 , ψ 8 , ψ 2 , ψ 3  and ψ 4 . Note for j=1, . . . , 8, a step of ψ j  is computed whenever kT ψ =k ψ     j   T ψ     j   , and otherwise, ψ j  retains its previous values of the data and the output. 
       Example 7 
       [0122]    Consider the Simulink diagram ψ of the bouncing ball of  FIG. 3  that was also discussed in Example 4, and its sorted-order displayed in  FIG. 3 . It can be seen that 
         [0000]      ψ={ψ 1 [0:7],ψ 2 [0:3],ψ 3 [0:2],ψ 4 [0:1],ψ 5 [0:5],ψ 6 [0:4],ψ 7 [0:0 ]}/C.  
 
         [0000]    It then follows that a step of ψ is the sequence of steps of ψ 7 , ψ 4 , ψ 3 , ψ 2 , ψ 6 , ψ 5  and ψ 1 . 
       5. Semantic Translation of Simulink Diagrams 
       [0123]    We describe how a Simulink diagram can be semantically translated to an I/O-EFA. 
         [0124]    For any system-block ψ, its I/O-EFA model is obtained by connecting two I/O-EFA models, one for output-assignments and other for state-updates. We use l 0−   ψ , l m−   ψ  to denote the initial/final location for first I/O-EFA, and l 0+   ψ , l m+   ψ  to denote the initial/final location for second I/O-EFA. The two I/O-EFA&#39;s are connected using two edges:
       succession-edge connecting the final location l m−   ψ  of the first I/O-EFA to the initial location l 0+   ψ  to of the second I/O-EFA, and   time-advancement edge connecting the final location l m+   ψ  of the second I/O-EFA to the initial location l 0−   ψ  to of the first I/O-EFA that increments time: k:=k+1.
 
Translating Atomic-Blocks.  FIG. 4  depicts the two I/O-EFA models connected by the succession and time-advancement edges for an atomic-block ψ. A formal description of the translation is provided in the following algorithm.
 
Algorithm 1 For an atomic-block ψ=(U ψ . Y ψ , D ψ , D o   ψ , {(G i   ψ , ƒ i   ψ , h i   ψ )} i=1   q     ψ   , (T ψ , T o   ψ )),
       
 
         [0127]    The 1st I/O-EFA of ψ is 
         [0000]        P   −   ψ =( L   −   ψ   ,−,U   ψ   ,Y   ψ   ,−,−,l   0−   ψ   ,−,l   m−   ψ   ,E   −   ψ ), 
         [0000]    where
       L −   ψ ={l 0−   ψ ,l m−   ψ } and   E −   ψ ={(l 0−   ψ , l m−   ψ , −, −, G i   ψ , −, h i   ψ )|i≦q ψ }.       
 
         [0130]    The 2nd I/O-EFA of ψ is 
         [0000]        P   +   ψ =( L   +   ψ   ,D   P     ψ     ,U   ψ   ,Y   ψ   ,−,−,l   0+   ψ   ,D   0   P     ψ     ,l   m+   ψ   ,E   +   ψ ), 
         [0000]    where
       L +   ψ ={l 0+   ψ ,l m+   ψ },   D P     ψ   :=D ψ ×K is the set of data, where K is the set of sampling times,   D 0   P     ψ   :=D 0   ψ ×{0} is the set of initial-data conditions, and   E +   ψ ={(l 0+   ψ , l m+   ψ , −, −, G i   ψ , ƒ i   ψ , −)|i≦q ψ}.  
 
Note that ƒ ψ =“nul” if ψ is a stateless block.
       
 
         [0135]    The combined I/O-EFA model of ψ is 
         [0000]        P   ψ =( L   ψ   ,D   P     ψ     ,U   ψ   ,Y   ψ   ,−,−,l   0   ψ   ,D   0   P     ψ     ,l   m   ψ   ,E   ψ ), 
         [0000]    where
       L ψ =L −   ψ ∪L +   ψ ,   l 0   ψ =l 0−   ψ ,   l m   ψ =l m+   ψ , and   E ψ =E −   ψ ∪E +   ψ ∪{(l m−   ψ , l 0+   ψ , −, −, −, −, −)}∪{(l m+   ψ , l 0−   ψ −, −, −, −, k=k+1)}.
 
Translating for Connecting-rule. In the I/O-EFA models of a connected system-block  ψ =Ψ/C, the initial and final locations of the first (resp., second) I/O-EFA are the initial and final locations of the first (resp., second) I/O-EFA model of ψεΨ that has the smallest and largest Ord(ψ)-value in Ψ, respectively. Also in order to preserve the sorted-order, there is an edge from the final location of the first (resp., second) I/O-EFA of ψεΨ to the initial location of the first (resp., second) I/O-EFA of ψ′εΨ if and only if Ord(ψ′)=Ord(ψ)+1. Also in order to allow multirate system-blocks within a connected system-block, certain “bypass” edges are introduced within each system-block ψεΨ connecting the initial location l 0−   ψ (resp., l 0+   ψ ) and final location l m−   ψ (resp., l m+   ψ ) of the first (resp., second) I/O-EFA of ψ. These edges are guarded by └kT   ψ   +T 0     ψ   ≠k ψ T ψ +T 0   ψ ┘. implying that will be bypassed at those values of k when kT   ψ   +T 0     ψ    is not equal to k ψ T ψ +T 0   ψ . In contrast, the converse guard condition of └kT   ψ   +T o     ψ   =k ψ T ψ +T 0   ψ ┘ is introduced for the original set of edges originating at l 0−   ψ  and l 0+   ψ . An illustration of the translating of  ψ =Ψ/C is depicted in  FIG. 5 , whereas a formalization is presented in Algorithm 2.
       
 
         [0140]    Without loss of generality, we assume that if ((ψ, i),(ψ, j))εC, then y i   ψ =u j   ψ , i.e., the same variable has been used to denote the two signals. 
         [0000]    Algorithm 2 For a connected system-block  ψ =Ψ/C, 
         [0141]    The 1st I/O-EFA of  ψ  is 
         [0000]        P   −     ψ   =( L   −     ψ     ,D   −   P       ψ       ,U     ψ     ,Y     ψ     ,−,−,l   0−     ψ     ,D   0−   P       ψ       ,l   m−     ψ     ,E   −     ψ   ), 
         [0000]    where
       L −     ψ   :=∪ ψεΨ L −   ψ ,   D −   P       ψ     :=K×Π ψεΨ K ψ ×T   ψ   T 0     ψ   ×Π ψεΨ T ψ ×Π ψεΨ T 0   ψ ,   U   ψ    and Y   ψ    are as defined in first part of Remark 2,   l 0−     ψ   =l 0−   ψ  such that Ord(ψ)=min{Ord(ψ):ψεΨ},   D 0−   P       ψ     ={0}×Π ψεΨ {0}×T   ψ   ×T o     ψ   ×Π ψεΨ T ψ ×Π ψεΨ T o   ψ ,   l m−     ψ   :=l m−   ψ  such that Ord(ψ)=max{Ord(ψ):ψεΨ}, and   E −     ψ   =∪ ψ {(l 0−   ψ , l m−   ψ , −, −, [kT   ψ   +T o     ψ   =k ψ T ψ+T   o   ψ ]̂G i   ψ , −, h i   ψ )|i≦q ψ }
           ∪ {(l   0−   ψ , l m−   ψ , −, −, └kT   ψ   +T o     ψ   ≠k ψ T ψ+T   o   ψ ┐, −, y ψ (k)=y ψ (k−1))}   ∪{(l m−   ψ , l 0−   ψ′, −, −, −, −, −)|Ord(ψ′)=Ord(ψ)+ 1≦|Ψ|, and ψ, ψ′εΨ}.   
               
 
         [0151]    The 2nd I/O-EFA of  ψ  is 
         [0000]        P   +     ψ   =( L   +     ψ     ,D   +   P     ψ     ,U     ψ     ,Y     ψ     ,−,−,l   0+     ψ     ,D   0+   P       ψ       ,l   m+     ψ     ,E   +     ψ   ), 
         [0000]    where
       L +     ψ   :=∪ ψεΨ L +   ψ ,   D P       ψ     :=D   ψ   ×K×Π ψεΨ K ψ ×T   ψ   ×T o     ψ   ×Π ψεΨ T ψ ×Π ψεΨ T o   ψ , where D   ψ    is as defined in first part of Remark 2,   U   ψ    and Y   ψ    are as defined in first part of Remark 2,   l 0+     ψ   =l 0+   ψ  such that Ord(ψ)=min{Ord(ψ): ψεΨ},   D 0+   P       ψ     =D 0     ψ   ×{0}×Π ψεΨ {0}×T   ψ   ×T o     ψ   ×Π ψεΨ T ψ ×Π ψεΨ T o   ψ , where D 0     ψ    is as defined in first part of Remark 2,   l m+     ψ   :=l m+   ψ  such that Ord(ψ)=max{Ord(ψ): ψεΨ}, and   E +     ψ   =∪ ψ {(l 0+   ψ , l m+   ψ , −, −, [kT   ψ   +T o     ψ   =k ψ T ψ +T o   ψ ]̂G i   ψ ,
           (d ψ (k+1), k ψ )=(θ i   ψ , k ψ +1), −)|i≦q ψ}     ∪ ψ {(l 0+   ψ , l m+   ψ , −, −, └kT   ψ   +T o     ψ   ≠k ψ T ψ +T o   ψ┐, d   ψ (k+1)=d ψ (k), −)}   ∪{(l m+   ψ , l 0+   ψ′ , −, −, −, −, −)|Ord(ψ′)=Ord(ψ)+1≦|Ψ|, and ψ, ψ′εΨ}.   
               
 
         [0162]    The combined I/O-EFA of  ψ  is 
         [0000]        P     ψ   =( L     ψ     ,D   P       ψ       ,U     ψ     ,Y     ψ     ,−,−,l   0     ψ     ,D   0   P       ψ       ,l   m     ψ     ,E     ψ   ), 
         [0000]    where
       L   ψ   :=L −     ψ   ∪L +     ψ   ,   D P       ψ     =D +   P       ψ     ,   l 0     ψ   =l 0−     ψ   ,   D 0   P       ψ     =D 0+   P       ψ     ,   l m     ψ   :=l m+     ψ   , and   E   ψ   =E −     ψ   ∪E +     ψ   ∪{(l m−     ψ   , l 0+     ψ   , −, −, −, −, −)}∪{(l m+     ψ   , l 0−     ψ   , −, −, −, −, k=k+1)}.
 
Remark 3 If  ψ  is a single-rate system-block, then the I/O-EFA model of  ψ =Ψ/C presented in Algorithm 2 can be simplified since in this case T   ψ   =T ψ  and T o     ψ   =T o   ψ  for each ψεΨ and so kT   ψ   +T o     ψ   =k ψ T ψ +T o   ψ  for each k.
       
 
       Accordingly 
       [0169]        E   −     ψ   =∪ ψ   E   −   ψ ∪{( l   m−   ψ   ,l   0−   ψ′ ,−,−,−,−,−)| Ord (Ψ′)= Ord (Ψ)+1≦|Ψ|, and ψ,ψ′εΨ}, and
 
         [0000]        E   +     ψ   =∪ ψ   E   +   ψ∪{(   l   m+   ψ   ,l   0+   ψ′ ,−,−,−,−,−)| Ord (Ψ′)= Ord (Ψ)+1≦|Ψ|, and ψ,ψ′εΨ}.
 
       Example 8 
       [0170]    Consider Ψ 2 /C 2 ={ψ 3 , ψ 4 , ψ 5 }/C 2  of Example 2, where Ord(ψ 3 )&lt;Ord(ψ 5 )&lt;Ord(ψ 4 ). The I/O-EFA model for Ψ 2 /C 2 , obtained using Algorithm 2 for the connecting-rule and Remark 3, is shown in  FIG. 6 . The dotted boxes contain the 1st/2nd I/O-EFAs of ψεΨ 2 , and also of Ψ 2 /C 2 . 
       Example 9 
       [0171]    Consider the multirate Simulink diagram of  FIG. 2  that was discussed in Example 3. The I/O-EFA model of ψ, obtained using Algorithm 2 for the connecting-rule, is shown in  FIG. 7 . 
         [0000]    Translating for Conditioning-rule. In the translation of a conditioned system-block  ψ =ψ         θ, the 1st I/O-EFA of  ψ  is the 1st I/O-EFA of ψ together with (i) a newly added location l 0−     ψ   , that also serves as the initial location of the first I/O-EFA model of  ψ , (ii) two newly added edges for capturing the conditional execution of ψ, and (iii) a “bypass edge” when the condition G θ  doesn&#39;t hold. The 2nd I/O-EFA of  ψ  is the 2nd I/O-EFA of ψ together with (i) a newly added location l 0+     ψ   , that also serves as the initial location of the second I/O-EFA model of  ψ , (ii) a newly added edge for capturing the conditional execution of ψ, and (iii) a “bypass edge” when the condition G θ  doesn&#39;t hold. An extra binary-valued data-variable d θ , with initial value 0, is introduced to keep track of the period over which G θ  holds. An illustration of the translating of  ψ =ψ         θ is depicted in  FIG. 8 , whereas a formalization is presented in Algorithm 3.
 
Algorithm 3 For a conditioned system-block  ψ =ψ         θ,
 
         [0172]    The 1st I/O-EFA model of  ψ  is 
         [0000]        P   −     ψ   =( L   −     ψ     ,D   θ   ,U     ψ     ,Y     ψ     ,−,−,l   0−     ψ     ,D   0   θ   ,l   m−     ψ     ,E   −     ψ   ), 
         [0000]    where
       L −     ψ   =L −   ψ ∪{l 0−     ψ   },   D θ ={0, 1},   U   ψ    and Y   ψ    are as defined in second part of Remark 2,   D 0   θ ={0},   l m−     ψ   =l m−   ψ , and   E −   ψ =E −   ψ ∪{(l 0−     ψ   , l 0−   ψ , −, −, G θ ̂[d θ =0],(ƒ θ ; d θ :=1), −)}∪ {(l 0−     ψ   , l 0−   ψ , −, −, G θ ̂[d θ =1], −, −)}∪{(l 0−     ψ   , l m−   ψ , −, −,          G θ , −, h θ )}.       
 
         [0179]    The 2nd I/O-EFA model of  ψ  is 
         [0000]        P   +     ψ   =( L   +     ψ     ,D   P       ψ       ,U     ψ     ,Y     ψ     ,−,−,l   0+     ψ     ,D   0   P       ψ       ,l   m+     ψ     ,E   +     ψ   ), 
         [0000]    where
       L +     ψ   =L +   ψ ∪{l 0+     ψ   },   D P       ψ     =D P     ψ   ×D θ ,   D 0   P       ψ     =D 0   P     ψ   ×D 0   θ ,   l m+     ψ   =l m+   ψ , and   E +     ψ   =E +   ψ ∪{(l 0+     ψ   , l 0+   ψ , −, −, G θ , −, −)}∪
           {(l 0+     ψ    l m+   ψ , −, −,           G θ , (d ψ (k+1), d θ )=(d ψ (k), 0), −)}.   
               
 
         [0186]    The combined I/O-EFA model of  ψ  is 
         [0000]        P     ψ   =( L     ψ     ,D   P       ψ       ,U     ψ     ,Y     ψ     ,−,−,l   0     ψ     ,D   0   P       ψ       ,l   m     ψ     ,E     ψ   ), 
         [0000]    where
       L   ψ   =L −     ψ   ∪L +     ψ   ,   l 0     ψ   =l 0−     ψ   ,   l m     ψ   =l m+   ψ , and   E   ψ   =E −     ψ   ∪E +     ψ   ∪{(l m−   ψ , l 0+   ψ , −, −, −, −, −)}∪{(l m+   ψ , l 0−     ψ   , −, −, −, −, k=k+1)}.
 
Remark 4 Algorithms 1, 2 and 3 provide translation under the fixed-step simulation semantics of Simulink. The algorithms can be modified to follow the variable-step simulation semantics as well. The variable-step solvers in the Simulink dynamically increase (or reduce) the step size (i.e., the value of T   ψ   ) if the error exceeds (or falls under) a specific limit Er ceiling  (or Er floor ) To see the modification, suppose the error calculation formula is ƒ e (y   ψ   (k), y   ψ   (k−1), . . . , T   ψ   ). Then the time-advancement edge (l m+   ψ , l 0−     ψ   , −, −, −, −, k=k+1) will be replaced by the following set of edges:
       
 
         [0000]      {( l   m+   ψ   ,l   0−     ψ   ,−,−,[ƒ e             Er   ceiling   ],T     ψ     =T     ψ   /2 ,k=k+ 1),( l   m+   ψ   ,l   0−     ψ   ,−,−,[θ e           Er floor   ],T     ψ   =2* T     ψ     ,k=k+ 1)
 
         [0000]      ( l   m+   ψ   ,l   0−     ψ     ,−,−,[Er   floor           ƒ e             Eƒ   ceiling   ],−,k=k +1)}.
 
       Example 10 
       [0191]    Consider ψ 1 =(Ψ 2 /C 2 )         θ of Example 2. The I/O-EFA model of Ψ 2 /C 2  was obtained in Example 8, and the I/O-EFA model of ψ 1 , obtained using Algorithm 3 for the conditioning-rule, is shown in  FIG. 9 . The dotted boxes contain the 1st/2nd I/O-EFAs of Ψ 2 /C 2 , and also of ψ 1 . 
       Example 11 
       [0192]    Consider the Simulink diagram ψ={ψ 1 , ψ 2 }/C of the counter shown in  FIG. 1  that was also discussed in Example 2. The I/O-EFA model for ψ 1  was obtained in Example 10, and the I/O-EFA model of ψ, obtained using Algorithm 2 for the connecting-rule and Remark 3, is shown in  FIG. 10 . 
         [0193]    Consider the Simulink diagram ψ of the bouncing ball of  FIG. 3 , and also discussed in Example 4. The I/O-EFA model of ψ, obtained using Algorithm 2 for the connecting-rule and Remark 3, is shown in  FIG. 11 . 
       6. Validation of Translating Approach 
       [0194]    In order to show that the translating approach is sound and complete, we introduce the concept of a step and of a step-trajectory of an I/O-EFA model of a system-block. In the I/O-EFA model P ψ  of a system-block ψ, each increment of k corresponds to an execution of a path π=(l 0   ψ , . . . , l m   ψ , l 0   ψ ). A computation along the kth execution of such a path gives an output value y(k) for an input u(k). 
         [0000]    Definition 6 Given an I/O-EFA model P ψ  of a system-block ψ and input uε∪ ψ , a step of P ψ  over u is the computation of a sequence of edges starting from l 0   ψ  and ending at l m   ψ , followed by the time-advancement edge. Given an input sequence {u(k)} k=0   K , a step-trajectory of P ψ  over {u(k)} k=0   K  is a sequence of steps, where the kth step (0≦k≦K) in the sequence is over the input u(k). Letting y(k) (0≦k≦K) denote the output of ψ over u(k), {y(k)} k=0   K  is called the output of step-trajectory of P ψ  over {u k } k=0   K . 
         [0195]    Next we show that the input-output behavior of an I/O-EFA model at a sampling time, defined in terms of a step, preserves the input-output behavior of the corresponding Simulink diagram at the same sampling time, defined in terms of a step. 
         [0000]    Lemma 1 Given a system-block ψ and an input u(k) and at the kth sampling time, let y ψ (k) and y P     ψ   (k) be the outputs of the steps of ψ and P ψ , respectively, over u(k). Then y ψ (k)=y P     ψ   (k), where P ψ  is obtained from the Algorithms 1, 2 and 3.
 
Proof: If ψ is an atomic-block, then from Algorithm 1 and Definitions 5 and 6, a step of both ψ and P ψ  at the kth sampling time k compute: y ψ (k)=h i   ψ (d(k),u(k)), where
 
         [0000]    
       
         
           
             
               
                 d 
                  
                 
                   ( 
                   k 
                   ) 
                 
               
               = 
               
                 { 
                 
                   
                     
                       
                         
                           f 
                           i 
                           ψ 
                         
                          
                         
                           ( 
                           
                             
                               d 
                                
                               
                                 ( 
                                 
                                   k 
                                   - 
                                   1 
                                 
                                 ) 
                               
                             
                             , 
                             
                               u 
                                
                               
                                 ( 
                                 
                                   k 
                                   - 
                                   1 
                                 
                                 ) 
                               
                             
                           
                           ) 
                         
                       
                     
                     
                       
                         
                           if 
                            
                           
                               
                           
                            
                           k 
                         
                         &gt; 
                         0 
                       
                     
                   
                   
                     
                       
                         d 
                         0 
                       
                     
                     
                       otherwise 
                     
                   
                 
                 } 
               
             
             , 
           
         
       
     
         [0000]    if G i   ψ (d(k),u(k)) holds, and 
         [0196]    i≦q ψ . 
         [0197]    If ψ=Ψ/C, then from Algorithms 2 and Definitions 5 and 6, a step of both ψ and P ψ  over u(k) at the kth sampling time compute (y ψ     j     min (k), . . . , y ψ     j   (k), . . . , y ψ     j     max (k)), where ψ j εΨ and: 
         [0198]    (i) If kT ψ +T o   ψ =k ψ     j   T ψ     j   +T o   ψ     j   :y ψ     j   (k)=(d(k),u(k)), where 
         [0000]    
       
         
           
             
               d 
                
               
                 ( 
                 k 
                 ) 
               
             
             = 
             
               { 
               
                 
                   
                     
                       
                         f 
                         i 
                         
                           ψ 
                           j 
                         
                       
                        
                       
                         ( 
                         
                           
                             d 
                              
                             
                               ( 
                               
                                 k 
                                 - 
                                 1 
                               
                               ) 
                             
                           
                           , 
                           
                             u 
                              
                             
                               ( 
                               
                                 k 
                                 - 
                                 1 
                               
                               ) 
                             
                           
                         
                         ) 
                       
                     
                   
                   
                     
                       
                         if 
                          
                         
                             
                         
                          
                         k 
                       
                       &gt; 
                       0 
                     
                   
                 
                 
                   
                     
                       d 
                       0 
                     
                   
                   
                     otherwise 
                   
                 
               
               } 
             
           
         
       
     
         [0000]    if G i   ψ     j   (d(k),u(k)) holds, 
         [0199]    i≦q ψ     j   , and 
         [0200]    u r   ψ     j   (k)=y s   ψ     j′   (k) if ((ψ j ,r),(ψ j′ ,s))εC 
         [0201]    (ii) If kT ψ +T o   ψ ≠k ψ     j   +T o   ψ     j   :y ψ     j   (k)=y ψ     j   (k−1). 
         [0000]    If  ψ =ψ         θ, then from Algorithms 3 and Definitions 5 and 6, a step of both ψ and P ψ  over u(k) at the kth sampling time compute: 
         [0000]    
       
         
           
             
               
                 
                   y 
                   
                     ψ 
                     _ 
                   
                 
                  
                 
                   ( 
                   k 
                   ) 
                 
               
               = 
               
                 { 
                 
                   
                     
                       
                         
                           h 
                           i 
                           ψ 
                         
                          
                         
                           ( 
                           
                             
                               
                                 d 
                                 ψ 
                               
                                
                               
                                 ( 
                                 k 
                                 ) 
                               
                             
                             , 
                             
                               
                                 u 
                                 ψ 
                               
                                
                               
                                 ( 
                                 k 
                                 ) 
                               
                             
                           
                           ) 
                         
                       
                     
                     
                       
                         
                           if 
                            
                           
                               
                           
                            
                           
                             
                               
                                 G 
                                 θ 
                               
                                
                               
                                 ( 
                                 
                                   u 
                                    
                                   
                                     ( 
                                     k 
                                     ) 
                                   
                                 
                                 ) 
                               
                             
                             ⋀ 
                             
                               
                                 G 
                                 i 
                                 ψ 
                               
                                
                               
                                 ( 
                                 
                                   
                                     
                                       d 
                                       ψ 
                                     
                                      
                                     
                                       ( 
                                       k 
                                       ) 
                                     
                                   
                                   , 
                                   
                                     
                                       u 
                                       ψ 
                                     
                                      
                                     
                                       ( 
                                       k 
                                       ) 
                                     
                                   
                                 
                                 ) 
                               
                             
                           
                            
                           holds 
                         
                         , 
                       
                     
                   
                   
                     
                       
                         
                           h 
                           θ 
                         
                          
                         
                           ( 
                           
                             
                               
                                 d 
                                 ψ 
                               
                                
                               
                                 ( 
                                 k 
                                 ) 
                               
                             
                             , 
                             
                               
                                 u 
                                 ψ 
                               
                                
                               
                                 ( 
                                 k 
                                 ) 
                               
                             
                           
                           ) 
                         
                       
                     
                     
                       
                         otherwise 
                         , 
                       
                     
                   
                 
                 } 
               
             
             , 
             
               
 
             
              
             
                 
             
              
             where 
           
         
       
       
         
           
             
               
                 d 
                 ψ 
               
                
               
                 ( 
                 k 
                 ) 
               
             
             = 
             
               { 
               
                 
                   
                     
                       { 
                       
                         
                           
                             
                               
                                 f 
                                 θ 
                               
                                
                               
                                 ( 
                                 
                                   
                                     
                                       d 
                                       ψ 
                                     
                                      
                                     
                                       ( 
                                       
                                         k 
                                         - 
                                         1 
                                       
                                       ) 
                                     
                                   
                                   , 
                                   
                                     
                                       u 
                                       ψ 
                                     
                                      
                                     
                                       ( 
                                       
                                         k 
                                         - 
                                         1 
                                       
                                       ) 
                                     
                                   
                                 
                                 ) 
                               
                             
                           
                           
                             
                               
                                 
                                   if 
                                    
                                   
                                       
                                   
                                    
                                   k 
                                 
                                  
                                 
                                     
                                 
                                 〉 
                               
                                
                               
                                   
                               
                                
                               0 
                             
                           
                         
                         
                           
                             
                               d 
                               0 
                               ψ 
                             
                           
                           
                             otherwise 
                           
                         
                       
                       } 
                     
                   
                   
                     
                       
                         
                           
                             if 
                              
                             
                                 
                             
                              
                             
                               
                                 G 
                                 θ 
                               
                                
                               
                                 ( 
                                 
                                   u 
                                    
                                   
                                     ( 
                                     k 
                                     ) 
                                   
                                 
                                 ) 
                               
                             
                              
                             
                                 
                             
                              
                             becomes 
                              
                             
                                 
                             
                              
                             true 
                           
                         
                       
                       
                         
                           
                             at 
                              
                             
                                 
                             
                              
                             the 
                              
                             
                                 
                             
                              
                             kth 
                              
                             
                                 
                             
                              
                             sampling 
                              
                             
                                 
                             
                              
                             time 
                           
                         
                       
                     
                   
                 
                 
                   
                     
                       
                         f 
                         i 
                         ψ 
                       
                       ( 
                       
                         
                           
                             d 
                             ψ 
                           
                            
                           
                             ( 
                             
                               k 
                               - 
                               1 
                             
                             ) 
                           
                         
                         , 
                         
                           
                             u 
                             ψ 
                           
                            
                           
                             ( 
                             
                               k 
                               - 
                               1 
                             
                             ) 
                           
                         
                       
                       ) 
                     
                   
                   
                     
                       if 
                        
                       
                           
                       
                        
                       
                         
                           G 
                           θ 
                         
                          
                         
                           ( 
                           
                             u 
                              
                             
                               ( 
                               k 
                               ) 
                             
                           
                           ) 
                         
                       
                        
                       
                           
                       
                        
                       remains 
                        
                       
                           
                       
                        
                       true 
                     
                   
                 
                 
                   
                     
                       { 
                       
                         
                           
                             
                               
                                 d 
                                 ψ 
                               
                                
                               
                                 ( 
                                 
                                   k 
                                   - 
                                   1 
                                 
                                 ) 
                               
                             
                           
                           
                             
                               
                                 
                                   if 
                                    
                                   
                                       
                                   
                                    
                                   k 
                                 
                                  
                                 
                                     
                                 
                                 〉 
                               
                                
                               
                                   
                               
                                
                               0 
                             
                           
                         
                         
                           
                             
                               d 
                               0 
                               ψ 
                             
                           
                           
                             otherwise 
                           
                         
                       
                       } 
                     
                   
                   
                     otherwise 
                   
                 
               
             
           
         
       
     
         [0202]    The following proposition shows that the input-output behavior of an I/O-EFA model over a sequence of sampling times, defined in terms of a step-trajectory, preserves the input-output behavior of the corresponding Simulink diagram over the same sequence of sampling times, defined in terms of a step-trajectory. 
         [0000]    Proposition 1 Given a system-block ψ and an input sequence {u(k)} k=0   K , let {y   ψ   (k)} k=0   K  and {y P       ψ     (k)} k=0   K  be the outputs of step-trajectories of ψ and P ψ , respectively, over {u(k)} k=0   K . Then {y   ψ   (k)} k=0   K ={y P       ψ     (k)} k=0   K , where P   ψ    is as obtained from the Algorithms 1, 2 and 3.
 
Proof: The proof follows from Lemma 1 and Definitions 5 and 6.
 
       Example 12 
       [0203]    To validate our model, a simulation for a certain input sequence (pulse with period 1.2 second and pulse width 25%) was obtained for the Simulink diagram ψ of  FIG. 1  (using fixed-step discrete solver) and is shown in  FIG. 12 . The simulation of the I/O-EFA model P ψ  was done in Stateflow. Since a step of P ψ  is defined to be the execution of a cycle starting from and ending at the initial location and visiting the final location once, the sample period for the Stateflow model of P ψ  was scaled down by the length of the cycle (the number of locations of P ψ ). The simulation result of P ψ  (using fixed-step discrete solver) is also shown in  FIG. 12 . 
         [0204]    A simulation was obtained for the multirate Simulink diagram ψ of  FIG. 2  (using fixed-step continuous solver odel Euler) and is shown in  FIG. 13 . The simulation of the I/O-EFA model P ψ  was done in Stateflow (note the computer cannot check the equality of two floating numbers, one way to handle this is to duplicate the set of T ψ s and T o   ψ s, relabel and amplify them to make them integers). Recall T ψ =0.005. The sample-period for the Stateflow model of P ψ  was scaled down by the number of locations of P ψ . The simulation result of P ψ  (using fixed-step discrete solver) is also shown in  FIG. 13 . 
         [0205]    A simulation was obtained for the Simulink diagram ψ of  FIG. 3  (using fixed-step continuous solver odel Euler) and is shown in  FIG. 14 . The simulation of the I/O-EFA model P ψ  was done in Stateflow. Recall the sample-period of ψ is 0.01. The sample-period for the Stateflow model of P ψ  was scaled down by the number of locations of P ψ . The simulation result of P ψ  (using fixed-step discrete solver) is also shown in  FIG. 14 . 
       7. Related Work 
       [0206]    We briefly introduce the works related to ours, discussing succinctly their features. [4] presented a translation algorithm for converting a restricted subclass of S/S diagrams into a semantically equivalent hybrid automaton. For the subclass of S/S diagrams considered there exists a clear separation between the discrete and the continuous dynamics: All mode changes are made through switches, and whose controlling variables are restricted to be the outputs of the Stateflow modules. In general, however, the discrete modes do not have to be determined by the output variables of the Stateflow modules, and switches do not have to be used to switch continuous dynamics. Our approach does not require a clear separation between discrete and continuous dynamics for modeling hybrid systems. Also our translation approach has no special restriction on the types of Simulink blocks. The approach supports virtually all blocks in Simulink Library (in this work we only consider time-driven blocks) provided that the block can be mathematically written as input-state-output functions over time. [5] described a translation scheme for deriving hybrid automata models from S/S models. However, no formal algorithms are provided. We presented formal algorithms for the translation. [3, 6, 13] describes a technique for translating discrete-time Simulink diagrams into Lustre programs. Lustre is a synchronous language and the translation is a mapping between elements of Simulink diagrams (for example, signals and atomic blocks) and Lustre programs (for example, flows and operators/nodes). The execution sequence of Simulink blocks in the Lustre programs is determined by Lustre compiler. Also only the discrete-time blocks are translated. In our approach, the execution sequence of Simulink blocks is directly captured in the I/O-EFA models. Also, our approach supports virtually all time-driven blocks in Simulink Library. [7] mentioned a translation of S/S diagrams into the language of “SAL [1] for the purposes of test generation. However, the details of the translation were not given. [8] reported translation of Simulink diagrams to a model of concurrent processes communicating with FIFO queues or registers, called SPI model, in contrast to I/O-EFA model in our approach. There has also been work on code-generation for simulink diagrams [12, 11]. One emphasis is in intellectual property reuse (i.e., code reuse for a group of atomic blocks) and so their approach is modular. In contrast we focus on formal modeling of Simulink diagrams with the goal of providing models that are readily amenable for further analysis (verification, test-generation, etc.). 
       8. Conclusion 
       [0207]    We presented a recursive approach for translating a class of Simulink diagrams as input/output-extended finite automata (I/O-EFA), which is amenable to automated test generation or verification. We treat the blocks in the Simulink library to be “atomic” and formulate two rules used in Simulink for building complex blocks by combining the simpler ones. We provided a recursive and formal definition for the class of Simulink diagrams formed using these rules. 
         [0208]    We presented algorithms for (i) translating an atomic-block as an I/O-EFA, (ii) combining the I/O-EFA models of simpler Simulink diagrams to build the I/O-EFA model of a more complex Simulink diagram, constructed using certain rules of composition. We introduced the concept of a step (resp., step-trajectory) of an I/O-EFA to emulate the computation of a Simulink diagram at a sample time (resp., over a sequence of sample times). We showed that the translating approach is sound and complete: The input-output behavior of an I/O-EFA model, as defined in terms of a step-trajectory preserves the input-output behavior of the corresponding Simulink diagram at each sample time (assuming the same integration method for any of the continuous blocks with dynamics). Finally, the translation approach has no specific restriction on the types of Simulink blocks or the structure of Simulink diagrams supported and can handle multirate Simulink diagrams, sample times with initial offsets and variable-step simulation etc. 
         [0209]    Although various embodiments have been shown and described in detail, the present invention is not to be limited to the specific embodiments shown as the present invention contemplates numerous variations, options, and alternatives in its implementation as may be appropriate in various situations. For example, the present invention contemplates that different types of diagrams may be used. The methodology may be implemented in various types of computing devices using any number of types of software to provide instruction sets for performing the logic of the methodologies described herein. 
       REFERENCES 
       [0210]    References below are incorporated by reference in their entireties.
   [1] Sal homepage. http://sal.csl.sri.com/.   [2] Simulink. http://www.mathworks.com/products/simulink/.   [3] P. Caspi, A. Curic, A. Maignan, C. Sofronis, and S. Tripakis. Translating discrete-time simulink to lustre.  Lecture Notes in Computer Science,  2855:84-99, 2003.   [4] A. Agrawal, G. Simon, and G. Karsai. Semantic translation of simulink/stateflow models to hybrid automata using graph transformations.  Electronic Notes in Theoretical Computer Science,  109:43-56, December 2004.   [5] R. Alur, A. Kanade, S. Ramesh, and K. C. Shashidhar. Symbolic analysis for improving simulation coverage of simulink/stateflow models. In  EMSOFT &#39; 08 : Proceedings of the  7 th ACM international conference on Embedded software , pages 89-98, New York, N.Y., USA, 2008. ACM.   [6] P. Caspi, A. Curic, A. Maignan, C. Sofronis, S. Tripakis, and P. Niebert. From simulink to scade/lustre to tta: a layered approach for distributed embedded applications.  SIGPLAN Not.,  38(7):153-162, 2003.   [7] A. Gadkari, S. Mohalik, K. C. Shashidhar, J. Suresh A Yeolekar, and S. Ramesh. Automatic generation of test cases using model checking for sl/sf models.  Workshop on Model - Driven Engineering, Verification, and Validation,  2007.   [8] M. Jersak, D. Ziegenbein, F. Wolf, K. Richter, R. Ernst, F. Cieslog, J. Teich, K. Strehl, and L. Thiele. Embedded system design using the spi workbench. In  Proc. of the  3 rd International Forum on Design Languages,  2000.   [9] R. Kumar, C. Zhou, and S. Basu. Finite bisimulation of reactive untimed infinite state systems modeled as automata with variables. In  Proceedings of the  25 th American Control Conference , pages 6057-6062, Minneapolis, Minn., June 2006.   [10] D. Lee and M. Yannakakis. Principles and methods of testing finite state machines—a survey.  Proceedings of the IEEE,  84(8):1090-1123, 1996.   [11] R. Lublinerman, C. Szegedy, and S. Tripakis. Modular code generation from synchronous block diagrams—modularity vs. code size. In  POPL&#39; 09, 2009.   [12] R. Lublinerman and S. Tripakis. Modular code generation from triggered and timed block diagrams. In  Real - Time and Embedded Technology and Applications Symposium  ( RTAS&#39; 08), 2008.   [13] N. Scaife, C. Sofronis, P. Caspi, S. Tripakis, and F. Maraninchi. Defining and translating a “safe” subset of simulink/stateflow into lustre. In  Proc. EMSOFT&#39; 04, 2004.   [14] T. Takenaka, K. Okano, T. Higashino, and K. Taniguchi. Symbolic model checking of extended finite state machines with linear constraints over integer variables.  Syst. Comput. Japan,  37(6):64-72, 2006.   [15] C. Zhou and R. Kumar. On identification of input/output extended automata with finite bisimilar quotients. In 2009  American Control Conference , St. Louis, Mo., June 2009.