Authors
Citation
L. Ilie, ON A CONJECTURE ABOUT SLENDER CONTEXT-FREE LANGUAGES, Theoretical computer science, 132(1-2), 1994, pp. 427-434
Citations number
7
Categorie Soggetti
Computer Sciences","Computer Science Theory & Methods
Journal title
ISSN journal
03043975
Volume
132
Issue
1-2
Year of publication
1994
Pages
427 - 434
Database
ISI
SICI code
0304-3975(1994)132:1-2<427:OACASC>2.0.ZU;2-Z
Abstract
We prove that every slender context-free language is a union of paired
loops, thus confirming a conjecture of Paun and Salomaa to appear. A
series of consequences of this result are inferred, most of them also
left as open problems in recent papers about slender languages.