{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,9]],"date-time":"2024-09-09T14:00:07Z","timestamp":1725890407555},"publisher-location":"Berlin, Heidelberg","reference-count":18,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642316227"},{"type":"electronic","value":"9783642316234"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2012]]},"DOI":"10.1007\/978-3-642-31623-4_6","type":"book-chapter","created":{"date-parts":[[2012,7,9]],"date-time":"2012-07-09T05:03:34Z","timestamp":1341810214000},"page":"76-88","source":"Crossref","is-referenced-by-count":2,"title":["Removing Nondeterminism in Constant Height Pushdown Automata"],"prefix":"10.1007","author":[{"given":"Zuzana","family":"Bedn\u00e1rov\u00e1","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Viliam","family":"Geffert","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":"6_CR1","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. (ed.) DCFS 2011. LNCS, vol.\u00a06808, pp. 80\u201392. Springer, Heidelberg (2011)"},{"key":"6_CR2","doi-asserted-by":"publisher","first-page":"114","DOI":"10.1145\/322234.322243","volume":"28","author":"A. Chandra","year":"1981","unstructured":"Chandra, A., Kozen, D., Stockmeyer, L.: Alternation. J. ACM\u00a028, 114\u2013133 (1981)","journal-title":"J. ACM"},{"key":"6_CR3","doi-asserted-by":"publisher","first-page":"497","DOI":"10.1016\/S0304-3975(03)00136-1","volume":"302","author":"M. Chrobak","year":"2003","unstructured":"Chrobak, M.: Finite automata and unary languages. Theoret. Comput. Sci.\u00a0302, 497\u2013498 (2003); Corrigendum, ibid. 302, 497\u2013498 (2003)","journal-title":"Theoret. Comput. Sci."},{"key":"6_CR4","volume-title":"Computers and Intractability: A\u00a0Guide to the Theory of NP-Completeness","author":"M.R. Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability: A\u00a0Guide to the Theory of NP-Completeness. W.H.\u00a0Freeman and Co., New York (1979)"},{"key":"6_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. and Comput.\u00a0208, 385\u2013394 (2010); A preliminary version appears. In: Jto, M., Toyama, M. (eds.) DLT 2008. LNCS, vol. 5257, pp. 359\u2013370. Springer, Heidelberg (2008)","journal-title":"Inf. and Comput."},{"key":"6_CR6","doi-asserted-by":"publisher","first-page":"189","DOI":"10.1016\/S0304-3975(02)00403-6","volume":"295","author":"V. Geffert","year":"2003","unstructured":"Geffert, V., Mereghetti, C., Pighizzini, G.: Converting two-way nondeterministic unary automata into simpler automata. Theoret. Comput. Sci.\u00a0295, 189\u2013203 (2003)","journal-title":"Theoret. Comput. Sci."},{"key":"6_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. Univ. Comput. Sci.\u00a08, 193\u2013234 (2002)","journal-title":"J. Univ. Comput. Sci."},{"key":"6_CR8","unstructured":"Gruska, J.: Quantum Computing. McGraw-Hill (1999)"},{"key":"6_CR9","doi-asserted-by":"publisher","first-page":"145","DOI":"10.1016\/0022-0000(79)90025-4","volume":"19","author":"E.M. Gurari","year":"1979","unstructured":"Gurari, E.M., Ibarra, O.H.: Simple counter machines and number-theoretic problems. J.\u00a0Comput. Syst. Sci.\u00a019, 145\u2013162 (1979)","journal-title":"J.\u00a0Comput. Syst. Sci."},{"key":"6_CR10","doi-asserted-by":"crossref","unstructured":"Holzer, M., Kutrib, M.: Descriptional complexity \u2014 an introductory survey. In: Mart\u00edn-Vide, C. (ed.) Scientific Applications of Language Methods, pp. 1\u201358. Imperial College Press (2010)","DOI":"10.1142\/9781848165458_0001"},{"key":"6_CR11","volume-title":"Introduction to Automata Theory, Languages, and Computation","author":"J.E. Hopcroft","year":"2001","unstructured":"Hopcroft, J.E., Motwani, R., Ullman, J.D.: Introduction to Automata Theory, Languages, and Computation. Addison-Wesley, Reading (2001)"},{"key":"6_CR12","doi-asserted-by":"crossref","unstructured":"Hromkovi\u010d, J.: Algorithmics for Hard Problems, 2nd edn. Springer (2003)","DOI":"10.1007\/978-3-662-05269-3"},{"key":"6_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1007\/978-3-642-02737-6_4","volume-title":"Developments in Language Theory","author":"C.A. Kapoutsis","year":"2009","unstructured":"Kapoutsis, C.A.: Size Complexity of Two-Way Finite Automata. In: Diekert, V., Nowotka, D. (eds.) DLT 2009. LNCS, vol.\u00a05583, pp. 47\u201366. Springer, Heidelberg (2009)"},{"key":"6_CR14","doi-asserted-by":"publisher","first-page":"1976","DOI":"10.1137\/S009753979935431X","volume":"30","author":"C. Mereghetti","year":"2001","unstructured":"Mereghetti, C., Pighizzini, G.: Optimal simulations between unary automata. SIAM J. Comput.\u00a030, 1976\u20131992 (2001)","journal-title":"SIAM J. Comput."},{"key":"6_CR15","doi-asserted-by":"crossref","unstructured":"Meyer, A.R., Fischer, M.J.: Economy of description by automata, grammars and formal systems. In: IEEE 12th Symp. Switching and Automata Theory, pp. 188\u2013191 (1971)","DOI":"10.1109\/SWAT.1971.11"},{"key":"6_CR16","doi-asserted-by":"crossref","unstructured":"Nielsen, M.A., Chuang, I.L.: Quantum Computation and Quantum Information, 10th edn. Cambridge University Press (2010)","DOI":"10.1017\/CBO9780511976667"},{"key":"6_CR17","doi-asserted-by":"publisher","first-page":"114","DOI":"10.1147\/rd.32.0114","volume":"3","author":"M. Rabin","year":"1959","unstructured":"Rabin, M., Scott, D.: Finite automata and their decision problems. IBM J. Res. Develop.\u00a03, 114\u2013125 (1959)","journal-title":"IBM J. Res. Develop."},{"key":"6_CR18","doi-asserted-by":"publisher","first-page":"198","DOI":"10.1147\/rd.32.0198","volume":"3","author":"J.C. Shepherdson","year":"1959","unstructured":"Shepherdson, J.C.: The reduction of two-way automata to one-way automata. IBM J. Res. Develop.\u00a03, 198\u2013200 (1959)","journal-title":"IBM J. Res. Develop."}],"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_6.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,5,4]],"date-time":"2021-05-04T11:40:41Z","timestamp":1620128441000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-31623-4_6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012]]},"ISBN":["9783642316227","9783642316234"],"references-count":18,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-31623-4_6","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2012]]}}}