{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,13]],"date-time":"2026-02-13T23:10:35Z","timestamp":1771024235238,"version":"3.50.1"},"reference-count":38,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2014,6,9]],"date-time":"2014-06-09T00:00:00Z","timestamp":1402272000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["SIGACT News"],"published-print":{"date-parts":[[2014,6,9]]},"DOI":"10.1145\/2636805.2636821","type":"journal-article","created":{"date-parts":[[2014,6,24]],"date-time":"2014-06-24T12:16:16Z","timestamp":1403612176000},"page":"47-67","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":43,"title":["Complexity of input-driven pushdown automata"],"prefix":"10.1145","volume":"45","author":[{"given":"Alexander","family":"Okhotin","sequence":"first","affiliation":[{"name":"University of Turku, Turku, Finland"}]},{"given":"Kai","family":"Salomaa","sequence":"additional","affiliation":[{"name":"Queen's University, Kingston, Ontario, Canada"}]}],"member":"320","published-online":{"date-parts":[[2014,6,9]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1007\/11523468_89"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/1007352.1007390"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/1516512.1516518"},{"key":"e_1_2_1_4_1","volume-title":"Formal and Natural Computing","author":"Berstel J.","year":"2002","unstructured":"J. Berstel , L. Boasson , \"Balanced grammars and their languages\" , Formal and Natural Computing 2002 , LNCS 2300, 3--25. J. Berstel, L. Boasson, \"Balanced grammars and their languages\", Formal and Natural Computing 2002, LNCS 2300, 3--25."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(83)80049-7"},{"key":"e_1_2_1_6_1","first-page":"1","article-title":"Input driven languages are recognized in log n space","volume":"24","author":"von Braunm\u00fchl B.","year":"1985","unstructured":"B. von Braunm\u00fchl , R. Verbeek , \" Input driven languages are recognized in log n space \", Annals of Discrete Mathematics , 24 ( 1985 ), 1 -- 20 . B. von Braunm\u00fchl, R. Verbeek, \"Input driven languages are recognized in log n space\", Annals of Discrete Mathematics, 24 (1985), 1--20.","journal-title":"Annals of Discrete Mathematics"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/28395.28409"},{"key":"e_1_2_1_8_1","volume-title":"Mathematical Foundations of Computer Science (MFCS","author":"Chervet P.","year":"2007","unstructured":"P. Chervet , I. Walukiewicz , \"Minimizing variants of visibly pushdown automata\" , Mathematical Foundations of Computer Science (MFCS 2007 , Cesky Krumlov, Czech Republic , 26-31 August 2007), LNCS 4708, 135--146. P. Chervet, I. Walukiewicz, \"Minimizing variants of visibly pushdown automata\", Mathematical Foundations of Computer Science (MFCS 2007, Cesky Krumlov, Czech Republic, 26-31 August 2007), LNCS 4708, 135--146."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-39274-0_10"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-13089-2_18"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-39274-0_26"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(88)90148-2"},{"key":"e_1_2_1_13_1","unstructured":"Y. Gao N. Moreira R. Reis S. Yu \"A review on state complexity of individual operations\" Faculdade de Ciencias Universidade do Porto Technical Report DCC-2011-8 www.dcc.fc.up.pt\/dcc\/Pubs\/TReports\/TR11\/dcc-2011-08.pdf  Y. Gao N. Moreira R. Reis S. Yu \"A review on state complexity of individual operations\" Faculdade de Ciencias Universidade do Porto Technical Report DCC-2011-8 www.dcc.fc.up.pt\/dcc\/Pubs\/TReports\/TR11\/dcc-2011-08.pdf"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2008.08.002"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(67)80003-5"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2009.01.004"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1006\/inco.2001.3069"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2010.12.013"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1142\/S0129054105003418"},{"key":"e_1_2_1_21_1","volume-title":"3rd International Computer Science Symposium in Russia (CSR","author":"Limaye N.","year":"2008","unstructured":"N. Limaye , M. Mahajan , A. Meyer , \"On the complexity of membership and counting in heightdeterministic pushdown automata \", 3rd International Computer Science Symposium in Russia (CSR 2008 ), LNCS 5010, 240--251. N. Limaye, M. Mahajan, A. Meyer, \"On the complexity of membership and counting in heightdeterministic pushdown automata\", 3rd International Computer Science Symposium in Russia (CSR 2008), LNCS 5010, 240--251."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/322033.322037"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/321406.321411"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(76)90013-2"},{"key":"e_1_2_1_25_1","volume-title":"Automata, Languages and Programming (ICALP","author":"Mehlhorn K.","year":"1980","unstructured":"K. Mehlhorn , \"Pebbling mountain ranges and its application to DCFL-recognition\" , Automata, Languages and Programming (ICALP 1980 , Noordweijkerhout, The Netherlands , 14-18 July 1980), LNCS 85, 422--435. K. Mehlhorn, \"Pebbling mountain ranges and its application to DCFL-recognition\", Automata, Languages and Programming (ICALP 1980, Noordweijkerhout, The Netherlands, 14-18 July 1980), LNCS 85, 422--435."},{"key":"e_1_2_1_26_1","volume-title":"Mathematical Foundations of Computer Science (MFCS","author":"Nowotka D.","year":"2007","unstructured":"D. Nowotka , J. Srba , \"Height-deterministic pushdown automata\" , Mathematical Foundations of Computer Science (MFCS 2007 ), LNCS 4708, 125--134. D. Nowotka, J. Srba, \"Height-deterministic pushdown automata\", Mathematical Foundations of Computer Science (MFCS 2007), LNCS 4708, 125--134."},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.5555\/1946370.1946406"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2012.01.003"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cosrev.2013.06.001"},{"key":"e_1_2_1_30_1","doi-asserted-by":"crossref","unstructured":"A.\n      Okhotin X.\n      Piao K.\n      Salomaa \"Descriptional complexity of input-driven pushdown automata\" In: H. Bordihn M. Kutrib B. Truthe (Eds.) Languages Alive\n  : Essays Dedicated to J\u00fcrgen Dassow on the Occasion of His 65th Birthday LNCS\n   7300 2012 186--206.  A. Okhotin X. Piao K. Salomaa \"Descriptional complexity of input-driven pushdown automata\" In: H. Bordihn M. Kutrib B. Truthe (Eds.) Languages Alive: Essays Dedicated to J\u00fcrgen Dassow on the Occasion of His 65th Birthday LNCS 7300 2012 186--206.","DOI":"10.1007\/978-3-642-31644-9_13"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.5555\/2022896.2022931"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.5555\/2034006.2034052"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-09698-8_9"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.5555\/3173440.3173451"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2009.05.002"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(86)90047-5"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2010.11.021"},{"key":"e_1_2_1_38_1","volume-title":"Succinctness of Description of Context-Free, Regular and Unambiguous Languages. Ph. D. thesis","author":"Schmidt E.M.","year":"1978","unstructured":"E.M. Schmidt , Succinctness of Description of Context-Free, Regular and Unambiguous Languages. Ph. D. thesis , Cornell University , 1978 . E.M. Schmidt, Succinctness of Description of Context-Free, Regular and Unambiguous Languages. Ph. D. thesis, Cornell University, 1978."},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.2168\/LMCS-5(1:2)2009"}],"container-title":["ACM SIGACT News"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2636805.2636821","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2636805.2636821","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T20:14:35Z","timestamp":1750277675000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2636805.2636821"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,6,9]]},"references-count":38,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2014,6,9]]}},"alternative-id":["10.1145\/2636805.2636821"],"URL":"https:\/\/doi.org\/10.1145\/2636805.2636821","relation":{},"ISSN":["0163-5700"],"issn-type":[{"value":"0163-5700","type":"print"}],"subject":[],"published":{"date-parts":[[2014,6,9]]},"assertion":[{"value":"2014-06-09","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}