On languages with a certain prefix property. (English) Zbl 0358.68107


68Q45 Formal languages and automata
Full Text: DOI


[1] R. Book andR. Lipton, On the complexity of infinite sequences, unpublished manuscript.
[2] R. Book andM. Nivat, Reversal-bounded acceptors, in preparation.
[3] R. Book, M. Nivat, andM. Paterson, Reversal-bounded acceptors and Intersections of linear languages,SIAM J. Computing 3 (1974), 283–295. · Zbl 0292.68023
[4] 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.
[5] S. Ginsburg, S. Greibach, andM. Harrison, Stack automata and compiling,J. Assoc. Comput. Mach. 14 (1967), 172–201.
[6] S. Ginsburg andE. Spanier, Finite-turn pushdown automata,Siam J. Control 4 (1966), 429–453. · Zbl 0147.25302
[7] S. Greibach, An infinite hierarchy of context-free languages,J. Assoc. Comput. Mach. 16 (1969), 91–106. · Zbl 0182.02002
[8] S. Greibach, Checking automata and one-way stack languages,J. Comput. System Sci. 3 (1969), 196–217. · Zbl 0174.02702
[9] W. Ogden, Intercalation Theorems for Pushdown Store and Stack Languages, Ph.D. dissertation, Stanford University, 1968.
[10] W. Ogden, A helpful result for proving inherent ambiguity,Math. Systems Theory 2 (1968), 191–195. · Zbl 0175.27802
[11] 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.
[12] R. Rodriguez, Une double hierarchie infinie de languages vérifiables,Revue d’Automatique, Informatique, Recherche Opérationelle (série rouge) 9 (1975), 5–19.
[13] R. Siromoney, On equal matrix languages,Information and Control 14 (1969), 135–151. · Zbl 0169.31402
[14] R. Siromoney, Finite-turn checking automata,J. Computer System Sci. 5 (1971), 549–559. · Zbl 0231.68032
[15] A. Thue, Über die gegenseitige Lage gleicher Teile gewisser Zeichenreiher,Videnskabssekskabets Skrifter I Mat. nat. Kl., Christiana, 1912. · JFM 44.0462.01
[16] G. A. Hedlund, Remarks on the work of Axel Thue on sequences,Nordisk Mat. Tidskr 15 (1967), 148–150. · Zbl 0153.33101
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.