Although logic is considered central to mathematics and computer science, there is evidence that teaching logic has not been a great success. We identify three issues where what is typically taught conflicts with what is needed by those who are supposed to apply logic. First, what is taught about the notion of implication often disagrees with human intuition. We argue that in some cases human intuition is wrong, and in some others teaching is to blame. Second, the formal concepts of logical consequence, logical equivalence and tautology are not the similar concepts that everyday mathematicians and computer scientists need. The difference is small enough to go unnoticed but big enough to cause confusion. Third, how to deal with undefined operations such as division by zero is left informal and perhaps fuzzy. These problems also harm development of computer tools for education. We present suggestions about how to address them in teaching.

Abstract In model checking, reduction techniques can be helpful tools to fight the state-space explosion problem. Partial-order reduction (POR) is a well-known example, and many POR variants have been developed over the years. However, none of these can be used in the context of model checking stutter-sensitive temporal properties. We propose POR techniques for parity games, a well-established formalism for solving a variety of decision problems, including model checking. As a result, we obtain the first POR method that is sound for the full modal $$\upmu $$ μ -calculus. We show how our technique can be applied to the fixed point logic called parameterised Boolean equation systems, which provides a high-level representation of parity games. Experiments with our implementation indicate that substantial reductions can be achieved.

We present an approach and a tool for automatically providing feedback on solutions that involve complicated reasoning patterns. Currently the tool supports linear systems of equations and inequations that may also contain the absolute value operator and a restricted form of rational functions. This suffices for designing problems that are laborious to solve with standard mechanical procedures, but much easier using short-cuts that students may find by creative thinking. Earlier research has found that struggling with important mathematics promotes conceptual development. Our goal is to encourage students to such struggling. A crucial feature is to give them great freedom to choose the paths via which they solve problems, and at any time ask the tool to check the work done so far, no matter what path was chosen. This was implemented by adopting standard notation from mathematical logic, and developing some new logical notation. The tool has been used in a course on elementary universi ty-level mathematics. It has worked reliably, but there is not yet any statistics on the pedagogical merits. The tool is expected to also support quadratic (in)equations in the near future.

Many partial order methods use some special condition for ensuring that the analysis is not terminated prematurely. In the case of stubborn set methods for safety properties, implementation of the condition is usually based on recognizing the terminal strong components of the reduced state space and, if necessary, expanding the stubborn sets used in their roots. In an earlier study it was pointed out that if the system may execute a cycle consisting of only invisible actions and that cycle is concurrent with the rest of the system in a non-obvious way, then the method may be fooled to construct all states of the full parallel composition. This problem is solved in this study by a method that “freezes” the actions in the cycle. The new method also preserves fair testing equivalence, making it usable for the verification of many progress properties.

One of the most popular state-space reduction techniques for model checking is partial-order reduction (POR). Of the many different POR implementations, stubborn sets are a very versatile variant and have thus seen many different applications over the past 32 years. One of the early stubborn sets works shows how the basic conditions for reduction can be augmented to preserve stutter-trace equivalence, making stubborn sets suitable for model checking of linear-time properties. In this paper, we identify a flaw in the reasoning and show with a counter-example that stutter-trace equivalence is not necessarily preserved. We propose a stronger reduction condition and provide extensive new correctness proofs to ensure the issue is resolved. Furthermore, we analyse in which formalisms the problem may occur. The impact on practical implementations is limited, since they all compute a correct approximation of the theory.

Abstract In model checking, partial-order reduction (POR) is an effective technique to reduce the size of the state space. Stubborn sets are an established variant of POR and have seen many applications over the past 31 years. One of the early works on stubborn sets shows that a combination of several conditions on the reduction is sufficient to preserve stutter-trace equivalence, making stubborn sets suitable for model checking of linear-time properties. In this paper, we identify a flaw in the reasoning and show with a counter-example that stutter-trace equivalence is not necessarily preserved. We propose a solution together with an updated correctness proof. Furthermore, we analyse in which formalisms this problem may occur. The impact on practical implementations is limited, since they all compute a correct approximation of the theory.

Abstract In process algebras, a congruence is an equivalence that remains valid when any subsystem is replaced by an equivalent one. Whether or not an equivalence is a congruence depends on the set of operators used in building systems from subsystems. Numerous congruences have been found, differing from each other in fine details, major ideas, or both, and none of them is good for all situations. The world of congruences seems thus chaotic, which is unpleasant, because the notion of congruence is at the heart of process algebras. This study continues attempts to clarify the big picture by proving that in certain sub-areas, there are no other congruences than those that are already known or found in the study. First, the region below stability-preserving fair testing equivalence is surveyed using an exceptionally small set of operators. The region contains few congruences, which is in sharp contrast with an earlier result on the region below Chaos-Free Failures Divergences (CFFD) equivalence, which contains 40 well-known and not well-known congruences. Second, steps are taken towards a general theory of dealing with initial stability, which is a small but popular detail. This theory is applied to the region below CFFD.

