Non-générateurs algébriques et substitution. (French) Zbl 0569.68060

We prove the following: given a rational cone \({\mathcal L}\) whose substitution closure is the largest sub-full AFL of the family of context-free languages, then \({\mathcal L}\) was already this subfamily.


68Q45 Formal languages and automata
Full Text: EuDML


[1] 1. J.-M. AUTEBERT, J. BEAUQUIER, L. BOASSON, M. NIVAT, Quelques problèmes ouverts en théorie des langages algébriques, R.A.I.R.O. Informatique théorique, vol. 13, 1979, p. 363-379. Zbl0434.68056 MR556958 · Zbl 0434.68056
[2] 2. J. BERSTEL, Transductions and Context-Free Languages, Teubner Verlag, 1979. Zbl0424.68040 MR549481 · Zbl 0424.68040
[3] 3. L. BOASSON, The Inclusion of the Substitution Closure of Linear and One-Counter Languages in the Largest Sub-Full AFL of the Family of CFL’s is Proper, Information Proc. Letter, vol. 2, 1973, p. 135-140. Zbl0329.68067 MR345452 · Zbl 0329.68067
[4] 4. S. GREIBACH, Chains of Full AFL’S, Math. System Theory, vol. 4, 1970, p. 231-242. Zbl0203.30102 MR329324 · Zbl 0203.30102
[5] 5. M. LATTEUX, A propos du lemme de substitution, Theoretical Comp. Science, vol.14, 1981, p. 119-123. Zbl0454.68086 MR609517 · Zbl 0454.68086
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.