{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T22:48:43Z","timestamp":1725662923051},"publisher-location":"Berlin, Heidelberg","reference-count":48,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540074076"},{"type":"electronic","value":"9783540379232"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1975]]},"DOI":"10.1007\/3-540-07407-4_1","type":"book-chapter","created":{"date-parts":[[2012,2,25]],"date-time":"2012-02-25T15:56:27Z","timestamp":1330185387000},"page":"1-15","source":"Crossref","is-referenced-by-count":1,"title":["Formal language theory and theoretical computer science"],"prefix":"10.1007","author":[{"given":"Ronald V.","family":"Book","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,5,25]]},"reference":[{"key":"1_CR1","unstructured":"G.H. Hardy. A Mathematician's Apology. Cambridge Univ. Press, 1940, reprinted 1967."},{"key":"1_CR2","doi-asserted-by":"crossref","unstructured":"P. Naur. Programming languages, natural languages, and mathematics. Conference Record, 2nd ACM Symp. Principles of Programming Languages. Palo Alto, Calif., 1975, 137\u2013148.","DOI":"10.1145\/512976.512991"},{"key":"1_CR3","doi-asserted-by":"crossref","first-page":"308","DOI":"10.1016\/S0022-0000(70)80016-2","volume":"4","author":"S. Ginsburg","year":"1970","unstructured":"S. Ginsburg and S.A. Greibach. Principal AFL. J. Computer System Sci. 4 (1970), 308\u2013338.","journal-title":"J. Computer System Sci."},{"key":"1_CR4","doi-asserted-by":"crossref","first-page":"304","DOI":"10.1137\/0202025","volume":"2","author":"S. A. Greibach","year":"1973","unstructured":"S.A. Greibach. The hardest context-free language. SIAM J. Computing 2 (1973), 304\u2013310.","journal-title":"SIAM J. Computing"},{"key":"1_CR5","unstructured":"L. Boasson and M. Nivat. Le cylindre des languages lineaires n'est pas principal. Proc. 2nd GI \u2014 Profession Conf. Automata Theory and Formal Languages. Springer Verlag, to appear."},{"key":"1_CR6","doi-asserted-by":"crossref","first-page":"213","DOI":"10.1016\/S0022-0000(74)80008-5","volume":"9","author":"R. Book","year":"1974","unstructured":"R. Book. Comparing complexity classes. J. Computer System Sci. 9 (1974), 213\u2013229.","journal-title":"J. Computer System Sci."},{"key":"1_CR7","unstructured":"R. Book. On hardest sets. In preparation."},{"key":"1_CR8","doi-asserted-by":"crossref","unstructured":"N. Jones and W. Laaser. Complete problems for deterministic polynomial time recognizable languages. Proc. 6th ACM Symp. Theory of Computing. Seattle, Wash., 1974, 40\u201346.","DOI":"10.1145\/800119.803883"},{"key":"1_CR9","volume-title":"Formal Languages","author":"A. Salomaa","year":"1973","unstructured":"A. Salomaa. Formal Languages. Academic Press. New York, 1973."},{"key":"1_CR10","unstructured":"P.G. Doucet. On the applicability of L-systems in developmental biology. In [11]."},{"key":"1_CR11","unstructured":"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."},{"key":"1_CR12","doi-asserted-by":"crossref","first-page":"397","DOI":"10.1016\/S0022-0000(71)80025-9","volume":"4","author":"R. Book","year":"1971","unstructured":"R. Book. Time-bounded grammars and their languages. J. Computer System Sci. 4 (1971), 397\u2013429.","journal-title":"J. Computer System Sci."},{"key":"1_CR13","volume-title":"Developmental Systems and Languages","author":"G. T. Herman","year":"1974","unstructured":"G.T. Herman and G. Rozenberg. Developmental Systems and Languages. North-Holland Publ. Co. Amsterdam, 1974."},{"key":"1_CR14","doi-asserted-by":"crossref","unstructured":"G. Rozenberg and A. Salomaa (eds.). L Systems. Lecture Notes in Computer Science, Vol. 15. Springer-Verlag, 1974.","DOI":"10.1007\/3-540-06867-8_1"},{"key":"1_CR15","unstructured":"Proceedings of the 1974 Conference on Biologically Motivated Automata Theory. McLean, Va. Published by the IEEE Computer Society."},{"key":"1_CR16","doi-asserted-by":"crossref","first-page":"119","DOI":"10.1016\/S0022-0000(73)80040-6","volume":"7","author":"S. Garland","year":"1973","unstructured":"S. Garland and D. Luckham. Program schemes, recursion schemes, and formal languages. J. Computer System Sci. 7 (1973), 119\u2013160.","journal-title":"J. Computer System Sci."},{"key":"1_CR17","doi-asserted-by":"crossref","first-page":"220","DOI":"10.1016\/S0022-0000(70)80022-8","volume":"4","author":"D. Luckham","year":"1970","unstructured":"D. Luckham, D. Park, and M. Paterson. On formalized computer programs. J. Computer System Sci. 4 (1970), 220\u2013249.","journal-title":"J. Computer System Sci."},{"key":"1_CR18","doi-asserted-by":"crossref","unstructured":"B.K. Rosen. Program equivalence and context-free grammars. Proc. 13th IEEE Symposium on Switching and Automata Theory. College Park, Md., 1972, 7\u201318.","DOI":"10.1109\/SWAT.1972.18"},{"key":"1_CR19","unstructured":"P.J. Downey. Formal languages and recursion schemes. Proc. 8th Princeton Conference on Information Science and Systems. Princeton, N.J., 1974."},{"key":"1_CR20","doi-asserted-by":"crossref","unstructured":"J. Engelfriet. Simple Program Schemes and Formal Longuages. Lecture Notes in Computer Science, Vol. 20. Springer-Verlag, 1974.","DOI":"10.1007\/3-540-06953-4"},{"key":"1_CR21","unstructured":"M Nivat. On the interpretation of recursive program schemes. IRIA Technical Report, 1974."},{"key":"1_CR22","doi-asserted-by":"crossref","first-page":"489","DOI":"10.1145\/321765.321780","volume":"20","author":"E. Ashcroft","year":"1973","unstructured":"E. Ashcroft, Z. Manna, and A. Pnueli. Decidable properties of monadic functional schemes. J. Assoc. Comput. Mach. 20 (1973), 489\u2013499.","journal-title":"J. Assoc. Comput. Mach."},{"key":"1_CR23","doi-asserted-by":"crossref","unstructured":"E.P. Friedman. The inclusion problem for simple languages. Theoretical Computer Science 1 (1975). To appear.","DOI":"10.1016\/0304-3975(76)90074-8"},{"key":"1_CR24","doi-asserted-by":"crossref","unstructured":"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\u201351.","DOI":"10.1109\/SWAT.1974.24"},{"key":"1_CR25","volume-title":"Syntactic Methods in Pattern Recognition","author":"K. Fu","year":"1974","unstructured":"K. Fu. Syntactic Methods in Pattern Recognition. Academic Press. New York, 1974."},{"key":"1_CR26","unstructured":"R. Lipton and L. Snyder. On the parsing of speech. Technical Report Number 37, Department of Computer Science, Yale University, 1975."},{"key":"1_CR27","unstructured":"S. Levinson. An Artificial Intelligence Approach to Automatic Speech Recognition. Doctoral Dissertation, U. Rhode Island, 1974."},{"key":"1_CR28","unstructured":"J.L. Peterson. Computation sequence sets. Unpublished manuscript."},{"key":"1_CR29","unstructured":"W.H. Byrn. Sequential Processes, Deadlocks, and Semaphore Primitives. Doctoral Dissertation, Harvard University, 1974."},{"key":"1_CR30","unstructured":"W.E. Riddle. Modeling and Analysis of Supervisory Systems. Doctoral Dissertation, Stanford University, 1972."},{"key":"1_CR31","doi-asserted-by":"crossref","first-page":"281","DOI":"10.1137\/0201019","volume":"1","author":"R. Book","year":"1972","unstructured":"R. Book. On languages accepted in polynomial time. SIAM J. Computing 1 (1972), 281\u2013287.","journal-title":"SIAM J. Computing"},{"key":"1_CR32","doi-asserted-by":"crossref","first-page":"636","DOI":"10.1145\/321420.321422","volume":"14","author":"R. Floyd","year":"1967","unstructured":"R. Floyd. Nondeterministic algorithms. J. Assoc. Comput. Mach. 14 (1967), 636\u2013644.","journal-title":"J. Assoc. Comput. Mach."},{"key":"1_CR33","unstructured":"A. Aho and J. Ullman. The Theory of Parsing, Translating, and Compiling, Vol. I. Prentice-Hall Publ. Co., 1972."},{"key":"1_CR34","first-page":"343","volume-title":"Proc. 3rd ACM Symp. Theory of Computing","author":"S. Cook","year":"1973","unstructured":"S. Cook. The complexity of theorem-proving procedures. Proc. 3rd ACM Symp. Theory of Computing. Shaker Hts., Ohio, 1973, 343\u2013353."},{"key":"1_CR35","doi-asserted-by":"crossref","unstructured":"R. Karp. Reducibilities among combinatorial problems. In Complexity of Computer Computation (R. Miller and J. Thatcher, eds.). Plenum, N.Y., 1972, 85\u2013104.","DOI":"10.1007\/978-1-4684-2001-2_9"},{"key":"1_CR36","unstructured":"A. Aho, J. Hopcroft, and J. Ullman, The Design and Analysis of Computer Algorithms. Addison-Wesley, 1974."},{"volume-title":"Complexity of Computation. SIAM-AMS Proc. VII","year":"1974","key":"1_CR37","unstructured":"R. Karp (ed.). Complexity of Computation. SIAM-AMS Proc. VII, Amer. Math. Soc. Providence, R.I., 1974."},{"key":"1_CR38","unstructured":"J. Hartmanis and J. Simon. Feasible computations. Proc. GI-Jahrestagung 74. Springer-Verlag, to appear."},{"key":"1_CR39","doi-asserted-by":"crossref","first-page":"4","DOI":"10.1145\/321623.321625","volume":"18","author":"S. Cook","year":"1971","unstructured":"S. Cook. Characterizations of pushdown machines in terms of time-bounded computers. J. Assoc. Comput. Mach. 18 (1971), 4\u201318.","journal-title":"J. Assoc. Comput. Mach."},{"key":"1_CR40","doi-asserted-by":"crossref","first-page":"97","DOI":"10.1007\/BF01705890","volume":"4","author":"R. Book","year":"1970","unstructured":"R. Book and S.A. Greibach. Quasi-realtime languages. Math. Systems Theory 4 (1970), 97\u2013111.","journal-title":"Math. Systems Theory"},{"key":"1_CR41","doi-asserted-by":"crossref","first-page":"645","DOI":"10.1145\/321420.321423","volume":"14","author":"A. Rosenberg","year":"1967","unstructured":"A. Rosenberg. Real-time definable languages. J. Assoc. Comput. Mach. 14 (1967), 645\u2013662.","journal-title":"J. Assoc. Comput. Mach."},{"key":"1_CR42","volume-title":"Complexity of Computation. SIAM-AMS Proc. VII","author":"S. Aanderaa","year":"1974","unstructured":"S. Aanderaa. On k-tape versus (k+1)-tape real time computation. In [37]."},{"key":"1_CR43","unstructured":"R. Book and M. Nivat. On linear languages and intersections of classes of languages. In preparation."},{"key":"1_CR44","doi-asserted-by":"crossref","first-page":"315","DOI":"10.1016\/S0022-0000(74)80027-9","volume":"8","author":"B. Baker","year":"1974","unstructured":"B. Baker and R. Book. Reversal-bounded multi-pushdown machines. J. Computer System Sci. 8 (1974), 315\u2013332.","journal-title":"J. Computer System Sci."},{"key":"1_CR45","doi-asserted-by":"crossref","first-page":"283","DOI":"10.1137\/0203023","volume":"3","author":"R. Book","year":"1974","unstructured":"R. Book, M. Nivat, and M. Paterson, Reversal-bounded acceptors and intersections of linear languages. SIAM J. Computing 3 (1974), 283\u2013295.","journal-title":"SIAM J. Computing"},{"key":"1_CR46","volume-title":"Complexity of Computation. SIAM-AMS Proc. VII","author":"J. Hartmanis","year":"1974","unstructured":"J. Hartmanis and H. Hunt. The LBA problem and its importance in the theory of computing. In [37]."},{"key":"1_CR47","unstructured":"C. Wrathall. Rudimentary predicates and relative computation. In preparation."},{"key":"1_CR48","doi-asserted-by":"crossref","unstructured":"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.","DOI":"10.1016\/S0022-0000(76)80038-4"}],"container-title":["Lecture Notes in Computer Science","Automata Theory and Formal Languages 2nd GI Conference Kaiserslautern, May 20\u201323, 1975"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-07407-4_1.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T19:57:30Z","timestamp":1605643050000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-07407-4_1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1975]]},"ISBN":["9783540074076","9783540379232"],"references-count":48,"URL":"https:\/\/doi.org\/10.1007\/3-540-07407-4_1","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1975]]}}}