Abstract is a stateful calculus in which clauses can be activated either through interactions with the external environment or by the evaluation of time expressions. Despite the apparent simplicity of its syntax and operational model, the combination of state evolution, time reasoning, and nondeterminism gives rise to significant analytical challenges. In particular, we show that determining whether a clause is never executed is undecidable. We formally prove that this undecidability result holds even for syntactically restricted fragments: namely, the time-ahead fragment, where all time expressions are strictly positive, the instantaneous fragment, where all time expressions evaluate to zero, and the determinate fragment, where the initial states of functions and events are disjoint. On the other hand, we identify a decidable subfragment: at the intersection of the instantaneous and determinate fragments reachability becomes decidable.

Spatial skills, in particular mental rotation, are increasingly linked to STEM achievements and to computational thinking (CT) abilities. Traditional 2D spatial assessments face validity and equity issues from visual ambiguity, occlusion, and missing depth cues, requiring cognitively demanding 2D-to-3D interpretation. These artifacts might contribute to gender disparities, giving males an advantage that may reflect test bias rather than true ability differences. Immersive Virtual Reality (VR) seems to mitigate these issues by providing stereoscopic depth, multi-perspective viewing, realistic lighting, and embodied interaction. We compared spatial performance in VR and traditional 2D assessments using the Virtual Reality Mental Rotation Assessment (VRMRA) in a within-subjects study of 48 adolescents (ages 12-16). VR improved performance, yielding higher accuracy in Mental Rotation Test (MRT)-style tasks (+1.3 items, p < .001), while PSVT:R accuracy did not differ significantly between 2D and VR. We observed that gender effects are task-specific: VR improved the performance of females most in MRT-style tasks, reversing the 2D male advantage, whereas males gained more in PSVT:R-style tasks. Spatial scores correlated positively with CT across both 2D and VR assessments, indicating a link to computational problem-solving. These results suggest that the assessment of spatial skills in VR produces distinct performance patterns with respect to traditional 2D assessment, highlighting the importance of immersive VR for the development of improved tools and its potential implications for inclusive STEM education and talent identification.

As the importance of concurrent and multithreaded programming continues to grow, many universities have incorporated these concepts into their introductory courses. Sonic Pi, a programming language designed for music creation, provides valuable support for exploring concurrency due to its simplified multithreading abstractions and its domain-specific nature. In this paper, we outline several teaching experiments aimed at undergraduate computer science students, using an interdisciplinary pedagogical approach that introduces concurrency early using Sonic Pi. The activities consist of code comprehension and code composition tasks in a collaborative learning environment. Our primary research goal is to explore and discuss students’ misconceptions about concurrency, and then draw some preliminary considerations and connections to analogous misconceptions in traditional concurrent programming languages.

As the importance of concurrent and multi-threaded programming continues to grow, many universities have incorporated these concepts into their introductory courses. Sonic Pi, a programming language designed for music creation, provides valuable support for exploring concurrency due to its simplified multi-threading abstractions and its domain-specific nature. This paper investigates the combined use of Sonic Pi and Team-Based Learning to mitigate the difficulties in early exposure to concurrency. Sonic Pi provides great support for "playing'' with concurrency, and "hearing'' common problems such as data races and lack of synchronization among different threads. Our primary research goal is to explore whether the use of Sonic Pi can support students, especially in the early stages, to understand concurrent programming concepts and help them face misconceptions identified in the concurrency education literature. The approach has been applied in teaching experiments with undergraduate students involving 184 participants.

Abstract Runtime verification is a lightweight formal verification technique used to verify the runtime behaviour of software (resp. hardware) systems. Given a formal property, one or more monitors are synthesized to verify the latter against a system execution. A monitor can only conclude the violation of a property when it observes such a violation. Unfortunately, in safety-critical scenarios, this might happen too late for the system to react properly. In such scenarios, it is advised to use predictive runtime verification, where monitors are capable of anticipating (by using a model of the system) future events before actually observing them. In this work, instead of assuming such a model is given, we describe a runtime verification workflow where the model is learnt and incrementally refined by using process mining techniques. We present the approach and the resulting prototype tool.

We show that Cubicle, an SMT-based infinite-state model checker, can be applied as a verification engine for GLog, a logic-based language based on relational updates rules that has been applied to specify topology-sensitive distributed protocols with asynchronous communication. In this setting, the absence of protocol anomalies can be reduced to a coverability problem in which the initial set of configurations is not fixed a priori (Existential Coverability Problem). Existential Coverability in GLog can naturally be expressed into Parameterized Verification judgements in Cubicle. The encoding is based on a translation of relational update rules into transition rules that modify cells of unbounded arrays. To show the effectiveness of the approach, we discuss several verification problems for distributed protocols and distributed objects, a challenging task for traditional verification tools. The experimental results show the flexibility and robustness of Cubicle for the considered class of protocol examples.

