✦ LIBER ✦

A recognition and parsing algorithm for arbitrary conjunctive grammars

✍ Scribed by Alexander Okhotin

Publisher: Elsevier Science
Year: 2003
Tongue: English
Weight: 425 KB
Volume: 302
Category: Article
ISSN: 0304-3975
DOI: 10.1016/s0304-3975(02)00853-8

No coin nor oath required. For personal study only.

✦ Synopsis

Conjunctive grammars are basically context-free grammars with an explicit set intersection operation added to the formalism of rules. This paper presents a cubic-time recognition and parsing algorithm for this family of grammars, which is applicable to an arbitrary conjunctive grammar without any initial transformations.

The algorithm is in fact an extension of the context-free recognition and parsing algorithm due to Graham, Harrison and Ruzzo, and it retains the cubic time complexity of its prototype. It is shown that for the case of linear conjunctive grammars this algorithm can be modiÿed to work in quadratic time and use linear space.

The given algorithm is then applied to solve the membership problem for conjunctive grammars in polynomial time, and subsequently to prove the problem's P-completeness, as well as P-completeness of the membership problem for linear conjunctive grammars.

📜 SIMILAR VOLUMES

SLR(1) and LALR(1) parsing for unrestric

SLR(1) and LALR(1) parsing for unrestricted grammars

✍ Lawrence A. Harris 📂 Article 📅 1987 🏛 Springer-Verlag 🌐 English ⚖ 930 KB

A Linear Parsing Algorithm For Parenthes

A Linear Parsing Algorithm For Parenthesis Terms

✍ Walter Felscher 📂 Article 📅 1989 🏛 John Wiley and Sons 🌐 English ⚖ 273 KB

A recognition algorithm for the total gr

A recognition algorithm for the total graphs

✍ F. Gavril 📂 Article 📅 1978 🏛 John Wiley and Sons 🌐 English ⚖ 581 KB

## Abstract A graph H is called total if there exists a graph G such that there is a one‐to‐one correspondence between the vertices of H and the vertices and edges of G such that two vertices of H are adjacent iff the corresponding elements of G are adjacent or incident. In this paper we present a

A fast and elementary algorithm for digi

A fast and elementary algorithm for digital plane recognition

✍ Y. Gérard 📂 Article 📅 2003 🏛 Elsevier Science 🌐 English ⚖ 126 KB

A digital naive plane is a subset of points (x, y, z) ∈ Z 3 verifying a double inequality h ≤ ax + by + cz < h + max{|a|, |b|, |c|} where (a, b, c) ∈ R/ {(0,0,0)} and h ∈ R. Given a finite subset of Z 3 , a problem is to determine whether or not there exists a digital naive plane containing it. This

A simple learning decision algorithm for

A simple learning decision algorithm for character recognition and pattern classification

✍ Gerard Gaillat 📂 Article 📅 1978 🏛 Elsevier Science 🌐 English ⚖ 429 KB

A fully dynamic algorithm for modular de

A fully dynamic algorithm for modular decomposition and recognition of cographs

✍ Ron Shamir; Roded Sharan 📂 Article 📅 2004 🏛 Elsevier Science 🌐 English ⚖ 236 KB

The problem of dynamically recognizing a graph property calls for e ciently deciding if an input graph satisÿes the property under repeated modiÿcations to its set of vertices and edges. The input to the problem consists of a series of modiÿcations to be performed on the graph. The objective is to m