In this paper, we introduce Manim-DFA, an extension of the Manim library for generating video visualisations to teach data flow analysis and abstract interpretation. Despite the importance of data flow analysis in static program analysis, educational visualisation tools remain scarce. Manim-DFA addresses this gap by enabling educators to animate control flow graphs and lattice structures, illustrating their transformation during program analysis. Currently, the tool supports automated animation of the worklist algorithm, as well as lattice visu-alisation. Designed with established pedagogical principles, Manim-DFA promotes active learning, reduces cognitive load, and enhances conceptual understanding. Preliminary evaluations suggest that it effectively complements traditional resources and supports autonomous learning.

While there is consensus that educational escape games have a beneficial impact on student learning in computer science, this hypothesis is not empirically demonstrated because the evaluation methods used by researchers in the field are carried out in an ad hoc manner, lack reproducibility and often rely on confidential samples. We introduce EvscApp, a standard methodology for evaluating educational escape games intended for the learning of computer science at the undergraduate level. Based on a state of the art in the realm of educational escape games and on the different associated pedagogical approaches existing in the literature, we arrive at a general-purpose experimental process divided in fifteen steps. The evaluation criteria used for assessing an escape game’s efficiency concern the aspects of motivation, user experience and learning. The EvscApp methodology has been implemented as an open source Web dashboard that helps researchers to carry out structured experimentations of educational escape games designed to teach computer science. The tool allows designers of educational computer escape games to escape the ad hoc construction of evaluation methods while gaining in methodological rigor and comparability. All the results collected through the experiments carried out with EvscApp are scheduled to be compiled in order to be able to rule empirically as to the pedagogical effectiveness of pedagogical escape games for computer science in general. A few preliminary experiments indicate positive early results of the method.

Anti-unification in logic programming refers to the process of capturing common syntactic structure among given goals, computing a single new goal that is more general called a generalization of the given goals. Finding an arbitrary common generalization for two goals is trivial, but looking for those common generalizations that are either as large as possible (called largest common generalizations) or as specific as possible (called most specific generalizations) is a non-trivial optimization problem, in particular when goals are considered to be \textit{unordered} sets of atoms. In this work we provide an in-depth study of the problem by defining two different generalization relations. We formulate a characterization of what constitutes a most specific generalization in both settings. While these generalizations can be computed in polynomial time, we show that when the number of variables in the generalization needs to be minimized, the problem becomes NP-hard. We subsequently revisit an abstraction of the largest common generalization when anti-unification is based on injective variable renamings, and prove that it can be computed in polynomially bounded time.

We introduce, describe and discuss the potentialities of Moulinog, a tool created during the COVID-19 lockdown, designed to generate individual questionnaires for the remote evaluation of large classrooms. Starting with a list of students and a series of predicates constituting a pool of parametric questions along with rules for their parametrization, Mouling generates a list of individual questionnaires, together with a shell script allowing an easy emailing of the (password-protected) questionnaires to the students. The tool’s use in practice is illustrated on a particular course case for which it has proven to be both useful and time-saving.

Abstract Anti-unification refers to the process of generalizing two (or more) goals into a single, more general, goal that captures some of the structure that is common to all initial goals. In general one is typically interested in computing what is often called a most specific generalization, that is a generalization that captures a maximal amount of shared structure. In this work we address the problem of anti-unification in CLP, where goals can be seen as unordered sets of atoms and/or constraints. We show that while the concept of a most specific generalization can easily be defined in this context, computing it becomes an NP-complete problem. We subsequently introduce a generalization algorithm that computes a well-defined abstraction whose computation can be bound to a polynomial execution time. Initial experiments show that even a naive implementation of our algorithm produces acceptable generalizations in an efficient way.

Algorithm recognition, which is the problem of verifying whether a program implements a given algorithm, is an important topic in program analysis. We propose an approach for algorithm recognition in binary code. For this paper, we have chosen the Dalvik Virtual Machine (DVM) bytecode. Given an algorithm A that is compiled into a DVM method M0, and a DVM program P that includes a series of methods {M1,..., Mn}, the approach is able to identify those blocks Mi from P that essentially implement the algorithm A. The technique we propose first translates binary code into Horn clauses. Then we consider programs as implementing the same algorithm if their Horn clause representations can be reduced to a single common set of Horn clauses by means of a sequence of transformations.

