Journal article
On The Computational Complexity of Marcus Contextual Languages
Abstract
We investigate the computational complexity of the basic type of contextual languages, that is, the ones introduced by Marcus and called subsequently external contextual languages. We prove that the family of languages generated by external contextual grammars with context-free selection contains only polynomial time parsable languages.
Authors
Ilie L
Journal
Fundamenta Informaticae, Vol. 30, No. 2, pp. 161–167
Publisher
SAGE Publications
Publication Date
May 1997
DOI
10.3233/fi-1997-30203
ISSN
0169-2968