Languages defined by Indian parallel systems. (English) Zbl 0586.68065

The book of L, dedic. A. Lindenmayer Occas. 60th Birthday, 233-243 (1986).
[For the entire collection see Zbl 0575.00023.]
A special kind of parallel systems, namely Indian parallel systems, is studied. In the context-independent case the application of homomorphisms on sequential form languages is found to be more powerful than the use of a terminal subalphabet, both for systems with one or finitely many tables. Especially, the language family obtained by systems with one table using a terminal subalphabet is (nearly) an Anti-AFL. The effect of having at most one or finitely many axioms, erasing in the productions, and of applying codings, weak codings, non-erasing or arbitrary homomorphisms is considered, and a (not yet) complete hierarchy is presented, including also the relation to the context-free and ETOL- languages. Some results in the context-dependent case are given too.


68Q45 Formal languages and automata


Zbl 0575.00023