MathCheck is a web-based tool for checking all steps of solutions to mathematics, logic and theoretical computer science problems, instead of checking just the final answers. It can currently deal with seven problem types related to arithmetic, logic, and syntax. Although MathCheck does have some ability to perform symbolic computation, checking is mostly based on testing with many combinations of the values of the variables in question. This introduces a small risk of failure of detection of errors, but also significantly widens the scope of problems that can be dealt with and facilitates providing a concrete counter-example when the student’s solution is incorrect. So MathCheck is primarily a feedback tool, not an assessment tool. MathCheck is more faithful to established mathematical notation than most programs. Special attention has been given to rigorous processing of undefined expressions, such as division by zero. To make this possible, in addition to the two truth values “false” and “true”, it uses a third truth value “undefined”.

All-encompassing digitalization and the digital skills gap pressure the current school system to change. Accordingly, to ’digi-jump’, the Finnish National Curriculum 2014 (FNC-2014) adds programming to K-12 math. However, we claim that the anticipated addition remains too vague and subtle. Instead, we should take into account education recommendations set by computer science organizations, such as ACM, and define clear learning targets for programming. Correspondingly, the whole math syllabus should be critically viewed in the light of these changes and the feedback collected from SW professionals and educators. These findings reveal an imbalance between supply and demand, i.e., what is over-taught versus under-taught, from the point of view of professional requirements. Critics claim an unnecessary surplus of calculus and differential equations, i.e., continuous mathematics. In contrast, the emphasis should shift more towards algorithms and data structures, flexibility in handling multiple data representations, logic; in summary – discrete mathematics.

This publication discusses how automatic verification of concurrent systems can be made more efficient by focusing on always may-terminating systems . First, making a system always may-terminating is a method for meeting a modelling need that exists independently of this publication. It is illustrated that without doing so, non-progress errors may be lost. Second, state explosion is often alleviated with stubborn, ample, and persistent set methods. They use expensive cycle or terminal strong component conditions in many cases. It is proven that for many important classes of properties, if the systems are always may-terminating, then these conditions can be left out.

This special issue is dedicated to papers selected from the 36th International Conference on Application and Theory of Petri Nets and Other Models of Concurrency (Petri Nets 2015), which was held June 21-26, 2015 in Brussels, Belgium.

This publication addresses two bottlenecks in the construction of minimal coverability sets of Petri nets: the detection of situations where the marking of a place can be converted to ω, and the manipulation of the set A of maximal ω-markings that have been found so far. For the former, a technique is presented that consumes very little time in addition to what maintaining A consumes. It is based on Tarjan’s algorithm for detecting maximal strongly connected components of a directed graph. For the latter, a data structure is introduced that resembles BDDs and Covering Sharing Trees, but has additional heuristics designed for the present use. Results from a few experiments are shown. They demonstrate significant savings in running time and varying savings in memory consumption compared to an earlier state-of-the-art technique.

Many algorithms for computing minimal coverability sets for Petri nets prune futures. That is, if a newmarking strictly covers an old one, then not just the old marking but also some subset of its successor markings is discarded from search. In this publication, a simpler algorithm that lacks future pruning is presented and proven correct. Its performance is compared with future pruning. It is demonstrated, using examples, that neither approach is systematically better than the other. However, the simple algorithm has some attractive features. It never needs to re-construct pruned parts of the minimal coverability set. It automatically gives most of the advantage of future pruning, if the minimal coverability set is constructed in depth-first or most tokens first order, and if so-called history merging is applied. Some implementation aspects of minimal coverability set construction are also discussed. Some measurements are given to demonstrate the effect of construction order and other implementation aspects.

Literature on the stubborn set and similar state space reduction methods presents numerous seemingly ad-hoc conditions for selecting the transitions that are investigated in the current state. There are good reasons to believe that the choice between

A new algorithm for bisimilarity minimization of labelled directed graphs is presented. Its time consumption is O(m log n), where n is the number of states and m is the number of transitions. Unlike earlier algorithms, it meets this bound even if the

Let PT-DFA mean a deterministic finite automaton whose transition relation is a partial function. We present an algorithm for minimizing a PT-DFA in $O(m lg n)$ time and $O(m+n+alpha)$ memory, where $n$ is the number of states, $m$ is the number of defined transitions, and $alpha$ is the size of the alphabet. Time consumption does not depend on $alpha$, because the $alpha$ term arises from an array that is accessed at random and never initialized. It is not needed, if transitions are in a suitable order in the input. The algorithm uses two instances of an array-based data structure for maintaining a refinable partition. Its operations are all amortized constant time. One instance represents the classical blocks and the other a partition of transitions. Our measurements demonstrate the speed advantage of our algorithm on PT-DFAs over an $O(alpha n lg n)$ time, $O(alpha n)$ memory algorithm.

Abstract A systematic analysis of trace- and failure-based compositional semantic models for Basic LOTOS is presented. The analysis is motivated by the fact that the weakest known equivalences preserving sufficient information for several typical verification tasks are failure-based, and the weakness of an equivalence can be advantageous for verification. Both the equivalences and the preorders corresponding to the semantic models are covered. The analysis yields in a natural way two compositional semantic models, which are particularly suited for the verification of a general class of liveness properties, a task which cannot be performed with most established models.