Random Grammars - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Rapport (Rapport De Recherche) Année : 1997

Random Grammars

Résumé

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.

Domaines

Autre [cs.OH]
Fichier principal
Vignette du fichier
RR-3187.pdf (350.34 Ko) Télécharger le fichier

Dates et versions

inria-00073502 , version 1 (24-05-2006)

Identifiants

  • HAL Id : inria-00073502 , version 1

Citer

Vadim A. A. Malyshev. Random Grammars. [Research Report] RR-3187, INRIA. 1997. ⟨inria-00073502⟩
43 Consultations
123 Téléchargements

Partager

Gmail Facebook X LinkedIn More