✦ LIBER ✦

On the separability of sparse context-free languages and of bounded rational relations

✍ Scribed by Christian Choffrut; Flavio D’Alessandro; Stefano Varricchio

Book ID: 108281319
Publisher: Elsevier Science
Year: 2007
Tongue: English
Weight: 228 KB
Volume: 381
Category: Article
ISSN: 0304-3975
DOI: 10.1016/j.tcs.2007.04.003

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

On the structure of the counting functio

On the structure of the counting function of sparse context-free languages

✍ Flavio D’Alessandro; Benedetto Intrigila; Stefano Varricchio 📂 Article 📅 2006 🏛 Elsevier Science 🌐 English ⚖ 222 KB

On the relation between the class of all

On the relation between the class of all context-free languages and the class of deterministic context-free languages

✍ A. Ya. Dikovskii 📂 Article 📅 1969 🏛 Springer US 🌐 English ⚖ 777 KB

On the context-free production complexit

On the context-free production complexity of finite languages

✍ Zsolt Tuza 📂 Article 📅 1987 🏛 Elsevier Science 🌐 English ⚖ 696 KB

The following problem is investigated. Let L be a given finite language, LcL,= {ub: I ~o,bsn, of/~}. Determine the minimal natural number c(L) such that L can be generated by c(L) context-free productions. Among others, max c(L) = O(n'/log n) is proved, and languages satisfying c(L) = IL) are charac

On the parallel recognition of unambiguo

On the parallel recognition of unambiguous context-free languages

✍ Michal Chytil; Maxime Crochemore; Burkhard Monien; Wojciech Rytter 📂 Article 📅 1991 🏛 Elsevier Science 🌐 English ⚖ 716 KB

On the Chomsky and Stanley's homomorphic

On the Chomsky and Stanley's homomorphic characterization of context-free languages

✍ Sadaki Hirose; Masaaki Yoneda 📂 Article 📅 1985 🏛 Elsevier Science 🌐 English ⚖ 172 KB

On the complexity of parallel parsing of

On the complexity of parallel parsing of general context-free languages

✍ Wojciech Rytter 📂 Article 📅 1986 🏛 Elsevier Science 🌐 English ⚖ 409 KB