Search

"What is an algorithm?" is a fundamental question of computer science. Gurevich's behavioural theory of sequential algorithms (aka the sequential ASM thesis) gives a partial answer by defining (non-deterministic) sequential algorithms axiomatically, without referring to a particular machine model or programming language, and showing that they are captured by (non-deterministic) sequential Abstract State Machines (nd-seq ASMs). Moschovakis pointed out that recursive algorithms such as mergesort are not covered by this theory. In this article we propose an axiomatic definition of the notion of sequential recursive algorithm which extends Gurevich's axioms for sequential algorithms by a Recursion Postulate and allows us to prove that sequential recursive algorithms are captured by recursive Abstract State Machines, an extension of nd-seq ASMs by a CALL rule. Applying this recursive ASM thesis yields a characterization of sequential recursive algorithms as finitely composed concurrent algorithms all of whose concurrent runs are partial-order runs., Comment: 34 pages

In this paper we use the Abstract State Machine (ASM) method for high-level system design and analysis created by Egon Borger to formally specify Grover’s quantum database search algorithm, stepwise refining it from its highest abstraction level down to its implementation as a quantum circuit. Our aim is to raise the question of whether the ASM method in general and quantum ASMs in particular can improve the current practices of quantum system engineering; providing accurate high-level modelling and linking the descriptions at the successive stages of quantum systems development through a chain of rigorous and coherent system models at stepwise refined levels of abstraction.

I sketch what I think led to the emergence of Abstract State Machines. A central role in this is played by the work of Ashok Chandra and David Harel on computable queries in databases. I also define Chandra-Harel Algebras, and analyse Blum-Shub-Smale computability over these algebras.

Over the last decades the field of computer science has changed a lot. In practice we are now dealing with very complex systems, but it seems that the theoretical foundations have not caught up with the development. This article is dedicated to a demonstration how a modernised theory of computation may look like. The theory is centred around the notion of algorithmic systems addressing behavioural theory, logic and complexity theory.

Reflective algorithms are algorithms that can modify their own behaviour. Recently a behavioural theory of reflective algorithms has been developed, which shows that they are captured by reflective abstract state machines (rASMs). Reflective ASMs exploit extended states that include an updatable representation of the ASM signature and rules to be executed by the machine in that state. Updates to the representation of ASM signatures and rules are realised by means of a sophisticated tree algebra defined in the background of the rASM. In this paper the theory is taken further by an extension of the logic of ASMs to capture inferences on rASMs. The key is the introduction of terms that are interpreted by ASM rules stored in some location. We show that fragments of the logic with a fixed bound on the number of steps preserve completeness, whereas the full run-logic for rASMs becomes incomplete.

Reflective algorithms are algorithms that can modify their own behaviour. Recently a behavioural theory of reflective algorithms has been developed, which shows that they are captured by reflective abstract state machines (rASMs). Reflective ASMs exploit extended states that include an updatable representation of the ASM signature and rules to be executed by the machine in that state. Updates to the representation of ASM signatures and rules are realised by means of a sophisticated tree algebra defined in the background of the rASM. In this article the theory is taken further by an extension of the logic of ASMs, by means of which we can formally express properties a reflective algorithm must satisfy. The proof theory associated with the logic then enables static verification of adaptive systems. The key is the introduction of terms that are interpreted by ASM rules stored in some location. We show that fragments of the logic with a fixed bound on the number of steps preserve completeness, whereas the full run-logic for rASMs becomes incomplete.

We develop a logic which enables reasoning about single steps of non-deterministic and parallel Abstract State Machines (ASMs). Our logic builds upon the unifying logic introduced by Nanchen and Stark for reasoning about hierarchical (parallel) ASMs. Our main contribution is the handling of non-determinism within the logical formalism. We do this without sacrificing the completeness of the logic for statements about single steps of non-deterministic and parallel ASMs, such as invariants of rules, consistency conditions for rules, or step-by-step equivalence of rules. Moreover, we show that the proposed one-step logic can be easily extended to a multiple-step logic which enables reasoning about concurrent ASMs.

