Search

A component-based realtime system is a simple model for the server-client relation with time constraints. This paper presents an efficient algorithm, called a blackbox testing algorithm, for detecting the emptiness of a component-based realtime system. This algorithm was originally proposed in [5], but with a certain flaw. We improve it and correct the flaw by using urgency [2] of transitions. [ABSTRACT FROM AUTHOR]

In this chapter we will present selected central elements in the theory of Duration Calculus and we will give examples of applications. The chapter will cover syntax, semantics and proof system for the basic logic. Furthermore, results on decidability, undecidability and model-checking will be presented. A few extensions of the basic calculus will be described, in particular, Hybrid Duration Calculus and Duration Calculus with iterations. Furthermore, a case study: the bi-phase mark protocol, is presented. We will not attempt to be exhaustive in our coverage of topics; but we will provide references for further study. [ABSTRACT FROM AUTHOR]

Due to its absence of side effects, it is usually claimed that reasoning about functional programs is simpler than reasoning about their imperative counterparts. Unfortunately, due to the absence of practical debuggers, finding bugs in lazy functional languages has been much more complex until quite recently. One of the easiest to use Haskell debuggers is Hood, whose behavior is based on the concept of observation of intermediate data structures. However, it can be hard to understand how it works when dealing with complex situations. In this paper, we introduce debugging facilities in the STG abstract machine. Our goal is to obtain debugging information as close to the one obtained by the Hood debugger as possible. By extending the STG abstract machine, we do not only provide a formal framework to the debugging process, but also an alternative method to implement debuggers. Keywords: Functional programming, debugging, abstract machines. [ABSTRACT FROM AUTHOR]

We study how to efficiently combine satisfiability procedures built by using a superposition calculus with satisfiability procedures for theories, for which the superposition calculus may not apply (e.g., for various decidable fragments of Arithmetic). Our starting point is the Nelson-Oppen combination method, where satisfiability procedures cooperate by exchanging entailed (disjunction of) equalities between variables. We show that the superposition calculus deduces sufficiently many such equalities for convex theories (e.g., the theory of equality and the theory of lists) and disjunction of equalities for non-convex theories (e.g., the theory of arrays) to guarantee the completeness of the combination method. Experimental results on proof obligations extracted from the certification of auto-generated aerospace software confirm the efficiency of the approach. Finally, we show how to make satisfiability procedures built by superposition both incremental and resettable by using a hierarchic variant of the Nelson-Oppen method. [ABSTRACT FROM AUTHOR]

Five tutorials were provided by ICTAC 2005. They were conducted by internationally recognised experts. A brief summary of each tutorial is include here. [ABSTRACT FROM AUTHOR]

We are concerned with theoretical aspects of computer viruses. For this, we suggest a new definition of viruses which is clearly based on the iteration theorem and above all on Kleene's recursion theorem. We show that we capture in a natural way previous definitions, and in particular the one of Adleman. We establish generic constructions in order to construct viruses, and we illustrate them by various examples. We discuss the relationship between information theory and viruses and we propose a defense against a kind of viral propagation. Lastly, we show that virus detection is Π2-complete. However, since we are able to deal with system vulnerability, we exhibit another defense based on controlling system access. [ABSTRACT FROM AUTHOR]

We present a new derivation of efficient algorithms for a class of optimization problems called maximum marking problems. We extend the class of weight functions used in the specification to allow for weight functions with accumulation, which is particularly useful when the weight of each element depends on adjacent elements. This extension of weight functions enables us to treat more interesting optimization problems such as a variant of the maximum segment sum problem and the fair bonus distribution problem. The complexity of the derived algorithm is linear with respect to the size of the input data. Keywords: Program derivation, Maximum marking problem, Accumulative weight function, Optimization problem. [ABSTRACT FROM AUTHOR]

We present a new algorithm for conjunctive and disjunctive boolean equation systems which arise frequently in the verification and analysis of finite state concurrent systems. In contrast to the previously known O(e2) time algorithms, our algorithm computes the solution to such a fixpoint equation system with size e and alternation depth d in O(e log d) time (here d < e). We show the correctness and complexity of the algorithm. We discuss heuristics and describe how the algorithm can be efficiently implemented. The algorithm is compared to a previous solution via experiments on verification examples. Our measurements indicate that the new algorithm makes the verification of a large class of fixpoint expressions more tractable. [ABSTRACT FROM AUTHOR]

