Raluca Lefticaru |
|
![]() |
This paper presents the newly introduced class of (simple) kernel P systems ((s)kP systems) and investigates through a 3-colouring problem case study the expressive power and efficiency of kernel P systems. It describes two skPsystems that model the problem and analyzes them in terms of efficiency and complexity. The skP models prove to be more succinct (in terms of number of rules, objects, number of cells and execution steps) than the corresponding tissue P system, availablein the literature, that solves the same problem, at the expense of a greater length of the rules.
This paper presents the application of membrane algorithms to broadcasting problems, which are regarded as NP-hard combinatorial optimization problems. A membrane algorithm, called HPSOPS, is proposed by appropriately combining membrane systems and a hybrid particle swarm optimization with wavelet mutation (HPSOWM). HPSOPS is designed with the hierarchical membrane structure and transformation/communication-like rules of membrane systems, the representation of individuals and the evolutionary mechanism of HPSOWM. Experimental results from various broadcasting problems show that HPSOPS performs better than its counterpart HPSOWM and genetic algorithms reported in the literature, in terms of search capability, efficiency, solution stability and precision.
This paper presents an approach to P system verification using the Spin model checker. It proposes a P system implementation in PROMELA, the modeling language accepted by SPIN. It also provides the theoretical background for transforming the temporal logic properties expressed for the P system into properties of the executable implementation. Furthermore, a comparison between P systems verification using SPIN and NUSMV is realized. The results obtained show that the PROMELA implementation is more adequate, especially for verifying more complex models, such as P systems that model ecosystems.
This paper presents the existing techniques for P system testing and performs an empirical evaluation of their fault-detection efficiency. The comparison is performed using mutation testing and, based on the results obtained, some improved testing methodologies are proposed.
This paper presents an approach to P systems verification using the Spin model checker. The authors have developed a tool which implements the proposed approach and can automatically transform P system specifications from P-Lingua into Promela, the language accepted by the well known model checker Spin. The properties expected for the P system are specified using some patterns, representing high level descriptions of frequently asked questions, formulated in natural language. These properties are automatically translated into LTL specifications for the Promela model and the Spin model checker is run against them. In case a counterexample is received, the Spin trace is decoded and expressed as a P system computation. The tool has been tested on a number of examples and the results obtained are presented in the paper.
This paper presents some testing approaches based on model checking and using different testing criteria. First, test sets are built from different Kripke structure representations. Second, various rule coverage criteria for transitional, non-deterministic, cell-like P systems, are considered in order to generate adequate test sets. Rule based coverage criteria (simple rule coverage, context-dependent rule coverage and variants) are defined and, for each criterion, a set of LTL (Linear Temporal Logic) formulas is provided. A codification of a P system as a Kripke structure and the sets of LTL properties are used in test generation: for each criterion, test cases are obtained from the counterexamples of the associated LTL formulas, which are automatically generated from the Kripke structure codification of the P system. The method is illustrated with an implementation using a specific model checker, NuSMV.
This paper presents an approach for P system testing, that uses model-checking for automatic test generation and P-Lingua as specification language. This approach is based on a transformation of the transitional, non-deterministic, cell-like P system into a Kripke structure, which is further used for test generation, by adding convenient temporal logic specifications. This paper extends our previous work in this field to multi-membrane, transitional P system, having cooperative rules, communication between membranes and membrane dissolution. A tool, which takes as input a P system specified in P-Lingua and translates it into the language accepted by the model checker NuSMV has been developed and used for test case generation. Some hints regarding the automatic test generation using NuSMV and P-Lingua are also given.
The application of metaheuristic search techniques in test data generation has been extensively investigated in recent years. Most studies, however, have concentrated on the application of such techniques in structural testing. The use of search-based techniques in functional testing is less frequent, the main cause being the implicit nature of the specification. On the other hand, such techniques could be employed in functional test generation if an explicit, graph-based, model, that describes the algorithm used to produce the required results, existed. However, the process of creating and validating such a model is usually a highly-specialized and time consuming task, which quite often cannot be economically justified in the case of non-safety-critical applications. In this paper we propose a framework for genetic model based testing. Under this framework, a graph-based model of the system under test is built using a genetic algorithm. Test data is then derived from the resulting model using (possibly) metaheuristic search techniques to provide the desired level of coverage. The approach is illustrated with a case study: an array sorting program.
Recent research in membrane computing [7, 8, 6, 14] examines and confirms the anticipated modelling potential of Kernel P systems in several case studies. On the one hand, this computational model is destined to be an abstract archetype which advocates the unity and integrity of P systems into a single formalism. On the other hand, this envisaged convergence is conceived at the expense of a vast set of primitives and intricate semantics, an exigent context when considering the development of simulation and verification methodologies and tools. Encouraged and guided by the successful attempts and steady progress of [6, 14, 15], in this paper we directly address the issue of formal verification of Kernel P systems by means of model checking and unveil a software framework, kpWorkbench, which integrates a set of related tools in support of our approach. A case study that centres around the well known Subset Sum problem progressively demonstrates each stage of the proposed methodology: expressing a kP system model in recently introduced kP lingua; the automatic translation of this model into a Promela (Spin) specification; the assisted, interactive construction of a set of LTL properties based on natural language patterns; and finally, the formal verification of these properties against the converted model, using the Spin model checker.
This paper explores the modelling capacities of a new class of P systems, called kernel P systems (kP systems). A specific language for describing kP systems and its translation into Promela, the specification language of Spin, are described. This Promela specification has been further used for simulation and property verification with the Spin model checker. Also, a parallel implementation on GPU parallel architectures, realized using CUDA, is presented and the results are compared with the ones obtained using Promela and Spin. A case study, namely the Subset sum problem, which has been modelled with kernel P systems and further implemented in Promela is presented.
This paper presents a new approach to test generation from extended finite state machines using genetic algorithms, by proposing a new fitness function for path data generation. The fitness function that guides the search is crucial for the success of a genetic algorithm; an improvement in the fitness function will reduce the duration of the generation process and increase the success chances of the search algorithm. The paper performs a comparison between the newly proposed fitness function and the most widely used function in the literature. The experimental results show that, for more complex paths, that can be logically decomposed into independent sub-paths, the new function outperforms the previously proposed function and the difference is statistically significant.
The newly introduced Kernel P systems offer an unitary and elegant way of integrating established features of existing P system variants with new elements with potential value for formal modelling. This paper presents a case study illustrating the expressive power and efficiency of kernel P systems on the 3-Col problem. The use of model checking (in particular of Spin) for formal verification of kernel P systems is also discussed and illustrated in this case.
This paper presents an integrated approach for model simulation, property extraction and formal verification of P systems, illustrated on a tissue P system with active membranes solving the 3-colouring problem. The paper focuses on this problem and reports the invariants and the properties extracted and verified using a series of tools (Daikon, MeCoSim, Maple, Spin, ProB) and languages (P-Lingua, Promela, Event-B). Appropriate tools and integration plugins, which facilitate and even automate the steps involved in the aforementioned approach, have also been developed. The case study chosen is complex (it involves an exponential growth of the number of states through the use of membrane division rules) and the properties obtained are non-trivial.
Membrane computing is a recently developed research field, whose models, P systems, are bio-inspired computational models, abstracted from the structure and the functioning of living cells. Their applications are various and have been reported in biology, bio-medicine, economics, approximate optimization and computer graphics. However, it is a difficult task to design a P system which solves a given problem, especially because of their characteristics, such as nondeterminism, parallelism, possible presence of active membranes. In this paper we propose an approach to P systems automatic design, which uses genetic algorithms and model checking. More precisely, we use a type of fitness function which performs several simulations of the P system, in order to assess its adequacy to realize the given task, complemented by formal verification of the model.
Formal verification of P systems using model checking has attracted a significant amount of research in recent years. However, up to now only P systems with static structure have been considered. This paper makes significant advances in this area by considering P systems with active membranes, in particular P systems with division rules. The paper presents a theoretical framework for addressing this problem and reports on a complex case study involving a well-known NP-complete problem solved using P systems with membrane division rules. This is implemented in Promela and non trivial properties are verified using Spin.
Event-B is a formal modeling language having set theory as its mathematical foundation and abstract state machines as its behavioral specifications. The language has very good tool support based on theorem proving and model checking technologies, but very little support for test generation. Motivated by industrial interest in the latter domain, this paper presents an approach based on genetic algorithms that generates test data for Event-B test paths. For that, new fitness functions adapted to the set-theoretic nature of Event-B are devised. The approach was implemented and its efficiency was proven on a carefully designed benchmark using statistically sound evaluations.
This position paper discusses the challenges and opportunities of applying search-based techniques to a formal environment of abstract state machines defined using a language called Event-B. Event-B is based on a formal abstract machine notation that has a mature tool support and gets continuous feedback from industry. Although search-based techniques recently developed for extended finite state machines may be adapted to this context, new challenges such as implicit states, non-determinism, non-numerical data types and hierarchical models are still to be solved for test data generation for Event-B models.
This paper presents an approach to P systems verification using the Spin model checker. A tool which implements the proposed approach has been developed and can automatically transform P system specifications from P-Lingua into Promela, the language accepted by the well known model checker Spin. The properties expected for the P system are specified using some patterns, representing high level descriptions of frequently asked questions, formulated in natural language. These properties are automatically translated into LTL specifications for the Promela model and the Spin model checker is run against them. In case a counterexample is received, the Spin trace is decoded and expressed as a P system computation. The tool has been tested on a number of examples and the results obtained are presented in the paper.
Formal verification of P systems using model checking has attracted a significant amount of research in recent years. However, up to now only P systems with static structure have been considered. This paper makes significant advances in this area by considering P systems with active membranes, in particular P systems with division rules. The paper presents a theoretical framework for addressing this problem and reports on a complex case study involving a well-known NP-complete problem solved using P systems with membrane division rules. This is implemented in Promela and non trivial properties are verified using Spin.
This paper presents a method of formally verifying P system specifications by first identifying invariants and then checking them, using the NuSMV model checker, against a Kripke structure representation. The method is applied to a basic class of P systems with transformation and communication rules using either maximal parallelism or asynchronous rewriting strategy and for a special variant of P systems with electrical charges, but without active membranes.
This paper presents some approaches on testing P systems that allow building specific testing tools. The two approaches used for automatic test case generation are based on model-checking and building the derivation tree, respectively. The classes of P systems addressed so far are transitional, with evolution-communication rules, and probabilistic P systems, with electrical charges.
This paper presents a novel membrane algorithm, called particle swarm optimization based on P systems (PSOPS), which combines P systems and particle swarm optimization. The PSOPS uses the representation of individuals, evolutionary rules of particle swarm optimization, and a hierarchical membrane structure and transformation or communication-like rules in P systems to design its algorithm. Experiments conducted on seven bench function optimization problems and time-frequency atom decomposition demonstrate the effectiveness and practicality of the introduced method.
This paper presents an approach for P system testing, that uses model-checking for automatic test generation and P-Lingua as specification language. This approach is based on a transformation of the transitional, non-deterministic, cell-like P system into a Kripke structure, which is further used for test generation, by adding convenient temporal logic specifications. This paper extends our previous work in this field to multi-membrane, transitional P system, having cooperative rules, communication between membranes and membrane dissolution. A tool, which takes as input a P system specified in P-Lingua and translates it into the language accepted by the model checker NuSMV was developed and used for test case generation. Some hints regarding
In recent years there has been a growing interest in applying metaheuristic search algorithms in model-checking. On the other hand, model checking has been used far less in other software engineering activities, such as model design and software testing. In this paper we propose an automated model design strategy, by integrating genetic algorithms (used for model generation) with model checking (used to evaluate the fitness, which takes into account the satisfied/unsatisfied specifications). Genetic programming is the process of evolving computer programs, by using a fitness value determined by the program's ability to perform a given computational task. This evaluation is based on the output produced by the program for a set of training input samples. The consequence is that the evolved program can function well for the sample set used for training, but there is no guarantee that the program will behave properly for every possible input. Instead of training samples, in this paper we use a model checker, which verifies if the generated model satisfies the specifications. This approach is empirically evaluated for the generation of finite state-based models. Furthermore, the previous fitness function proposed in the literature, that takes into account only the number of unsatisfied specifications, presents plateaux and so does not offer a good guidance for the search. This paper proposes and evaluates the performance of a number of new fitness functions, which, by taking also into account the counterexamples provided by the model checker, improve the success rate of the genetic algorithm.
P systems are employed in various contexts to specify or model different problems. In certain cases the system is not entirely known. In this paper we will consider the broadcasting algorithm and present a method to determine the format of the rules of the P system used to specify the algorithm.
Landscape analysis of fitness functions is an important topic. This paper makes an attempt to characterize the search problems associated with the fitness functions used in search-based testing, employing the following measures: diameter, autocorrelation and fitness distance correlation. In a previous work, a general form of objective functions for structural search-based software testing was tailored for state-based testing. A comparison is performed in this paper between the general fitness functions and some problem-specific fitness functions, taking into account their performance with different search methods.
The application of metaheuristic search techniques in test data generation has been extensively investigated in recent years. Most studies, however, have concentrated on the application of such techniques in structural testing. The use of search-based techniques in functional testing is less frequent, the main cause being the implicit nature of the specification. This paper investigates the use of search-based techniques for functional testing, having the specification in form of a state machine. Its purpose is to generate input data for chosen paths in a state machine, so that the parameter values provided to the methods satisfy the corresponding guards and trigger the desired transitions. A general form of a fitness function for an individual path is presented and this approach is empirically evaluated using three search techniques: simulated annealing, genetic algorithms and particle swarm optimization.
This paper investigates the adequacy of a general form of fitness function, based on a state-based specification, by characterizing the associated search problem and the dynamics of the applied metaheuristic. The measurement approach of the fitness landscape is experimented on various examples and suggests some tuning choices to be made for the metaheuristic considered.
Although a lot of research has been done in the field of state-based testing, the automatic generation of test cases from a functional specification in the form of a state machine is not straightforward. This paper investigates the use of genetic algorithms in test data generation for the chosen paths in the state machine, so that the input parameters provided to the methods trigger the specified transitions.
Empirical studies report unsatisfactory fault detection of state-based methods in class testing and advocate the use of functional methods to complement state-based testing. In this paper, we take the view that the modest fault detection of state-based class testing reported in the literature is actually due to the inappropriate state diagram used. We show that functional testing of a class can be reduced to state-based testing, provided that the right state model is produced. We present a strategy for constructing a state diagram for a class method, based on a domain partition derived through functional techniques. We also describe a method for deriving test sequences from the resulting state diagrams, essentially a variant of the W-method. The paper also reports results from an experimental evaluation of the proposed approach, based on mutants generated by MuJava.
This deliverable summarizes the work conducted by the partners in the DEPLOY extension called "DEPLOY Enlarged EU". As a result of this extension, two new partners from Romania, University of Bucharest and University of Pitesti, joined the DEPLOY consortium. The work started in June 2010 and continued until the end of the DEPLOY project in April 2012. The objective of this deliverable is to report on the research performed in this project extension and on the integration of the new partners in the project.