Standard

Unambiguous Boolean grammars. / Okhotin, Alexander.

In: Information and Computation, Vol. 206, No. 9-10, 01.09.2008, p. 1234-1247.

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

Harvard

Okhotin, A 2008, 'Unambiguous Boolean grammars', Information and Computation, vol. 206, no. 9-10, pp. 1234-1247. https://doi.org/10.1016/j.ic.2008.03.023

APA

Okhotin, A. (2008). Unambiguous Boolean grammars. Information and Computation, 206(9-10), 1234-1247. https://doi.org/10.1016/j.ic.2008.03.023

Vancouver

Okhotin A. Unambiguous Boolean grammars. Information and Computation. 2008 Sep 1;206(9-10):1234-1247. https://doi.org/10.1016/j.ic.2008.03.023

Author

Okhotin, Alexander. / Unambiguous Boolean grammars. In: Information and Computation. 2008 ; Vol. 206, No. 9-10. pp. 1234-1247.

BibTeX

@article{89961a4bd9e3426ca1cb2ebf144d8f32,
title = "Unambiguous Boolean grammars",
abstract = "Boolean grammars are an extension of context-free grammars, in which conjunction and negation may be explicitly used in the rules. In this paper, the notion of ambiguity in Boolean grammars is defined. It is shown that the known transformation of a Boolean grammar to the binary normal form preserves unambiguity, and that every unambiguous Boolean language can be parsed in time O(n2). Linear conjunctive languages are shown to be unambiguous, while the existence of languages inherently ambiguous with respect to Boolean grammars is left open.",
keywords = "Ambiguity, Boolean grammars, Conjunctive grammars, Parsing",
author = "Alexander Okhotin",
year = "2008",
month = sep,
day = "1",
doi = "10.1016/j.ic.2008.03.023",
language = "English",
volume = "206",
pages = "1234--1247",
journal = "Information and Computation",
issn = "0890-5401",
publisher = "Elsevier",
number = "9-10",

}

RIS

TY - JOUR

T1 - Unambiguous Boolean grammars

AU - Okhotin, Alexander

PY - 2008/9/1

Y1 - 2008/9/1

N2 - Boolean grammars are an extension of context-free grammars, in which conjunction and negation may be explicitly used in the rules. In this paper, the notion of ambiguity in Boolean grammars is defined. It is shown that the known transformation of a Boolean grammar to the binary normal form preserves unambiguity, and that every unambiguous Boolean language can be parsed in time O(n2). Linear conjunctive languages are shown to be unambiguous, while the existence of languages inherently ambiguous with respect to Boolean grammars is left open.

AB - Boolean grammars are an extension of context-free grammars, in which conjunction and negation may be explicitly used in the rules. In this paper, the notion of ambiguity in Boolean grammars is defined. It is shown that the known transformation of a Boolean grammar to the binary normal form preserves unambiguity, and that every unambiguous Boolean language can be parsed in time O(n2). Linear conjunctive languages are shown to be unambiguous, while the existence of languages inherently ambiguous with respect to Boolean grammars is left open.

KW - Ambiguity

KW - Boolean grammars

KW - Conjunctive grammars

KW - Parsing

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

U2 - 10.1016/j.ic.2008.03.023

DO - 10.1016/j.ic.2008.03.023

M3 - Article

AN - SCOPUS:50149122569

VL - 206

SP - 1234

EP - 1247

JO - Information and Computation

JF - Information and Computation

SN - 0890-5401

IS - 9-10

ER -

ID: 41141675