The Computational Complexity of Linear PCGSs
L. Cai
Computing and Informatics, Tome 28 (2012) no. 1, / Harvested from Computing and Informatics
Text on Computing and Informatics
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.
Publié le : 2012-01-26
Classification:  
@article{cai701,
     author = {L. Cai},
     title = {The Computational Complexity of Linear PCGSs},
     journal = {Computing and Informatics},
     volume = {28},
     number = {1},
     year = {2012},
     language = {en},
     url = {http://dml.mathdoc.fr/item/cai701}
}

L. Cai. The Computational Complexity of Linear PCGSs. Computing and Informatics, Tome 28 (2012) no. 1, . http://gdmltest.u-ga.fr/item/cai701/