In constraint-based program testing, symbolic execution is a technique which allows to generate test data exercising a given execution path, selected within the program to be tested. Applied to a set of paths covering a sufficient part of the code under test, this technique permits to generate automatically adequate test sets for units of code. As databases are ubiquitous in software, generalizing such a technique for efficient testing of programs manipulating databases is an interesting approach to enhance the reliability of software. In this work, we propose a relational symbolic execution algorithmto be used for testing of simple Java methods, reading and writing with transactional SQL in a relational database, subject to integrity constraints. This algorithm considers the Java method under test as a sequence of operations over a set of constrained relational variables, modeling both the database tables and the method variables. By integrating this relational model of the method and database with the classical symbolic execution process, the algorithm can generate a set of Alloy constraints for any finite path to test in the control-flow graph of the method. Solutions of these constraints are data which constitute a test case, including valid content for the database, which exercises the selected path in the method. A tool implementing the proposed algorithm is demonstrated over a number of examples.

In this paper we propose a novel representation scheme, called probabilistic encoding. In this representation, each gene of an individual represents the probability that a certain trait of a given problem has to belong to the solution. This allows to deal with uncertainty that can be present in an optimization problem, and grant more exploration capability to an evolutionary algorithm. With this encoding, the search is not restricted to points of the search space. Instead, whole regions are searched, with the aim of individuating a promising region, i.e., a region that contains the optimal solution. This implies that a strategy for searching the individuated region has to be adopted. In this paper we incorporate the probabilistic encoding into a multi-objective and multi-modal evolutionary algorithm. The algorithm re- turns a promising region, which is then searched by using simulated annealing. We apply our proposal to the problem of discovering biclusters in microarray data. Results confirm the validity of our proposal.

Learning concept descriptions from data is a challenging, and inherently multi-objective, optimization problem. The model induced by the learner has to be complete, consistent and easily interpretable, and producing it should take few computational resources. These objectives are often conflicting and require thus some heuristics to be balanced. The classical approach is to combine all the objectives into a single scoring function that is used for guiding the search in the hypothesis space. However, we believe that a multi-objective approach is more appropriate for this problem. Evolutionary Algorithms (EAs) are particularly suited for solving multi-objective optimization problems. In this paper, we propose an improved version of the Evolutionary Concept Learner (ECL) system, called Multi-Objective ECL (MOECL). While the search performed by ECL is based on a single-objective EA, MOECL adopts a multi-objective search strategy. It uses two objectives independent of class distribution, the true positive rate and the true negative rate, and is inspired by the simple and effective Pareto-based optimization algorithm SPEA2 for fitness assignement. Experiments show that the results of the MOECL system are globally more accurate than those of ECL and of the other state-of-the-art systems, on propositional datasets and on one relational dataset. As such, we believe the MOECL system to constitute a promising approach towards a multi-objective and effective concept learner.

In this work, we present a new constraint-based workflow definition language called Saturn, which uses Linear-time Temporal Logic (LTL) to express workflow constraints. A declarative approach to model business processes has recently been advocated as a viable complement to, or even replacement of, more traditional imperative-style workflow definition languages. Such an approach offers multiple advantages especially in the context of so-called flexible business processes where the processes and the underlying workflow definitions tend to change over time.

This article makes two contributions to the work on semantics-based termination analysis for logic programs. The first involves a novel notion of type - based norm where for a given type, a corresponding norm is defined to count in a term the number of subterms of that type. This provides a collection of candidate norms, one for each type defined in the program. The second enables an analyzer to base termination proofs on the combination of several different norms. This is useful when different norms are better suited to justify the termination of different parts of the program. Application of the two contributions together consists in considering the combination of the type-based candidate norms for a given program. This results in a powerful and practical technique. Both contributions have been introduced into a working termination analyzer. Experimentation indicates that they yield state-of-the-art results in a fully automatic analysis tool, improving with respect to methods that do not use both types and combined norms.

The so called “cogen approach” to program specialisation, writing a compiler generator instead of a specialiser, has been used with considerable success in partial evaluation of both functional and imperative languages. This paper demonstrates that the cogen approach is also applicable to the specialisation of logic programs (called partial deduction) and leads to effective specialisers. Moreover, using good binding-time annotations, the speed-ups of the specialised programs are comparable to the speed-ups obtained with online specialisers. The paper first develops a generic approach to offline partial deduction and then a specific offline partial deduction method, leading to the offline system LIX for pure logic programs. While this is a usable specialiser by itself, it is used to develop the cogen system LOGEN. Given a program, a specification of what inputs will be static, and an annotation specifying which calls should be unfolded, LOGEN generates a specialised specialiser for the program at hand. Running this specialiser with particular values for the static inputs results in the specialised program. While this requires two steps instead of one, the efficiency of the specialisation process is improved in situations where the same program is specialised multiple times. The paper also presents and evaluates an automatic binding-time analysis that is able to derive the annotations. While the derived annotations are still suboptimal compared to hand-crafted ones, they enable non-expert users to use the LOGEN system in a fully automated way. Finally, LOGEN is extended so as to directly support a large part of Prolog's declarative and non-declarative features and so as to be able to perform so called mixline specialisations.