Minimizing the size of finite automata is a fundamental problem in theoretical computer science. Beyond standard minimization, further reductions can be achieved by decomposing an automaton into smaller components whose languages combine via intersection or union to recover the original language. However, in general, no polynomial-time algorithm is known for computing such decompositions. In this paper, we focus on automata that recognize ideals, that is, languages at level 1/2 in the Straubing–Thérien hierarchy. Equivalently, these languages are expressible as a finite union of languages of the form Σ^*a₁Σ^*… Σ^*a_nΣ^* where Σ is an alphabet and a_i are letters of Σ. We show that the two problems of deciding whether an automata recognizing an ideal can be decomposed into an intersection or a union of smaller automata are decidable in NL. Moreover, we provide a polynomial-time algorithm that computes a decomposition into an intersection, if one exists, while ensuring that the resulting components also recognize ideal languages.

We study bounded deviation of non-deterministic finite transducers under the Hamming distance: the bounded comparison problem asks, given two transducers and k ∈ ℕ, whether for every input the two transducers produce words at Hamming distance at most k. This problem is known to be decidable in polynomial time when k is fixed, and in co-NP otherwise. We show that the problem is NL-complete when k is fixed, co-NP-complete when k is given in binary, and it is DP-complete to decide if the distance is exactly k. We also prove that if the two transducers have bounded comparison, then the maximal distance is at most quadratic in the size of both transducers, and that this bound is asymptotically tight. We prove the results on deviation problems, which asks similar questions on the distance of the pairs of input and output of a single transducer, and show that these two families of problems are logspace many-one equivalent.

Scheduling independent tasks on a parallel platform is a widely-studied problem, in particular when the goal is to minimize the total execution time, or makespan ($P\Vert C_{max}$problem in Graham's notations). Also, many applications do not consist of sequential tasks, but rather parallel moldable tasks that can decide their degree of parallelism at execution (i.e., on how many processors they are executed). Furthermore, since the energy consumption of data centers is a growing concern, both from an environmental and economical point of view, minimizing the energy consumption of a schedule is a main challenge to be addressed. One can then decide, for each task, on how many processors it is executed, and at which speed the processors are operated, with the goal to minimize the total energy consumption. We further focus on co-schedules, where tasks are partitioned into shelves, and we prove that the problem of minimizing the energy consumption remains NP-complete when static energy is consumed during the whole duration of the application. We are however able to provide an optimal algorithm for the schedule within one shelf, i.e., for a set of tasks that start at the same time. Several approximation results are derived, and simulations are performed to show the performance of the proposed algorithms.

Summary Bias in the performance evaluation of scheduling heuristics has been shown to undermine the scope of existing studies. Improving the assessment step leads to stronger scientific claims when validating new optimization strategies. This article considers the problem of allocating independent tasks to unrelated machines such as to minimize the maximum completion time. Testing heuristics for this problem requires the generation of cost matrices that specify the execution time of each task on each machine. Numerous studies showed that the task and machine heterogeneities belong to the properties impacting heuristics performance the most. This study focuses on orthogonal properties, the average correlations between each pair of rows and each pair of columns, which measure the proximity with uniform instances. Cost matrices generated with 2 distinct novel generation methods show the effect of these correlations on the performance of several heuristics from the literature. In particular, EFT performance depends on whether the tasks are more correlated than the machines and HLPT performs the best when both correlations are close to one.

Summary In recent years, important efforts have been made for offering a dedicated language for modelling and verifying security protocols. Outcome of the European project AVISPA, the high‐level security protocol language (HLPSL) aims at providing a means for verifying usual security properties (such as data secrecy) in message exchanges between agents. However, verifying the security protocol model does not guarantee that the actual implementation of the protocol will fulfil these properties. This article presents a model‐based testing approach, relying on the mutation of HLPSL models to generate abstract test cases. The proposed mutations aim at introducing leaks in the security protocols and represent real‐world implementation errors. The mutated models are then analysed by the automated validation of Internet security protocols and applications tool set, which produces, when the mutant protocol is declared unsafe, counterexample traces exploiting the security flaws and, thus, providing test cases. A dedicated framework is then used to concretize the abstract attack traces, bridging the gap between the formal model level and the implementation level. This model‐based testing technique has been experimented on a wide range of security protocols, in order to evaluate the mutation operators. This process has also been fully tool‐supported, from the mutation of the HLPSL model to the concretization of the abstract test cases into test scripts. It has been applied to a realistic case study of the Paypal payment protocol, which made it possible to discover a vulnerability in an implementation of an e‐commerce framework. Copyright © 2014 John Wiley & Sons, Ltd.

SUMMARY Developing efficient and automatic testing techniques is one of the major challenges faced by the software validation community. Recent work by A. Deniseet al.shows how to draw traces uniformly at random for testing large systems modelled by finite automata. Because finite automata are strong abstractions of systems, many test cases generated following this approach may be unconcretizable, that is, they do not correspond to any concrete execution of the system under test. In this paper, this problem is tackled by extending the approach to pushdown systems that can encode either a stack data structure or the call stack. The method is based on context‐free grammars and related algorithms, and relies on combinatorial techniques to guarantee the uniformity of generated traces. In addition, the combination of coverage criteria with random testing is investigated to benefit from both approaches for evaluating the quality of the test suites. The application of the random approach is illustrated within both structural and model‐based testing contexts. Copyright © 2014 John Wiley & Sons, Ltd.

In the recent years, important efforts have been made for offering a dedicated language for modelling and verifying security protocols. Outcome of the European project AVISPA, the High-Level Security Protocol Language (HLPSL) aims at providing a means for verifying usual security properties (such as data secrecy) in message exchanges between agents. Nevertheless, verifying the security protocol model does not guarantee that the actual implementation of the protocol will fulfil these properties. We propose in this paper a testing technique that makes it possible to validate an implementation of a security protocol, based on a HLPSL model. We introduce a set of mutation operators for HLPSL models that aim at introducing leaks in the security protocols. The mutated models are then analysed by the AVISPA tool set that will produce counter-example traces leading to the leaks, thus providing the test cases. We report an experiment of our mutation technique on a wide range of security protocols and discuss the relevance of the proposed mutation operators.

Random testing represents a simple and tractable way for software assessment. This paper presents the Seed tool that can be used for the uniform random generation of recursive data structures such as labelled trees and logical formulas. We show how Seed can be used in several testing contexts, from model based testing to performance testing. Generated data structures are defined by grammar-like rules, given in an XML format, multiplying Seed possible applications. Seed is based on combinatorial techniques, and can generate uniformly at random k structures of size n with an efficient time complexity. Finally, Seed is available as a free Java application and a great effort has been made to make it easy-to-use.