Affiliations: Fakultät für Informatik, Otto-von-Guericke-Universität Magdeburg, Postfach 4120, D-39016 Magdeburg, Germany. email: bordihn@iws.cs.uni-magdeburg.de | Wilhelm-Schickard-Institut für Informatik, Universität Tübingen, Sand 13, D-72076 Tübingen, Germany. email: fernau@informatik.uni-tuebingen.de | Département d'I.R.O., Université de Montréal, C.P. 6128, succ. Centre-Ville, Montréal (Québec), H3C3J7 Canada. email: holzer@iro.umontreal.ca
Note: [] Address for correspondence: Fakultät für Informatik, Otto-von-Guericke-Universität Magdeburg, Postfach 4120, D-39016 Magdeburg, Germany
Note: [] Partially supported by Deutsche Forschungsgemeinschaft grant DFG La 618/3-1/2. Address for correspondence: Wilhelm-Schickard-Institut für Informatik, Universität Tübingen, Sand 13, D-72076 Tübingen, Germany
Note: [] Address for correspondence: Fakultät für Informatik, Otto-von-Guericke-Universität Magdeburg, Postfach 4120, D-39016 Magdeburg, Germany Part of the work done while the author worked at Wilhelm-Schickard Institut für Informatik, Universität Tübingen, Sand 13, D-72076 Tübingen, Germany. Address for correspondence: Département d'I.R.O., Université de Montréal, C.P. 6128, succ. Centre-Ville, Montréal (Québec), H3C3J7 Canada
Abstract: We consider pure Lindenmayer systems, more precisely, 0L and T0L systems as language accepting devices and compare them to their generating counterparts. Accepting Lindenmayer systems can be seen as systems of inverse finite substitutions which are iteratively applied over a free monoid. Hereby, we investigate the deterministic case in detail, comparing several different concepts of determinism in such systems. Whereas in the usual generating case these concepts trivially are equally powerful, the structure of families of accepted languages is much richer. In passing, the case of unary Lindenmayer systems is investigated.
Keywords: accepting systems, determinism in Lindenmayer systems
