A Family of Simulation Criteria to Guide DEVS Models Validation Rigorously, Systematically and Semi-Automatically

The most common method to validate a DEVS model against the requirements is to simulate it several times under different conditions, with some simulation tool. The behavior of the model is compared with what the system is supposed to do. The number of different scenarios to simulate is usually infinite, therefore, selecting them becomes a crucial task. This selection, actually, is made following the experience or intuition of an engineer. Here we present a family of criteria to conduct DEVS model simulations in a disciplined way and covering the most significant simulations to increase the confidence on the model. This is achieved by analyzing the mathematical representation of the DEVS model and, thus, part of the validation process can be automatized.


Introduction
The development and use of simulation models has been increasing considerably in recent years. Frequently they are used as the first representation of systems that later will be used for decision-making on critical situations. It has become increasingly necessary the definition of rigorous techniques to assure that these models represent as well as possible the real system being modeled. In other words, Verification and Validation (V&V) of simulation models has become crucial.
According to the U.S. Department of Defense directive [1] verification is "the process of determining that a model implementation accurately represents the developer's conceptual description and specifications". In the context of simulation models, the question that model verification tries to answer is: "Are we simulating, or have we simulated, the model right?". On the other hand, validation is "the process of determining the degree to which a model is an accurate representation of the real-world from the perspective of the intended uses of the model". Here, the question is: "Are we simulating, or have we simulated, the right model?".
Performing V&V of simulation models has been identified as a paramount activity as it can increase the confidence of the user in the simulation results and lead to the accreditation/certification of the simulated system [2]. This accreditation or certification is specially important when the simulation results influence decision making over crucial issues. Figure 1, presented by Robinson [3], which, in turn, is adapted from Sargent [4] shows the different phases of V&V onto the modeling process. Our work is related to the Conceptual Model Validation phase, i.e., validate the conceptual or abstract simulation model against the requirements.

Validation of Simulation Models and Model-Based Testing
The validation of a model against the requirements, usually, cannot be performed mathematically because the requirements are not formal. An alternative way is via simulations. The engineer compares the results of the simulations with the requirements in order to decide if the model is correct or not. This is particularly important when either the model is large, its implementation is critical or critical decisions are made according to the results provided by the implementation of the model or by its simulations. Besides, since it is very important to find as many errors as possible and as earlier as possible, then a thorough simulation process can be an activity that will reduce the total cost of ownership of the target system.
During model simulation it would be desirable to run simulations from all possible simulation configurations and compare these behaviors against the requirements. Unfortunately, exhaustive simulation is impractical in almost all projects, since it involves an infinite number of simulation configurations. Considering this, the selection of an appropriate set of simulation configurations is a crucial issue that should consider two opposite factors: a) the set of simulation configurations should be large enough as to give a reasonable assurance that the model is a correct representation of the requirements; and b) the set should be small enough so V&V fits within time and budget.
In this paper DEVS (Discrete EVent system Specification) [5] is used as the modeling formalism. DEVS has gained popularity in recent years and it is the most general formalism to describe discrete event systems (DES). DEVS is an abstract basis for model specification that is independent of any particular simulation implementation. It is a formalism based on system theory, expressive enough to represent all other DES formalisms, i.e. all models representable in those formalisms can be represented in DEVS [6]. Figure 2 presents a possible DEVS model validation process via simulations. According to this picture, first of all, the requirements and expected results are extracted from the Real World, or from the depiction of the problem being modeled. Based on them, the conceptual or abstract model is defined using a modeling formalism, in this case, DEVS. At this point, it is important to point out that, in order to simplify the validation process, this model must be described using a mathematical or logical representation of DEVS.
According to this validation process, once the abstract DEVS model is defined, a set of simulations configuration is derived from it. Afterwards, both, the simulations and the abstract DEVS model are refined, i.e written in the input language of some concrete simulator (for instance, DEVS-C++ [7], DEVSim++ [8], CD++ [9], PowerDEVS [10], JDEVS [11]). That is, in this context refinement means to translate an abstract representation into a concrete one. The concept of refinement is borrowed from the software engineering community [12] Finally, the (concrete) simulation results need to be abstracted. In this sense, abstraction is the inverse process of refinement. Later, these abstract results are compared with the expected results. This latter issue, generally known as the oracle problem, is acute in this context as it is, for instance, in software testing, and there is no general solution [2,13].
Despite the fact that the final goal is to formalize the whole validation process, this article is focused on the selection of an appropriate set of simulation configurations. As mentioned before, this is the crucial part of this validation process. It consists in turning an infinite problem (the set of all simulations configurations) into a finite one. Further, this must be done trying to keep in the final set the important or revealing simulations. In order words, the final set of simulation configurations must be small and must thoroughly cover all the functional alternatives described in the model. The rest of the validation process consists mainly in an implementation process and is further detailed in Section 4. In general, model simulation is performed according to the experience or intuition of a specialist. Therefore no rigorous guidelines or criteria are followed to define an adequate set of simulations, making the simulation process informal and error prone. On the other hand, given that the selection of the simulations is an informal activity it cannot be automated in a high degree. However, it can be automated to some extent if the selection process is formalized in such a way that, later, a software tool can help in this task. Therefore, it would be desirable to formally define simulation criteria to consider the simulation of a model as a validation process with an acceptable degree of accuracy.
In the software testing field there is an analogous scenario. According to Utting and Legeard [12] software testing deals with the dynamic verification of the behavior of a program on a finite set of test cases, suitably selected from the usually infinite execution domain, against the expected behavior. There are several works trying to formalize the software testing process. Most of these works belong to a subfield of testing known as Model-Based Testing (MBT). Utting and Legeard define MBT as the generation of executable test cases, based on models of the behavior of the system under test (SUT). Hence, an analogy can be established between MBT and model validation by simulation. The model can be seen as the specification of the SUT in MBT and the test case generation as the generation of simulation configurations.
Being so important in software development, the MBT process has been improved up to the point of turning it almost automatic, in many cases obtaining quite good results [13,12,14]. Thus, it is worth to explore if MBT techniques can be replicated in the context of model validation by simulation.
An important part of this automation is possible because there are precise testing criteria. That is, testing criteria indicate which tests must be generated from the model, since there is usually an infinite number of possible tests [12]. Some of these criteria are based on the exploration of the model and others on the exploration of the source code of the program.
Even though many MBT methods can be used or adapted to follow the analogy mentioned before, we based our work on the Test Template Framework (TTF). The TTF is a MBT method presented by Stocks and Carrington [15] and implemented by Cristiá et al. [14]. The TTF was introduced to formally define test data sets providing structure to the testing process. The selection of the TTF as a MBT method is motivated by the fact that it deals with the logical and mathematical definition of the model instead of analyze, for instance, traces or executions of the model. Therefore, it can be applied to systems more complex than Finite State Machines (FSM) and DEVS is much more general than a simple FSM.
Taking all of this into account, the idea of this work is to extend the rigorous validation process of DEVS models presented by Hollmann et al. [16]. Also, a possible way to automate this process is discussed here. Furthermore, a new case study is presented and, in addition, we show some possible errors that could be overlooked during the validation or simulation phase if it is not carried following some systematic and disciplined criteria. The major contribution of this paper is to present an alternative systematic and semi-automatic method to conduct the simulation process of DEVS models in order to validate them. This alternative method is based on well-known techniques in the testing world that can be adapted for the model and simulation community. We believe that simulating DEVS models following the techniques presented in this work will increase the confidence that the model is correct validating aspects or features of the model that could be overlooked by the specialist.
It is important to point out that the issue of running the simulations is not faced in this paper, leaving it as a second step of our research. Here, we give formal criteria to generate the simulation configurations that allow the corresponding simulations to be run in order to validate the model. However, we discuss how this work can be extended in such a way that simulation configurations can be provided to simulation tools.
The remainder of this paper is organized as follows. In the following section we describe and comment some other approaches to model validation. Section 3 presents the simulation criteria that form the core of our contribution. The possible automation of this validation process is addressed in Section 4. In Section 5 two case studies are described, and in section 6 conclusion and some future work is discussed.

