{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T22:47:44Z","timestamp":1725662864732},"publisher-location":"Berlin, Heidelberg","reference-count":11,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540088608"},{"type":"electronic","value":"9783540358077"}],"license":[{"start":{"date-parts":[[1978,1,1]],"date-time":"1978-01-01T00:00:00Z","timestamp":252460800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1978]]},"DOI":"10.1007\/3-540-08860-1_26","type":"book-chapter","created":{"date-parts":[[2012,2,25]],"date-time":"2012-02-25T16:34:36Z","timestamp":1330187676000},"page":"353-362","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["States can sometimes do more than stack symbols in PDA's"],"prefix":"10.1007","author":[{"given":"John K.","family":"Price","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Detlef","family":"Wotschke","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,5,26]]},"reference":[{"key":"26_CR1","doi-asserted-by":"crossref","unstructured":"M. M. Geller, H. B. Hunt, III, T. G. Szymanski and J. D. Ullman, Economy of Description by Parsers, DPDAs and PDAs, 16th Annual Symposium on Foundations of Computer Science, 1975.","DOI":"10.1109\/SFCS.1975.12"},{"key":"26_CR2","doi-asserted-by":"crossref","unstructured":"S. Ginsburg, The Mathematical Theory of Context-Free Languages, McGraw-Hill Book Company, 1966.","DOI":"10.1145\/321312.321318"},{"key":"26_CR3","doi-asserted-by":"publisher","first-page":"582","DOI":"10.1145\/321978.321980","volume":"23","author":"S. Ginsburg","year":"1976","unstructured":"S. Ginsburg and N. Lynch, Size complexity in context-free grammar forms, J. ACM 23 (1976), 582\u2013598.","journal-title":"J. ACM"},{"key":"26_CR4","doi-asserted-by":"publisher","first-page":"423","DOI":"10.1137\/0304034","volume":"4","author":"S. Ginsburg","year":"1966","unstructured":"S. Ginsburg and E. H. Spanier, Finite-turn pushdown automata, SIAM J. Control 4, 423\u2013434, 1966.","journal-title":"SIAM J. Control"},{"key":"26_CR5","doi-asserted-by":"crossref","unstructured":"J. Gruska, Descriptional complexity (of languages), a short survey, Proc. Conf. on Math. Foundations of Comp. Sci., Gdansk, September, 1976 (Springer Lecture Notes in Comp. Sci., Vol. 45), 65\u201380.","DOI":"10.1007\/3-540-07854-1_162"},{"key":"26_CR6","doi-asserted-by":"crossref","unstructured":"H. B. Hunt, III, and T. G. Szymanski, On the complexity of grammar and related problems, Proc. 7th ACM Symp. on Theory of Computing, May, 1975, 54\u201365.","DOI":"10.1145\/800116.803753"},{"key":"26_CR7","doi-asserted-by":"crossref","unstructured":"A. R. Meyer and M. J. Fischer, Economy of description by automata, grammars, and formal systems, Proc. 12th Symp. on Switching and Automata Theory, October, 1971, 188\u2013191.","DOI":"10.1109\/SWAT.1971.11"},{"issue":"3","key":"26_CR8","doi-asserted-by":"publisher","first-page":"191","DOI":"10.1007\/BF01694004","volume":"2","author":"W. Ogden","year":"1968","unstructured":"W. Ogden, A Helpful Result for Proving Inherent Ambiguity, Mathematical Systems Theory 2:3 (1968), 191\u2013194.","journal-title":"Mathematical Systems Theory"},{"key":"26_CR9","doi-asserted-by":"crossref","unstructured":"A. Pirick\u00e1, Complexity and normal forms of context-free languages, Proc. Conf. on Math. Foundations of Comp. Sci., June, 1974 (Springer Lecture Notes in Comp. Sci., Vol. 28), 292\u2013297.","DOI":"10.1007\/3-540-07162-8_688"},{"key":"26_CR10","doi-asserted-by":"crossref","unstructured":"A. Pirick\u00e1-Kelemenov\u00e1, Greibach normal form complexity, Proc. Conf. on Math. Foundations of Comp. Sci., September, 1975 (Springer Lecture Notes in Comp. Sci., Vol. 32), 344\u2013350.","DOI":"10.1007\/3-540-07389-2_219"},{"key":"26_CR11","doi-asserted-by":"publisher","first-page":"139","DOI":"10.1016\/S0019-9958(76)90173-X","volume":"32","author":"L. G. Valiant","year":"1976","unstructured":"L. G. Valiant, A note on the succinctness of descriptions of deterministic languages, Inf. and Contr. 32 (1976), 139\u2013145.","journal-title":"Inf. and Contr."}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-08860-1_26","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,12,31]],"date-time":"2021-12-31T00:54:06Z","timestamp":1640912046000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-08860-1_26"}},"subtitle":["Preliminary version"],"short-title":[],"issued":{"date-parts":[[1978]]},"ISBN":["9783540088608","9783540358077"],"references-count":11,"URL":"https:\/\/doi.org\/10.1007\/3-540-08860-1_26","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1978]]},"assertion":[{"value":"26 May 2005","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}