Hard real-time systems are embedded systems with a strong emphasis on the guaranty of safety-critical properties. In order to provide the necessary confidence level, with regard to the respect of functional and non-functional properties, a system analysis that accounts for all possible execution paths must be performed. Symbolic execution has been successfully used to explore and analyze reachable system states. In this paper, we formally define a symbolic execution semantics for an abstract state machine based model. The unification of the update semantics redefined in terms of symbolic moves, enable us to achieve reacher methods for path condition resolution and ultimately better scalability of the execution. The goal of this paper is to provide a formal ground for the integration of symbolic execution in existing timing analysis frameworks based on abstract state machines that will facilitate the computability of the analysis tools.

Distribution of computation is well-known, and there are several frameworks, including some formal frameworks, that capture distributed computation. As yet, however, models of distributed computation are based on the idea that data is conceptually centralized. That is, they assume that data, even if it is distributed, is consistent. This assumption is not valid for many of the database systems in use today, where consistency is compromised to ensure availability and partition tolerance. Starting with an informal definition of eventual consistency, this paper explores several measures of inconsistency that quantify how far from consistency a system is. These measures capture key aspects of eventual consistency in terms of distributed abstract state machines. The definitions move from the traditional binary definition of consistency to more quantitative definitions, where the classical consistency is given by the highest possible level of consistency. Expressing eventual consistency in terms of abstract state machines allows models to be developed that capture distributed computation and highly available distributed data within a single framework.

International audience; According to the Church-Turing Thesis, effectively calculable functions are functions computable by a Turing machine. Models that compute these functions are called Turing-complete. For example, we know that common imperative languages (such as C, Ada or P ython) are Turing complete (up to unbounded memory). Algorithmic completeness is a stronger notion than Turing-completeness. It focuses not only on the input-output behavior of the computation but more importantly on the step-by-step behavior. Moreover, the issue is not limited to partial recursive functions, it applies to any set of functions. A model could compute all the desired functions, but some algorithms (ways to compute these functions) could be missing (see [10, 27] for examples related to primitive recursive algorithms). This paper's purpose is to prove that common imperative languages are not only Turing-complete but also algorithmically complete, by using the axiomatic definition of the Gurevich's Thesis and a fair bisimulation between the Abstract State Machines of Gurevich (defined in [16]) and a version of Jones' While programs. No special knowledge is assumed, because all relevant material will be explained from scratch.

In this paper we study the notion of stepwise simulation between Abstract State Machines, to explore if some natural change on the original definition would keep it sound. We prove that we have to keep the classical notion and give results about the computability of the simulation itself.

In this paper we define a formal refinement theory for a variant of Abstract State Machines (ASMs) with submachines and power cuts. The theory is motivated by the development of a verified flash file system. Different components of the system are modeled as submachines and refined individually. We define a non-atomic semantics that is suitable for considering power cuts in the middle of operations. We prove that refinement is compositional with respect to submachines and crashes. We give a criterion “crash-neutrality” and corresponding proof obligations that are sufficient to reduce non-atomic reasoning to standard pre/post verification in the context of power failures in file systems.

