×

zbMATH — the first resource for mathematics

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

MSC:
68Q45 Formal languages and automata
PDF BibTeX XML Cite
Full Text: DOI
References:
[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 · doi:10.1137/0203023
[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 · doi:10.1137/0304034
[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 · doi:10.1016/S0022-0000(69)80012-7
[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 · doi:10.1007/BF01694004
[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 · doi:10.1016/S0019-9958(69)90050-3
[14] R. Siromoney, Finite-turn checking automata,J. Computer System Sci. 5 (1971), 549–559. · Zbl 0231.68032 · doi:10.1016/S0022-0000(71)80015-6
[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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.