Formal language theory and theoretical computer science

1. G.H. Hardy. A Mathematician's Apology. Cambridge Univ. Press, 1940, reprinted 1967.

   Google Scholar 

2. P. Naur. Programming languages, natural languages, and mathematics. Conference Record, 2nd ACM Symp. Principles of Programming Languages. Palo Alto, Calif., 1975, 137–148.

   Google Scholar 

3. S. Ginsburg and S.A. Greibach. Principal AFL. J. Computer System Sci. 4 (1970), 308–338.

   Article  MathSciNet  Google Scholar 

4. S.A. Greibach. The hardest context-free language. SIAM J. Computing 2 (1973), 304–310.

   Article  MathSciNet  Google Scholar 

5. L. Boasson and M. Nivat. Le cylindre des languages lineaires n'est pas principal. Proc. 2nd GI — Profession Conf. Automata Theory and Formal Languages. Springer Verlag, to appear.

   Google Scholar 

6. R. Book. Comparing complexity classes. J. Computer System Sci. 9 (1974), 213–229.

   Article  MathSciNet  Google Scholar 

7. R. Book. On hardest sets. In preparation.

   Google Scholar 

8. N. Jones and W. Laaser. Complete problems for deterministic polynomial time recognizable languages. Proc. 6th ACM Symp. Theory of Computing. Seattle, Wash., 1974, 40–46.

   Google Scholar 

9. A. Salomaa. Formal Languages. Academic Press. New York, 1973.

   MATH  Google Scholar 

10. P.G. Doucet. On the applicability of L-systems in developmental biology. In [11].

    Google Scholar 

11. A. Lindenmayer and G. Rozenberg (eds.). Abstract of papers presented at a Conference on Formal Languages, Automata, and Development. Univ. Utrecht, Utrecht, The Netherlands, 1975.

    Google Scholar 

12. R. Book. Time-bounded grammars and their languages. J. Computer System Sci. 4 (1971), 397–429.

    Article  MathSciNet  Google Scholar 

13. G.T. Herman and G. Rozenberg. Developmental Systems and Languages. North-Holland Publ. Co. Amsterdam, 1974.

    MATH  Google Scholar 

14. G. Rozenberg and A. Salomaa (eds.). L Systems. Lecture Notes in Computer Science, Vol. 15. Springer-Verlag, 1974.

    Google Scholar 

15. Proceedings of the 1974 Conference on Biologically Motivated Automata Theory. McLean, Va. Published by the IEEE Computer Society.

    Google Scholar 

16. S. Garland and D. Luckham. Program schemes, recursion schemes, and formal languages. J. Computer System Sci. 7 (1973), 119–160.

    Article  MathSciNet  Google Scholar 

17. D. Luckham, D. Park, and M. Paterson. On formalized computer programs. J. Computer System Sci. 4 (1970), 220–249.

    Article  MathSciNet  Google Scholar 

18. B.K. Rosen. Program equivalence and context-free grammars. Proc. 13th IEEE Symposium on Switching and Automata Theory. College Park, Md., 1972, 7–18.

    Google Scholar 

19. P.J. Downey. Formal languages and recursion schemes. Proc. 8th Princeton Conference on Information Science and Systems. Princeton, N.J., 1974.

    Google Scholar 

20. J. Engelfriet. Simple Program Schemes and Formal Longuages. Lecture Notes in Computer Science, Vol. 20. Springer-Verlag, 1974.

    Google Scholar 

21. M Nivat. On the interpretation of recursive program schemes. IRIA Technical Report, 1974.

    Google Scholar 

22. E. Ashcroft, Z. Manna, and A. Pnueli. Decidable properties of monadic functional schemes. J. Assoc. Comput. Mach. 20 (1973), 489–499.

    Article  MathSciNet  Google Scholar 

23. E.P. Friedman. The inclusion problem for simple languages. Theoretical Computer Science 1 (1975). To appear.

    Google Scholar 