A wide range of tools and applications have been developed for supporting Computer Science Education, ranging from visual programming languages to web applications. In this setting it is crucial to model user needs and provide personalized support to improve the effectiveness and satisfaction of learning experiences. This summary gives a brief overview of the workshop Adaptation and Personalization in Computer Science Education organized at UMAP 2020 in order to bring together researchers, practitioners and education stakeholders interested in these topics. The workshop program consists of a keynote speech by Wolfgang Slany head of the Catrobat Project and by three technical sessions offering different perspectives on the main themes of the workshop.

We present a logic-based framework for the specification and validation of distributed protocols. Our specification language is a logic-based presentation of update rules for arbitrary graphs. Update rules are specified via conditional rewriting rules defined over a relational language. We focus ou r attention on unary and binary relations as a way to specify predicates over nodes and edges of a graph. For the considered language, we define assertions that can be applied to specify correctness properties for arbitrary configurations. We apply the language to model the distributed version of the Dining Philosopher Protocol. The protocol is defined for asynchronous processes distributed over a graph with arbitrary topology. We propose then validation methods based on source to source transformations and deductive reasoning. We apply the resulting method to provide a succint correctness proof of the considered case-study.

Internet of things (IoT) systems are becoming ubiquitous and assuring their quality is fundamental. Unfortunately, a few proposals for testing these complex, and often safety‐critical, systems are present in the literature. The authors propose an approach for acceptance testing of IoT systems adopting graphical user interfaces as a principal way of interaction. Acceptance testing is a type of black box testing based on test scenarios, i.e. sequences of steps/actions performed by the user or the system. In their approach, test scenarios are derived from a state machine that expresses the behaviour of the system under test, and test cases are derived from them by specifying the actual data and assertions and made executable by implementing the corresponding test scripts. As a case study, they selected a mobile health IoT system for diabetes management composed of local sensors/actuators, smartphones, and a remote cloud‐based system. The effectiveness of the approach has been evaluated by measuring the capability of two test suites implemented using different localisation strategies (visual and structure‐based) in detecting mutants of the original m‐health system. Results show the effectiveness of the test suites implemented by following the proposed approach since 93% of the generated mutants have been detected.

We study parameterized verification problems for networks of interacting register automata. The network is represented through a graph, and processes may exchange broadcast messages containing data with their neighbours. Upon reception a process can either ignore a sent value, test for equality wit h a value stored in a register, or simply store the value in a register. We consider safety properties expressed in terms of reachability, from arbitrarily large initial configurations, of a configuration exposing some given control states and patterns. We investigate, in this context, the impact on decidability and complexity of the number of local registers, the number of values carried by a single message, and dynamic reconfigurations of the underlying network.

We study the extension of relational multiagent systems (RMASs), where agents manipulate full-fledged relational databases, with data types and facets equipped with domain-specific, rigid relations (such as total orders). Specifically, we focus on design-time verification of RMASs against rich first-order temporal properties expressed in a variant of first-order mu-calculus with quantification across states. We build on previous decidability results under the state-bounded assumption, i.e., in each single state only a bounded number of data objects is stored in the agent databases, while unboundedly many can be encountered over time. We recast this condition, showing decidability in presence of dense, linear orders, and facets defined on top of them. Our approach is based on the construction of a finite-state, sound and complete abstraction of the original system, in which dense linear orders are reformulated as non-rigid relations working on the active domain of the system only. We also show undecidability when including a data type equipped with the successor relation.

We study decidability issues for reachability problems in graph transformation systems, a powerful infinite-state model. For a fixed initial configuration, we consider reachability of an entirely specified configuration and of a configuration that satisfies a given pattern (coverability). The former is a fundamental problem for any computational model, the latter is strictly related to verification of safety properties in which the pattern specifies an infinite set of bad configurations. In this paper we reformulate results obtained, e.g., for context-free graph grammars and concurrency models, such as Petri nets, in the more general setting of graph transformation systems and study new results for classes of models obtained by adding constraints on the form of reduction rules.

Abstract In this paper, we investigate the connection between fragments of associative-commutative Term Rewriting and fragments of Mobile Ambients, a powerful model for mobile and distributed computations. The connection can be used to transfer decidability and undecidability results for important computational properties like reachability from one formalism to the other. Furthermore, it can be viewed as a vehicle to apply tools based on rewriting for the simulation and validation of specifications given in Mobile Ambients.

Abstract We present a technique for the automated verification of abstract models of multithreaded programs providing fresh name generation, name mobility, and unbounded control. As high level specification language we adopt here an extension of communication finite-state machines with local variables ranging over an infinite name domain, called TDL programs. Communication machines have been proved very effective for representing communication protocols as well as for representing abstractions of multithreaded software. The verification method that we propose is based on the encoding of TDL programs into a low level language based on multiset rewriting and constraints that can be viewed as an extension of Petri Nets. By means of this encoding, the symbolic verification procedure developed for the low level language in our previous work can now be applied to TDL programs. Furthermore, the encoding allows us to isolate a decidable class of verification problems for TDL programs that still provide fresh name generation, name mobility, and unbounded control. Our syntactic restrictions are in fact defined on the internal structure of threads: In order to obtain a complete and terminating method, threads are only allowed to have at most one local variable (ranging over an infinite domain of names).

