Random Grammars

Abstract : This is the first part in a series of papers, where we consider new connections between computer science and modern mathematical physics. Here we begin to study a class of "concrete" random processes covering most of well known processes, such as locally interacting processes, random fractals, random walks, queueing networks, random Turing machines, etc. Here we restrict ourselves to linear graphs. We establish existence and uniqueness of the dynamics in the thermodynamic limit and prove that this dynamics is clustering. We get ergodicity and non-recurrence conditions in a small perturbation region. We study invariant measures and large time fractal type behaviour for random context free grammars and languages.
Type de document :
Rapport
[Research Report] RR-3187, INRIA. 1997
Liste complète des métadonnées

https://hal.inria.fr/inria-00073502
Contributeur : Rapport de Recherche Inria <>
Soumis le : mercredi 24 mai 2006 - 13:04:35
Dernière modification le : vendredi 25 mai 2018 - 12:02:05
Document(s) archivé(s) le : dimanche 4 avril 2010 - 23:48:19

Fichiers

Identifiants

  • HAL Id : inria-00073502, version 1

Collections

Citation

Vadim A. Malyshev. Random Grammars. [Research Report] RR-3187, INRIA. 1997. 〈inria-00073502〉

Partager

Métriques

Consultations de la notice

93

Téléchargements de fichiers

117