24. E.P. Friedman. Relationships between monadic recursion schemes and deterministic context-free languages. Proc. 15th IEEE Symposium on Switching and Automata Theory. New Orleans, La., 1974, 43–51.

    Google Scholar 

25. K. Fu. Syntactic Methods in Pattern Recognition. Academic Press. New York, 1974.

    MATH  Google Scholar 

26. R. Lipton and L. Snyder. On the parsing of speech. Technical Report Number 37, Department of Computer Science, Yale University, 1975.

    Google Scholar 

27. S. Levinson. An Artificial Intelligence Approach to Automatic Speech Recognition. Doctoral Dissertation, U. Rhode Island, 1974.

    Google Scholar 

28. J.L. Peterson. Computation sequence sets. Unpublished manuscript.

    Google Scholar 

29. W.H. Byrn. Sequential Processes, Deadlocks, and Semaphore Primitives. Doctoral Dissertation, Harvard University, 1974.

    Google Scholar 

30. W.E. Riddle. Modeling and Analysis of Supervisory Systems. Doctoral Dissertation, Stanford University, 1972.

    Google Scholar 

31. R. Book. On languages accepted in polynomial time. SIAM J. Computing 1 (1972), 281–287.

    Article  MathSciNet  Google Scholar 

32. R. Floyd. Nondeterministic algorithms. J. Assoc. Comput. Mach. 14 (1967), 636–644.

    Article  Google Scholar 

33. A. Aho and J. Ullman. The Theory of Parsing, Translating, and Compiling, Vol. I. Prentice-Hall Publ. Co., 1972.

    Google Scholar 

34. S. Cook. The complexity of theorem-proving procedures. Proc. 3rd ACM Symp. Theory of Computing. Shaker Hts., Ohio, 1973, 343–353.

    Google Scholar 

35. R. Karp. Reducibilities among combinatorial problems. In Complexity of Computer Computation (R. Miller and J. Thatcher, eds.). Plenum, N.Y., 1972, 85–104.

    Google Scholar 

36. A. Aho, J. Hopcroft, and J. Ullman, The Design and Analysis of Computer Algorithms. Addison-Wesley, 1974.

    Google Scholar 

37. R. Karp (ed.). Complexity of Computation. SIAM-AMS Proc. VII, Amer. Math. Soc. Providence, R.I., 1974.

    Google Scholar 

38. J. Hartmanis and J. Simon. Feasible computations. Proc. GI-Jahrestagung 74. Springer-Verlag, to appear.

    Google Scholar 

39. S. Cook. Characterizations of pushdown machines in terms of time-bounded computers. J. Assoc. Comput. Mach. 18 (1971), 4–18.

    Article  MathSciNet  Google Scholar 

40. R. Book and S.A. Greibach. Quasi-realtime languages. Math. Systems Theory 4 (1970), 97–111.

    Article  MathSciNet  Google Scholar 

41. A. Rosenberg. Real-time definable languages. J. Assoc. Comput. Mach. 14 (1967), 645–662.

    Article  MathSciNet  Google Scholar 

42. S. Aanderaa. On k-tape versus (k+1)-tape real time computation. In [37].

    Google Scholar 

43. R. Book and M. Nivat. On linear languages and intersections of classes of languages. In preparation.

    Google Scholar 

44. B. Baker and R. Book. Reversal-bounded multi-pushdown machines. J. Computer System Sci. 8 (1974), 315–332.

    Article  MathSciNet  Google Scholar 

45. R. Book, M. Nivat, and M. Paterson, Reversal-bounded acceptors and intersections of linear languages. SIAM J. Computing 3 (1974), 283–295.

    Article  MathSciNet  Google Scholar 

46. J. Hartmanis and H. Hunt. The LBA problem and its importance in the theory of computing. In [37].

    Google Scholar 

47. C. Wrathall. Rudimentary predicates and relative computation. In preparation.

    Google Scholar 

48. H. Hunt, D. Rosenkrantz, and T. Szymanski. On the equivalence, containment, and covering problems for the regular and context-free languages. J. Computer System Sci., to appear.

    Google Scholar 

Download references