The computational complexity of PCGS with regular components. (English) Zbl 1096.68640

Dassow, Jürgen (ed.) et al., Developments in language theory. II. At the crossroads of mathematics, computer science and biology. Papers from the conference held in Magdeburg, Germany, July 17–21, 1995. Singapore: World Scientific (ISBN 981-02-2682-9). 209-219 (1996).
Summary: The computational complexity of languages generated by parallel communicating grammar systems (PCGs) with regular components is investigated. It is shown that the class of languages generated by PCGs with regular components can be recognized by nondeterministic \(O(\log n)\)-space Turing machines.
For the entire collection see [Zbl 0919.00068].


68Q42 Grammars and rewriting systems
68Q25 Analysis of algorithms and problem complexity
68Q45 Formal languages and automata