1974-01-02
On the size of DOL languages
Publication
Publication
Languages generated by monogenic (i.e. deterministic) context independent Linden-mayer systems (DOL systems) are investigated. Necessary and sufficient conditions are established under which the language generated by a DOL system is finite. Thus, sharp bounds on the cardinality of such a language are obtained. A feasible solution for the membership problem is given. The problems are solved of what is the minimum sized alphabet over which there is a DOL language of cardinality n and, conversely, what is the maximum sized finite DOL language over an alphabet of m letters. This in turn provides us with some number theoretic functions, interesting in their own right, of which several properties, interrelations and asymptotic approximations are derived.
| Additional Metadata | |
|---|---|
| , , , , | |
| doi.org/10.1007/3-540-06867-8_6 | |
| Lecture Notes in Computer Science/Lecture Notes in Artificial Intelligence | |
| Organisation | Centrum Wiskunde & Informatica, Amsterdam (CWI), The Netherlands |
|
Vitányi, P. (1974). On the size of DOL languages. In L Systems.https://doi.org/10.1007/3-540-06867-8_6 |
|
