Paper Info
Title
On the Computational Complexity of Context-Free Parallel Communicating Grammar Systems
Abstract
In this paper we investigate the computational complexity for Parallel Communicating Grammar Systems (PCGSs) whose components are context-free grammars. We show that languages generated by nonreturning context-free PCGSs can be recognized by O(n) space-bounded Turing machines. Also we state a sufficient condition for linear space complexity of returning context-free PCGSs. Based on this complexity characterization we also investigate the generative power of context-free PCGSs with respect to context-sensitive PCGSs and context-sensitive grammars.
Year
DOI
Venue
1997
10.1007/3-540-62844-4_18
New Trends in Formal Languages
Keywords
Field
DocType
computational complexity,parallel communicating grammar systems,context free grammar,linear space,turing machine
Quantum complexity theory,Complexity class,PH,2-EXPTIME,DTIME,Extended Affix Grammar,Computer science,Theoretical computer science,Adaptive grammar,Mildly context-sensitive grammar formalism
Conference
Volume
ISSN
ISBN
1218
0302-9743
3-540-62844-4
Citations 
PageRank 
References 
0
0.34
1
Authors
1
Name
Order
Citations
PageRank
Stefan D. Bruda16212.18