Indian parallel systems. (English) Zbl 0541.68049

Foundations of software technology and theoretical computer science, 2nd Conf., Bangalore/India 1982, 283-289 (1982).
[For the entire collection see Zbl 0527.00034.]
In this paper a special kind of context-independent parallel rewriting is studied, namely Indian parallel systems, called OB systems using a notation known from Lindenmayer systems. The basic relations between language families of different OB systems (monotone, deterministic ones, with and without tables) and between other well-known language families is investigated, as well as the role and effect of terminal symbols. A theorem stating that EOB systems generate only context-free languages if each terminal symbol can derive only itself as a terminal word allows to show that the class EOB is not closed under most of the AFL operations. Finally, it is shown that the family of adult languages of OB systems is exactly the class of context-free languages.


68Q45 Formal languages and automata
68Q42 Grammars and rewriting systems


Zbl 0527.00034