Relational specifications
Sémantique des processus communicants
Sémantique logique et dénotationnelle des interpréteurs PROLOG
Some geometric perspectives in concurrency theory.
Some issues in using formal methods for the development of reactive systems.
Some key research problems in automated theorem proving for hardware and software verification.
This paper sketches the state of the art in the application of mechanical theorem provers to the verification of commercial computer hardware and software. While the paper focuses on the theorem proving system ACL2, developed by the two authors, it references much related work in formal methods. The paper is intended to satisfy the curiosity of readers interested in logic and artificial intelligence as to the role of mechanized theorem proving in hardware and software design today. In addition,...
Systèmes de déduction pour les arbres et les schémas de programmes (I)
Systèmes de déduction pour les arbres et les schémas de programme (II)
Taclets: a new paradigm for constructing interactive theorem provers.
Frameworks for interactive theorem proving give the user explicit control over the construction of proofs based on meta languages that contain dedicated control structures for describing proof construction. Such languages are not easy to master and thus contribute to the already long list of skills required by prospective users of interactive theorem provers. Most users, however, only need a convenient formalism that allows to introduce new rules with minimal overhead. On the the other hand, rules...
The alternation hierarchy for the theory of -lattices.
The Formalization of Decision-Free Petri Net
In this article we formalize the definition of Decision-Free Petri Net (DFPN) presented in [19]. Then we formalize the concept of directed path and directed circuit nets in Petri nets to prove properties of DFPN. We also present the definition of firing transitions and transition sequences with natural numbers marking that always check whether transition is enabled or not and after firing it only removes the available tokens (i.e., it does not remove from zero number of tokens). At the end of this...
Thread algebra for noninterference
Thread algebra is a semantics for recent object-oriented programming languages [J.A. Bergstra and M.E. Loots, J. Logic Algebr. Program. 51 (2002) 125–156; J.A. Bergstra and C.A. Middelburg, Formal Aspects Comput. (2007)] such as C# and Java. This paper shows that thread algebra provides a process-algebraic framework for reasoning about and classifying various standard notions of noninterference, an important property in secure information flow. We will take the noninterference property given by...
Thread algebra for noninterference
Thread algebra is a semantics for recent object-oriented programming languages [J.A. Bergstra and M.E. Loots, J. Logic Algebr. Program.51 (2002) 125–156; J.A. Bergstra and C.A. Middelburg, Formal Aspects Comput. (2007)] such as C# and Java. This paper shows that thread algebra provides a process-algebraic framework for reasoning about and classifying various standard notions of noninterference, an important property in secure information flow. We will take the noninterference property given...
Three notes on the complexity of model checking fixpoint logic with chop
This paper analyses the complexity of model checking fixpoint logic with Chop – an extension of the modal μ-calculus with a sequential composition operator. It uses two known game-based characterisations to derive the following results: the combined model checking complexity as well as the data complexity of FLC are EXPTIME-complete. This is already the case for its alternation-free fragment. The expression complexity of FLC is trivially P-hard and limited from above by the complexity of solving...
Una teoria algebrica per i «guarded commands» di Dijkstra
Une charpente de semi-unification
Une modification de la méthode GRG
Vers une formalisation de l'analyse sémantique de matches en sports collectifs. Application au rugby à XV
Cet article met l'accent sur l'originalité de la démarche adoptée. Dans le domaine de l'étude des sports collectifs, avec comme exemple de référence le rugby à XV, on se place du point de vue formel en utilisant des outils issus de l'informatique théorique. Les techniques de spécification mises en oeuvre sont les automates qui proviennent de la théorie des graphes, et la notation classique BNF, combinée aux Expressions Régulières, vue comme un langage de spécification formelle. L'un des intérêts...
Visual representation of formal software specification.
Z specification of object oriented constraint programs.
Object oriented constraint programs (OOCPs) emerge as a leading evolution of constraint programming and artificial intelligence, first applied to a range of industrial applications called configuration problems. The rich variety of technical approaches to solving configuration problems (CLP(FD), CC(FD), DCSP, Terminological systems, constraint programs with set variables, . . . ) is a source of difficulty. No universally accepted formal language exists for communicating about OOCPs, which makes...