Standard

Hardest languages for conjunctive and Boolean grammars. / Okhotin, Alexander.

In: Information and Computation, Vol. 266, 01.06.2019, p. 1-18.

Research output: Contribution to journal › Article › peer-review

Harvard

Okhotin, A 2019, 'Hardest languages for conjunctive and Boolean grammars', Information and Computation, vol. 266, pp. 1-18. https://doi.org/10.1016/j.ic.2018.11.001

APA

Okhotin, A. (2019). Hardest languages for conjunctive and Boolean grammars. Information and Computation, 266, 1-18. https://doi.org/10.1016/j.ic.2018.11.001

Vancouver

Okhotin A. Hardest languages for conjunctive and Boolean grammars. Information and Computation. 2019 Jun 1;266:1-18. https://doi.org/10.1016/j.ic.2018.11.001

Author

Okhotin, Alexander. / Hardest languages for conjunctive and Boolean grammars. In: Information and Computation. 2019 ; Vol. 266. pp. 1-18.

BibTeX

@article{993f15d56e694e8880ca5d5295dd9cab,
title = "Hardest languages for conjunctive and Boolean grammars",
abstract = " 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. ",
keywords = "Boolean grammars, Conjunctive grammars, Context-free grammars, Hardest language, Homomorphisms, CYLINDER, CONTEXT",
author = "Alexander Okhotin",
year = "2019",
month = jun,
day = "1",
doi = "10.1016/j.ic.2018.11.001",
language = "English",
volume = "266",
pages = "1--18",
journal = "Information and Computation",
issn = "0890-5401",
publisher = "Elsevier",

}

RIS

TY - JOUR

T1 - Hardest languages for conjunctive and Boolean grammars

AU - Okhotin, Alexander

PY - 2019/6/1

Y1 - 2019/6/1

N2 - 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.

AB - 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.

KW - Boolean grammars

KW - Conjunctive grammars

KW - Context-free grammars

KW - Hardest language

KW - Homomorphisms

KW - CYLINDER

KW - CONTEXT

UR - http://www.scopus.com/inward/record.url?scp=85059190199&partnerID=8YFLogxK

U2 - 10.1016/j.ic.2018.11.001

DO - 10.1016/j.ic.2018.11.001

M3 - Article

AN - SCOPUS:85059190199

VL - 266

SP - 1

EP - 18

JO - Information and Computation

JF - Information and Computation

SN - 0890-5401

ER -

ID: 41478644