Standard

On the number of nonterminal symbols in unambiguous conjunctive grammars. / Jez, Artur; Okhotin, Alexander.

в: Fundamenta Informaticae, Том 162, № 1, 01.01.2018, стр. 43-72.

Результаты исследований: Научные публикации в периодических изданиях › статья › Рецензирование

Harvard

Jez, A & Okhotin, A 2018, 'On the number of nonterminal symbols in unambiguous conjunctive grammars', Fundamenta Informaticae, Том. 162, № 1, стр. 43-72. https://doi.org/10.3233/FI-2018-1713

APA

Jez, A., & Okhotin, A. (2018). On the number of nonterminal symbols in unambiguous conjunctive grammars. Fundamenta Informaticae, 162(1), 43-72. https://doi.org/10.3233/FI-2018-1713

Vancouver

Jez A, Okhotin A. On the number of nonterminal symbols in unambiguous conjunctive grammars. Fundamenta Informaticae. 2018 Янв. 1;162(1):43-72. https://doi.org/10.3233/FI-2018-1713

Author

Jez, Artur ; Okhotin, Alexander. / On the number of nonterminal symbols in unambiguous conjunctive grammars. в: Fundamenta Informaticae. 2018 ; Том 162, № 1. стр. 43-72.

BibTeX

@article{3bdf7efa8f45427b881782a222d178b5,
title = "On the number of nonterminal symbols in unambiguous conjunctive grammars",
abstract = "Unambiguous conjunctive grammars with 1 nonterminal symbol are shown to be strictly weaker than the grammars with 2 nonterminal symbols, which are in turn strictly weaker that the grammars with 3 or more nonterminal symbols. This hierarchy is established by considering grammars over a one-symbol alphabet, for which it is shown that 1-nonterminal grammars describe only regular languages, 2-nonterminal grammars describe some non-regular languages, but all of them are in a certain sense sparse, whereas 3-nonterminal grammars may describe some non-regular languages of non-zero density. It is also proved that one can test a 2-nonterminal grammar for equivalence with a regular language, whereas the equivalence between a pair of 2-nonterminal grammars is undecidable.",
keywords = "Ambiguity, Conjunctive grammars, Descriptional complexity, Language equations, Unary languages",
author = "Artur Jez and Alexander Okhotin",
year = "2018",
month = jan,
day = "1",
doi = "10.3233/FI-2018-1713",
language = "English",
volume = "162",
pages = "43--72",
journal = "Fundamenta Informaticae",
issn = "0169-2968",
publisher = "IOS Press",
number = "1",

}

RIS

TY - JOUR

T1 - On the number of nonterminal symbols in unambiguous conjunctive grammars

AU - Jez, Artur

AU - Okhotin, Alexander

PY - 2018/1/1

Y1 - 2018/1/1

N2 - Unambiguous conjunctive grammars with 1 nonterminal symbol are shown to be strictly weaker than the grammars with 2 nonterminal symbols, which are in turn strictly weaker that the grammars with 3 or more nonterminal symbols. This hierarchy is established by considering grammars over a one-symbol alphabet, for which it is shown that 1-nonterminal grammars describe only regular languages, 2-nonterminal grammars describe some non-regular languages, but all of them are in a certain sense sparse, whereas 3-nonterminal grammars may describe some non-regular languages of non-zero density. It is also proved that one can test a 2-nonterminal grammar for equivalence with a regular language, whereas the equivalence between a pair of 2-nonterminal grammars is undecidable.

AB - Unambiguous conjunctive grammars with 1 nonterminal symbol are shown to be strictly weaker than the grammars with 2 nonterminal symbols, which are in turn strictly weaker that the grammars with 3 or more nonterminal symbols. This hierarchy is established by considering grammars over a one-symbol alphabet, for which it is shown that 1-nonterminal grammars describe only regular languages, 2-nonterminal grammars describe some non-regular languages, but all of them are in a certain sense sparse, whereas 3-nonterminal grammars may describe some non-regular languages of non-zero density. It is also proved that one can test a 2-nonterminal grammar for equivalence with a regular language, whereas the equivalence between a pair of 2-nonterminal grammars is undecidable.

KW - Ambiguity

KW - Conjunctive grammars

KW - Descriptional complexity

KW - Language equations

KW - Unary languages

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

UR - http://www.mendeley.com/research/number-nonterminal-symbols-unambiguous-conjunctive-grammars

U2 - 10.3233/FI-2018-1713

DO - 10.3233/FI-2018-1713

M3 - Article

AN - SCOPUS:85051991792

VL - 162

SP - 43

EP - 72

JO - Fundamenta Informaticae

JF - Fundamenta Informaticae

SN - 0169-2968

IS - 1

ER -

ID: 33857265