Although liveness and fairness have been used for a long time in classical model checking, with process-algebraic methods they have seen far less use. One problem is that it is difficult to combine fairness constraints with the compositionality of process algebra. Here we show how a class of fairness constraints can be applied in a consistent way to processes in the compositional setting. We use only ordinary, but possibly infinite, LTSs as our models of processes. In many cases the infinite LTSs are part of a larger system, which can again be represented as a finite LTS. We show how this finiteness can be recovered, namely, we present an algorithm that checks whether a finite representation exists and, if it does, constructs a finite LTS that is equivalent to the infinite system. Even in the negative case, the system produced by the algorithm is a conservative estimate of the infinite system. Such a finite representation can be placed as a component in further compositional analysis just like any other LTS. [ABSTRACT FROM AUTHOR]

Open systems capable of handling unanticipated future changes are very desirable. A common approach towards open systems is based on components. There are some essential issues of the component-based software paradigm. First, the most challenging analysis issue is about component consistency - namely a component does not violate some property in another when composed. The paper presents a formal approach to the issue by including consistency semantic to component specification. Based on this semantic information, components can be efficiently cross-checked for the consistency among components. The second issue is on how components are realized from the formal specification. The layered architecture is recommended for component-based system design in which component specifications are separated into layers. Subsequently, each layer can be then respectively implemented by a corresponding module via aspect-oriented programming. The target system simply involves composing those modules together in a well-defined order. [ABSTRACT FROM AUTHOR]

This paper presents a theory of Object-Oriented concepts embedded shallowly in HOL for the verification of OO analysis models. The theory is application-specific in the sense that it is automatically constructed depending on the type information of the application. This allows objects to have attributes of arbitrary types, making it possible to verify models using not only basic types but also highly abstracted types specific to the target domain. The theory is constructed by definitional extension based on the operational semantics of a heap memory model, which guarantees the soundness of the theory. This paper mainly focuses on the implementation details of the theory. [ABSTRACT FROM AUTHOR]

We have recently developed an object-oriented refinement calculus called rCOS to formalize the basic object-orient design principles, patterns and refactoring as refinement laws. The aim is of rCOS is to provide a formal support to the use-cased driven, incremental and iterative Rational Unified Process (RUP). In this paper, we apply rCOS to a step-wised development of a Point of Sale Terminal (POST) system, from a requirement model to a design model, and finally, to the implementation in Visual C#. Keywords: Refinement, Software design, Object-orientation, Refactoring, UML. [ABSTRACT FROM AUTHOR]

Although increasingly popular, software component techniques still lack suitable formal foundations on top of which rigorous methodologies for the description and analysis of software architectures could be built. This paper aims to contribute in this direction: building on previous work by the authors on coalgebraic semantics, it discusses component refinement at three different but interrelated levels: behavioural, syntactic, i.e., relative to component interfaces, and architectural. Software architectures are defined through component aggregation. On the other hand, such aggregations, no matter how large and complex they are, can also be dealt with as components themselves, which paves the way to a discipline of hierarchical design. In this context, a major contribution of this paper is the introduction of a set of rules for architectural refinement. Keywords: Software component, software architecture, refinement, coalgebra. [ABSTRACT FROM AUTHOR]

In this paper we introduce a novel notion of bisimulation to properly capture the behavior of stochastic systems with general distributions. The key idea consists in the identification of different sequences of random variables if the additions of the random variables of each sequence are identically distributed. That is, we will not only identify sequences of internal actions with one of them (as it is usually done in weak bisimulations) but we will also reduce (in some conditions) sequences of stochastic transitions to only one transition. Therefore, we will identify processes that are considered non-equivalent in previous notions of bisimulation for this kind of languages. [ABSTRACT FROM AUTHOR]

The paper describes an implementation in the HOL theorem prover of the quantitative Temporal Logic (qTL) of Morgan and McIver [18,4]. qTL is a branching-time temporal logic suitable for reasoning about probabilistic nondeterministic systems. The interaction between probabilities and nondeterminism, which is generally very difficult to reason about, is handled by interpreting the logic over real- rather than boolean-valued functions. In theqTL framework many laws of standard branching-time temporal logic generalize nicely giving access to a number of logical tools for reasoning about quantitative aspects of randomized algorithms. [ABSTRACT FROM AUTHOR]

