Factorizable language: from dynamics to bacterial complete genomes

Symbolic sequences generated by symbolic dynamics of a dynamical system bel ong to a special class of language in which any admissible word is factoris able as well as prolongable. From a complete genome sequence of an organism , one may also define a factorizable language. A factorizable language enjo ys the nice property that it is entirely determined by the set of minimal f obidden words or distinct excluded blocks (DEBs). We use this property to c alculate the fractal dimension of patterns related to a visualisation schem e of under-represented strings in bacterial complete genomes within the lim it of infinitely long strings. The same problem may be solved by using a pu rely combinatorial approach. The methods described in this paper may be app lied to other regular fractals with self-similar and self-overlapping struc ture. (C) 2000 Elsevier Science B.V. All rights reserved.