Characterizations of the Dyck sets
Wrathall, Celia
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 11 (1977), p. 53-62 / Harvested from Numdam
Access to full text
Full (PDF)
Full (DJVU)
Publié le : 1977-01-01
@article{ITA_1977__11_1_53_0,
     author = {Wrathall, Celia},
     title = {Characterizations of the Dyck sets},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     volume = {11},
     year = {1977},
     pages = {53-62},
     mrnumber = {483787},
     zbl = {0354.68104},
     language = {en},
     url = {http://dml.mathdoc.fr/item/ITA_1977__11_1_53_0}
}

Wrathall, Celia. Characterizations of the Dyck sets. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 11 (1977) pp. 53-62. http://gdmltest.u-ga.fr/item/ITA_1977__11_1_53_0/

1. H. Alt and K. Mehlhorn, Lower Bounds for the Space Complexity of Context-Free Recognition, unpublished manuscript.

2. R. Book, On the Chomsky-Schützenberger Theorem, Technical Report, Department of Computer Science, Yale University, New Haven, Conn., 1975.

3. R. Book and S. Greibach, Quasirealtime Languages, Math. Systems Theory, Vol. 4, 1970, pp. 97-111. | MR 276019 | Zbl 0188.33102

4. R. Book, M. Nivat and M. Paterson, Reversal-Bounded Acceptors and Intersections of Linear Languages, SIAM J. Comput., Vol. 3, 1974, pp. 283-295. | MR 433992 | Zbl 0292.68023

5. P. Fischer, A. Meyer and A. Rosenberg, Counter Machines and Counter Languages, Math. Systems Theory, Vol. 2, 1968, pp. 265-283. | MR 235932 | Zbl 0165.32002

6. S. Ginsburg and S. Greibach, Abstract Families of Languages, Memoir 87, American Mathematical Society, Providence, R.I., 1969, pp. 1-32. | MR 297491

7. S. Ginsburg, S. Greibach and J. Hopcroft, Pre-AFL, Memoir 87, American Mathematical Society, Providence, R.I., 1969, pp. 41-51. | MR 297493 | Zbl 0194.31402

8. S. Greibach, An Infinite Hierarchy of Context-Free Languages, J. Assoc. Computing Machinery, Vol. 16, 1969, pp. 91-106. | MR 238632 | Zbl 0182.02002

9. G. Hotz and J. Messerschmidt, Dyck-Sprachen sind in Bandkomplexitat log n analysierbar, Technical Report, Universität des Saarlandes, 1975.

10. N. Jones, Context-Free Languages and Rudimentary Attributes, Math. Systems Theory, Vol. 3, 1969, pp. 102-109. | MR 265084 | Zbl 0179.02202

11. M. Latteux, Cônes rationnels commutativement clos, This Journal. | Numdam | MR 478782 | Zbl 0354.68103

12. M. Minsky, Recursive Unsolvability of Post's Problem of Tag and other Topics in the Theory of Turing Machines, Annals of Math., Vol. 74, 1961, pp. 437-455. | MR 140405 | Zbl 0105.00802

13. R. Ritchie, and F. Springsteel, Language Recognition by Marking Automata, Inf. and Control, Vol. 20, 1972, pp. 313-330. | MR 325300 | Zbl 0242.68032

14. C. Wrathall, Subrecursive Predicates and Automata, Research Report 56, Department of Computer Science, Yale University, New Haven, Conn., 1975.

15. Y. Yu, Rudimentary Relations and Formal Languages, Ph. D. dissertation, University of California, Berkeley, Calif., 1970.