Abstract
A languageL has theprefix property if for allx, y ∈ L, eitherx is a prefix ofy ory is a prefix ofx. It is shown that for certain classes of languages, if a language in the class has the prefix property, then it is a regular set. The results provide new distinctions between classes as well as new profs of previously known distinctions.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
R. Book andR. Lipton, On the complexity of infinite sequences, unpublished manuscript.
R. Book andM. Nivat, Reversal-bounded acceptors, in preparation.
R. Book, M. Nivat, andM. Paterson, Reversal-bounded acceptors and Intersections of linear languages,SIAM J. Computing 3 (1974), 283–295.
A. Ehrenfeucht andG. Rozenberg, A pumping theorem for deterministic ETOL languages,Revue d'Automatique, Informatique, Recherche Opérationnelle (série rouge) 9 (1975), 13–23.
S. Ginsburg, S. Greibach, andM. Harrison, Stack automata and compiling,J. Assoc. Comput. Mach. 14 (1967), 172–201.
S. Ginsburg andE. Spanier, Finite-turn pushdown automata,Siam J. Control 4 (1966), 429–453.
S. Greibach, An infinite hierarchy of context-free languages,J. Assoc. Comput. Mach. 16 (1969), 91–106.
S. Greibach, Checking automata and one-way stack languages,J. Comput. System Sci. 3 (1969), 196–217.
W. Ogden, Intercalation Theorems for Pushdown Store and Stack Languages, Ph.D. dissertation, Stanford University, 1968.
W. Ogden, A helpful result for proving inherent ambiguity,Math. Systems Theory 2 (1968), 191–195.
F. Rodriguez, Cones d'Accepteurs-Application a l'Etude d'une Hierarchie Infinie de Cones Rationnels de Languages d'Accepteurs Vérificateurs, Thèse Docteur-Ingenieur, Toulouse, 1973.
R. Rodriguez, Une double hierarchie infinie de languages vérifiables,Revue d'Automatique, Informatique, Recherche Opérationelle (série rouge) 9 (1975), 5–19.
R. Siromoney, On equal matrix languages,Information and Control 14 (1969), 135–151.
R. Siromoney, Finite-turn checking automata,J. Computer System Sci. 5 (1971), 549–559.
A. Thue, Über die gegenseitige Lage gleicher Teile gewisser Zeichenreiher,Videnskabssekskabets Skrifter I Mat. nat. Kl., Christiana, 1912.
G. A. Hedlund, Remarks on the work of Axel Thue on sequences,Nordisk Mat. Tidskr 15 (1967), 148–150.
Author information
Authors and Affiliations
Additional information
This research was supported in part by the National Science Foundation under Grant DCR-75-15945 and Grant MCS76-05744.
Rights and permissions
About this article
Cite this article
Book, R.V. On languages with a certain prefix property. Math. Systems Theory 10, 229–237 (1976). https://doi.org/10.1007/BF01683274
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF01683274