The Regular Viewpoint on PA-Processes

Denis Lugiez 1 Philippe Schnoebelen
1 PROTHEO - Constraints, automatic deduction and software properties proofs
INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
Abstract : PA is the process algebra allowing non-determinism, sequential and parallel compositions, and recursion. We suggest a view of PA-processes as {\em tree languages}. Our main result is that the set of iterated predecessors of a regular set of PA-processes is a regular tree language, and similarly for iterated successors. Furthermore, the corresponding tree-automata can be built effectively in polynomial-time. This has many immediate applications to verification problems for PA-processes, among which a simple and general model-checking algorithm.
Type de document :
Rapport
[Research Report] RR-3403, INRIA. 1998, pp.27
Liste complète des métadonnées

https://hal.inria.fr/inria-00073287
Contributeur : Rapport de Recherche Inria <>
Soumis le : mercredi 24 mai 2006 - 12:26:23
Dernière modification le : jeudi 11 janvier 2018 - 06:19:58
Document(s) archivé(s) le : dimanche 4 avril 2010 - 20:57:51

Fichiers

Identifiants

  • HAL Id : inria-00073287, version 1

Collections

Citation

Denis Lugiez, Philippe Schnoebelen. The Regular Viewpoint on PA-Processes. [Research Report] RR-3403, INRIA. 1998, pp.27. 〈inria-00073287〉

Partager

Métriques

Consultations de la notice

104

Téléchargements de fichiers

100