{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T21:48:16Z","timestamp":1725486496663},"publisher-location":"Berlin, Heidelberg","reference-count":20,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540434535"},{"type":"electronic","value":"9783540460114"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2002]]},"DOI":"10.1007\/3-540-46011-x_30","type":"book-chapter","created":{"date-parts":[[2007,6,18]],"date-time":"2007-06-18T22:54:16Z","timestamp":1182207256000},"page":"340-348","source":"Crossref","is-referenced-by-count":2,"title":["On the Relationship between the McNaughton Families of Languages and the Chomsky Hierarchy"],"prefix":"10.1007","author":[{"given":"M.","family":"Beaudry","sequence":"first","affiliation":[]},{"given":"M.","family":"Holzer","sequence":"additional","affiliation":[]},{"given":"G.","family":"Niemann","sequence":"additional","affiliation":[]},{"given":"F.","family":"Otto","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2002,3,19]]},"reference":[{"key":"30_CR1","unstructured":"M. Beaudry, M. Holzer, G. Niemann, and F. Otto. McNaughton languages. Mathematische Schriften Kassel 26\/00, Universit\u00e4t Kassel, November 2000.A revised version will appear in Theoret. Comput. Sci."},{"key":"30_CR2","doi-asserted-by":"publisher","first-page":"332","DOI":"10.1016\/0022-0000(85)90056-X","volume":"31","author":"L. Boasson","year":"1985","unstructured":"L. Boasson and G. S\u00e9nizergues. NTS languages are deterministic and congruential. J. Comput. System Sci., 31:332\u2013342, 1985.","journal-title":"J. Comput. System Sci."},{"key":"30_CR3","doi-asserted-by":"publisher","first-page":"231","DOI":"10.1016\/0304-3975(82)90036-6","volume":"19","author":"R.V. Book","year":"1982","unstructured":"R.V. Book, M. Jantzen, and C. Wrathall. Monadic Thue systems. Theoret. Comput. Sci., 19:231\u2013251, 1982.","journal-title":"Theoret. Comput. Sci."},{"key":"30_CR4","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4613-9771-7","volume-title":"String-Rewriting Systems","author":"R.V. Book","year":"1993","unstructured":"R.V. Book and F. Otto. String-Rewriting Systems. Springer-Verlag, NewYork, 1993."},{"key":"30_CR5","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1006\/inco.1997.2681","volume":"141","author":"G. Buntrock","year":"1998","unstructured":"G. Buntrock and F. Otto. Growing context-sensitive languages and Church-Rosser languages. Inform. and Comput., 141:1\u201336, 1998.","journal-title":"Inform. and Comput."},{"key":"30_CR6","doi-asserted-by":"crossref","unstructured":"S. Buss. The Boolean formula value problem is in ALOGTIME. In Proc. of 19th STOC, pp. 123\u2013131. ACM Press, 1987.","DOI":"10.1145\/28395.28409"},{"key":"30_CR7","doi-asserted-by":"publisher","first-page":"385","DOI":"10.1016\/0196-6774(87)90018-6","volume":"8","author":"S.A. Cook","year":"1987","unstructured":"S.A. Cook and P. McKenzie. Problems complete for deterministic logarithmic space. J. Algorithms, 8:385\u2013394, 1987.","journal-title":"J. Algorithms"},{"key":"30_CR8","doi-asserted-by":"publisher","first-page":"141","DOI":"10.1016\/S0304-3975(96)00267-8","volume":"181","author":"C. Herzog","year":"1997","unstructured":"C. Herzog. Pushdown automata with bounded nondeterminism and bounded ambiguity. Theoret. Comput. Sci., 181:141\u2013157, 1997.","journal-title":"Theoret. Comput. Sci."},{"key":"30_CR9","doi-asserted-by":"crossref","unstructured":"M. Holzer and K.-J. Lange. On the complexities of linear LL(1) and LR(1) grammars. In Z. \u00c9sik, editor, Proceedings 9th FCT, Lect. Notes Comput. Sci. 710, pp. 299\u2013308. Springer-Verlag, Berlin, 1993.","DOI":"10.1007\/3-540-57163-9_25"},{"key":"30_CR10","volume-title":"Introduction to Automata Theory, Languages, and Computation","author":"J.E. Hopcroft","year":"1979","unstructured":"J.E. Hopcroft and J.D. Ullman. Introduction to Automata Theory, Languages, and Computation. Addison-Wesley, Reading, M.A., 1979."},{"key":"30_CR11","first-page":"67","volume-title":"Handbook of Theoretical Computer Science","author":"D.S. Johnson","year":"1990","unstructured":"D.S. Johnson. A catalog of complexity classes. In J. van Leeuwen, editor, Handbook of Theoretical Computer Science, pp. 67\u2013161. The MIT Press\/Elsevier, Cambridge, MA\/Amsterdam, 1990."},{"key":"30_CR12","doi-asserted-by":"publisher","first-page":"105","DOI":"10.1016\/0304-3975(76)90068-2","volume":"3","author":"N.D. Jones","year":"1977","unstructured":"N.D. Jones and W.T. Laaser. Complete problems for deterministic polynomial time. Theoret. Comput. Sci., 3:105\u2013117, 1977.","journal-title":"Theoret. Comput. Sci."},{"key":"30_CR13","unstructured":"M. Lohrey. Private communication, November 2000."},{"key":"30_CR14","doi-asserted-by":"publisher","first-page":"119","DOI":"10.1016\/0304-3975(93)90213-D","volume":"113","author":"K. Madlener","year":"1993","unstructured":"K. Madlener, P. Narendran, F. Otto, and L. Zhang. On weakly confluent monadic stringrewriting systems. Theoret. Comput. Sci., 113:119\u2013165, 1993.","journal-title":"Theoret. Comput. Sci."},{"key":"30_CR15","doi-asserted-by":"publisher","first-page":"324","DOI":"10.1145\/42282.42284","volume":"35","author":"R. McNaughton","year":"1988","unstructured":"R. McNaughton, P. Narendran, and F. Otto. Church-Rosser Thue systems and formal languages. J. ACM, 35:324\u2013344, 1988.","journal-title":"J. ACM"},{"key":"30_CR16","unstructured":"P. Narendran. Church-Rosser and related Thue systems. PhD thesis, Rensselaer Polytechnic Institute, Troy, NewYork, 1984."},{"key":"30_CR17","unstructured":"G. Niemann. Regular Languages and Church-Rosser congruential languages. In R. Freund and A. Kelemenov\u00e1, editors, Grammar Systems 2000, Proceedings, pp. 359\u2013370. Silesian University, Opava, 2000."},{"key":"30_CR18","unstructured":"G. Niemann and J. Waldmann. Some regular languages that are Church-Rosser congruential. This volume."},{"key":"30_CR19","doi-asserted-by":"crossref","unstructured":"G. Niemann and F. Otto. The Church-Rosser languages are the deterministic variants of the growing context-sensitive languages. In M. Nivat, editor, Proceedings FoSSaCS\u201998, Lect. Notes Comput. Sci. 1378, pp. 243\u2013257. Springer-Verlag, Berlin, 1998.","DOI":"10.1007\/BFb0053554"},{"key":"30_CR20","doi-asserted-by":"publisher","first-page":"405","DOI":"10.1145\/322077.322083","volume":"25","author":"H. Sudborough","year":"1978","unstructured":"H. Sudborough. On the tape complexity of deterministic context-free languages. J. ACM, 25:405\u2013414, 1978.","journal-title":"J. ACM"}],"container-title":["Lecture Notes in Computer Science","Developments in Language Theory"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-46011-X_30","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,29]],"date-time":"2019-04-29T04:23:43Z","timestamp":1556511823000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-46011-X_30"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2002]]},"ISBN":["9783540434535","9783540460114"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/3-540-46011-x_30","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2002]]}}}