Journal
INFORMATION AND COMPUTATION
Volume 266, Issue -, Pages 1-18Publisher
ACADEMIC PRESS INC ELSEVIER SCIENCE
DOI: 10.1016/j.ic.2018.11.001
Keywords
Context-free grammars; Conjunctive grammars; Boolean grammars; Homomorphisms; Hardest language
Ask authors/readers for more resources
A famous theorem by Greibach (The hardest context-free language, SIAM J. Comp., 1973) states that there exists such a context-free language L-0, that every context-free language over any alphabet is reducible to L-0 by a homomorphic reduction-in other words, is representable as its inverse homomorphic image h(-1)(L-0), for a suitable homomorphism h. This paper establishes similar characterizations for conjunctive grammars, that is, for grammars extended with a conjunction operator, as well as for Boolean grammars, which are further equipped with a negation operator. At the same time, it is shown that no such characterization is possible for several subclasses of linear grammars. (C) 2018 Elsevier Inc. All rights reserved.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available