Turing machines and register machines have been used for decades in theoretical computer science as abstract models of computation. Also the $\lambda$-calculus has played a central role in this domain as it allows to focus on the notion of functional computation, based on the substitution mechanism, while abstracting away from implementation details. The present article starts from the observation that the equivalence between these formalisms is based on the Church-Turing Thesis rather than an actual encoding of $\lambda$-terms into Turing (or register) machines. The reason is that these machines are not well-suited for modelling $\lambda$-calculus programs. We study a class of abstract machines that we call "addressing machine" since they are only able to manipulate memory addresses of other machines. The operations performed by these machines are very elementary: load an address in a register, apply a machine to another one via their addresses, and call the address of another machine. We endow addressing machines with an operational semantics based on leftmost reduction and study their behaviour. The set of addresses of these machines can be easily turned into a combinatory algebra. In order to obtain a model of the full untyped $\lambda$-calculus, we need to introduce a rule that bares similarities with the $\omega$-rule and the rule $\zeta_\beta$ from combinatory logic.

In this paper we present SyBeL (System Behaviour modelling Language), an XML based formalism for software system modelling. In particular, SyBeL focuses on the description of the system behaviour in order to capture its functional requirements and has been designed to fulfill some of the most trendy software engineering issues. The use of the underlying XML language makes the artifacts generated by SyBeL immediately available to further automatic manipulation (e. g., to automatically generate test cases) without the need of intermediate models, as usually done in semi-formal approaches. Moreover, we are experimenting SyBeL on a variety of practical case studies.

In this paper we present SMDP (Scenario Model Development Process), an XML-based methodology for the description and manipulation of scenarios that are used to formalize and reuse software requirements. SMDP is an iterative and incremental process that supports scenario evolution during the requirements engineering process. The formalization of scenarios through the underlying XML-based language of SMDP makes them immediately available to further automatic manipulation (e.g., to automatically generate test cases) without the need for intermediate models, as it is usually done in semi-formal approaches. Thanks to the implementation of a software assistant environment for SMDP, the methodology is currently being experimented on a variety of case studies, in particular web applications.

One of the most succesfull approach to automatic software verification is SAT based Bounded Model Checking (BMC). One of the main factors limiting the size of programs that can be automatically verified via BMC is the huge number of clauses that the backend SAT solver has to process. In fact, because of this, the SAT solver may easily run out of RAM. We present two disk based algorithms that can considerably decrease the number of clauses that a BMC backend SAT solver has to process in RAM. Our experimental results show that using our disk based algorithms we can automatically verify programs that are out of reach for RAM based BMC.

Scenarios are a new way of representing knowledge that has been attracting a lot of attention from practitioners and researchers. In this paper we present the SDML formalism, an XML definition language to support scenario-based requirements engineering. The definition of scenarios through SDML enables to exploit the emerging XML technologies in order to offer powerful ways to create, maintain, distribute and use scenarios. Moreover, we are experimenting the SDML language on a variety of practical case studies.

The main barrier to automatic verification of concurrent systems is the huge amount of memory required to complete the verification task (state explosion). In this paper we present a probabilistic algorithm for automatic verification via model checking. Our algorithm trades space with time. In particular, when memory is full because of state explosion our algorithm does not give up verification. Instead it just proceeds at a lower speed and its results will only hold with some arbitrarily small error probability. Our preliminary experimental results show that by using our probabilistic algorithm we can typically save more than 30% of RAM with an average time penalty of about 100% w.r.t. a deterministic state space exploration with enough memory to complete the verification task. This is better than giving up the verification task because of lack of memory.