CCS with Replication in the Chomsky Hierarchy: The Expressive Power of Divergence

Jesus Aranda 1, 2 Cinzia Di Giusto 3, * Mogens Nielsen 4 Frank Valencia 1, *
* Auteur correspondant
1 COMETE - Concurrency, Mobility and Transactions
LIX - Laboratoire d'informatique de l'École polytechnique [Palaiseau], Inria Saclay - Ile de France, X - École polytechnique, CNRS - Centre National de la Recherche Scientifique : UMR7161
2 EISC - Escuela de Ingenieria de Sistemas y Computacion
3 UNIBO - Università di Bologna [Bologna]
4 Aarhus University [Aarhus]
Abstract : A remarkable result in [4] shows that in spite of its being less expressive than CCS w.r.t. weak bisimilarity, CCS! (a CCS variant where infinite behavior is specified by using replication rather than recursion) is Turing powerful. This is done by encoding Random Access Machines (RAM) in CCS!. The encoding is said to be non-faithful because it may move from a state which can lead to termination into a divergent one which do not correspond to any configuration of the encoded RAM. I.e., the encoding is not termination preserving. In this paper we study the existence of faithful encodings into CCS! of models of computability strictly less expressive than Turing Machines. Namely, grammars of Types 1 (Context Sensitive Languages), 2 (Context Free Languages) and 3 (Regular Languages) in the Chomsky Hierarchy. We provide faithful encodings of Type 3 grammars. We show that it is impossible to provide a faithful encoding of Type 2 grammars and that termination-preserving CCS! processes can generate languages which are not Type 2. We finally show that the languages generated by termination-preserving CCS! processes are Type 1 .
keyword : Expressiveness Process calculi CCS
Type de document :
Communication dans un congrès
Zhong Shao. 5th Asian Symposium on Programming Languages and Systems (APLAS'07), Nov 2007, Singapore, Singapore. Springer, 4807, pp.383-398, 2007, Lecture Notes in Computer Science. 〈10.1007/978-3-540-76637-7_26〉
Liste complète des métadonnées

Littérature citée [15 références]  Voir  Masquer  Télécharger
https://hal.inria.fr/inria-00201547
Contributeur : Jesus Aranda <>
Soumis le : mercredi 2 janvier 2008 - 01:31:15
Dernière modification le : jeudi 10 mai 2018 - 02:06:55
Document(s) archivé(s) le : jeudi 27 septembre 2012 - 13:31:03

Fichier

aplas07.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

INRIA | LIX | X-LIX | X | PARISTECH | X-DEP-INFO

Citation

Jesus Aranda, Cinzia Di Giusto, Mogens Nielsen, Frank Valencia. CCS with Replication in the Chomsky Hierarchy: The Expressive Power of Divergence. Zhong Shao. 5th Asian Symposium on Programming Languages and Systems (APLAS'07), Nov 2007, Singapore, Singapore. Springer, 4807, pp.383-398, 2007, Lecture Notes in Computer Science. 〈10.1007/978-3-540-76637-7_26〉. 〈inria-00201547〉

Exporter

BibTeX TEI DC DCterms EndNote

Partager

Métriques

Consultations de la notice

496

Téléchargements de fichiers

115

Contact


archive-ouverte@inria.fr