Related Works and Similar Approaches
Below we discuss and comment different works involving verification and validation of simulation models. These works either present the most similar approaches to the one presented here, or they motivate or show why our work should be relevant for the modeling and simulation community.
Balci [17] presents guidelines for conducting verification, validation and accreditation of simulation models. He made a classification of the different V&V techniques for simulation models presenting a taxonomy of more than 77 V&V techniques for conventional simulation models and 38 V&V techniques for object-oriented simulation models. In his work, Balci listed model testing as one of the candidates for V&V of simulation models. Also, Labiche and Wainer [2] make a review of the V&V of discrete event system models. They propose to apply or adapt existing software testing techniques to the V&V of DEVS models. In particular, they claim that formal techniques should be applied. Thus justifying our approach. In several works [18,19,20,21] Sargent discusses different approaches, paradigms and techniques related to validation and verification of simulation models. These are interesting works to learn about a generalization of different validation and verification processes, however they do not describe any particular validation process in detail. Our present work complements all these papers by giving a detailed, semi-formal validation method adapted from the software engineering community.
There are several works that use verification techniques, like model checking, to verify the correctness of a model. For instance, Napoli and Parente [22] present a model-checking algorithm for Hierarchical Finite State Machines as an abstract DEVS model. They also focus on the generation of simulation configurations for DEVS, but as counter-examples obtained by the application of their model-checking algorithm. Another relevant and recent work involving verification techniques is [23] where Saadawi and Wainer introduce a new extension to the DEVS formalism, called the Rational Time-Advance DEVS (RTA-DEVS). RTA-DEVS models can be formally checked with standard model-checking algorithm and tools. Further, they introduce a methodology to transform classic DEVS models to RTA-DEVS models, allowing formal verification of classic DEVS. Although model checking techniques are formally defined and they are useful to prove properties and theorems over a model, the main problem of such techniques is the so-called state explosion problem [24], i.e. the exponential blowup of the state space and variables in any real or practical system. This made almost impossible the use of such techniques in large projects, although model checking has been used in real projects.
K. J. Hong and T. G. Kim [25] introduce a method for the verification of discrete event models. They propose a formalism, Time State Reachability Graph (TSRG), to specify modules of a discrete event model and a methodology for the generation of test sequences to test such modules at an I/O level. Later, a graph theoretical analysis of TSGR generates all possible timed I/O sequences from which a test set of timed I/O sequences with 100% coverage can be constructed. Similar to our work, they make an analogy between model verification and software testing.
Another recent work that applies verification techniques over discrete event simulation is [26] where da Silva and de Melo presents a method to perform simulations orderly and verify properties about them using transitions systems. Both, the possible simulation paths and the property to be verified are described as transition systems. The verification is achieved by building a special kind of synchronous product between these two transition systems. They focused their work on the verification of properties by simulation but not on the generation of simulations in order to validate the model.
Li et al. [27] present a framework to test DEVS tools. In their framework they combine black-box and white-box testing approaches. Actually, this work is not really related to ours because they do not validate or verify a DEVS model, whereas they test DEVS implementations. However, it is useful to see how they introduce software testing techniques in the DEVS world.
After reviewing many works about V&V for simulation models it seems that there is no proposals similar to the validation method presented in this article. For instance, we could not find any work that deals with the mathematical or logical representation of the model as a starting point of the validation process. Moreover, we think that, in general, people of the modeling and simulation community do not take this issue into account. Actually they develop their models directly over a simulation tool, using its own modeling language, and make experiments directly over it. By working with the concrete model, these techniques aim at a verification problem, i.e. comparing the concrete model with the abstract model. We, on the other hand, propose, as a complementary technique, to work with the abstract model to check whether it conforms with the user requirements or objectives. More concretely, our work proposes a method to formally validate abstract models and to introduce well known MBT techniques into this community.

