0000000000890573
AUTHOR
Antti Valmari
All congruences below stability-preserving fair testing or CFFD
AbstractIn 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 …
Partial-order reduction for parity games and parameterised Boolean equation systems
AbstractIn 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 pro…
Pedagogical experiments with MathCheck in university teaching
MathCheck is a relatively new online tool that gives students feedback on their solutions to elementary university mathematics and theoretical computer science exercises. MathCheck was designed with constructivism learning theory in mind and it differs from other online tools as it checks the solutions step by step and shows a counter-example if the step is incorrect. It has been in student use since the autumn of 2015 and under design-based research from the first online day. The main research questions of this study are the following. 1) How can the usage of MathCheck support the aspects of conceptual understanding and procedural fluency of constructivism learning? 2) How can MathCheck em…
Algorithms and Logic as Programming Primers
To adapt all-immersive digitalization, the Finnish National Curriculum 2014 (FNC-2014) ‘digi-jumps’ by integrating programming into elementary education. However, applying the change to mathematics teachers’ everyday praxis is hindered by a too high-level specification. To elaborate FNC-2014 into more concrete learning targets, we review the computer science syllabi of countries that are well ahead, as well as the education recommendations set by computer science organizations, such as ACM and IEEE. The whole mathematics syllabus should be critically viewed in the light of these recommendations and feedback collected from software professionals and educators. The feedback reveals an imbalan…
Automated Checking of Flexible Mathematical Reasoning in the Case of Systems of (In)Equations and the Absolute Value Operator
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 path…
The Inconsistent Labelling Problem of Stutter-Preserving Partial-Order Reduction
AbstractIn 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 whi…
A Detailed Account of The Inconsistent Labelling Problem of Stutter-Preserving Partial-Order Reduction
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 correc…
Adapting Formal Logic for Everyday Mathematics
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 cau…
A Completeness Proof for a Regular Predicate Logic with Undefined Truth Value
We provide a sound and complete proof system for an extension of Kleene's ternary logic to predicates. The concept of theory is extended with, for each function symbol, a formula that specifies when the function is defined. The notion of "is defined" is extended to terms and formulas via a straightforward recursive algorithm. The "is defined" formulas are constructed so that they themselves are always defined. The completeness proof relies on the Henkin construction. For each formula, precisely one of the formula, its negation, and the negation of its "is defined" formula is true on the constructed model. Many other ternary logics in the literature can be reduced to ours. Partial functions …
Modelling Without a Modelling Language
Developments in computer hardware and programming languages, in this case C++, have made it feasible to write models of concurrent systems under verification in the programming language, instead of some established modelling language such as Promela. While this does not reduce the usefulness of modelling languages, it offers new possibilities that may be advantageous, for instance, when teaching state space ideas to newcomers or when experimenting with new scientific ideas. In earlier work, we were able to express everything else fairly naturally in C++, except the set of transitions. The present study uses C++ lambda functions to represent naturally transitions that consist of a tail state…
Arithmetic, Logic, Syntax and MathCheck
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 primari…
Elementary Math to Close the Digital Skills Gap
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 ove…
Progress Checking for Dummies
Verification of progress properties is both conceptually and technically significantly more difficult than verification of safety and deadlock properties. In this study we focus on the conceptual side. We make a simple modification to a well-known model to demonstrate that it passes progress verification although the resulting model is intuitively badly incorrect. Then we point out that the error can be caught easily by adding a termination branch to the system. We compare the use of termination branches to the established method of addressing the same need, that is, weak fairness. Then we discuss another problem that may cause failure of catching progress errors even with weak fairness. Fi…
Stubborn sets, frozen actions, and fair testing
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 tha…