Standard

Non-closure under complementation for unambiguous linear grammars. / Мартынова, Ольга Максимовна; Охотин, Александр Сергеевич.

In: Information and Computation, Vol. 292, 105031, 01.06.2023.

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

Harvard

Мартынова, ОМ & Охотин, АС 2023, 'Non-closure under complementation for unambiguous linear grammars', Information and Computation, vol. 292, 105031. https://doi.org/10.1016/j.ic.2023.105031

APA

Мартынова, О. М., & Охотин, А. С. (2023). Non-closure under complementation for unambiguous linear grammars. Information and Computation, 292, [105031]. https://doi.org/10.1016/j.ic.2023.105031

Vancouver

Мартынова ОМ, Охотин АС. Non-closure under complementation for unambiguous linear grammars. Information and Computation. 2023 Jun 1;292. 105031. https://doi.org/10.1016/j.ic.2023.105031

Author

Мартынова, Ольга Максимовна ; Охотин, Александр Сергеевич. / Non-closure under complementation for unambiguous linear grammars. In: Information and Computation. 2023 ; Vol. 292.

BibTeX

@article{9d4dc820a7d24be9ac2f0f4920e6b116,
title = "Non-closure under complementation for unambiguous linear grammars",
abstract = "The paper demonstrates the non-closure of the family of unambiguous linear languages (that is, those defined by unambiguous linear context-free grammars) under complementation. To be precise, a particular unambiguous linear grammar is presented, and it is proved that the complement of this language is not defined by any context-free grammar. This also constitutes an alternative proof for the result of Hibbard and Ullian (“The independence of inherent ambiguity from complementedness among context-free languages”, JACM, 1966) on the non-closure of the unambiguous languages under complementation.",
keywords = "Closure properties, Complementation, Context-free grammars, Linear grammars, Unambiguous grammars",
author = "Мартынова, {Ольга Максимовна} and Охотин, {Александр Сергеевич}",
year = "2023",
month = jun,
day = "1",
doi = "10.1016/j.ic.2023.105031",
language = "English",
volume = "292",
journal = "Information and Computation",
issn = "0890-5401",
publisher = "Elsevier",

}

RIS

TY - JOUR

T1 - Non-closure under complementation for unambiguous linear grammars

AU - Мартынова, Ольга Максимовна

AU - Охотин, Александр Сергеевич

PY - 2023/6/1

Y1 - 2023/6/1

N2 - The paper demonstrates the non-closure of the family of unambiguous linear languages (that is, those defined by unambiguous linear context-free grammars) under complementation. To be precise, a particular unambiguous linear grammar is presented, and it is proved that the complement of this language is not defined by any context-free grammar. This also constitutes an alternative proof for the result of Hibbard and Ullian (“The independence of inherent ambiguity from complementedness among context-free languages”, JACM, 1966) on the non-closure of the unambiguous languages under complementation.

AB - The paper demonstrates the non-closure of the family of unambiguous linear languages (that is, those defined by unambiguous linear context-free grammars) under complementation. To be precise, a particular unambiguous linear grammar is presented, and it is proved that the complement of this language is not defined by any context-free grammar. This also constitutes an alternative proof for the result of Hibbard and Ullian (“The independence of inherent ambiguity from complementedness among context-free languages”, JACM, 1966) on the non-closure of the unambiguous languages under complementation.

KW - Closure properties

KW - Complementation

KW - Context-free grammars

KW - Linear grammars

KW - Unambiguous grammars

UR - https://www.mendeley.com/catalogue/01050a0e-0f3f-37e1-bb8a-19ca5d4ee30a/

U2 - 10.1016/j.ic.2023.105031

DO - 10.1016/j.ic.2023.105031

M3 - Article

VL - 292

JO - Information and Computation

JF - Information and Computation

SN - 0890-5401

M1 - 105031

ER -

ID: 108695910