A family of simulation criteria
The simulation criteria presented in this work aim to provide a guideline for methodically simulate DEVS models in order to validate them. As we mentioned in the introduction, DEVS is a formalism widely used in the modeling and simulation community and is the most general formalism to describe discrete event systems.
According to Zeigler et al [5], there are two classes of models, Atomic models and Coupled models. Our work concerns only atomic models. In fact, a coupled model is equivalent to a (complex) atomic model [5].
An atomic DEVS Model is defined by the structure: where: • X is the set of input event values, i.e., the set of all possible values that an input event can assume; • Y is the set of output event values; • S is the set of state values; • δ int : S → S is the internal transition function; • δ ext : Q × S → S is the external transition function, where: , s ∈ S, 0 ≤ e ≤ ta(s)} is the total state set, and e is the time elapsed since last transition; • λ : S → Y is the output function; and • ta : S → R + 0,∞ is the time advance function.
δ int , δ ext , λ and ta are the functions that define the system dynamics. Each possible state s ∈ S has associated a time advance, ta(s) ∈ R + 0,∞ , which indicates the time that the system will remain in that state if no input events occur. Once that time has passed, an internal transition is performed, reaching a new state s , s = δ int (s). At the same time, an output event, y, is generated by the output function, y = λ(s). Therefore, δ int , ta and λ define the autonomous behavior of the system.
When an input event arrives, an external transition is performed. The new state depends on the input value, the previous state and also the elapsed time since the last transition. If the system is in the state s and the input event x arrives in the instant e (i.e. e time unites the last transition) the new state, s , is calculated as s = δ ext (s, e, x). In case of an external transition, no output event is generated.

Simulation Configurations Partition
Given a DEVS model, in order to simulate it with some simulation tool, it is necessary to provide an initial state (not defined by the formalism) and a sequence of input events with their corresponding occurrence time, we call this initial state and sequence of input event a Simulation Configuration. Usually, the set of possible simulation configurations (all possible initial state and all possible input events) is infinite, even if the model has finite sets of inputs, states and outputs. Therefore, validation via simulation requires to select some of these possible simulation configurations, see Figure 3. Currently, this selection is done according the experience of the engineer, therefore, a domain expert is usually needed.
The technique presented in this work proposes to divide the set of all possible simulation configurations into equivalence classes by applying one or more partition criteria. We call each of these equivalence classes a Simulation Configuration Class (SCC), i.e. a SCC is a set of possible simulation configurations. Afterward, one simulation configuration of each SCC must be selected, see Figure 4. These selected simulation configurations are the only one that should be executed.
The reason for selecting just one simulation configuration from each class is based on the uniformity hypothesis presented by Bougé et al. [28]. They assert, in software testing, that "A program behaves uniformly on a equivalence class if the following holds: if the program

