The Computational Complexity of Linear PCGSs

Abstract

The computational complexity is investigated for Parallel Communicating Grammar Systems (PCGSs) whose components are linear grammars. It is shown that language generated by linear PCGSs can be recognized by O(log n) space/bounded Turing machines. Based on the complexity characterization, the generative power of linear PCGSs is analyzed with respect to context-free and context-sensitive grammars.