Abstract
A string y is in C(x), the commutative image of a string x, if y is a permutation of the symbols in x. A language L is Parikh-bounded if L contains a bounded language B and all x in L have a corresponding y in B such that x is in C(y). The central result in this paper is that if L is context-free it is also Parikh-bounded. Parikh's theorem follows as a corollary. If L is not bounded but is a Parikh-bounded language closed under intersection with regular sets, then for any positive integer k there is an x in L such that #(C(x) ∩ L) ≥ k. The notion of Parikh-discreteness is introduced.
This research was supported in part by NSF Grant No. MCS 77-02470.
Chapter PDF
Similar content being viewed by others
References
Greibach, S., "Chains of full AFL's," Math. Systems Theory, Vol. 4, No. 3, 1970, pp. 231–242.
Ginsburg, S. and Spanier, E. H., "Bounded ALGOL-like languages," Trans. of the AMS, Vol. 113, 1964, pp. 333–368.
Harrison, M., Introduction to Formal Language Theory. Addison-Wesley, Reading, Mass. 1978.
Latteux, M., "Languages Commutatifs," These Sc. Math., Lille, 1978.
Latteux, M., "Mots infinis et languages commutatifs," RAIRO Informatique theorique / Theor. Comp. Science, Vol. 12, No. 3, 1978, pp. 185–192.
Latteux, M., "Cones rationnels commutatifs," JCSS, Vol. 18, No. 3, June 1979, pp. 307–333.
Latteux, M. and Leguy, J., "Une propriete de la famille GRE." Fundamentals of Computation Theory, FCT 1979. Akademie-Verlag, Berlin 1979.
Parikh, R. J., "On context-free languages," JACM, Vol. 13, 1966, pp. 570–581.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1981 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Blattner, M., Latteux, M. (1981). Parikh-bounded languages. In: Even, S., Kariv, O. (eds) Automata, Languages and Programming. ICALP 1981. Lecture Notes in Computer Science, vol 115. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-10843-2_26
Download citation
DOI: https://doi.org/10.1007/3-540-10843-2_26
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-10843-6
Online ISBN: 978-3-540-38745-9
eBook Packages: Springer Book Archive