Tree-systems of morphisms

Citation
J. Dassow et al., Tree-systems of morphisms, ACT INFORM, 38(2), 2001, pp. 131-153
Citations number
10
Categorie Soggetti
Information Tecnology & Communication Systems
Journal title
ACTA INFORMATICA
ISSN journal
00015903 → ACNP
Volume
38
Issue
2
Year of publication
2001
Pages
131 - 153
Database
ISI
SICI code
0001-5903(200111)38:2<131:TOM>2.0.ZU;2-B
Abstract
Starting from the idea of determinism in membrane systems, we introduce a l anguage generating device consisting of morphisms placed in the nodes of a tree. Initial strings are given in the leaves: by iteratively applying the morphisms to them, we produce new strings, which are collected in the root of the tree. Such a device is called a tree-system of morphisms (in short, a T system). We investigate here the power of T systems, both in the extend ed (a terminal alphabet is considered and only strings over it are accepted ) and non-extended case, mainly in comparison with classes of languages in Lindenmayer hierarchy.