Simulation Configurations
Partitions Figure 4: Our Proposal: Simulation Configurations Partition works correctly for some input data of the equivalence class then it works correctly for any of them." This is a key assumption made by the software testing community because it allows to reduce the potentially infinite input domain to a small, finite one. Being an assumption it is not proved although many testing methods are based on it [13]. In fact, the very idea of testing is implicitly based on this hypothesis because a single test case actually represents a whole class of test cases. In other words, when a tester selects a test case, he or she is assuming that it represents a set of possible candidates.
We adapt this concept to model validation. Therefore, we say that these subsets, in which the set of possible simulations was divided, are equivalence classes because it is assumed that the model has an uniform behavior for each subset of simulations. Furthermore, if the uniformity hypothesis holds and an error in the model is found for some simulation of a given class, then the same error would be revealed with any other simulation of that class.
In this context, the uniformity hypothesis can be formalized as follows. Let M abs be some abstract model (M abs can be seen as a mathematical or logical formula), M con its concrete model, i.e. its corresponding refinement in a simulation tool language. If a is a simulation configuration derived from M abs , let a be its refinement. Then, M con (a ) means the execution of a on M con ; and M abs (a, M con (a )) asserts that M con (a ) is the expected result with respect to a according to M abs . Note that if M con (a ) is not the expected result of a according to M abs , then M abs (a, M con (a )) if false (i.e. ¬M abs (a, M con (a )) is true). Then, the uniformity hypothesis holds if and only if for every SCC i and a ∈ SCC i the following holds: that is, the uniformity hypothesis holds if the model behaves the same for any two elements of a given SCC i .
With this uniformity hypothesis, some strategies or criteria assume that every element of a class is equivalent to all the others (of the same class) for the simulation of a particular functionality of the model. However, this is just an hypothesis and it is not always satisfied. Therefore, as noted by Stocks and Carrington [15], this assumption is often invalid and they propose to apply repeatedly the strategies in order to partition the classes into sub-classes until either the engineer considers that the classes are reasonable small or each functionality of the model is covered by only one class [29].
Each element of a SCC consists of an initial state (to initialize the simulation) and an input pair containing the event to simulate and its corresponding time, i.e. when the event must be simulated.
Following this idea, in order to describe a SCC we need to define the set of possible initial states and the set of possible input pairs for the simulation. An input pair is an ordered pair (event, time). Therefore a SCC is defined by: • a set of states, IniSt ⊆ S, and • a set of ordered pairs of event and time, where τ represents the no event situation and an internal transitions occur in that case. This is necessary to indicate the simulation of an internal transition.
It is important to point out that in the DEVS formalism no initial state is defined. This, actually, belongs to the simulation phase and, since this work aims to conduct these simulations, an initial state must be defined. This is not necessarily the initial state of the system it is just the starting state for the simulation. Moreover, defining the initial state makes the simulation of the different functionalities of the model simpler, since it would not be necessary to guide the system to a particular state and start a simulation from there.
The total class of simulations, i.e. the set of all possible simulations, for a given DEVS model is defined by: IniSt represents all possible initial states from which a simulation can be started. Note that, initially, all the states of the model, i.e. S, are potential candidates. InP airs is the set of all possible input pairs. Therefore, the idea is to partition IniSt × InP airs by analyzing the DEVS model guided by criteria defined below.

Partition Criteria
Now we present the different partition criteria proposed in this work. The criteria are applied to different aspects of DEVS models. Some criteria apply, for instance, to the external transition function definition, others to the internal transition function definition and others to the definition of the states or input and outputs sets.
It is important to mention that at any time of the partition process it is possible that some criteria could not generate new classes, this is because the result could be classes already obtained. Moreover, it does not matter the order in which the criteria are applied, since each criterion is independent from the others.
In each of the following subsections a partition criterion is described.

Transition Functions Defined by Cases
It is very common to define the external and internal transition functions by cases. The first and more intuitive criterion is to partition the set of possible simulations into several classes, one for each case in the definition of the function.
Let δ ext and δ int be the transition functions of a DEVS model defined by cases: where expr i ext and expr j int are the results of the function if the proposition P i ext or P j int , respectively, holds. This criterion proposes to generate one class for each proposition in the definition of the internal and external transition functions. Each class is defined by: • Associated to the External Transition Function: • Associated to the Internal Transition Function: In the case of the internal transition the idea is to configure a certain state allowing a particular internal transition to occur, that's why the time relative to the τ event is 0.

Extensional Sets
In the definition of DEVS models, sometimes, some sets are defined by extension (states, input events or output events), i.e. listing the elements of the set. Necessarily these sets will be finite and relatively small. Therefore, this criterion proposes to simulate all scenarios where appears at least once each element of these sets.
Let us suppose that the set of states values, S, of some DEVS model is an extensional set: . . , s n } therefore, the classes generated by applying this criterion should be: with i ∈ [1, n]. By applying this criterion the engineer guarantees the simulation of the model in each possible state. However, if this criterion is only applied over the state definition, and no other criterion is applied, certain input events would not be simulated for certain states.
Let us suppose now, that the set of input variables is defined as: the resulting classes now would be: Herein, the engineer ensures to simulate all possible input events. Combining these classes with the former, allows the simulation of all states with all inputs. This is explained further in section 3.3.

Intentional Sets
Set comprehensions or intentional sets is another usual form for defining sets in a DEVS model, i.e. specifying the properties that each element of the set must comply. This is done by a logical predicate, that could be a simple one or a very complex definition involving several operations. Thus, this criterion proposes to use this definition to partition the set of simulation configurations.
Let us suppose that the set of state is an intentional set, S = {s : T Y P E | P (s)}, where T Y P E is the type of the elements of the set and P is a logical predicate. The criterion proposes, first, to write P in its disjunctive normal form (DNF) [30]: . . ∧ P m nm ) and, afterward, partition the simulation configurations set according to this DNF: The same idea can be applied to the set of inputs, outputs or any other intentional set of the model. For instance, let us suppose that the set of inputs X of a given model is X = {(n, m)|n * m > 0 ⇒ n > m}. Therefore, the predicate P = n * m > 0 ⇒ n > m is written is its DNF by applying a known algorithm [30], P = ¬(n * m > 0) ∨ (n > m) and two SCCs should be defined, one for the predicate ¬(n * m > 0) and the other for n > m.

