Appendix B  BIBLIOGRAPHY

• Adleman, L. (1978). "Two theorems on random polynomial time," Proceedings of the 19th IEEE Symposium on Foundations of Computer Science, 75-83.
• Aho, A., Hopcroft, J., and Ullman, J. (1974). The Design and Analysis of Computer Algorithms, Reading, MA: Addison-Wesley.
• Aho, A., Sethi, R., and Ullman, J. (1986). Compilers: Principles, Techniques, and Tools, Reading, MA: Addison-Wesley.
• Allender, E. (1986). "Characterizations of PUNC and precomputation," International Colloquium on Automata, Languages and Programming, Lecture Notes in Computer Science 226, Berlin: Springer-Verlag, 1-10.
• Bar-Hillel, Y., Perles, M., and Shamir, E. (1961). "On formal properties of simple phrase structure grammars", Zeitschrift für Phonetik Sprachwissenschaft und Kommunikations-forschung 14, 143-172.
• Batcher, K. (1968). "Sorting networks and their applications," Proceedings of the 32nd AFIPS Spring Joint Computer Conference, 307-314.
• Bird, M. (1973). "The equivalence problem for deterministic two-tape automata," Journal of Computer and Systems Sciences 7, 218-236.
• Borodin, A. (1977). "On relating time and space to size and depth," SIAM Journal on Computing 6, 733-744.
• Büchi, J. (1960). "Weak second-order arithmetic and finite automata," Zeitschrift fur math. Logik und Grundlagen d. Math. 6, 66-92.
• Chandra, A., Stockmeyer, L., and Vishkin, U. (1984). "Constant depth reducibilities," SIAM Journal on Computing 13, 423-439.
• Chomsky, N. (1959). "On certain formal properties of grammars," Information and Control 2, 137-167.
• Chomsky, N. (1962). "Context-free grammars and pushdown storage," Quarterly Progress Report 65, MIT Research Laboratories of Electronics, 187-194.
• Chomsky, N., and Miller, G. (1958). "Finite-state languages," Information and Control 1, 91-112.
• Chomsky, N., and Schutzenberger, M. (1963). "The algebraic theory of context free languages," Computer Programming and Formal Systems, 118- 161.
• Church, A. (1936). "An unsolvable problem of elementary number theory," American Journal of Mathematics 58, 345-363.
• Cobham, A. (1964). "The intrinsic computational difficulty of functions," Proceedings of the 1964 Congress for Logic, Mathematics and the Philosophy of Science, Amsterdam: North Holland, 24-30.
• Cook, S. (1971). "The complexity of theorem-proving procedures," Proceedings of the 3rd Annual ACM Symposium on Theory of Computing, 151-158.
• Cook, S. (1981). "Towards a complexity theory of synchronous parallel computations," L'Enseignement Mathematique 27, 99-124.
• Cook, S. (1983). "The classification of problems which have fast parallel algorithms," Proceedings of the 4th International Foundations of Computer Science Conference, Lecture Notes in Computer Science 158, Berlin: Springer Verlag, 78-93.
• Cook, S., and Reckhov, R. (1973). "Time bounded random access machines," Journal of Computer and Systems Sciences 7, 354-375.
• Danthine, A. (1980). "Protocol representation with finite state models," IEEE Transactions on Communications 4, 632-643.
• DeLeeuw, K., Moore, E., Shannon, C., and Shapiro, N. (1956). "Computability by probabilistic machines," Automata Studies, Princeton, NJ: Princeton University Press, 183-212.
• Edmonds, J. (1965a). "Path, trees and flowers," Canadian Journal of Mathematics 17, 449-467.
• Edmonds, J. (1965b). "Minimum partition of matroid in independent subsets," Journal of Research of the National Bureau of Standard Sect 69B, 67-72.
• Ehrenfeucht, A., Parikh, R., and Rozenberg, G. (1981). "Pumping lemmas for regular sets," SIAM Journal on Computing 10, 536-541.
• Evey, J. (1963). "Application of pushdown store machines," Proceedings 1963 Fall Joint Computer Conference, Montvale, NJ: AFIPS Press, 215-227.
• Floyd, R. (1967). "Nondeterministic algorithms," Journal of the Association for Computing Machinery 14, 636-644.
• Fortune, S., and Wyllie, J. (1978). "Parallelism in random access machines," Proceedings of the 10th Annual ACM Symposium on Theory of Computing, 114-118.
• Freivalds, R. (1979). "Fast probabilistic algorithms," Proceedings of the 1979 Mathematical Foundations of Computer Science, Lecture Notes in Computer Science 74, Berlin: Springer-Verlag, 57-69.
• Garey, M., and Johnson, D. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness, San Francisco, CA: W. H. Freeman and Company.
• Gill, J. (1977). "Computational complexity of probabilistic Turing machines," SIAM Journal on Computing 6, 675-694.
• Goldschlager, L. (1982). "A unified approach to models of synchronous parallel machines," Journal of the Association for Computing Machinery 29, 1073-1086.
• Greibach, S. (1981). "Formal languages: Origins and directions," Annals of the History of Computing 3, 14-41.
• Griffiths, T. (1968). "The unsolvability of the equivalence problem for -free nondeterministic generalized machines," Journal of the Association for Computing Machinery 15, 409-413.
• Grolmusz, V., and Ragde, P. (1987). "Incomparability in parallel computation," Proceedings of the 28th IEEE Symposium on Foundations of Computer Science, 89-98.
• Gurari, E. (1979). "Transducers with decidable equivalence problem," Technical Report, University of Wisconsin-Milwaukee, 1979. Revised version, State University of New York at Buffalo, 1981.
• Harrison, M. (1978). Introduction to Formal Language Theory, Reading, MA: Addison-Wesley.
• Hartmanis, J., and Stearns, R. (1965). "On the computational complexity of algorithms," Transactions of the American Mathematical Society 117, 285-306.
• Hilbert, D. (1901). "Mathematical problems," Bulletin of the American Mathematical Society 8, 437-479.
• Hopcroft, J., and Ullman, J. (1969). "Some results on tape bounded Turing machines," Journal of the Association for Computing Machinery 16, 168-177.
• Hopcroft, J., and Ullman, J. (1979). Introduction to Automata Theory, Languages and Computation, Reading, MA: Addison-Wesley.
• Hunt, H. (1973). "On the time and type complexity of languages," Proceedings of the 5th Annual ACM Symposium on Theory of Computing, 10-19.
• Hunt, H., Constable, R., and Sahni, S. (1980). "On the computational complexity of scheme equivalence," SIAM Journal on Computing 9, 396-416.
• Ibarra, O., and Rosier, L. (1981). "On the decidability of equivalence for deterministic pushdown transducers," Information Processing Letters 13, 89-93.
• Immerman, N. (1987). "Space is closed under complementation," Technical Report, New Haven, CT: Yale University.
• Hong, J. (1985). "On similarity and duality of computation," Information and Control 62, 109-128.
• Johnson, D. (1983). "The NP-completeness column: An ongoing guide," Journal of Algorithms 4, 189-203.
• Johnson, D. (1984). "The NP-completeness column: An ongoing guide," Journal of Algorithms 5, 433-447.
• Jones, N., and Laaser, W., (1976). "Complete problems for deterministic polynomial time," Theoretical Computer Science 3, 105-118.
• Jones, N., and Muchnick, S. (1977). "Even simple programs are hard to analyze," Journal of the Association for Computing Machinery 24, 338-350.
• Jones, N., and Muchnick, S. (1978). "The complexity of finite memory programs with recursion," Journal of the Association for Computing Machinery 25, 312-321.
• Kannan, R. (1982). "Circuit-size lower bounds and non-reducibility to sparse sets," Information and Control 55, 40-56.
• Karp, R. (1972). "Reducibility among combinatorial problems," Complexity of Computer Computations, edited by R. Mille and J. Thatcher, New York: Plenum Press, 85-104.
• Kindervater, G., and Lenstra, J. (1985). "Parallel Algorithms," in Combinatorial Optimization: Annotated Bibliographies, edited by M. O'hEigeartaigh, J. Lenstra, and A. Rinnooy Kan, New York: John Wiley and Sons, 106-128.
• Kleene, S. (1956). "Representation of events in nerve nets and finite automata," Automata Studies, Princeton, NJ: Princeton University Press, 3-41.
• Kuera, K. (1982). "Parallel computation and conflicts in memory access," Information Processing Letters 14, 93-96. A correction, ibid 17, 107.
• Kuroda, S. (1964). "Classes of languages and linear bounded automata," Information and Control 7, 207-223.
• Ladner, R. (1975). "The circuit value problem is log space complete for P," Sigact News 7, 18-20.
• Landweber, P. (1963). "Three theorems on phrase structure grammars of Type 1," Information and Control 6, 131-136.
• Lesk, M. (1975). "LEX - a lexical analyzer generator," Technical Report 39, Murray Hill, NJ: Bell Laboratories.
• Levin, L. (1973). "Universal sorting problems," Problemi Peredaci Informacii 9, 115-116. English translation in Problems of Information Transmission 9, 265-266.
• Lueker, G. (1975). "Two NP-complete problems in non-negative integer programming," Report No. 178, Computer Science Laboratory, Princeton, NJ: Princeton University.
• Maffioli, F., Speranza, M., and Vercellis, C. (1985). "Randomized algorithms," in Combinatorial Optimization - Annotated Bibliographies, edited by M. O'hEigeartaigh, J. Lenstra, and A. Rinnooy Man, New York: John Wiley and Sons, 89-105.
• Matijasevic, Y. (1970). "Enumerable sets are Diophantine," Doklady Akademiky Nauk SSSR 191, 279-282. English translation: Soviet Math Doklady 11, 354-357.
• McCarthy, J. (1963). "A basis for a mathematical theory of computation," Computer Programming and Formal Systems, edited by P. Braffort and D., Hirschberg, Amsterdam: North-Holland.
• McCulloch, W., and Pitts, W. (1943). "A logical calculus of the ideas immanent in nervous activity," Bulletin of Mathematical Biophysics 5, 115- 133.
• Megiddo, N. (1981). "Applying parallel computation algorithms in the design of serial algorithms," Proceedings of the 22nd IEEE Symposium on Foundations of Computer Science, 399-408.
• Meyer, A., and Ritchie, R. (1967). "The complexity of loop programs," Proceedings of the ACM National Meeting, 465-469.
• Moore, E. (1956). "Gedanken experiments on sequential machines," Automata Studies, Princeton, NJ: Princeton University Press, 129-153.
• Muller, D., and Preparata, F. (1975). "Bounds to complexities of networks for sorting and for switching," Journal of the Association for Computing Machinery 22, 195-201.
• Myhill, J. (1957). "Finite automata and the representation of events," WADD TR-57-624, Dayton, OH: Wright Patterson Air Force Base.
• Myhill, J. (1960). "Linear bounded automata," WADD TR-60-165, Dayton, OH: Wright Patterson Air Force Base.
• Oettinger, A. (1961). "Automatic syntactic analysis and the pushdown store," Proceedings of the 12th Symposia in Applied Mathematics, Providence, RI: American Mathematical Society, 104-109.
• Pippenger, E. (1979). "On simultaneous resource bounds," Proceedings of the 20th IEEE Symposium on Foundations of Computer Science, 307-311.
• Post, E. (1946). "A variant of a recursively unsolvable problem," Bulletin of the American Mathematical Society 52, 264-268.
• Rabin, M. (1976). "Probabilistic algorithms," Algorithms and Complexity - New Directions and Recent Results, edited by J. Traub, New York: Academic- Press, 21-29.
• Rabin, M., and Scott, D. (1959). "Finite automata and their decision problems," IBM Journal of Research and Development 3, 114-125.
• Ritchie, R. (1963). "Classes of predictably computable functions," Transactions of the American Mathematical Society 106, 139-173.
• Ruzzo, L. (1981). "On uniform circuit complexity," Journal of Computer and Systems Sciences 22, 365-383.
• Savitch, W. (1970). "Relationships between nondeterministic and deterministic tape complexities," Journal of Computer and Systems Sciences 4, 177-192.
• Scheinberg, S. (1960). "Note on the Boolean properties of context free languages," Information and Control 3, 372-375.
• Schutzenberger, M. (1963). "On context-free languages and pushdown automata," Information and Control 6, 246-264.
• Schwartz, J. (1980). "Fast probabilistic algorithms for verification of polynomial identities," Journal of the Association for Computing Machinery 27, 701-717.
• Shannon, C. (1949). "The synthesis of two terminal switching circuts," Bell System Technical Journal 28, 59-98.
• Sheperdson, J. (1959). "The reduction of two-way automata to one-way automata," IBM Journal of Research and Development 3, 198-200.
• Shiloach, Y., and Vishkin, U. (1981). "Finding the maximum, merging and sorting in a parallel computation model," Journal of Algorithms 2, 88-102.
• Sipser, M. (1978). "Halting bounded computations," Proceedings of the 19th IEEE Symposium on Foundations of Computer Science, 73-74.
• Solovay, R. and Strassen, V. (1977). "A fast Monte Carlo test for primality," SIAM Journal on Computing 6, 84-85. A correction, ibid 7, 118.
• Stearns, R., Hartmanis, J., and Lewis, P. (1965). "Hierarchies of memory limited computations," Proceedings of the 6th Annual IEEE Symposium on Switching Circuit Theory and Logical Design, 191-202.
• Stockmeyer, L. (1985). "Classifying the computational complexity of problems," IBM Research Report, San Jose, CA.
• Szelepcsenyi, R. (1987). "The method of forcing for nondeterministic automata," Bulletin of the European Association for Theoretical Computer Science 33, 96-100.
• Turing, A. (1936). "On computable numbers with an application to the Entscheidungs problem," Proceedings of the London Mathematical Society 2, 230-265. A correction, ibid, 544-546.
• Valiant, L. (1973). "Decision procedures for families of deterministic pushdown automata," Ph.D. Thesis, University of Warwick, U.K.
• Valiant, L. (1975). "Parallelism in comparison problems," SIAM Journal on Computing 4, 348-355.
• Welsh, D. (1983). "Randomised algorithms," Discrete applied Mathematics 5, 133-145.

[next] [prev] [prev-tail] [front] [up]