A logic for reasoning about quantum circuits and protocols is proposed. It incorporates the basic features of quantum theory-probability, unitary dynamics, tensor products and measurement. The underlying language could be used for verification and synthesis of quantum circuits. Important algorithms like the quantum search algorithm of Grover are discussed. The logic also forms the foundation on which more elaborate formal systems for reasoning about quantum protocols could be based. A sound and complete axiomatization is presented. Algorithms for circuit verification, circuit equivalence (exact and approximate) are outlined. Some related complexity issues are also discussed. Keywords: Probability logic, quantum computing, quantum circuits, complexity. [ABSTRACT FROM AUTHOR]

Continuous stochastic logic (CSL) deals with the verification of systems operating in continuous time, it may be traced to the well known tree logic CTL. We propose a probabilistic interpretation of this logic that is based on stochastic relations without making specific assumptions on the underlying distribution, and study the problem of bisimulations in a fairly general context from the viewpoint of congruences for stochastic relations. The goal is finding minimal sets of formulas that permit efficient checking of models. [ABSTRACT FROM AUTHOR]

It has recently been shown that fair exchange, a security problem in distributed systems, can be reduced to a fault tolerance problem, namely a special form of distributed consensus. The reduction uses the concept of security modules which reduce the type and nature of adversarial behavior to two standard fault-assumptions: message omission and process crash. In this paper, we investigate the feasibility of solving consensus in asynchronous systems in which crash and message omission faults may occur. Due to the impossibility result of consensus in such systems, following the lines of unreliable failure detectors of Chandra and Toueg, we add to the system a distributed device that gives information about the failure of other processes. Then we give an algorithm using this device to solve the consensus problem. Finally, we show how to implement such a device in an asynchronous system using some weak timing assumptions. [ABSTRACT FROM AUTHOR]

Role-based access control (RBAC) is recognized as an excellent model for access control in large-scale networked applications. Formalization of RBAC in a logical approach makes it feasible to reason about a specified policy and verify its correctness. We propose a formalization of RBAC by the description logic language . We also show that the RBAC constraints can be captured by . Furthermore, we demonstrate how to make access control decision, perform the RBAC functions as well as check the consistency of RBAC via the description logic reasoner RACER. [ABSTRACT FROM AUTHOR]

We investigate the issue of typing confidentiality in a language-based information-flow security approach, aiming at improving some previously proposed type systems, especially for higher-order languages with mutable state à la ML. We show that the typing of termination leaks can be largely improved, by particularizing the case where the alternatives in a conditional branching both terminate. Moreover, we also provide a quite precise way of approximating the confidentiality level of an expression, that ignores the level of values used for side-effects only. [ABSTRACT FROM AUTHOR]

Detecting information flows inside a program is useful to check non-interference of program variables, an important aspect of software security. Information flows have been computed in the past by using abstract interpretation over an abstract domain IF which expresses sets of flows. In this paper we reconstruct IF as the linear refinement of a basic domain C expressing constancy of program variables. This is important since we also show that , and hence IF, is closed w.r.t. linear refinement, and is hence optimal and condensing. Then a compositional, input-independent static analysis over IF has the same precision of a non-compositional, input-driven analysis. Moreover, we show that has a natural representation in terms of Boolean formulas, efficiently implementable through binary decision diagrams. [ABSTRACT FROM AUTHOR]

Many different behavioral refinement notions for algebraic specifications have been proposed in the literature but the relationship between the various concepts is still unclear. In this paper we provide a classification and a comparative study of behavioral refinements according to two directions, the externalized approach which uses an explicit behavioral abstraction operator that is applied to the specification to be implemented, and the internalized approach which uses a built-in behavioral semantics of specifications. We show that both concepts are equivalent under suitable conditions. The formal basis of our study is provided by the COL institution (constructor-based observational logic). Hence, as a side-effect of our study on internalized behavioral refinements, we introduce also a novel concept of behavioral refinement for COL-specifications. [ABSTRACT FROM AUTHOR]

