HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation

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.
Document type :
Complete list of metadata

Contributor : Rapport de Recherche Inria Connect in order to contact the contributor
Submitted on : Wednesday, May 24, 2006 - 1:04:35 PM
Last modification on : Thursday, February 3, 2022 - 11:18:44 AM
Long-term archiving on: : Sunday, April 4, 2010 - 11:48:19 PM


  • HAL Id : inria-00073502, version 1



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



Record views


Files downloads