{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,9]],"date-time":"2024-09-09T15:21:30Z","timestamp":1725895290321},"publisher-location":"Berlin, Heidelberg","reference-count":19,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540882817"},{"type":"electronic","value":"9783540882824"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/978-3-540-88282-4_36","type":"book-chapter","created":{"date-parts":[[2008,9,24]],"date-time":"2008-09-24T07:46:38Z","timestamp":1222242398000},"page":"397-408","source":"Crossref","is-referenced-by-count":0,"title":["On Alternating Phrase-Structure Grammars"],"prefix":"10.1007","author":[{"given":"Etsuro","family":"Moriya","sequence":"first","affiliation":[]},{"given":"Friedrich","family":"Otto","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"36_CR1","doi-asserted-by":"publisher","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. Information and Computation\u00a0141, 1\u201336 (1998)","journal-title":"Information and Computation"},{"key":"36_CR2","first-page":"98","volume-title":"Proc. 17th FOCS","author":"A.K. Chandra","year":"1976","unstructured":"Chandra, A.K., Stockmeyer, L.J.: Alternation. In: Proc. 17th FOCS, pp. 98\u2013108. IEEE Computer Society Press, Los Alamitos (1976)"},{"key":"36_CR3","doi-asserted-by":"crossref","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. Journal of the Association for Computing Machinery\u00a028, 114\u2013133 (1981)","journal-title":"Journal of the Association for Computing Machinery"},{"key":"36_CR4","first-page":"1540","volume":"73","author":"Z.Z. Chen","year":"1990","unstructured":"Chen, Z.Z., Toda, S.: Grammatical characterizations of P and PSPACE. IEICIE Transactions on Information and Systems\u00a0E 73, 1540\u20131548 (1990)","journal-title":"IEICIE Transactions on Information and Systems"},{"key":"36_CR5","doi-asserted-by":"publisher","first-page":"456","DOI":"10.1016\/0022-0000(86)90062-0","volume":"33","author":"E. Dahlhaus","year":"1986","unstructured":"Dahlhaus, E., Warmuth, M.: Membership for growing context-sensitive grammars is polynomial. Journal of Computer and System Sciences\u00a033, 456\u2013472 (1986)","journal-title":"Journal of Computer and System Sciences"},{"key":"36_CR6","volume-title":"ntroduction to Automata Theory, Languages, and Computation","author":"J.E. Hopcroft","year":"1979","unstructured":"Hopcroft, J.E., Ullman, J.D.: Introduction to Automata Theory, Languages, and Computation. Addison-Wesley, Reading (1979)"},{"key":"36_CR7","doi-asserted-by":"publisher","first-page":"301","DOI":"10.1016\/0304-3975(92)90355-J","volume":"99","author":"O.H. Ibarra","year":"1992","unstructured":"Ibarra, O.H., Jiang, T., Wang, H.: A characterization of exponential-time languages by alternating context-free grammars. Theoretical Computer Science\u00a099, 301\u2013313 (1992)","journal-title":"Theoretical Computer Science"},{"key":"36_CR8","doi-asserted-by":"publisher","first-page":"492","DOI":"10.1016\/S0022-0000(70)80045-9","volume":"4","author":"T. Kasai","year":"1970","unstructured":"Kasai, T.: An infinite hierarchy between context-free and context-sensitive languages. Journal of Computer and Systems Sciences\u00a04, 492\u2013508 (1970)","journal-title":"Journal of Computer and Systems Sciences"},{"key":"36_CR9","volume-title":"Proc. 19th FOCS","author":"R.E. Ladner","year":"1978","unstructured":"Ladner, R.E., Lipton, R.J., Stockmeyer, L.J.: Alternating pushdown automata. In: Proc. 19th FOCS. IEEE Computer Society Press, Los Alamitos (1978)"},{"key":"36_CR10","doi-asserted-by":"publisher","first-page":"135","DOI":"10.1137\/0213010","volume":"13","author":"R.E. Ladner","year":"1984","unstructured":"Ladner, R.E., Lipton, R.J., Stockmeyer, L.J.: Alternating pushdown and stack automata. SIAM Journal on Computing\u00a013, 135\u2013155 (1984)","journal-title":"SIAM Journal on Computing"},{"key":"36_CR11","series-title":"Word, Language, Grammar","doi-asserted-by":"crossref","first-page":"175","DOI":"10.1007\/978-3-642-59136-5_4","volume-title":"Handbook of Formal Languages","author":"A. Mateescu","year":"1997","unstructured":"Mateescu, A., Salomaa, A.: Aspects of classical language theory. In: Rozenberg, G., Salomaa, A. (eds.) Handbook of Formal Languages. Word, Language, Grammar, vol.\u00a01, pp. 175\u2013251. Springer, Berlin (1997)"},{"key":"36_CR12","doi-asserted-by":"publisher","first-page":"360","DOI":"10.1016\/S0019-9958(64)90406-1","volume":"7","author":"G. Matthews","year":"1964","unstructured":"Matthews, G.: A note on symmetry in phrase structure grammars. Information and Control\u00a07, 360\u2013365 (1964)","journal-title":"Information and Control"},{"key":"36_CR13","doi-asserted-by":"publisher","first-page":"75","DOI":"10.1016\/0304-3975(89)90023-6","volume":"67","author":"E. Moriya","year":"1989","unstructured":"Moriya, E.: A grammatical characterization of alternating pushdown automata. Theoretical Computer Science\u00a067, 75\u201385 (1989)","journal-title":"Theoretical Computer Science"},{"key":"36_CR14","doi-asserted-by":"publisher","first-page":"183","DOI":"10.1016\/j.tcs.2004.12.029","volume":"337","author":"E. Moriya","year":"2005","unstructured":"Moriya, E., Hofbauer, D., Huber, M., Otto, F.: On state-alternating context-free grammars. Theoretical Computer Science\u00a0337, 183\u2013216 (2005)","journal-title":"Theoretical Computer Science"},{"key":"36_CR15","unstructured":"Moriya, E., Nakayama, S.: Grammatical characterizations of alternating pushdown automata and linear bounded automata. Gakujutsu Kenkyu, Series of Math., vol.\u00a045, pp. 13\u201324. School of Education, Waseda Univ. (1997) (in Japanese)"},{"key":"36_CR16","doi-asserted-by":"publisher","first-page":"889","DOI":"10.1093\/ietisy\/e90-d.6.889","volume":"90","author":"E. Moriya","year":"2007","unstructured":"Moriya, E., Otto, F.: Two ways of introducing alternation into context-free grammars and pushdown automata. IEICIE Transactions on Information and Systems\u00a0E 90- D, 889\u2013894 (2007)","journal-title":"IEICIE Transactions on Information and Systems"},{"key":"36_CR17","unstructured":"Moriya, E., Otto, F.: On alternating non-context-free gammars. Kasseler Informatik Schriften 2007, 6. Fachbereich Elektrotechnik\/Informatik, Universit\u00e4t Kassel (2007), \n                    \n                      https:\/\/kobra.bibliothek.uni-kassel.de\/handle\/urn:nbn:de:hebis:34-2007110719587"},{"key":"36_CR18","first-page":"519","volume":"6","author":"A. Okhotin","year":"2001","unstructured":"Okhotin, A.: Conjunctive grammars. Journal of Automata, Languages and Combinatorics\u00a06, 519\u2013535 (2001)","journal-title":"Journal of Automata, Languages and Combinatorics"},{"key":"36_CR19","first-page":"959","volume":"87","author":"F. Otto","year":"2004","unstructured":"Otto, F., Moriya, E.: Shrinking alternating two-pushdown automata. IEICIE Transactionns on Information and Systems\u00a0E 87- D, 959\u2013966 (2004)","journal-title":"IEICIE Transactionns on Information and Systems"}],"container-title":["Lecture Notes in Computer Science","Language and Automata Theory and Applications"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-88282-4_36.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T12:00:09Z","timestamp":1619524809000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-88282-4_36"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540882817","9783540882824"],"references-count":19,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-88282-4_36","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[]}}