e{open}-productions in context-free grammars

Goldschlager L.M. (1981) e{open}-productions in context-free grammars. Acta Informatica, 16 3: 303-308. doi:10.1007/BF00289308


Author Goldschlager L.M.
Title e{open}-productions in context-free grammars
Journal name Acta Informatica   Check publisher's open access policy
ISSN 0001-5903
Publication date 1981-01-01
Sub-type Article (original research)
DOI 10.1007/BF00289308
Volume 16
Issue 3
Start page 303
End page 308
Total pages 6
Publisher Springer-Verlag
Subject 1710 Information Systems
Abstract The effect of e{open}-productions on the space complexity of various context-free language problems is investigated. It is shown that the removal of e{open}-productions from a context-free grammar can probably not be achieved with small storage space. This explains the apparent discrepancy between two different results in the literature on the membership problem. By way of contrast, it is shown that the space complexity of the emptiness and the finiteness problems are independent of the presence of e{open}-productions.
Q-Index Code C1
Q-Index Status Provisional Code
Institutional Status Unknown

Document type: Journal Article
Sub-type: Article (original research)
Collection: Scopus Import
 
Versions
Version Filter Type
Citation counts: Scopus Citation Count Cited 8 times in Scopus Article | Citations
Google Scholar Search Google Scholar
Created: Tue, 05 Jul 2016, 14:39:25 EST by System User