This special issue is inspired by the homonymous ICLP workshops that took place during ICLP 2001 and ICLP 2002. Extending and shifting slightly from the scope of their predecessors (on verification and logic languages) held in the context of previous editions of ICLP, the aim of the SAVE workshops was to bring together researchers interested in the use of computational logic as a tool for the specification, the analysis and the validation of systems, with particular emphasis on emerging technologies such as World Wide Web and E-Commerce, (protocols for) Smart Cards and Mobile Telephony, Wireless Technology, Hybrid Systems, Real-Time and Distributed systems, etc.

Constraint Handling Rules (CHR) are a committed-choice declarative language which has been designed for writing constraint solvers. A CHR program consists of multi-headed guarded rules which allow one to rewrite constraints into simpler ones until a solved form is reached.CHR has received a considerable attention, both from the practical and from the theoretical side. Nevertheless, due the use of multi-headed clauses, there are several aspects of the CHR semantics which have not been clarified yet. In particular, no compositional semantics for CHR has been defined so far.In this paper we introduce a fix-point semantics which characterizes the input/output behavior of a CHR program and which is and-compositional, that is, which allows to retrieve the semantics of a conjunctive query from the semantics of its components. Such a semantics can be used as a basis to define incremental and modular analysis and verification tools.

The overall goal of this paper is to investigate the theoretical foundations of algorithmic verification techniques for first order linear logic specifications. The fragment of linear logic we consider in this paper is based on the linear logic programming language called LO (Andreoli and Pareschi, 1990) enriched with universally quantified goal formulas. Although LO was originally introduced as a theoretical foundation for extensions of logic programming languages, it can also be viewed as a very general language to specify a wide range of infinite-state concurrent systems (Andreoli, 1992; Cervesato, 1995). Our approach is based on the relation between backward reachability and provability highlighted in our previous work on propositional LO programs (Bozzano et al., 2002). Following this line of research, we define here a general framework for the bottom-up. evaluation of first order linear logic specifications. The evaluation procedure is based on an effective fixpoint operator working on a symbolic representation of infinite collections of first order linear logic formulas. The theory of well quasi-orderings Abdulla et al., 1996; Finkel and Schnoebelen, 2001) can be used to provide sufficient conditions for the termination of the evaluation of non trivial fragments of first order linear logic.

In this paper we investigate the applicability of a bottom-up evaluation strategy for a first order fragment of linear logic [7] for the purposes of automated validation of authentication protocols. Following [11], we use multi-conclusion clauses to represent the behaviour of agents in a protocol session, and we adopt the Dolev-Yao intruder model and related message and cryptographic assumptions. Also, we use universal quantification to provide a logical and clean way to express creation of nonces. Our approach is well suited to verify properties which can be specified by means of minimality conditions. Unlike traditional approaches based on model-checking, we can reason about parametric, infinite-state systems, thus we do not pose any limitation on the number of parallel runs of a given protocol. Furthermore, our approach can be used both to find attacks and to prove correctness of protocols. We present some preliminary experiments which we have carried out using the above approach. In particular, we analyze the ffgg protocol introduced by Millen [30]. This protocol is a challenging case study in that it is free from sequential attacks, whereas it suffers from parallel attacks that occur only when at least two sessions are run in parallel.

In this paper we investigate the theoretical foundation of a new bottom-up semantics for linear logic programs, and more precisely for the fragment of LinLog (Andreoli, 1992) that consists of the language LO (Andreoli & Pareschi, 1991) enriched with the constant 1. We use constraints to symbolically and finitely represent possibly infinite collections of provable goals. We define a fixpoint semantics based on a new operator in the style of TP working over constraints. An application of the fixpoint operator can be computed algorithmically. As sufficient conditions for termination, we show that the fixpoint computation is guaranteed to converge for propositional LO. To our knowledge, this is the first attempt to define an effective fixpoint semantics for linear logic programs. As an application of our framework, we also present a formal investigation of the relations between LO and Disjunctive Logic Programming (Minker et al., 1991). Using an approach based on abstract interpretation, we show that DLP fixpoint semantics can be viewed as an abstraction of our semantics for LO. We prove that the resulting abstraction is correct and complete (Cousot & Cousot, 1977; Giacobazzi & Ranzato, 1997) for an interesting class of LO programs encoding Petri Nets.

No abstract available.

Several calculi of objects have been studied in the recent literature, that support the central features of object-based languages: messages, inheritance, dynamic dispatch, object update and object-extension. We show that a complete semantic account of these features may be given in a fragment of higher-order linear logic.