Cai, Liming 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]. Cited in 3 Documents MSC: 68Q42 Grammars and rewriting systems 68Q25 Analysis of algorithms and problem complexity 68Q45 Formal languages and automata PDFBibTeX XMLCite \textit{L. Cai}, in: 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. 209--219 (1996; Zbl 1096.68640)