Browse Prior Art Database

SUBWORDS IN DETERMINISTIC TOL LANGUAGES

IP.com Disclosure Number: IPCOM000128354D
Original Publication Date: 1973-Dec-31
Included in the Prior Art Database: 2005-Sep-15
Document File: 6 page(s) / 20K

Publishing Venue

Software Patent Institute

Related People

A. Ehrenfeucht: AUTHOR [+4]

Abstract

Developmental systems are formal structures which model the way in which certain biological organisms develop. The study of such systems has recently attracted particular atten-tion as a new branch of the theory of formal languages, see for example (11, [41,-[61 and their references. 'In this paper we continue research into TOL systems which were introduced.in [2] and further studies, for example, in (3], [5].

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 39% of the total text.

Page 1 of 6

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

SUBWORDS IN DETERMINISTIC TOL LANGUAGES

By A. Ehrenfeucht G. Rosenberg *** Department of Computer Science University of Colorado,, Boulder, Colorado' Department of Computer Science State University of New York at Buffalo

Report # CU-CS-015-73 March,, 1973

1
1. INTRODUCTION.

Developmental systems are formal structures which model the way in which certain biological organisms develop. The study of such systems has recently attracted particular atten-tion as a new branch of the theory of formal languages, see for example (11, [41,-[61 and their references. 'In this paper we continue research into TOL systems which were introduced.in [2] and further studies, for example, in (3], [5].

A TOL system has th6 following components W A finite set of symbols, E, the alphabet, (ii) A finite collection P of tables, each of which tell us by what strings in E* a symbol may be replaced. A table.mayl in general, contain several productions for each symbol. in every step of a derivation, all symbols in a string must be simultaneously replaced according to the production rules of one arbitrarily chosen table. (iii) A starting string, w, the axiom. The language generated by a given TOL system consists of w and all strings which can be derived from w in a finite number of steps.

A TOL system is called deterministic (abbreviated a DTOL system) if each of its tables is such that for each symbol in the alphabet the table contains exactly one production with the symbol on the left. The-role of a deterministic restriction is one of the important questions, from both the biological and formal points of view, in the theory of developmental systems.

In this paper we prove a result, which we believe is a fundamental one for the characterization of languages generated by DTOL systems (called DTOL languages.) This result says that if L is a DTOL languageover an alphabet containing at.least two letters'then the relative number of subwords of a given length k occurring in the words of L tends to zero as k increases.

The formal definition of a TOL system is given for example. in (31 the terminology and notation of which we shall follow in this paper. In addition to this we shall use the following notation:

1) If x is a word then jxj denotes its length a . nd if A is a set then #A denotes the cArdinality of,
A. The empty word is denoted by A.

2) If 0 is a DTOL system and TO then. a --a T abbreviates "the production a -,--a is in, T11, and for a word x

TW denotes the word y such that x y. T

1 This work supported by N.,S.F. Grant.GJ-660.

University of Colorado Page 1 Dec 31, 1973

Page 2 of 6

SUBWORDS IN DETERMINISTIC TOL LANGUAGES

3) If L is a language and k a natural number, then P (L) k denotes the set of all subwords of length k occurring in the words of L.

2. PRELIMINARY LEMMAS.

Let E be a finite alphabet where #E n 2. and

(Equation Omitted)

a finite non-empty subset of E* such that

(Equation Omitted)...