In TCS 146, Bard Bloom presented rule formats for four main notions of bisimulation with silent moves. He proved that weak bisimulation equivalence is a congruence for any process algebra defined by WB cool rules, and established similar results for rooted weak bisimulation (Milner's "observational congruence"), branching bisimulation and rooted branching bisimulation. This study reformulates Bloom's results in a more accessible form and contributes analogues for (rooted) η-bisimulation and (rooted) delay bisimulation. Moreover, finite equational axiomatisations of rooted weak bisimulation equivalence are provided that are sound and complete for finite processes in any RWB cool process algebra. These require the introduction of auxiliary operators with lookahead. Finally, a challenge is presented for which Bloom's formats fall short and further improvement is called for. [ABSTRACT FROM AUTHOR]

We construct a Galois connection between the theories that underlie CCS [7] and CSP [4]. It projects the complete transition system for CCS onto exactly the subset that satisfies the healthiness conditions of CSP. The construction applies to several varieties of both calculi: CCS with strong, weak or barbed simulation, and CSP with trace refinement or failures refinement, or failures/divergence. We suggest the challenge of linking other theories of concurrency by Galois connection. [ABSTRACT FROM AUTHOR]

Coalgebras provide effective models of data structures and state-transition systems. A virtual covariety is a class of coalgebras closed under coproducts, images of coalgebraic morphisms, and subcoalgebras defined by split equalisers. A covariety has the stronger property of closure under all subcoalgebras, and is behavioural if it is closed under domains of morphisms, or equivalently under images of bisimulations. There are many computationally interesting properties that define classes of these kinds. We identify conditions on the underlying category of a comonad which ensure that there is an exact correspondence between (behavioural/virtual) covarieties of -coalgebras and subcomonads of defined by comonad morphisms to with natural categorical properties. We also relate this analysis to notions of coequationally defined classes of coalgebras. [ABSTRACT FROM AUTHOR]

This paper introduces the notion of finite precision timed automata (FPTAs) and proposes a data structure to represent its symbolic states. To reduce the state space, FPTAs only record the integer values of clock variables together with the order of their most recent resets. We provide constraints under which the reachability checking of a timed automaton can be reduced to that of the corresponding FPTA, and then present an algorithm for reachability analysis. Finally, the paper reports some preliminary experimental results, and analyzes the advantages and disadvantages of the new data structure. Keywords: Finite precision timed automata, model checking, symbolic methods. [ABSTRACT FROM AUTHOR]

We transfer the concept of robust interpretation from arithmetic first-order theories to metric-time temporal logics. The idea is that the interpretation of a formula is robust iff its truth value does not change under small variation of the constants in the formula. Exemplifying this on Duration Calculus (DC), our findings are that the robust interpretation of DC is equivalent to a multi-valued interpretation that uses the real numbers as semantic domain and assigns Lipschitz-continuous interpretations to all operators of DC. Furthermore, this continuity permits approximation between discrete and dense time, thus allowing exploitation of discrete-time (semi-)decision procedures on dense-time properties. Keywords: Metric-time temporal logic; Robust interpretation; Discrete time vs. dense time. [ABSTRACT FROM AUTHOR]

Case studies can significantly contribute towards improving the understanding of formalisms and thereby to their applicability in practice. One such case, namely a cascade of the familiar 24-hour timers (in suitably generalized form) provides interesting gedanken experiments and illustrations for presenting, illustrating and comparing various formalisms for modelling real-time behaviour of systems. The timer cascade is first modelled in a general-purpose functional formalism (Funmath) and various properties are derived, including an interesting algebraic monoid structure of timer programs. Then it is described and analyzed in duration calculus, thereby highlighting, similarities and differences in the approach to modelling and reasoning, and also the link between the formalisms. Future work consists in using this case as a running example for exploring the same issues for other formalisms intended for real time and hybrid systems. The underlying idea is that other authors join this effort and contribute towards extending it, finally arriving at a broad comparative survey of such formalisms. Index Terms — Automata, cascade connection, Duration Calculus, functional description, Funmath, hybrid systems, real time systems, systems modelling, timers. [ABSTRACT FROM AUTHOR]

A software program requesting a resource that is not available usually raises an out-of-resource exception. Component software is software that has been assembled from standardized, reusable components which, in turn, may also composed from other components. Due to the independent development and reuse of components, component software has a high risk of causing out-of-resource exceptions. We present a small component language and develop a type system which can statically prevent this type of errors . This work continues our previous works [3,18] by including explicit deallocation. We prove that the type system is sound with respect to safe deallocation and that sharp resource bounds can be computed statically. [ABSTRACT FROM AUTHOR]

This paper introduces a tool that automatically translates a concrete form of specifications into C code linked with BSPlib. The translation tool is rigorously developed with important safety properties proved. A Logs specification for Bulk-Synchronous Parallelism is a relation of an initial state, a final state and some intermediate states. Nondeterminism and parallelism correspond to disjunction and conjunction respectively. Various advanced specification commands can be derived from the basic ones. The translator checks syntax, freedom of communication interference, type consistency and communication dependencies before generating the target code. Static analysis (including both static checkings and translation) is presented in abstract interpretation. It is shown that a few laws are complete for transforming any specification into a normal form. These laws are satisfied by the abstract functions. We demonstrate the actual effects of the abstract functions by applying them on the normal form. The approach has been implemented using an object-oriented language. [ABSTRACT FROM AUTHOR]

In this paper we prove some properties of combinational programs which is an improvement of the results presented in our previous work. We prove the derivation of loop-programs for combinational ones by both event semantics and stability semantics. We give a normal form for syntactically well-formed combinational programs, and show that for them Dimitrov's multiple parallel approach and Zhu's shared store parallel approach are equivalent. [ABSTRACT FROM AUTHOR]

In this paper, we study an upside-down transformation of a branch in SOL/Connection tableaux and show that SOL/Connection tableaux using the folding-up operation can always accomplish a size-preserving transformation for any branch in any tableau. This fact solves the exponentially-growing size problem caused both by the order- preserving reduction and by an incremental answer computation problem. [ABSTRACT FROM AUTHOR]

We develop semantics for modal logic programs in basic serial multimodal logics, which are parameterized by an arbitrary combination of generalized versions of axioms T, B, 4, 5 (in the form, e.g., ) and . We do not assume any special restriction for the form of programs and goals. Our fixpoint semantics and SLD-resolution calculus are defined using the direct approach and closely reflect the axioms of the used modal logic. We prove that our SLD-resolution calculus is sound and complete. [ABSTRACT FROM AUTHOR]

Compositionality plays an important role in designing reactive systems as it allows one to compose/decompose a complex system from/to several simpler components. Generally speaking, it is hard to design a complex system in a logical frame in a compositional way because it is difficult to find a connection between the structure of a system to be developed and that of its specification given by the logic. In this paper, we investigate the compositionality of the Fixpoint Logic with Chop (FLC for short). To this end, we extend FLC with the nondeterministic choice "+" (FLC+ for the extension) and then establish a correspondence between the logic and the basic process algebra with deadlock and termination (abbreviated BPAεδ). Subsequently, we show that the choice "+" is definable in FLC. As an application of the compositionality of FLC, an algorithm is given to construct characteristic formulae of BPAεδ up to strong bisimulation directly from the syntax of processes in a compositional manner. Keywords: FLC, compositionality, verification, bisimulation, characteristic formula, basic process algebra. [ABSTRACT FROM AUTHOR]

Splicing Array Grammar Systems (SAGS) generating pictures of rectangular arrays of symbols are introduced. The components consist of two-dimensional tabled matrix Grammars working in parallel and arrays generated in two different components of the SAGS are allowed to be "cut" and "pasted" according to array splicing domino rules. This model is motivated by the study of Dassow and Mitrana (1996) on string splicing grammar systems. Certain properties of SAGS are obtained. [ABSTRACT FROM AUTHOR]

In this paperA full version can be found in the LIFO RR-2005-2 at the following URL http://www.univ-orleans.fr/lifo/prodsci/rapports/RR2005.htm.en, we study the class of pseudo-regular relations which is an extension of regular relations that weakens some restrictions on the "synchronization" between tuple components of the relation. We choose logic programming as formalism to describe tree tuple languages (i.e. relations) and logic program transformation techniques for computing operations on them. We show that even if pseudo-regular cs-programs are syntactically less restrictive than regular ones, they define the same class of tree tuple languages. However, pseudo-regular relations allow one to define classes of term rewrite systems the transitive closure of which is a regular relation. We apply this result to give a decidable class of first order formulae based on the joinability predicate ↓?R where R is a pseudo-regular term rewrite system. [ABSTRACT FROM AUTHOR]

A string x is an outfix of a string y if there is a string w such that x1wx2=y, where x = x1x2 and a set X of strings is outfix-free if no string in X is an outfix of any other string in X. We examine the outfix-free regular languages. Based on the properties of outfix strings, we develop a polynomial-time algorithm that determines the outfix-freeness of regular languages. We consider two cases: A language is given as a set of strings and a language is given by an acyclic deterministic finite-state automaton. Furthermore, we investigate the prime outfix-free decomposition of outfix-free regular languages and design a linear-time prime outfix-free decomposition algorithm for outfix-free regular languages. We demonstrate the uniqueness of prime outfix-free decomposition. [ABSTRACT FROM AUTHOR]

We discuss some of the difficulties and significant issues that we need to consider when developing a formal method for component-based software engineering. We argue that to deal with the challenges, there is a need in research to link existing theories and methods of programming for effective support to component-based software engineering. We then present our initiative on a unified multi-view approach to modelling, design and analysis of component systems, emphasising the integration of models for different views. Keywords: Components, Interfaces, Contracts, Protocols, Functionality, Consistency, Composition, Refinement, Simulation. [ABSTRACT FROM AUTHOR]

In distributed and mobile systems with volatile bandwidth and fragile connectivity, non-functional aspects like performance and reliability become more and more important. To formalise, measure, and predict these properties, stochastic methods are required. At the same time such systems are characterised by a high degree of architectural reconfiguration. Viewing the architecture of a distributed system as a graph, this is naturally modelled by graph transformations. To address these two concerns, stochastic graph transformation systems have been introduced associating with each rule its application rate—the rate of the exponential distribution governing the delay of its application. Deriving continuous-time Markov chains, Continuous Stochastic Logic is used to specify reliability properties and verify them through model checking. In particular, we study a protocol for the reconfiguration of P2P networks intended to improve their reliability by adding redundant connections. The modelling of this protocol as a (stochastic) graph transformation system takes advantage of negative application and conditions path expressions. This ensuing high-level style of specification helps to reduce the number of states and increases the capabilities for automated analysis. [ABSTRACT FROM AUTHOR]

We describe motivations and background behind the design of Klaim, a process description language that has proved to be suitable for describing a wide range of applications distributed over wide area networks with agents and code mobility. We argue that a drawback of Klaim is that it is neither a programming language, nor a process calculus. We then outline the two research directions we have recently pursued. On the one hand we have evolved Klaim to a full-fledged language for highly distributed mobile programming. On the other hand we have distilled the language to a number of simple calculi that we have used to define new semantic theories and equivalences and to test the impact of new operators for network aware programming. [ABSTRACT FROM AUTHOR]

Classes of codes defined by binary relations are considered. It turns out that many classes of codes can be defined by length-increasing transitive binary relations. By introducing a general embedding schema we show that the embedding problem can be solved in a unified way for many classes of codes defined in such a way. Several among these classes of codes can be characterized by means of variants of Parikh vectors. This is very useful in constructing many-word concrete codes, maximal codes in corresponding classes of codes. Also, this allows to establish procedures to generate all maximall codes as well as algorithms to embed a code in a maximal one in some classes of codes. Keywords: Code, binary relation, embedding problem, Parikh vector. [ABSTRACT FROM AUTHOR]

Rewriting logic is a simple computational logic very well suited as a semantic framework within which many different models of computation, systems and languages can be naturally modeled. It is also a flexible logical framework in which many different logical formalisms can be both represented and executed. As the title suggests, this paper does not try to give a comprehensive overview of rewriting logic. Instead, after introducing the basic concepts, it focuses on some recent research directions emphasizing: (i) extensions of the logic to model real-time systems and probabilistic systems; and (ii) some exciting application areas such as: semantics of programming languages, security, and bioinformatics. [ABSTRACT FROM AUTHOR]