{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T05:00:23Z","timestamp":1725512423199},"publisher-location":"Berlin, Heidelberg","reference-count":16,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540713883"},{"type":"electronic","value":"9783540713890"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/978-3-540-71389-0_25","type":"book-chapter","created":{"date-parts":[[2007,7,1]],"date-time":"2007-07-01T20:22:53Z","timestamp":1183321373000},"page":"346-360","source":"Crossref","is-referenced-by-count":9,"title":["Complexity Results on Balanced Context-Free Languages"],"prefix":"10.1007","author":[{"given":"Akihiko","family":"Tozawa","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yasuhiko","family":"Minamide","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"25_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1007\/3-540-45711-9_1","volume-title":"Formal and Natural Computing","author":"J. Berstel","year":"2002","unstructured":"Berstel, J., Boasson, L.: Balanced grammars and their languages. In: Brauer, W., et al. (eds.) Formal and Natural Computing. LNCS, vol.\u00a02300, pp. 3\u201325. Springer, Heidelberg (2002)"},{"issue":"9","key":"25_CR2","doi-asserted-by":"publisher","first-page":"649","DOI":"10.1007\/s00236-002-0085-4","volume":"38","author":"J. Berstel","year":"2002","unstructured":"Berstel, J., Boasson, L.: Formal properties of XML grammars and languages. Acta Informatica\u00a038(9), 649\u2013671 (2002)","journal-title":"Acta Informatica"},{"key":"25_CR3","series-title":"Teubner Studienb\u00fccher","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-663-09367-1","volume-title":"Transductions and Context-Free Languages","author":"J. Berstel","year":"1979","unstructured":"Berstel, J.: Transductions and Context-Free Languages. Teubner Studienb\u00fccher. Teubner, Wiesbaden (1979)"},{"issue":"1","key":"25_CR4","doi-asserted-by":"publisher","first-page":"114","DOI":"10.1145\/322234.322243","volume":"28","author":"A.K. Chandra","year":"1981","unstructured":"Chandra, A.K., Kozen, D.C., Stockmeyer, L.J.: Alternation. J. ACM\u00a028(1), 114\u2013133 (1981), doi:10.1145\/322234.322243","journal-title":"J. ACM"},{"key":"25_CR5","unstructured":"Hagenah, C.: Gleichungen mit regul\u00e4ren Randbedingungen \u00fcber freien Gruppen. PhD thesis, Universit\u00e4t Stuttgart, Fakult\u00e4t Informatik (2000)"},{"key":"25_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","DOI":"10.1007\/11823230_22","volume-title":"Static Analysis","author":"C. Kirkegaard","year":"2006","unstructured":"Kirkegaard, C.: Static analysis for Java Servlets and JSP. In: Yi, K. (ed.) SAS 2006. LNCS, vol.\u00a04134, Springer, Heidelberg (2006)"},{"issue":"3","key":"25_CR7","doi-asserted-by":"publisher","first-page":"269","DOI":"10.1016\/S0019-9958(67)90564-5","volume":"11","author":"D.E. Knuth","year":"1967","unstructured":"Knuth, D.E.: A characterization of parenthesis languages. Information and Control\u00a011(3), 269\u2013289 (1967)","journal-title":"Information and Control"},{"key":"25_CR8","unstructured":"Lawler, E.: Combinatorial Optimization: Networks and Matroids (1976)"},{"issue":"3","key":"25_CR9","doi-asserted-by":"crossref","first-page":"490","DOI":"10.1145\/321406.321411","volume":"14","author":"R. McNaughton","year":"1967","unstructured":"McNaughton, R.: Parenthesis grammars. Journal of the Association for Computing Machinery\u00a014(3), 490\u2013500 (1967)","journal-title":"Journal of the Association for Computing Machinery"},{"key":"25_CR10","first-page":"125","volume-title":"Conf. Rec. 13th IEEE Symp. on Switching and Automata Theory","author":"A.R. Meyer","year":"1972","unstructured":"Meyer, A.R., Stockmeyer, L.J.: The equivalence problem for regular expressions with squaring requires exponential space. In: Conf. Rec. 13th IEEE Symp. on Switching and Automata Theory, pp. 125\u2013129. IEEE Computer Society Press, Los Alamitos (1972)"},{"key":"25_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"357","DOI":"10.1007\/11924661_22","volume-title":"Programming Languages and Systems","author":"Y. Minamide","year":"2006","unstructured":"Minamide, Y., Tozawa, A.: XML validation for context-free grammars. In: Kobayashi, N. (ed.) APLAS 2006. LNCS, vol.\u00a04279, pp. 357\u2013373. Springer, Heidelberg (2006)"},{"key":"25_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"460","DOI":"10.1007\/BFb0049431","volume-title":"Algorithms - ESA \u201994","author":"W. Plandowski","year":"1994","unstructured":"Plandowski, W.: Testing equivalence of morphisms on context-free languages. In: van Leeuwen, J. (ed.) ESA 1994. LNCS, vol.\u00a0855, pp. 460\u2013470. Springer, Heidelberg (1994)"},{"key":"25_CR13","unstructured":"Schleimer, S.: Polynomial-time word problems (2006), http:\/\/front.math.ucdavis.edu\/math.GR\/0608563"},{"issue":"3","key":"25_CR14","doi-asserted-by":"publisher","first-page":"424","DOI":"10.1137\/0219027","volume":"19","author":"H. Seidl","year":"1990","unstructured":"Seidl, H.: Deciding equivalence of finite tree automata. SIAM Journal on Computing\u00a019(3), 424\u2013437 (1990)","journal-title":"SIAM Journal on Computing"},{"key":"25_CR15","doi-asserted-by":"crossref","unstructured":"Stockmeyer, L.J., Meyer, A.R.: Word problems requiring exponential time: Preliminary report. In: Stoc, pp. 1\u20139 (1973)","DOI":"10.1145\/800125.804029"},{"issue":"1","key":"25_CR16","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/S0019-9958(75)90058-3","volume":"21","author":"M. Takahashi","year":"1975","unstructured":"Takahashi, M.: Generalizations of regular sets and their application to a study of context-free languages. Information and Control\u00a021(1), 1\u201336 (1975)","journal-title":"Information and Control"}],"container-title":["Lecture Notes in Computer Science","Foundations of Software Science and Computational Structures"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-71389-0_25.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,19]],"date-time":"2020-11-19T05:19:38Z","timestamp":1605763178000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-71389-0_25"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540713883","9783540713890"],"references-count":16,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-71389-0_25","relation":{},"subject":[]}}