Abstract
The main result of the paper can be viewed both as a generalization of a classical results concerning colorings of graphs, as well as a very useful over-all theorem from which various specific results concerning grammar and language families can be deduced. Essentially our main result says that, when considering infinitary families obtainable by inverse morphisms, it suffices to consider their finitary parts. Various applications are given, in particular, to grammar forms and context-free languages over infinite alphabets.
Similar content being viewed by others
References
J.-M. Autebert, J. Beauquier, L. Boasson, Langages sur les alphabets infinis.Discrete Applied Mathematics 2, 1–20 (1980).
N. G. De Bruijn, P. Erdös, A color problem for infinite graphs and a problem in the theory of relations.Indagationes Mathematicae 13, 371–373 (1951).
A. Cremers, S. Ginsburg, Context-free grammar forms.Journal of Computer and System Sciences 11, 86–116 (1975).
H. A. Maurer,Theoretische Grundlagen der Programmier-sprachen. BI Mannheim (1976).
H. A. Maurer, A. Salomaa, D. Wood, Colorings and interpretations—a connection between graphs and grammar forms.Discrete Applied Mathematics 3, 119–135 (1981).
H. A. Maurer, A. Salomaa, D. Wood, Dense hierarchies of grammatical families.Journal of the Association for Computing Machinery, to appear.
H. A. Maurer, A. Salomaa, D. Wood, On predecessors of finite languages. McMaster University Computer Science Technical Report 80-CS-14 (1980), submitted for publication.
H. A. Maurer, A. Salomaa, E. Welzl, D. Wood, Dense intervals of linguistical families.Information Processing Letters, to appear.
Th. Ottmann, A. Salomaa, D. Wood, Sub-regular grammar forms.Information Processing Letters 12, 184–187 (1981).
A. Salomaa,Formal Languages. Academic Press, New York (1973).
A. Salomaa, On color-families of graphs.Annales Academiae Scientiarum Fennicae, to appear.
E. Welzl, Color-families are dense.Theoretical Computer Science, to appear.
D. Wood, Grammar andL Forms: An Introduction:Springer Lecture Notes in Computer Science 91 (1980).
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Maurer, H.A., Salomaa, A. & Wood, D. Finitary and infinitary interpretations of languages. Math. Systems Theory 15, 251–265 (1981). https://doi.org/10.1007/BF01786982
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF01786982