A behavioural theory consists of machine-independent postulates characterizing a particular class of algorithms or systems, an abstract machine model that provably satisfies these postulates, and a rigorous proof that any algorithm or system stipulated by the postulates is captured by the abstract machine model. The class of interest in this article is that of synchronous parallel algorithms. For this class a behavioural theory has already been developed by Blass and Gurevich, which unfortunately, though mathematically correct, fails to be convincing, as it is not intuitively clear that the postulates really capture the essence of (synchronous) parallel algorithms. In this article we present a much simpler (and presumably more convincing) set of four postulates for (synchronous) parallel algorithms, which are rather close to those used in Gurevich's celebrated sequential ASM thesis, i.e. the behavioural theory of sequential algorithms. The key difference is made by an extension of the bounded exploration postulate using multiset comprehension terms instead of ground terms formulated over the signature of the states. In addition, all implicit assumptions are made explicit, which amounts to considering states of a parallel algorithm to be represented by meta-finite first-order structures. The article first provides the necessary evidence that the axiomatization presented in this article characterizes indeed the whole class of deterministic, synchronous, parallel algorithms, then formally proves that parallel algorithms are captured by Abstract State Machines (ASMs). The proof requires some recourse to methods from finite model theory, by means of which it can be shown that if a critical tuple defines an update in some update set, then also every other tuple that is logically indistinguishable defines an update in that update set.

The request of formal methods for the specification and analysis of distributed systems is nowadays increasing, especially when considering the development of Cloud systems and Web applications. This is due to the fact that modeling languages currently used in these areas have informal definitions and ambiguous semantics, and therefore their use may be unreliable. Thanks to their mathematical foundation, formal methods can guarantee rigorous system design, leading to precise models where requirements can be validated and properties can be assured, already at the early stages of the system development. In this paper, we present a rigorous engineering process for distributed systems, based on the Abstract State Machines (ASM) formal method. We rely on the foundational notions of ASM ground model and model refinement to obtain a precise model for a client-server application for Cloud systems. This application has been proposed to tackle the problem of making Cloud services usable to different end-devices by adapting on-the-fly the content coming from the Cloud to the different devices contexts. The ASM-based modeling process is supported by a number of validation and verification activities that have been exploited on the component under development to guarantee consistency, correctness, and reliability properties.

Graph algorithms that involve complex conditions on subgraphs can be specified much easier, if the specification allows expressions in higher-order logic to be used. In this paper an extension of Abstract State Machines by such expressions is introduced and its usefulness is demonstrated by examples of computations on graphs, such as graph factoring and checking self-similarity. In a naive way these high-level specifications can be refined using submachines for the evaluation of the higher-order expressions. We show that refinements can be obtained in an automatic way for well-defined fragments of higher-order logic that collapse to second-order, by means of which the naive refinement is only necessary for second-order logic expressions.

State Machines (ASMs) have been successfully applied for modeling critical and complex systems in a wide range of application domains. However, unlike other well-known formalisms, e.g. Petri nets, ASMs lack inherent, domain-independent characterisations of computationally important properties. Here, we provide an ASM-based characterisation of the starvation-free property. The classic, informal notion of starvation, usually provided in literature, is analysed and expressed as a necessary condition in terms of ASMs. Thus, we enrich the ASM framework with the notion of vulnerable rule as a practical tool for analysing starvation issues in an operational fashion, This is an Accepted Manuscript of an article published by Taylor & Francis Group in the International Journal of Parallel, Emergent & Distributed Systems on 14/02/2017, available online: http://www.tandfonline.com/10.1080/17445760.2017.1288808

A concurrent system can be characterised by autonomously acting agents, where each agent executes its own program, uses shared resources and communicates with the others, but otherwise is totally oblivious to the behaviour of the other agents. In an evolving concurrent system agents may change their programs, enter or leave the collection at any time thereby changing the behaviour of the overall system. In this paper we present a behavioural theory of evolving concurrent systems, i.e. we provide (1) a small set of postulates that characterise evolving concurrent systems in a precise conceptual way without any reference to a particular language, (2) an abstract machine model together with a plausibility proof that the abstract machines satisfy the postulates, and (3) a characterisation proof that any system stipulated by the postulates can be step-by-step simulated by an abstract machine. The theory integrates the behavioural theories for unbounded (synchronous) parallel algorithms, asynchronous concurrent systems, and reflective algorithms, respectively. However, in the latter two theories only sequential agents and sequential reflective algorithms were considered. Furthermore, linguistic reflection has not been integrated with parallelism. We will show how these research gaps can be closed. The behavioural theory implies that concurrent reflective Abstract State Machines (crASMs) can be used as a specification and development language for evolving concurrent systems. We therefore investigate a logic for crASMs. Based on the simple observation that concurrent ASMs can be mimicked by non-deterministic parallel ASMs we exploit the complete one-step logic for non-deterministic ASMs for the definition of a logic capturing concurrency. By making the extra-logical rules in the logic subject to being interpreted in a state we extend the logic to capture also reflection.

