𝔖 Bobbio Scriptorium
✦   LIBER   ✦

A Polynomial-Time Parsing Algorithm forK-Depth Languages

✍ Scribed by Alessandra Cherubini; Pierluigi San Pietro

Publisher
Elsevier Science
Year
1996
Tongue
English
Weight
736 KB
Volume
52
Category
Article
ISSN
0022-0000

No coin nor oath required. For personal study only.

✦ Synopsis

K-depth grammars extend context-free grammars allowing k 1 rewriting points for a single non-terminal at every step of a derivation. The family of languages generated by k-depth grammars is a proper extension of the family of context-free languages, while retaining many context-free properties, such as closure properties, a version of Chomsky Schu tzenberger theorem, the existence of an accepting device (the multi-pushdown automaton). Here a polynomial-time parsing algorithm for k-depth languages is defined, and its correctness is proved.

πŸ“œ SIMILAR VOLUMES

A polynomial time circle packing algorit
A polynomial time circle packing algorithm
✍ Bojan Mohar πŸ“‚ Article πŸ“… 1993 πŸ› Elsevier Science 🌐 English βš– 428 KB

Mohar, B., A polynomial time circle packing algorithm, Discrete Mathematics 117 (1993) 2577263. The Andreev-Koebe-Thurston circle packing theorem is generalized and improved in two ways. Simultaneous circle packing representations of the map and its dual map are obtained such that any two edges dua

A polynomial time algorithm recognizing
A polynomial time algorithm recognizing link trees
✍ Peter Bugata; Attila Nagy; Roman VΓ‘vra πŸ“‚ Article πŸ“… 1995 πŸ› John Wiley and Sons 🌐 English βš– 672 KB

The link of a vertex u of a graph G is the subgraph induced by all vertices adjacent to u . If all the links of G are isomorphic to a finite graph L, then G is called a realization of L, and L is called a link graph. At the Smolenice symposium of 1963, Zykov posed the problem of recognizing iink gr

A Polynomial-time Algorithm for the Bist
A Polynomial-time Algorithm for the Bistable Roommates Problem
✍ Jay Sethuraman; Chung-Piaw Teo πŸ“‚ Article πŸ“… 2001 πŸ› Elsevier Science 🌐 English βš– 127 KB

In a recent paper, Weems introduced the bistable matching problem, and asked if a polynomial-time algorithm exists to decide the feasibility of the bistable roommates problem. We resolve this question in the affirmative using linear programming. In addition, we show that several (old and new) result

A Polynomial Time Algorithm for Diophant
A Polynomial Time Algorithm for Diophantine Equations in One Variable
✍ F CUCKER; P KOIRAN; S SMALE πŸ“‚ Article πŸ“… 1999 πŸ› Elsevier Science 🌐 English βš– 195 KB

We exhibit an algorithm computing, for a polynomial f ∈ Z [t], the set of its integer roots. The running time of the algorithm is polynomial in the size of the sparse encoding of f .