Critical S0L systems

A.I. Petrov

2002, v.8, Issue 3, 509-526

ABSTRACT

L systems were first introduced by Aristid Lindenmayer as models in developmental biology in the late 1960s. One can find surveys on L systems in journals in biology, molecular genetics, semiotics, artificial intelligence, theory of formal languages. A stochastic version of the 0L systems was introduced in [P. Eichhorst and W.J. Savitch, Growth functions of stochastic Lindenmayer systems. Information and Control, 1980, v.45, 217-228] and [T. Yokomori, Stochastic characterizations of EOL languages, Information and Control, 1980, v.45, 26-33] but statistical physics point of view (thermodynamic limit, cluster expansions technique, etc.) started only recently, see [V.A. Malyshev, Random grammars, Russian Math. Surveys, 1998, v.53, N2, 107-134]. In this paper we undertake more detailed study of the long time behaviour of the critical S0L systems. The supercritical case was considered in [F.I. Karpelevich, V.A. Malyshev, A.I. Petrov, S.A. Pirogov, A.N. Rybko, Context free evolution of words, Rapport de Recherche INRIA, 2002, No. 4413 and [A.I. Petrov, Context free random grammars: supercritical case with nonzero extinction probability. To appear in Theory Probab. and Appl., 2002]. This paper can be read independently of these two papers.

Keywords: random grammars,0L systems,context free,branching process,critical area,thermodynamic limit

COMMENTS

Please log in or register to leave a comment