We define a programming language independent controller TaCtl for multi-level transactions and an operator $TA$, which when applied to concurrent programs with multi-level shared locations containing hierarchically structured complex values, turns their behavior with respect to some abstract termination criterion into a transactional behavior. We prove the correctness property that concurrent runs under the transaction controller are serialisable, assuming an Inverse Operation Postulate to guarantee recoverability. For its applicability to a wide range of programs we specify the transaction controller TaCtl and the operator $TA$ in terms of Abstract State Machines (ASMs). This allows us to model concurrent updates at different levels of nested locations in a precise yet simple manner, namely in terms of partial ASM updates. It also provides the possibility to use the controller TaCtl and the operator $TA$ as a plug-in when specifying concurrent system components in terms of sequential ASMs., Comment: 25 pages, 1 figure. arXiv admin note: substantial text overlap with arXiv:1706.01762

This paper presents Asm2C++, a tool that automatically generates executable C++ code for Arduino from a formal specification given as Abstract State Machines (ASMs). The code generation process follows the model-driven engineering approach, where the code is obtained from a formal abstract model by applying certain transformation rules. The translation process is highly configurable in order to correctly integrate the underlying hardware. The advantage of the Asm2C++ tool is that it is part of the Asmeta framework that allows to analyze, verify, and validate the correctness of a formal model.

Context: State machine diagrams are a powerful means to describe the behavior of reactive systems. Unfortunately, the implementation of state machines is difficult, because state machine concepts, like states, events and transitions, are not directly supported in commonly used programming languages. Most of the implementation approaches known so far have one or more serious drawbacks: they are difficult to understand and maintain, lack in performance, depend on the properties of a specific programming language or do not implement the more advanced state machine features like hierarchy, concurrency or history. Objective: This paper proposes and examines an approach to implement state machines, where both states and events are objects. Because the reaction of the state machine depends on two objects (state and event), a method known as double-dispatch is used to invoke the transition between the states. The aim of this work is to explore this approach in detail. Method: To prove the usefulness of the proposed approach, an example was implemented with the proposed approach as well as with other commonly known approaches. The implementation strategies are then compared with each other with respect to run-time, code size, maintainability and portability. Results: The presented approach executes fast but needs slightly more memory than other approaches. It supports hierarchy, concurrency and history, is human authorable, easy to understand and easy to modify. Because of its pure object-oriented nature depending only on inheritance and late binding, it is extensible and can be implemented with a wide variety of programming languages. Conclusion: The results show that the presented approach is a useful way to implement state machines, even on small micro-controllers.

The Business Process Model and Notation (BPMN) is a widely-used standard for process modelling. A drawback of BPMN, however, is that modality is implicitly expressed through the structure of the process flow but not directly within the corresponding activity. Thus, an extension of BPMN with deontic logic has been proposed in previous work, called Deontic BPMN. Deontic BPMN reduces the structural complexity of the process flow and increases the readability by explicitly highlighting obligatory and permissible activities. In addition, an algebraic graph transformation from a subset of BPMN to Deontic BPMN, called Deontic BpmnGTS, has been defined. The goal of the current research is to show that DeonticBpmnGTS is terminating and confluent, resulting in a globally deterministic transformation. Moreover, the semantic equivalence of BPMN models and the respective Deontic BPMN models is proven based on Abstract State Machines (ASMs). Thus, DeonticBpmnGTS can be called a trusted model transformation.