Standard Partitions
In almost all models, different mathematical operators appear in the definitions of the model elements (transition functions, time advance function, state values) and they can be simple (addition, sets union) or more complex (operators defined in terms of simpler ones, functions defined in a programming language or in a pseudo-code). Each operator has a particular input domain and this criterion proposes to divide this domain associating to it a standard partition. A standard partition is a partition of the operator's domain into sets called sub-domains; each sub-domain is defined by the conditions that each operand of the operation must satisfy. Thus, each sub-domain is transformed into a condition to generate a SCC.
Therefore, for each operator in the model a standard partition should be defined. For example, for the operator < (a < b), the standard partition could be [29]: Let us suppose that x 1 , . . . , x n are some of the variables that define the set of states, S, of some model and θ(x 1 , . . . , x n ) is an operator of arity n with the associated standard partition SP 1 (x 1 , . . . , x n ), . . . , SP m (x 1 , . . . , x n ). When θ appears in an expression the set of possible simulations must be partitioned using the standard partition associated with it:

Domain Propagation
This is a particular criterion, since it does not generate new partitions by itself. The purpose of it is to obtain standard partitions of complex operators combining the standard partitions of simpler sub-operators.
Each sub-operation has input domain partitions of its own which are ignored by the standard partitions criterion if it is applied to the complex operator. Using domain propagation the input domain partition of sub-operations are propagated to the higher level [31].
For example, let be a complex operator defined as: (A, B, C) = (A B)♦C where and ♦ are simple operators. Let us suppose that and ♦ have the following standard partitions: We apply first SP to the sub-expression (A B), replacing the formal parameters appearing in SP by A and B respectively: Afterward we do the same with SP ♦ , obtaining: Finally, we combine both propositions obtained and simplify:

Time Partitions
In timed formalisms, like DEVS, modeling the time is a crucial issue. It is very common, in DEVS models, to use additional variables to model time. Furthermore, one characteristic of these models is that the elapsed time appears in the external transition function definition as a variable. Therefore, in the validation of such a model, a question arise: "how do we know if each event has been already simulated in all relevant or significant time interval?". That is, those time intervals in which it is possible to find an error in the model. Again, to answer that question all events must be simulated in all possible time interval making the validation an infinite process.
Therefore, this criterion consists in, first, identifying those variables of the state that interact with the elapsed time or are used to simulate the time advance or timers, for instance. Afterward it defines key time points, or intervals according with the interaction of those variables, for example, using the standard partition for the operations that involve every time variable. Once these key time intervals are defined, one class must be generated for each input at each time point. For example, let us suppose that the time interval [a, b] is relevant to see a particular functionality of the model, therefore it would be meaningful to simulate input events (x, t) with x ∈ X ∪ {τ } and times t < a, t = a, a < t < b, t = b and t > b. Formally, for each defined time interval [a i , b i ], five SCCs should be created: and for each defined time point t j , three classes should be created: The intention of this criterion is to simulate different scenarios where events occur at different moments, to verify the interaction of those variables used to simulate the time among them and the interaction between these ones with the elapsed time (for external transitions).
Later, when this classes are combined with those generated, for instance, by the Extensional Sets criterion, it will be able to simulate all input events in all relevant time instants.

Combining Classes
As has been mentioned in Section 3.2, the partition criteria are independent from each other. Furthermore, each simulation configuration aims to validate a particular characteristic of the model. However, it is usually more efficient to simultaneously validate more than one characteristic. We use efficiency as a measure of the number of errors found in the model. Computational efficiency is not addressed here.
In order to achieve this, it is better to combine the classes generated by applying each criterion. Observe that, however, not all criteria are always applied. This will depend on the model and on the time available for validating it. Also, observe that the same criterion can be applied more than once on the same model. For instance, if the criterion known as Extensional Sets is firstly applied over the state set and secondly over the input set of a given model, the result is two independent sets of configurations. These sets of configurations can be combined in order to simulate the arrival of every input event on every state. In this way, these combined SCCs would find errors, for example, due to the arrival of an event on a wrong state.
Let us see how SCCs can be combined with a toy example. Let M T = (X, Y, S, δ int , δ ext , λ, ta), with X = N and S = N × {ON, OF F }, be part of the model of some system. Suppose that after applying some criteria the following SCCs are obtained: Now, we can combine these classes by intersecting the corresponding IniSt and InP airs sets as follows: InP airs e = InP airs a ∩ InP airs Note, however, that only SCC d and SCC e are valid SCC since SCC f is empty because IniSt f is an empty set. As this example shows, combining SCCs by intersection may yield empty classes. If this is the case: a) eliminate them; and b) keep the SCCs that produced the empty ones.
Observe that, since intersection is commutative, it is the same to combine, for instance, SCC a and SCC b as SCC a ∩ SCC b or as SCC b ∩ SCC a . Moreover, if SCC d is the result of combining SCC a and SCC b , and SCC d is combined with some SCC α the result is SCC b ∩ SCC a ∩ SCC α which is the same regardless of the order in which classes are combined. In summary, SCCs can be combined in any order.

Simulation Sequencing
Once all SCCs are defined it is necessary to set the initial state of the simulation and to execute a transition. However, the new state obtained from the transition may be the initial state of another SCC. If this is the case, then it would be computationally more efficient to continue the simulation by executing the transition indicated by this other SCC. This avoids a new configuration of another simulation for the mentioned SCC, i.e. this reuses the configuration left by the previous run. Then, this process yields a sequence of configurations that should be run one after the other.
Here we propose an algorithm to generate these sequences by analyzing the classes obtained by the application of the criteria. The pseudo code of the algorithm can be seen in Algorithm 1, and it is explained below. select scc ∈ T otSCC 3: select is ∈ scc.IniSt

