✦ LIBER ✦

Cooperation in context-free grammars

✍ Scribed by Jürgen Dassow; Victor Mitrana

Publisher: Elsevier Science
Year: 1997
Tongue: English
Weight: 527 KB
Volume: 180
Category: Article
ISSN: 0304-3975
DOI: 10.1016/s0304-3975(96)00330-1

No coin nor oath required. For personal study only.

✦ Synopsis

A new dynamical measure of the descriptional complexity for context-free grammars and languages, namely the degree of cooperation, is introduced and studied. This measure is connected with respect to both families of languages considered, namely the regular and context-free languages. We prove that the degree of cooperation is computable for regular and unambigous context-free grammars and it is not computable for arbitrary context-free grammars. The computability status of this measure for languages remains to be investigated.

📜 SIMILAR VOLUMES

LR(k)-coupled-context-free grammars

✍ Gisela Pitsch 📂 Article 📅 1995 🏛 Elsevier Science 🌐 English ⚖ 875 KB

Context-free grammars and nonnegative ma

Context-free grammars and nonnegative matrices

✍ David Sankoff 📂 Article 📅 1972 🏛 Elsevier Science 🌐 English ⚖ 269 KB

Consistency of stochastic context-free g

Consistency of stochastic context-free grammars

✍ Roland Gecse; Attila Kovács 📂 Article 📅 2010 🏛 Elsevier Science 🌐 English ⚖ 405 KB

Completeness of context-free grammar for

Completeness of context-free grammar forms

✍ H.A. Maurer; A. Salomaa; D. Wood 📂 Article 📅 1981 🏛 Elsevier Science 🌐 English ⚖ 600 KB

Statistical estimation of stochastic con

Statistical estimation of stochastic context-free grammars

✍ Francisco Casacuberta 📂 Article 📅 1995 🏛 Elsevier Science 🌐 English ⚖ 636 KB

Learning context-free grammars using tab

Learning context-free grammars using tabular representations

✍ Yasubumi Sakakibara 📂 Article 📅 2005 🏛 Elsevier Science 🌐 English ⚖ 301 KB

We present a novel algorithm using new hypothesis representations for learning context-free grammars from a finite set of positive and negative examples. We propose an efficient hypothesis representation method which consists of a table-like data structure similar to the parse table used in efficien