The Order-Maintenance (OM) data structure maintains a total order list of items for insertions, deletions, and comparisons. As a basic data structure, OM has many applications, such as maintaining the topological order, k -core, and k -truss in graphs, and maintaining ordered sets in the Unified Modelling Language (UML) specification. The prevalence of multicore machines suggests parallelizing such a basic data structure. This paper proposes a new parallel OM data structure that supports insertions, deletions, and comparisons in parallel. Specifically, parallel insertions and deletions are efficiently synchronized using locks, which achieves up to 7x and 5.6x speedups with 64 workers. One significant advantage is that comparisons are lock-free, enabling them to execute highly in parallel with other insertions and deletions, which achieves up to 34.4x speedups with 64 workers. Typical real applications maintain order lists that always have a much larger portion of comparisons than insertions and deletions. For example, in core maintenance, the number of comparisons is up to 297 times larger compared with insertions and deletions in certain graphs. This shows that the lock-free order comparison provides a significant practical contribution.

The core numbers of vertices in a graph are one of the most well-studied cohesive subgraph models because of the linear running time. In practice, many data graphs are dynamic graphs that are continuously changing by inserting or removing edges. The core numbers are updated in dynamic graphs with edge insertions and deletions, which is called core maintenance. When a burst of a large number of inserted or removed edges come in, we have to handle these edges on time to keep up with the data stream. There are two main sequential algorithms for core maintenance, Traversal and Order. The experiments show that the Order algorithm significantly outperforms the Traversal algorithm over a variety of real graphs.

This work presents the rationale behind tools and a guideline for the Universal Design of Jupyter notebooks containing programs, explanations, graphics, algorithms, and proofs, all of which may have mathematical symbols. The tools qualitatively improve accessibility and ease the authoring of such notebooks at the same time. The tools and guidelines are currently being used for a course on concurrent system design and a course on formal languages and compiler construction at McMaster University.

Statecharts are an executable visual language for specifying the reactive behavior of systems. We propose to statically verify the design expressed by a statechart by allowing individual states to be annotated with invariants and checking the consistency of the invariants with the transitions. We present an algorithm that uses the locality of state invariants for generating "many small" verification conditions that should be more amenable to automatic checking than an approach based on a single global invariant.

Abstract Tabular representations have been proposed for structuring complex mathematical expressions as they appear in the specification of programs. We argue that tables not only help in writing and checking complex expressions, but also in their formal manipulation. More specifically, we explore the use of tabular predicates and tabular relations in program verification and refinement.

The trace assertion method is a formal state machine based method for specifying module interfaces. A module interface specification treats the module as a black-box, identifying all the module's access programs (i.e., programs that can be invoked from outside of the module) and describing their externally visible effects. In the method, both the module states and the behaviors observed are fully described by traces built from access program invocations and their visible effects. A formal model for the trace assertion method is proposed. The concept of step-traces is introduced and applied. The stepwise refinement of trace assertion specifications is considered. The role of nondeterminism, normal and exceptional behavior, value functions, and multiobject modules are discussed. The relationship with algebraic specifications is analyzed. A tabular notation for writing trace specifications to ensure readability is adapted.

An operator for the composition of two processes, where one process has priority over the other process, is studied. Processes are described by action systems, and data refinement is used for transforming processes. The operator is shown to be compositional, i.e. monotonic with respect to refinement. It is argued that this operator is adequate for modelling priorities as found in programming languages and operating systems. Rules for introducing priorities and for raising and lowering priorities of processes are given. Dynamic priorities are modelled with special priority variables which can be freely mixed with other variables and the prioritising operator in program development. A number of applications show the use of prioritising composition for modelling and specification in general.