7:
T otSCC ← T otSCC \ {scc} 8: while ∃ scc ∈ T otSCC | s ∈ scc .IniSt do 9: select scc ∈ T otSCC | s ∈ scc .IniSt 10: select ip ∈ scc .InP airs 11: s ← simulate(s, ip ) SimSeq ← SimSeq ∪ {seq} 16: end while The main progress of Algorithm 1 is led by the following idea: select one SCC (scc ∈ T otSCC), an initial state from that SCC (is ∈ scc.IniSt) and simulate one event of the set of input pairs (event, time) associated to that SCC (ip ∈ scc.InP air). simulate(s, ip ) means to execute on step of the simulation model. Once the selected event has been simulated and a new state, s, is reached the current sequence is updated (sentence 6) and the set of SCCs is reduced by removing the SCC added to the sequence (sentence 7). Now, there are two alternatives: a) wait for an internal transition to occur (if ta(s) = ∞); b) simulate another event. As shown in sentence 8, if there is a SCC, scc , such that s is one of its initial states, then scc is chosen as the next SCC. In which case one of its input pairs is simulated (sentences 10 and 11). Afterward, the process continues repeatedly choosing an event or waiting for an internal transition. At any point of this process, if the state reached from the last simulation step does not belong to any initial state of the remaining SCCs, that sequence ends there and it is added to the set of configuration simulation sequences (sentence 15). A new configuration simulation sequence is started if there are more SCCs.
Thereby, with Algorithm 1 all SCCs are used at least once. Further, more complex coverage criteria could be defined for the generation of the sequences, for example, in a similar way than Souza et al. [32].

Discussion and Automation
As has been mentioned in the introduction, the technique presented in this paper would allow the automation of an important part of the DEVS model validation process. The intention of this section is to show that it would be possible to build a software tool to assist engineers when they apply our method. Therefore, we explain what can be automatically done in each step and we describe the main issues that need to be addressed in order to achieve this automation. Also, further considerations about this methodology are discussed.
An overview of this semi-automated process is the following: 1. Parse the mathematical description of the DEVS model. 2. Select and apply the partition criteria to generate the simulations. 3. Select simulations and generate simulation sequences. 4. Translate the simulation configurations into some simulation language and simulate them. 5. Translate the simulation results into the model formalism. 6. Compare the results with the requirements in order to achieve a verdict about the validation of the model.
The mathematical description of a DEVS model can be automatically be parsed only if it is written in a standard, formal notation. Being so important this issue in the modeling and simulation community, there exists an international group [33] trying to develop standards for a computer processable representation of the mathematical description of DEVS models. This is still an open area. This standard should be based on mathematics and logics, for instance, like Z [34] or TLA [35], instead of a standard based on or akin to a programming language. In this way, engineers do not need to have programming skills for writing their models. For example, we think that DEVSpecL [36], a DEVS specification language developed by Hong and Kim, looks more like a programming language rather than a mathematical representation of DEVS. The definition of a standard mathematical language for DEVS involves the definition of its syntax and semantic and the implementation of a compiler or parser to transform the mathematical model to the input language of a simulator.
Regarding the application of the criteria, a preliminary analysis indicates that it would be appropriate to apply them semi-automatically. We think that a tool should allow engineers to select which criterion must be applied to which part of the model. Moreover, the engineer could add new criteria and use them. Another alternative would be to implement an heuristic that automatically select the criteria according to an analysis over the description of the model.
The application of the criteria involves an important problem, which is the total number of SCCs generated. A preliminary analysis indicates that, although the number of classes could be considerable, it is not exponential since the number of criteria involved is fixed and small. The crucial issue is the combination between classes. The order of classes is given by O(x n ) where x is the number of classes generated by a criterion and n the number of criteria applied (recall that n is fixed and small).
Once the criteria have been applied and the SCCs have been defined in the following phase one simulation configuration for each SCC is selected. Finding a simulation configuration for a given SCC means to find an element belonging to it. Usually, this involves solving a formula over Set Theory, Arithmetic over Integer and Real Numbers and, possibly, other mathematical theories. Further, free variables range over infinite sets, making the problem undecidable. One possibility is to adopt a Satisfiability Modulo Theories (SMT) solver [37,38], by adapting the work of Cristiá and Frydman [39]. Another alternative could be to use constraint solvers such as {log} (pronounced 'setlog') [40,41,42].
The simulation configurations generated above, are described essentially in mathematics. Therefore, to perform the simulations these need to be refined, i.e. rewritten in the input language of some simulation tool, as the model definition. A possible way to do this, is adapting the work done for MBT [43]. This would be a semi-automatic process, since the engineer must define some rules to do this translation.
After performing the simulations, the reverse process must be done. That is, the results of these simulations must be rewritten in the mathematical or formal language used to describe the DEVS model. Again, this would be a semi-automatic process due to the definition of the translation rules. Then, the simulation results can be compared with the expected result (Requirements). This comparison is necessarily manual since involves the requirements.
Besides, it is possible to use this methodology to test the concrete simulation model. However, note that both validations cannot be done simultaneously for the same model. In effect, if our methodology is used to validate the abstract model it is necessary to assume that the concrete model is a faithful representation of the abstract one. On the other hand, if it is used to validate the concrete model it is necessary to assume that the abstract model is correct with respect to the requirements.
Finally, as can be seen, the simulation criteria are applied over the mathematical definition of the model and are based also on mathematical or logical operations. Therefore, the proposed validation methodology is rigorous and systematic (because it is based on mathematics, logic and formal languages). Moreover this methodology is systematic since the whole set of simulation configurations is systematically partitioned obtaining refined and more expressive simulation configuration classes. In this way, given that covering all possible paths of the model is impossible (because they are infinite) we propose to cover the logical and mathematical structure of the model, thus, covering the significant paths of the model.