We propose a formalization of generic algorithms that includes analog algorithms. This is achieved by reformulating and extending the framework of abstract state machines to include continuous-time models of computation. We prove that every hybrid algorithm satisfying some reasonable postulates may be expressed precisely by a program in a simple and expressive language.

Medical devices are nowadays more and more software dependent, and software malfunctioning can lead to injuries or death for patients. Several standards have been proposed for the development and the validation of medical devices, but they establish general guidelines on the use of common software engineering activities without any indication regarding methods and techniques to assure safety and reliability. This paper takes advantage of the Hemodialysis machine case study to present a formal development process supporting most of the engineering activities required by the standards, and provides rigorous approaches for system validation and verification. The process is based on the Abstract State Machine formal method and its model refinement principle.

This paper defines a static check for clash-freedom of ASM rules, including sequential and parallel composition, nondeterministic choice, and recursion. The check computes a formula that, if provable, makes a relational encoding of ASM rules possible, which is an important prerequisite for efficient deduction. The check is general enough to cover all sequential rules as well as many typical uses of parallel composition.

Formal models of computation such as Turing machines are usually defined as performing operations on strings of symbols.

The paper presents our efforts in defining UASM, a unified syntax for Abstract State Machines ASMs, based on the syntaxes of two of the main ASM frameworks, CoreASM and ASMETA, which have been adapted to accept UASM as input syntax of all their validation and verification tools.

We show how to model distributed algorithms by Abstract State Machines ASMs. Comparing these models with Petri nets PNs reveals a certain number of idiosyncrasies of PNs which complicate both model design and analysis. The ASMs we define illustrate how one can avoid such framework related technicalities.

We define a flexible abstract ambient concept which turned out to support current programming practice, in fact can be instantiated to apparently any environment paradigm in use in frameworks for distributed computing with heterogeneous components. For the sake of generality and to also support rigorous high-level system design practice we give the definition in terms of Abstract State Machines. We show the definition to uniformly capture the common static and dynamic disciplines for isolating states or concurrent behavior (e.g. handling of multiple threads for Java) as well as for sharing memory, patterns of object-oriented programming (e.g. for delegation, incremental refinement, encapsulation, views) and agent mobility.

As research on developing assertion languages for the analog and mixed-signal (AMS) domain gains in momentum, it is increasingly being felt that extensions of existing assertion languages like property specification language and SystemVerilog assertions into the AMS domain are not adequate for expressing the analog design intent. This is largely due to the intricacy of the analog behavioral intent which cannot be captured purely in terms of logic. In this paper, we show that by using auxiliary forms of formal specifications such as abstract state machines and real-valued functions, called auxiliary functions, as references for AMS assertions, it becomes possible to model complex AMS behavioral properties. In addition, we present complexity results for the satisfiability problem of such specifications. This approach leverages the growing adoption of AMS behavioral modeling in the industry. This paper also shows that the use of auxiliary state machines allows us to separate out the scope of different analog assertions leading to significant performance gains in the assertion checking overhead.

ASM refinements are verified using generalized forward simulations which allow us to refine m abstract operations to n concrete operations with arbitrary m and n. One main difference from data refinement is that ASM refinement considers infinite runs and termination. Since backward simulation does not preserve termination in general, the standard technique of adding history information to the concrete level is not applicable to get a completeness proof. The power set construction also adds infinite runs and is therefore not applicable either. This paper shows that a completeness proof is nevertheless possible by adding infinite prophecy information, effectively moving nondeterminism to the initial state. Adding such prophecy information can be done not only on the semantic level, but also by a simple syntactic transformation that removes the choose construct of ASMs. The completeness proof is also translated to a completeness proof for IO automata. Finally, the proof is extended to deal with supplementary predicates, that specify fairness and liveness assumptions, by transferring a related result of Wim Hesselink for refinements that use the Abadi–Lamport setting.

