{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,31]],"date-time":"2026-03-31T11:35:31Z","timestamp":1774956931024,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":21,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783642316227","type":"print"},{"value":"9783642316234","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2012]]},"DOI":"10.1007\/978-3-642-31623-4_16","type":"book-chapter","created":{"date-parts":[[2012,7,9]],"date-time":"2012-07-09T01:03:34Z","timestamp":1341795814000},"page":"209-221","source":"Crossref","is-referenced-by-count":2,"title":["Descriptional Complexity of Pushdown Store Languages"],"prefix":"10.1007","author":[{"given":"Andreas","family":"Malcher","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Katja","family":"Meckel","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Carlo","family":"Mereghetti","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Beatrice","family":"Palano","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"16_CR1","doi-asserted-by":"crossref","unstructured":"Autebert, J.-M., Berstel, J., Boasson, L.: Context-free languages and pushdown automata. In: Handbook of Formal Languages, vol.\u00a01, pp. 111\u2013174. Springer (1997)","DOI":"10.1007\/978-3-642-59136-5_3"},{"key":"16_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"80","DOI":"10.1007\/978-3-642-22600-7_7","volume-title":"DCFS 2011","author":"Z. Bedn\u00e1rov\u00e1","year":"2011","unstructured":"Bedn\u00e1rov\u00e1, Z., Geffert, V., Mereghetti, C., Palano, B.: The Size-Cost of Boolean Operations on Constant Height Deterministic Pushdown Automata. In: Holzer, M., Kutrib, M., Pighizzini, G. (eds.) DCFS 2011. LNCS, vol.\u00a06808, pp. 80\u201392. Springer, Heidelberg (2011)"},{"key":"16_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"135","DOI":"10.1007\/978-3-642-22600-7_11","volume-title":"DCFS 2011","author":"J. Dassow","year":"2011","unstructured":"Dassow, J., Manea, F., Truthe, B.: On contextual grammars with subregular selection languages. In: Holzer, M., Kutrib, M., Pighizzini, G. (eds.) DCFS 2011. LNCS, vol.\u00a06808, pp. 135\u2013146. Springer, Heidelberg (2011)"},{"key":"16_CR4","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"M.R. Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman and Co., San Francisco (1979)"},{"key":"16_CR5","doi-asserted-by":"publisher","first-page":"385","DOI":"10.1016\/j.ic.2010.01.002","volume":"208","author":"V. Geffert","year":"2010","unstructured":"Geffert, V., Mereghetti, C., Palano, B.: More concise representation of regular languages by automata and regular expressions. Inf. Comput.\u00a0208, 385\u2013394 (2010)","journal-title":"Inf. Comput."},{"key":"16_CR6","doi-asserted-by":"publisher","first-page":"172","DOI":"10.1145\/321371.321385","volume":"14","author":"S. Ginsburg","year":"1967","unstructured":"Ginsburg, S., Greibach, S.A., Harrison, M.A.: Stack automata and compiling. J. ACM\u00a014, 172\u2013201 (1967)","journal-title":"J. ACM"},{"key":"16_CR7","first-page":"193","volume":"8","author":"J. Goldstine","year":"2002","unstructured":"Goldstine, J., Kappes, M., Kintala, C.M.R., Leung, H., Malcher, A., Wotschke, D.: Descriptional complexity of machines with limited resources. J. UCS\u00a08, 193\u2013234 (2002)","journal-title":"J. UCS"},{"key":"16_CR8","doi-asserted-by":"publisher","first-page":"263","DOI":"10.1090\/S0002-9939-1967-0209086-1","volume":"18","author":"S.A. Greibach","year":"1967","unstructured":"Greibach, S.A.: A note on pushdown store automata and regular systems. Proc. Amer. Math. Soc.\u00a018, 263\u2013268 (1967)","journal-title":"Proc. Amer. Math. Soc."},{"key":"16_CR9","doi-asserted-by":"publisher","first-page":"91","DOI":"10.1145\/321495.321503","volume":"16","author":"S.A. Greibach","year":"1969","unstructured":"Greibach, S.A.: An infinite hierarchy of context-free languages. J. ACM\u00a016, 91\u2013106 (1969)","journal-title":"J. ACM"},{"key":"16_CR10","volume-title":"Introduction to Formal Language Theory","author":"M.A. Harrison","year":"1978","unstructured":"Harrison, M.A.: Introduction to Formal Language Theory. Addison-Wesley, Reading (1978)"},{"key":"16_CR11","doi-asserted-by":"crossref","unstructured":"Hartmanis, J.: Context-free languages and Turing machines computations. In: Proc. Symposium on Applied Mathematics, vol.\u00a019, pp. 42\u201351 (1967)","DOI":"10.1090\/psapm\/019\/0235938"},{"key":"16_CR12","doi-asserted-by":"crossref","unstructured":"Hoogeboom, H.J., Engelfriet, J.: Pushdown automata. In: Formal Languages and Applications. STUDFUZZ, vol. 148, pp. 117\u2013138. Springer (2004)","DOI":"10.1007\/978-3-540-39886-8_6"},{"key":"16_CR13","doi-asserted-by":"publisher","first-page":"563","DOI":"10.1142\/S0129054109006747","volume":"20","author":"M. Holzer","year":"2009","unstructured":"Holzer, M., Kutrib, M.: Nondeterministic finite automata\u2014recent results on the descriptional and computational complexity. Int. J. Found. Comp. Sci.\u00a020, 563\u2013580 (2009)","journal-title":"Int. J. Found. Comp. Sci."},{"key":"16_CR14","doi-asserted-by":"crossref","unstructured":"Holzer, M., Kutrib, M.: Descriptional complexity\u2014an introductory survey. In: Scientific Applications of Language Methods, pp. 1\u201358. Imperial College Press (2010)","DOI":"10.1142\/9781848165458_0001"},{"key":"16_CR15","volume-title":"Introduction 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":"16_CR16","doi-asserted-by":"publisher","first-page":"935","DOI":"10.1137\/0217058","volume":"17","author":"N. Immerman","year":"1988","unstructured":"Immerman, N.: Nondeterministic space is closed under complementation. SIAM J. Comput.\u00a017, 935\u2013938 (1988)","journal-title":"SIAM J. Comput."},{"key":"16_CR17","doi-asserted-by":"publisher","first-page":"68","DOI":"10.1016\/S0022-0000(75)80050-X","volume":"11","author":"N.D. Jones","year":"1975","unstructured":"Jones, N.D.: Space-bounded reducibility among combinatorial questions. J. Comput. System. Sci.\u00a011, 68\u201385 (1975)","journal-title":"J. Comput. System. Sci."},{"key":"16_CR18","unstructured":"Jones, N.D., Laaser, W.T.: Complete problems for deterministic polynomial time"},{"key":"16_CR19","doi-asserted-by":"publisher","first-page":"315","DOI":"10.1051\/ita:2006007","volume":"40","author":"C. Mereghetti","year":"2006","unstructured":"Mereghetti, C., Palano, B.: Quantum finite automata with control language. Theoretical Informatics and Applications\u00a040, 315\u2013332 (2006)","journal-title":"Theoretical Informatics and Applications"},{"key":"16_CR20","doi-asserted-by":"publisher","first-page":"279","DOI":"10.1007\/BF00299636","volume":"26","author":"R. Szelepcs\u00e9nyi","year":"1988","unstructured":"Szelepcs\u00e9nyi, R.: The method of forced enumeration for nondeterministic automata. Acta Inform.\u00a026, 279\u2013284 (1988)","journal-title":"Acta Inform."},{"key":"16_CR21","doi-asserted-by":"crossref","unstructured":"Yu, S.: Regular languages. In: Handbook of Formal Languages, vol.\u00a01, pp. 41\u2013110. Springer (1997)","DOI":"10.1007\/978-3-642-59136-5_2"}],"container-title":["Lecture Notes in Computer Science","Descriptional Complexity of Formal Systems"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-31623-4_16.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,5,4]],"date-time":"2021-05-04T07:40:35Z","timestamp":1620114035000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-31623-4_16"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012]]},"ISBN":["9783642316227","9783642316234"],"references-count":21,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-31623-4_16","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012]]}}}