Case Studies
In this section we show the application of the criteria in two examples. In each case, first we present the requirements of the system, then we describe the DEVS model and finally the SCCs that follow the application of the criteria.

Elevator
The following requirements correspond to the control system of an elevator. It has a control panel with one button for each floor and two other buttons, one for opening and one for closing the door. Furthermore, it has a switch to interrupt or restart its operation. Every time the elevator reaches a floor it receives a signal (the same signal for all floors). To prevent accidents or malfunction of the elevator, it has two sensors, one to check, before or during the door close, if someone or something is crossing it; and the other one to prevent exceeding the weight limit of the elevator. To complete the functionality of the elevator, the system has three timers, whose purpose is described below.
The requirements of the system are: • The door should not be closed if: -Any sensor is active (someone or something is crossing the door, or the weight limit is exceeded).
-The Stop Switch is on.
• If the elevator is stopped at any floor and someone call it from another floor or someone press the button (on the control panel) of another floor, after T D 1 units of time the door should start closing, and takes T D 2 units of time to close completely. However, if the Open Button is pressed or the door sensor activates the timer is reset.
• If after T A units of time (T A > T D 1 ) since the elevator is called the door is not closed, an alarm is fired. Unlike the former timer, this is not reset even though the door sensor is activated or the open button is pressed. It is reset only when the door is totally closed and the elevator starts moving. If the alarm is fired, it should be turned off when this timer is reset. • This elevator has no memory, therefore, it goes to the first floor indicated since it has been stopped. Figure 5, Figure 6 and Figure 7 represent a possible DEVS model corresponding to the control system of the elevator described before.  ((f, f c, eng, d, (ws, ds), sw, a, (at, dt1, dt2, gf t, ot), nt)) =
The input, can be a number (indicating a floor) or different signals, indicating that the elevator has reached a floor, the weight or door sensor has been activated or deactivated, the opening or closing door button is pressed or the switch is turned on or off.
The output, in turn, is a tuple, where each variable represent an indication, respectively, for the display, the engine, the door and the alarm. ⊥ means "do nothing".
Regarding the internal transition function let us describe some cases in order to understand it. For instance, the case (15) represents when the timer of the alarm finish and the alarm must fire, with its corresponding cases (24) and (25) in the output function case. The case (9), in turn, represents when the open button is pressed and the door must be opened, being the door closing. The corresponding case in the output function is (15).
On the other hand, the external transition function is more intuitive to understand each case of it. For instance, case (1) represents when the elevator is called from some floor, different from the actual, the engine is stopped and there is no other floor called. Meanwhile, cases (8) and (9) stand for the case when the switch is activated being the engine stopped or not respectively.