We propose an extension of the behavioral theory of interactive sequential algorithms to deal with the following situation. A query is issued during a certain step, but the step ends before any reply is received. Later, a reply arrives, and later yet the algorithm makes use of this reply. By a persistent query, we mean a query for which a late reply might be used. Our proposal involves issuing, along with a persistent query, a location where a late reply is to be stored. After presenting our proposal in general terms, we discuss the modifications that it requires in the existing axiomatics of interactive sequential algorithms and in the existing syntax and semantics of abstract state machines. To make that discussion self-contained, we include a summary of this material before the modifications. Fortunately, only rather minor modifications are needed.

We formalize the algorithms computing primitive recursive (PR) functions as the abstract state machines (ASMs) whose running length is computable by a PR function. Then we show that there exists a programming language (implementing only PR functions) by which it is possible to implement any one of the previously defined algorithms for the PR functions in such a way that their complexity is preserved.

The instruction set architecture (ISA) of a computing machine is the definition of the binary instructions, registers, and memory space visible to an executable binary image. ISAs are typically implemented in hardware as microprocessors, but also in software running on a host processor, i.e. virtual machines (VMs). Despite there being many ISAs in existence, all share a set of core properties which have been tailored to their particular applications. An abstract model may capture these generic properties and be subsequently refined to a particular machine, providing a reusable template for development of robust ISAs by the formal construction of all normal and exception conditions for each instruction. This is a task to which the Event-B (Metayer et al. in Rodin deliverable 3.2 Event-B language, http://rodin.cs.ncl.ac.uk , 2005; Schneider in The B-method an introduction, Palgrave, Basingstoke, 2001) formal notation is well suited. This paper describes a project to use the Rodin tool-set (Abrial in Formal methods and software engineering, Springer, Berlin, 2006) to perform such a process, ultimately producing two variants of the MIDAS (Microprocessor Instruction and Data Abstraction System) ISA (Wright in Abstract state machines, B and Z, Springer, Berlin, 2007; Wright in MIDAS machine specification, Bristol University, http://www.cs.bris.ac.uk/Publications , 2009) as VMs. The abstract model is incrementally refined to variant models capable of automatic translation to C source code, which this is compiled to create useable VMs. These are capable of running binary executables compiled from high-level languages such as C (Kernighan and Ritchie in The C programming language, Prentice-Hall, Englewood Cliffs, 1988), and compilers targeted to each variant allow demonstration programs to be executed on them.

In this paper we consider an adaptation of counter abstraction for the CSP/FDR setting. The technique allows us to transform a concurrent system with an unbounded number of agents into a finite-state abstraction. The systems to which the method can be applied are composed of many identical node processes that run in parallel with a controller process. Refinement checks on the abstract state machine can be performed automatically in the traces and stable failures models using the FDR model checker. We illustrate the method on an example based on a multiprocessor operating system.

We consider parallel algorithms working in sequential global time, for example, circuits or parallel random access machines (PRAMs). Parallel abstract state machines (parallel ASMs) are such parallel algorithms, and the parallel ASM thesis asserts that every parallel algorithm is behaviorally equivalent to a parallel ASM. In an earlier article, we axiomatized parallel algorithms, proved the ASM thesis, and proved that every parallel ASM satisfies the axioms. It turned out that we were too timid in formulating the axioms; they did not allow a parallel algorithm to create components on the fly. This restriction did not hinder us from proving that the usual parallel models, like circuits or PRAMs or even alternating Turing machines, satisfy the postulates. But it resulted in an error in our attempt to prove that parallel ASMs always satisfy the postulates. To correct the error, we liberalize our axioms and allow on-the-fly creation of new parallel components. We believe that the improved axioms accurately express what parallel algorithms ought to be. We prove the parallel thesis for the new, corrected notion of parallel algorithms, and we check that parallel ASMs satisfy the new axioms.

ASM refinements are verified using generalized forward simulations which allow to refine m abstract operations to n concrete operations with arbitrary m and n. One main difference to data refinement is that ASM refinement considers infinite runs and termination. Since backward simulation does not preserve termination in general, the standard technique of adding history information to the concrete level is not applicable. The powerset construction also adds infinite runs and is therefore not applicable too. This paper shows that a completeness proof is nevertheless possible by adding infinite prophecy information, effectively moving nondetermism to the initial state. Adding such prophecy information can be done on the semantic level, but also by a simple syntactic transformation that removes the choose construct of ASMs. The completeness proof is also ported to give a completeness proof for IO automata.

The theory of Turing machines, which is basic to proving the various limitations of computers, is quite well known. The theory of finite state automata, the basic hardware models such as Moore machines, Mealy machines, and their generalizations, are similarly well known. Our purpose here is to survey basic work done between 1958 and 1975 on still another mathematical model for computer science, the state vector model. In this model there are many variables, each with its own current value, rather than a single state; this makes the model closer to what happens in a real computer.

We present a framework for the formal verification of abstract state machine (ASM) designs using the multiway decision graphs (MDG) tool. ASM is a state based language for describing transition systems. MDG provides symbolic representation of transition systems with support of abstract sorts and functions. We implemented a transformation tool that automatically generates MDG models from ASM specifications. Then formal verification techniques provided by the MDG tool, such as model checking or equivalence checking, can be applied on the generated models. We illustrate this work with the case study of an ATM switch controller, in which behavior and structure were specified in ASM and, using our ASM-MDG facility, are successfully verified with the MDG tool.

In this paper, we propose to integrate an embedding of Property Specification Language (PSL) in Abstract State Machines Language (AsmL) with a top–down design for verification approach in order to enable the model checking of large systems at the early stages of the design process. We provide a complete embedding of PSL in the ASM language AsmL, which allows us to integrate PSL properties as a part of the design. For verification, we propose a technique based on the AsmL tool that translates the code containing both the design and the properties into a finite state machine (FSM) representation. We use the generated FSM to run model checking on an external tool, here SMV. Our approach takes advantage of the AsmL language capabilities to model designs at the system level as well as from the power of the AsmL tool in generating both C# code and FSMs from AsmL models. We applied our approach on the PCI-X bus standard, which AsmL model was constructed from the informal standard specifications and a subsequent UML model. Experimental results on the PCI-X bus case study showed a superiority of our approach to conventional verification.

In the requirements engineering community, consistency and completeness have been identified as important properties of system specifications. Custom algorithms to verify these properties automatically have been devised for a number of specification languages, including SCR, RSML, and Statecharts. In this paper, we provide means to automatically verify completeness and consistency of Abstract State Machine (ASM) specifications. The verification is performed using a widely available tool, a SAT solver. The use of a SAT solver removes the need for designing and fine tuning language specific verification algorithms. Furthermore, the use of a SAT solver automates the verification procedure and produces a counterexample automatically when a specification is incomplete or inconsistent. We provide an algorithm to translate ASM specifications to a SAT problem instance. The translation is illustrated using the TASM toolset in conjunction with the “production cell system” case study.

We explain why for the verified software challenge proposed in Hoare (J ACM 50(1): 63–69, 2003), Hoare and Misra (Verified software: theories, tools, experiments. Vision of a Grand Challenge project. In: [Meyer05]) to gain practical impact, one needs to include rigorous definitions and analysis, prior to code development and comprising both experimental validation and mathematical verification, of ground models , i.e., blueprints that describe the required application-content of programs. This implies the need to link via successive refinements the relevant properties of such high-level models in a traceable and checkable way to code a compiler can verify. We outline the Abstract State Machines (ASM) method, a discipline for reliable system development which allows one to bridge the gap between informal requirements and executable code by combining application-centric experimentally validatable system modelling with mathematically verifiable stepwise detailing of abstract models to compile-time-verifiable code.

The focus of this paper is state diagrams that are used to represent state machines. Current diagrammatic representations of state machines are almost too compacted and do not completely depict their underlying semantics or clarify basic static structure and elementary dynamic features. The paper proposes using a new diagrammatic representation for state-based depictions. Advantages of the new diagrams include enhanced understanding of the related problems and exposure to new variations in viewing state machines and how to reflect about them. The proposed method is demonstrated through diagramming of a traffic light controller that has been represented in state and statechart diagrams. In addition, a Turing machine example is depicted by the new methodology.

International audience; The Synapse protocol is a scalable protocol designed for information retrieval over inter-connected heterogeneous overlay networks. In this paper, we give a formal description of Synapse using the Abstract State Machines framework. The formal description pertains to Synapse actions that manipulate distributed keys. Based on this formal description, we present results concerning the expected exhaustiveness for a number of scenarios and systems maintained by the Synapse protocol, and provide comparisons to the results of the corresponding simulations and experiments. We show that the predicted theoretical results match the obtained experimental results, and give recommendations on the design of systems using Synapse.

State Machines (ASMs) represent a general model of computation which subsumes all other classic computational models. Since the notion of ASM state naturally captures the classic notion of program state, ASMs are suitable to be verified through a predicate abstraction approach. The aim of this paper is to discuss how predicates over ASM states can support the formal verification of ASM-based models. The proposal can overcome the main limitations that penalize traditional model checking techniques applied to ASMs.

We present SecureMDD, a development method for secure service applications that integrates a model-driven approach with formal specification techniques using abstract state machines (ASMs), refinement to code and verification with the interactive theorem prover KIV. A larger case study is used to highlight various aspects of the method with a focus on services and their formal verification.

This position paper aims at setting a new semantics for multi-modal mu-calculus to represent interactive states where abstract actions may be applied to. A least fixed point formula may be available to denote states allowing interaction. A simple algebraic representation for interactive states can be definable. For communication between human and machinery, a modality is reserved. In applicative task domains, knowledge construction is focused on with respect to interactive action applications through communications. Panel touch behaviour on iDevice as practice, URL references as functions and grammatical rule applications for sequential effects are studied, as knowledge construction technologies. These views coherent with abstract state machine are finally related to recent trends as semiring in algebraic structure and coalgebra for streams as sequential knowledge structures. A refinement of interactive techniques is positioned into a formal approach to multi-modal logic, applicable to some practices.

This is the second in a series of three articles extending the proof of the Abstract State Machine Thesis---that arbitrary algorithms are behaviorally equivalent to abstract state machines---to algorithms that can interact with their environments during a step, rather than only between steps. As in the first article of the series, we are concerned here with ordinary, small-step, interactive algorithms. This means that the algorithms:(1) proceed in discrete, global steps,(2) perform only a bounded amount of work in each step,(3) use only such information from the environment as can be regarded as answers to queries, and(4) never complete a step until all queries from that step have been answered.After reviewing the previous article's formal description of such algorithms and the definition of behavioral equivalence, we define ordinary, interactive, small-step abstract state machines (ASMs). Except for very minor modifications, these are the machines commonly used in the ASM literature. We define their semantics in the framework of ordinary algorithms and show that they satisfy the postulates for these algorithms.This material lays the groundwork for the final article in the series, in which we shall prove the Abstract State Machine thesis for ordinary, intractive, small-step algorithms: All such algorithms are equivalent to ASMs.

These notes give an overview of the main frameworks that have been developed for specifying the formal semantics of programming languages. Some of the pragmatic aspects of semantic descriptions are discussed, including modularity, and potential applicability to visual and modelling languages. References to the literature provide starting points for further study.

The Abstract State Machine Language, AsmL, is a novel executable specification language based on the theory of Abstract State Machines. AsmL is object-oriented, provides high-level mathematical data-structures, and is built around the notion of synchronous updates and finite choice. AsmL is fully integrated into the .NET framework and Microsoft development tools. In this paper, we explain the design rationale of AsmL and provide static and dynamic semantics for a kernel of the language.