×

On languages satisfying ”interchange lemma”. (English) Zbl 0770.68083

Summary: The paper deals with the closure properties of the family of languages satisfying the “interchange lemma” conditions and with a short comparison between these conditions and other iteration conditions on formal languages.

MSC:

68Q45 Formal languages and automata
PDFBibTeX XMLCite
Full Text: DOI EuDML

References:

[1] 1. J. M. AUTEBERT and L. BOASSON, Generators of Cones and Cylinders, Formal Languages Theory: Perspectives and Open Problems, R. V. BOOK Ed., Acad. Press, 1980, pp. 49-88.
[2] 2. J. BERSTEL, Sur les mots sans carré définis par un morphisme, Lecture Notes in Comput Sci., 1979, 71, pp. 16-25. Zbl0425.20046 MR573232 · Zbl 0425.20046
[3] 3. L. BOASSON and S. HORVATH, On language satisfying Ogden’s lemma, R.A.I.R.O. Inform. Theor. Appl., 1978, 12, pp. 193-199. Zbl0387.68054 MR510636 · Zbl 0387.68054
[4] 4. J. DASSOW and Gh. PAUN, Regulated rewriting in formal language theory, Akademie-Verlag, Berlin, 1989. Zbl0697.68067 MR1067543 · Zbl 0697.68067
[5] 5. S. A. GREIBACH, A note on undecidable properties of formal languages, Math. Syst. Theory, 1968, 2, 1, pp. 1-6. Zbl0157.01902 MR225609 · Zbl 0157.01902 · doi:10.1007/BF01691341
[6] 6. S. MARCUS, Algebraic linguistics. Analytical models, New York, London, Academic Press, 1967. Zbl0174.02402 MR225610 · Zbl 0174.02402
[7] 7. W. OGDEN, A helpful result for proving inherent ambiquity, Math. Syst. Theory, 1968, 2, pp. 191-197. Zbl0175.27802 MR233645 · Zbl 0175.27802 · doi:10.1007/BF01694004
[8] 8. W. OGDEN, R. ROSS and K. WINKLEMANN, An ”interchange lemma” for context-free languages, S.I.A.M. J. Comput., 1985, 14, pp. 410-415. Zbl0601.68051 MR784746 · Zbl 0601.68051 · doi:10.1137/0214031
[9] 9. S. SOKOLOWSKI, A method for proving programming language non context-free, Inf. Proc. Lett., 1978, 7, pp. 151-153. Zbl0384.68071 MR475012 · Zbl 0384.68071 · doi:10.1016/0020-0190(78)90080-7
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.