Generating Simulations
Starting with the set of all possible simulations for this example, we now apply each criteria presented before generating different classes. Later, these classes are conjoined, generating new classes. For each criterion, here, we show only some classes, the rest of them can be observed in Appendix A.
Transition Function Defined by Cases. The first criterion that we apply to this example uses the definition of the external and the internal transition functions generating one class for each case in each function definition.
To describe the SCCs for this example, we will use several times a generic s ∈ S defined as s = (f, f c, eng, d, (ws, ds), sw, a, f (at, dt1, dt2, gf t, ot), nt).
Some classes generated by this criterion: Extensional Sets. In this example we have six sets defined by extension, Engine, Door, Sensors, Alarm, Switch and N extT imer. Furthermore, X is the union of an infinite set and a set defined by extension. Since these sets have a relative small number of elements (considering only the finite set of the union resulting in X), we should define one SCC for each element of them, as this criterion proposes: Standard Partitions. Now we apply the standard partitions criterion over the operators <, >, + and −. For these operators could be used the same standard before in subsection 3.2.4. However, some cases must be ignored since the involved variables can not be less than zero (f ≥ 0 and f c ≥ 0). The following classes are some of the result of applying this criterion. The first two relate to the occurrence of the operators < and > in the definition of the internal transition function and the last two, to the occurrence of the operators + and − in the external transition function.
Finally, we apply this particular criterion, taking into account the relation between the elapsed time, e, and the variables used for the timers: at, dt1, dt2, gf t and ot. Considering the values that this variables assume, the relevant key time intervals are: [0, . Therefore, the relevant times t to simulate the each input event are: Hence, some of the classes generated by this criterion are: Combining Classes. Once all criteria are applied we make the intersection of the resulting classes obtaining new and refined ones. Here, we show only some of the classes yielded by these combinations. For example, if we want to test when someone call the elevator from some floor when the engine is stopped with the door open we must conjoin SCC 1 and SCC 49 resulting as follows: • SCC 1 ∩ SCC 49 : InP airs 89 = InP airs 1 ∩ InP airs 49 = Here it can be seen the effect of the commutativity of intersection, since SCC 1 ∩ SCC 49 than SCC 49 ∩ SCC 1 Another interesting combination results from SCC 1 and SCC 57 , because now, the alarm is fired: • SCC 1 ∩ SCC 57 : With the following two classes, errors could be found if the tie-breaking rules are not well defined or they are not given at all. These are obtained by combining SCC 36 with SCC 87 , on one side, and SCC 13 , SCC 59 and SCC 85 on the other. For instance, the SCC defined by IniSt 91 and InP airs 91 simulates the case when the elevator is called at the same time when the "ground floor timer" finish.

Soda can vending machine
This system consists in the control of a soda can vending machine. The machine accepts coins of $ 0.25, $ 0.50 and $ 1. It gives change, optimizing it (i.e. giving the less coins as possible).
The machine has cans of two different prices (normal and diet), and the system that controls the machine must comply with the following requirements: • During an operation, if after T ret units of time no coin is introduced into the machine or no soda is selected, the machine returns all the money that has been introduced.
• Prices of sodas increase as time passes. Every T incr units of time both prices are increased in $ 0.25.
• if the returned money is not collected by the user after T chg units of time the machine recovers it.
• The machine has a display that shows the amount of money introduced or the change after an operation.
• At any time, before selecting a soda, the user can cancel the operation and the machine returns the money.

DEVS Model
In Figure 8 is described a possible DEVS model for this example.
In this model, a state s ∈ S is a tuple where each variable represents, respectively, the machine state, the display, an internal timer, the actual prices (normal and diet), the timer controlling the prices increment, the money stored in the machine, the money inserted for the current operation and the change.
The input values represent, each coin denomination, the request of a normal or diet soda, the cancellation of the current operation and the signal of the change retreated.
The external transition function has one case for each input different from a coin (2, 3, 4 and 5) and one case (1) for all coins. Meanwhile, the internal transition function has one case for each internal state of the machine (m ∈ M achState) for the "operational timer" (1, 2, 3, 4 and 5) and one case (6) for the timeout of the "increase price timer".
The output consists of an ordered pair indicating what to show in the display and how much money (if any) must be returned.

Generating Simulations
As in the previous example, we start with the set of all possible simulations, apply the criteria generating different classes and later conjoin this classes obtaining new ones. As in the previous example, here we show only a few classes. The whole description of the classes obtained can be found in the Appendix B.
Transition Function Defined by Cases. Here we also use a generic s ∈ S to describe the SCCs for this example, defined as s = (m, d, ot, np, dp, it, ms, om, mr).
Some of the classes generated applying this criterion are: • ≥ appears twice (d ≥ np and d ≥ dp) and the standard partition for this operator is equal to the standard partition for the < described in section 3.2.4. The following classes are some the result of applying this criterion. The first two correspond to the application of the criterion over the operation d ≥ np and the last one over the operation d ≥ dp: -IniSt 12 = {s : s ∈ S | d = np = 0}, InP airs 12 = {(x, t) | x ∈ X ∪ {τ }, t ∈ R + 0 } -IniSt 14 = {s : s ∈ S | d = 0 ∧ np > 0}, InP airs 14 = {(x, t) | x ∈ X ∪ {τ }, t ∈ R + 0 } -IniSt 19 = {s : s ∈ S | d > 0 ∧ dp > 0}, InP airs 19 = {(x, t) | x ∈ X ∪ {τ }, t ∈ R+ 0 } • ⊕, by definition, is based on + and with the same type involved, N 0 , therefore they could have the same standard partition. However, since they involve only elements in N 0 no further significant partitions can be proposed. Except if we want to simulate those cases where the implementation of those operations in the modeling language could rise some errors, e.g. overflow errors. In this case, the errors are not properly in the model but in its implementation. This is more related to a testing problem rather than validating through simulations.

Conclusions and future work
We present a family of criteria to conduct DEVS model simulations in a disciplined way and covering the most significant simulations to increase the confidence on the model. The main advantage of performing the simulations of a model as we propose is that users do not need the experience of a specialist or group of specialists, neither a domain expert, to select the simulations to validate the model. The selection of simulations is the result of following a set of formal rules over the mathematical model without having to know about the domain over which it is modeled. This decreases the possibility of overlooking some simulation configurations which could find errors in the model. Another advantage of this work is the possibility of automating at least part of the validation process of DEVS models. An important open issue that needs to be addressed to enable automation is to develop a formal grammar for a mathematical language to describe DEVS models. The development of this grammar is part of our future research.
It should also be considered the possibility of re-using these techniques to test software derived from a DEVS model. A DEVS model could be used as a suitable form of the specification of a system to be implemented in some programming language. The simulation sequences generated from the application of the partition criteria could be used as test cases to test the implementation. Moreover, there exist simulation tools that generate code automatically. Thereby, if the model is thoroughly validated, the resulting piece of software would be correct.
Future work concerns with the automation of the validation process by simulation. First it is necessary to define a standard language to write the mathematical description of a DEVS model. Afterward, we would design and develop the validation tool, including a parser for the standard language, the simulation generator and an automatic translator to some simulation tool. This would also include the definition of new coverage criteria for sequencing simulations.
Other lines of future research are: a) to extend the partition criteria to coupled models; and b) to adapt this validation technique to other formalisms.