期刊
INFORMATION AND COMPUTATION
卷 266, 期 -, 页码 1-18出版社
ACADEMIC PRESS INC ELSEVIER SCIENCE
DOI: 10.1016/j.ic.2018.11.001
关键词
Context-free grammars; Conjunctive grammars; Boolean grammars; Homomorphisms; Hardest language
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.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据