{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,1]],"date-time":"2022-04-01T08:57:46Z","timestamp":1648803466918},"reference-count":32,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2007,7,10]],"date-time":"2007-07-10T00:00:00Z","timestamp":1184025600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2008,5]]},"DOI":"10.1007\/s00224-007-9004-y","type":"journal-article","created":{"date-parts":[[2007,7,16]],"date-time":"2007-07-16T23:14:00Z","timestamp":1184627640000},"page":"488-518","source":"Crossref","is-referenced-by-count":4,"title":["On the Complexity of 2-Monotone Restarting Automata"],"prefix":"10.1007","volume":"42","author":[{"given":"Tomasz","family":"Jurdzi\u0144ski","sequence":"first","affiliation":[]},{"given":"Friedrich","family":"Otto","sequence":"additional","affiliation":[]},{"given":"Franti\u0161ek","family":"Mr\u00e1z","sequence":"additional","affiliation":[]},{"given":"Martin","family":"Pl\u00e1tek","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2007,7,10]]},"reference":[{"key":"9004_CR1","first-page":"613","volume":"13","author":"J.W. Bresnan","year":"1983","unstructured":"Bresnan, J.W., Kaplan, R.M., Peters, S., Zaenen, A.: Cross-serial dependencies in Dutch. Linguist. Inq. 13, 613\u2013635 (1983)","journal-title":"Linguist. Inq."},{"key":"9004_CR2","unstructured":"Buntrock, G.: Wachsende kontext-sensitive Sprachen. Habilitationsschrift, Fakult\u00e4t f\u00fcr Mathematik und Informatik, Universit\u00e4t W\u00fcrzburg (1996)"},{"key":"9004_CR3","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1006\/inco.1997.2681","volume":"141","author":"G. Buntrock","year":"1998","unstructured":"Buntrock, G., Otto, F.: Growing context-sensitive languages and Church-Rosser languages. Inf. Comput. 141, 1\u201336 (1998)","journal-title":"Inf. Comput."},{"key":"9004_CR4","doi-asserted-by":"crossref","first-page":"456","DOI":"10.1016\/0022-0000(86)90062-0","volume":"33","author":"E. Dahlhaus","year":"1986","unstructured":"Dahlhaus, E., Warmuth, M.K.: Membership for growing context-sensitive grammars is polynomial. J. Comput. Syst. Sci. 33, 456\u2013472 (1986)","journal-title":"J. Comput. Syst. Sci."},{"key":"9004_CR5","unstructured":"Dikovsky, A., Modina, L.: Dependencies on the other side of the curtain. In: Kahane, S. (ed.) Les grammaires de d\u00e9pendance. Trait. Autom. Langues (TAL) 41, 79\u2013111 (2000)"},{"key":"9004_CR6","doi-asserted-by":"crossref","first-page":"69","DOI":"10.1007\/978-94-009-1337-0_3","volume-title":"Natural Language Parsing and Linguistic Theories","author":"G. Gazdar","year":"1988","unstructured":"Gazdar, G.: Applicability of indexed grammars to natural languages. In: Reyle, U., Rohrer, C. (eds.) Natural Language Parsing and Linguistic Theories, pp.\u00a069\u201394. Reidel, Dordrecht (1988)"},{"key":"9004_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"283","DOI":"10.1007\/3-540-60249-6_60","volume-title":"FCT\u201995, Proc.","author":"P. Jan\u010dar","year":"1995","unstructured":"Jan\u010dar, P., Mr\u00e1z, F., Pl\u00e1tek, M., Vogel, J.: Restarting automata. In: Reichel, H. (ed.) FCT\u201995, Proc. Lecture Notes in Computer Science, vol.\u00a0965, pp.\u00a0283\u2013292. Springer, Berlin (1995)"},{"key":"9004_CR8","first-page":"102","volume-title":"Developements in Language Theory II, Proc.","author":"P. Jan\u010dar","year":"1996","unstructured":"Jan\u010dar, P., Mr\u00e1z, F., Pl\u00e1tek, M., Proch\u00e1zka, M., Vogel, J.: Restarting automata, Marcus grammars and context-free languages. In: Dassow, J., Rozenberg, G., Solomaa, A. (eds.) Developements in Language Theory II, Proc., pp.\u00a0102\u2013111. World Scientific, Singapore (1996)"},{"key":"9004_CR9","first-page":"287","volume":"4","author":"P. Jan\u010dar","year":"1999","unstructured":"Jan\u010dar, P., Mr\u00e1z, F., Pl\u00e1tek, M., Vogel, J.: On monotonic automata with a\u00a0restart operation. J. Autom. Lang. Comb. 4, 287\u2013311 (1999)","journal-title":"J. Autom. Lang. Comb."},{"key":"9004_CR10","doi-asserted-by":"crossref","first-page":"206","DOI":"10.1017\/CBO9780511597855.007","volume-title":"Natural Language Parsing\u2014Psychological, Computational, and Theoretical Perspectives","author":"A.K. Joshi","year":"1985","unstructured":"Joshi, A.K.: Tree adjoining grammars: how much context-sensitivity is required to provide reasonable structural descriptions?. In: Dowty, D., Karttunen, L., Zwicky, A. (eds.) Natural Language Parsing\u2014Psychological, Computational, and Theoretical Perspectives, pp.\u00a0206\u2013250. Cambridge University Press, New York (1985)"},{"key":"9004_CR11","doi-asserted-by":"crossref","first-page":"136","DOI":"10.1016\/S0022-0000(75)80019-5","volume":"10","author":"A.K. Joshi","year":"1975","unstructured":"Joshi, A.K., Levy, L.S., Takahashi, M.: Tree adjunct grammars. J. Comput. Syst. Sci. 10, 136\u2013163 (1975)","journal-title":"J. Comput. Syst. Sci."},{"key":"9004_CR12","doi-asserted-by":"crossref","first-page":"361","DOI":"10.1142\/S0129054107004723","volume":"18","author":"T. Jurdzi\u0144ski","year":"2007","unstructured":"Jurdzi\u0144ski, T., Otto, F.: Shrinking restarting automata. Int. J. Found. Comput. Sci. 18, 361\u2013385 (2007). A preliminary short version appeared in: J\u0119drzejowicz, J., Szepietowski, A. (eds.) Mathematical Foundations of Computer Science, MFCS 2005, Proc. Lecture Notes in Computer Science, vol.\u00a03618, pp.\u00a0532\u2013543. Springer, Berlin (2005)","journal-title":"Int. J. Found. Comput. Sci."},{"key":"9004_CR13","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/j.tcs.2006.08.029","volume":"369","author":"T. Jurdzi\u0144ski","year":"2006","unstructured":"Jurdzi\u0144ski, T., Mr\u00e1z, F., Otto, F., Pl\u00e1tek, M.: Degrees of non-monotonicity for restarting automata. Theor. Comput. Sci. 369, 1\u201334 (2006)","journal-title":"Theor. Comput. Sci."},{"key":"9004_CR14","first-page":"407","volume":"9","author":"T. Jurdzi\u0144ski","year":"2004","unstructured":"Jurdzi\u0144ski, T., Lory\u015b, K., Niemann, G., Otto, F.: Some results on RWW- and RRWW-automata and their relation to the class of growing context-sensitive languages. J. Autom. Lang. Comb. 9, 407\u2013437 (2004)","journal-title":"J. Autom. Lang. Comb."},{"key":"9004_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"249","DOI":"10.1007\/978-3-540-30550-7_21","volume-title":"Developments in Language Theory, DLT 2004, Proc.","author":"T. Jurdzi\u0144ski","year":"2004","unstructured":"Jurdzi\u0144ski, T., Otto, F., Mr\u00e1z, F., Pl\u00e1tek, M.: On left-monotone deterministic restarting automata. In: Calude, C.S., Calude, E., Dinneen, M.J. (eds.) Developments in Language Theory, DLT 2004, Proc. Lecture Notes in Computer Science, vol.\u00a03340, pp.\u00a0249\u2013260. Springer, Berlin (2004)"},{"key":"9004_CR16","unstructured":"Lautemann, C.: One pushdown and a\u00a0small tape. In: Wagner, K.W. (ed.) Dirk Siefkes zum 50. Geburtstag, pp.\u00a042\u201347. Technische Universit\u00e4t Berlin and Universit\u00e4t Augsburg (1988)"},{"key":"9004_CR17","doi-asserted-by":"crossref","first-page":"324","DOI":"10.1145\/42282.42284","volume":"35","author":"R. McNaughton","year":"1988","unstructured":"McNaughton, R., Narendran, P., Otto, F.: Church-Rosser Thue systems and formal languages. J. Assoc. Comput. Mach. 35, 324\u2013344 (1988)","journal-title":"J. Assoc. Comput. Mach."},{"key":"9004_CR18","first-page":"103","volume-title":"Developments in Language Theory\u2014Foundations, Applications, and Perspectives, DLT 1999, Proc.","author":"G. Niemann","year":"2000","unstructured":"Niemann, G., Otto, F.: Restarting automata, Church-Rosser languages, and representations of r.e. languages. In: Rozenberg, G., Thomas, W. (eds.) Developments in Language Theory\u2014Foundations, Applications, and Perspectives, DLT 1999, Proc., pp.\u00a0103\u2013114. World Scientific, Singapore (2000)"},{"key":"9004_CR19","doi-asserted-by":"crossref","first-page":"341","DOI":"10.1142\/9789812810908_0026","volume-title":"Words, Semigroups, and Transductions. Essays in Honour of Gabriel Thierrin, On the Occasion of His 80th Birthday","author":"G. Niemann","year":"2001","unstructured":"Niemann, G., Otto, F.: On the power of RRWW-automata. In: Ito, M., P\u0103un, G., Yu, S. (eds.) Words, Semigroups, and Transductions. Essays in Honour of Gabriel Thierrin, On the Occasion of His 80th Birthday, pp.\u00a0341\u2013355. World Scientific, Singapore (2001)"},{"key":"9004_CR20","doi-asserted-by":"crossref","first-page":"352","DOI":"10.1142\/9789812704979_0027","volume-title":"Words, Languages and Combinatorics III, Proc.","author":"G. Niemann","year":"2003","unstructured":"Niemann, G., Otto, F.: Further results on restarting automata. In: Ito, M., Imaoka, T. (eds.) Words, Languages and Combinatorics III, Proc., pp.\u00a0352\u2013369. World Scientific, Singapore (2003)"},{"key":"9004_CR21","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/j.ic.2004.09.003","volume":"197","author":"G. Niemann","year":"2005","unstructured":"Niemann, G., Otto, F.: The Church-Rosser languages are the deterministic variants of the growing context-sensitive languages. Inf. Comput. 197, 1\u201321 (2005). A\u00a0preliminary short version appeared in: Nivat, M. (ed.) FoSSaCS 1998, Proc. Lecture Notes in Computer Science, vol.\u00a01378, pp.\u00a0243\u2013257. Springer, Berlin (1998)","journal-title":"Inf. Comput."},{"key":"9004_CR22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"82","DOI":"10.1007\/978-3-540-39398-6_12","volume-title":"TSD 2003, Proc.","author":"K. Oliva","year":"2003","unstructured":"Oliva, K., Kv\u011bto\u0148, P., Ondru\u0161ka, R.: The computational complexity of rule-based part-of-speech tagging. In: Matou\u0161ek, V., Mautner, P. (eds.) TSD 2003, Proc. Lecture Notes in Computer Science, vol.\u00a02807, pp.\u00a082\u201389. Springer, Berlin (2003)"},{"key":"9004_CR23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"55","DOI":"10.1007\/3-540-45007-6_5","volume-title":"Developments in Language Theory, DLT 2003, Proc.","author":"F. Otto","year":"2003","unstructured":"Otto, F.: Restarting automata and their relations to the Chomsky hierarchy. In: Esik, Z., F\u00fcl\u00f6p, Z. (eds.) Developments in Language Theory, DLT 2003, Proc. Lecture Notes in Computer Science, vol.\u00a02710, pp.\u00a055\u201374. Springer, Berlin (2003)"},{"key":"9004_CR24","doi-asserted-by":"crossref","unstructured":"Pl\u00e1tek, M.: Composition of translation with D-trees. In: COLLING\u201982, Proc., pp.\u00a0313\u2013318 (1982)","DOI":"10.3115\/991813.991863"},{"key":"9004_CR25","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"316","DOI":"10.1007\/3-540-45627-9_28","volume-title":"SOFSEM\u201901, Proc.","author":"M. Pl\u00e1tek","year":"2001","unstructured":"Pl\u00e1tek, M.: Two-way restarting automata and j-monotonicity. In: Pacholski, L., Ru\u017ei\u010dka, P. (eds.) SOFSEM\u201901, Proc. Lecture Notes in Computer Science, vol.\u00a02234, pp.\u00a0316\u2013325. Springer, Berlin (2001)"},{"key":"9004_CR26","unstructured":"Pl\u00e1tek, M., Mr\u00e1z, F.: Degrees of (non)monotonicity of RRW-automata. In: Dassow, J., Wotschke, D. (eds.) Preproceedings of the 3rd Workshop on Descriptional Complexity of Automata, Grammars and Related Structures, Report No. 16, pp.\u00a0159\u2013165. Fakult\u00e4t f\u00fcr Informatik, Universit\u00e4t Magdeburg (2001)"},{"key":"9004_CR27","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/S0019-9958(78)90010-4","volume":"38","author":"M. Pl\u00e1tek","year":"1978","unstructured":"Pl\u00e1tek, M., Sgall, P.: A\u00a0scale of context-sensitive languages: application to natural language. Inf. Control 38, 1\u201320 (1978)","journal-title":"Inf. Control"},{"key":"9004_CR28","unstructured":"Pl\u00e1tek, M., Lopatkov\u00e1, M., Oliva, K.: Restarting automata: motivations and applications. In: Holzer, M. (ed.) Workshop \u2018Petrinetze\u2019 and 13. Theorietag \u2018Formale Sprachen und Automaten,\u2019 Proc., pp.\u00a090\u201396. Institut f\u00fcr Informatik, Technische Universit\u00e4t M\u00fcnchen (2003)"},{"key":"9004_CR29","unstructured":"Pollard, C.: Generalized phrase structure grammars, head grammars and natural language. Ph.D. dissertation, Stanford University (1984)"},{"key":"9004_CR30","doi-asserted-by":"crossref","first-page":"333","DOI":"10.1007\/BF00630917","volume":"8","author":"S. Shieber","year":"1985","unstructured":"Shieber, S.: Evidence against the context-freeness of natural language. Linguist. Philos. 8, 333\u2013343 (1985)","journal-title":"Linguist. Philos."},{"key":"9004_CR31","doi-asserted-by":"crossref","first-page":"523","DOI":"10.2307\/414385","volume":"61","author":"M.J. Steedman","year":"1985","unstructured":"Steedman, M.J.: Dependency and coordination in the grammar of Dutch and English. Language 61, 523\u2013568 (1985)","journal-title":"Language"},{"key":"9004_CR32","doi-asserted-by":"crossref","first-page":"511","DOI":"10.1007\/BF01191624","volume":"27","author":"K. Vijay-Shankar","year":"1994","unstructured":"Vijay-Shankar, K., Weir, D.J.: The equivalence of four extensions of context-free grammars. Math. Syst. Theory 27, 511\u2013546 (1994)","journal-title":"Math. Syst. Theory"}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-007-9004-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00224-007-9004-y\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-007-9004-y","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,24]],"date-time":"2019-05-24T11:51:33Z","timestamp":1558698693000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00224-007-9004-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007,7,10]]},"references-count":32,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2008,5]]}},"alternative-id":["9004"],"URL":"https:\/\/doi.org\/10.1007\/s00224-007-9004-y","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"value":"1432-4350","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2007,7,10]]}}}