{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,9]],"date-time":"2024-09-09T18:10:58Z","timestamp":1725905458262},"publisher-location":"Cham","reference-count":15,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319628080"},{"type":"electronic","value":"9783319628097"}],"license":[{"start":{"date-parts":[[2017,1,1]],"date-time":"2017-01-01T00:00:00Z","timestamp":1483228800000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2017]]},"DOI":"10.1007\/978-3-319-62809-7_27","type":"book-chapter","created":{"date-parts":[[2017,7,20]],"date-time":"2017-07-20T04:37:57Z","timestamp":1500525477000},"page":"353-364","source":"Crossref","is-referenced-by-count":2,"title":["One-Way Bounded-Error Probabilistic Pushdown Automata and Kolmogorov Complexity"],"prefix":"10.1007","author":[{"given":"Tomoyuki","family":"Yamakami","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2017,7,21]]},"reference":[{"key":"27_CR1","first-page":"143","volume":"14","author":"Y Bar-Hillel","year":"1961","unstructured":"Bar-Hillel, Y., Perles, M., Shamir, E.: On formal properties of simple phrase-structure grammars. Z. Phonetik Sprachwiss. Kommunikationsforsch 14, 143\u2013172 (1961)","journal-title":"Z. Phonetik Sprachwiss. Kommunikationsforsch"},{"key":"27_CR2","doi-asserted-by":"crossref","first-page":"1389","DOI":"10.1137\/S0097539702417754","volume":"32","author":"O Glier","year":"2003","unstructured":"Glier, O.: Kolmogorov complexity and deterministic context-free languages. SIAM J. Comput. 32, 1389\u20131394 (2003)","journal-title":"SIAM J. Comput."},{"key":"27_CR3","volume-title":"Introduction to Automata Theory, Languages, and Computation","author":"JE Hopcroft","year":"1979","unstructured":"Hopcroft, J.E., Ullman, J.D.: Introduction to Automata Theory, Languages, and Computation. Addison-Wesley, Reading (1979)"},{"key":"27_CR4","doi-asserted-by":"crossref","first-page":"982","DOI":"10.1016\/j.ic.2009.11.001","volume":"208","author":"J Hromkovi\u010d","year":"2010","unstructured":"Hromkovi\u010d, J., Schnitger, G.: On probabilistic pushdown automata. Inf. Comput. 208, 982\u2013995 (2010)","journal-title":"Inf. Comput."},{"key":"27_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"187","DOI":"10.1007\/3-540-63248-4_16","volume-title":"Randomization and Approximation Techniques in Computer Science","author":"J Kan\u0327eps","year":"1997","unstructured":"Kan\u0327eps, J., Geidmanis, D., Freivalds, R.: Tally languages accepted by Monte Carlo pushdown automata. In: Rolim, J. (ed.) RANDOM 1997. LNCS, vol. 1269, pp. 187\u2013195. Springer, Heidelberg (1997). doi: 10.1007\/3-540-63248-4_16"},{"key":"27_CR6","volume-title":"Elements of the Theory of Computation","author":"HR Lewis","year":"1998","unstructured":"Lewis, H.R., Papadimitriou, C.H.: Elements of the Theory of Computation, 2nd edn. Prentice-Hall, Englewood Cliffs (1998)","edition":"2"},{"key":"27_CR7","doi-asserted-by":"crossref","first-page":"398","DOI":"10.1137\/S009753979324485X","volume":"24","author":"M Li","year":"1995","unstructured":"Li, M., Vit\u00e1nyi, P.: A new approach to formal language theory by Kolmogorov complexity. SIAM J. Comput. 24, 398\u2013410 (1995)","journal-title":"SIAM J. Comput."},{"key":"27_CR8","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4757-2606-0","volume-title":"Kolmogorov Complexity and Its Applications","author":"M Li","year":"1997","unstructured":"Li, M., Vit\u00e1nyi, P.: Kolmogorov Complexity and Its Applications, 2nd edn. Springer, New York (1997)","edition":"2"},{"key":"27_CR9","doi-asserted-by":"crossref","first-page":"117","DOI":"10.1016\/S0304-3975(98)00059-0","volume":"207","author":"II Macarie","year":"1998","unstructured":"Macarie, I.I., Ogihara, M.: Properties of probabilistic pushdown automata. Theor. Comput. Sci. 207, 117\u2013130 (1998)","journal-title":"Theor. Comput. Sci."},{"key":"27_CR10","doi-asserted-by":"crossref","first-page":"157","DOI":"10.3233\/FI-2015-1148","volume":"136","author":"G Pighizzini","year":"2015","unstructured":"Pighizzini, G., Pisoni, A.: Limited automata and context-free languages. Fundam. Inf. 136, 157\u2013176 (2015)","journal-title":"Fundam. Inf."},{"key":"27_CR11","unstructured":"Yamakami, T.: Swapping lemmas for regular and context-free languages. arXiv:0808.4122 (2008)"},{"key":"27_CR12","doi-asserted-by":"crossref","first-page":"941","DOI":"10.1142\/S0129054110007659","volume":"21","author":"T Yamakami","year":"2010","unstructured":"Yamakami, T.: The roles of advice to one-tape linear-time turing machines and finite automata. Int. J. Found. Comput. Sci. 21, 941\u2013962 (2010)","journal-title":"Int. J. Found. Comput. Sci."},{"key":"27_CR13","doi-asserted-by":"crossref","first-page":"6432","DOI":"10.1016\/j.tcs.2011.07.013","volume":"412","author":"T Yamakami","year":"2011","unstructured":"Yamakami, T.: Immunity and pseudorandomness of context-free languages. Theor. Comput. Sci. 412, 6432\u20136450 (2011)","journal-title":"Theor. Comput. Sci."},{"key":"27_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"514","DOI":"10.1007\/978-3-319-04298-5_45","volume-title":"SOFSEM 2014: Theory and Practice of Computer Science","author":"T Yamakami","year":"2014","unstructured":"Yamakami, T.: Oracle pushdown automata, nondeterministic reducibilities, and the hierarchy over the family of context-free languages. In: Geffert, V., Preneel, B., Rovan, B., \u0160tuller, J., Tjoa, A.M. (eds.) SOFSEM 2014. LNCS, vol. 8327, pp. 514\u2013525. Springer, Cham (2014). doi: 10.1007\/978-3-319-04298-5_45 . A complete version arXiv:1303.1717v2 under a slightly different title"},{"key":"27_CR15","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/j.tcs.2015.10.026","volume":"613","author":"T Yamakami","year":"2016","unstructured":"Yamakami, T.: Pseudorandom generators against advised context-free languages. Theor. Comput. Sci. 613, 1\u201327 (2016)","journal-title":"Theor. Comput. Sci."}],"container-title":["Lecture Notes in Computer Science","Developments in Language Theory"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-62809-7_27","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,10,12]],"date-time":"2020-10-12T21:19:48Z","timestamp":1602537588000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-62809-7_27"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017]]},"ISBN":["9783319628080","9783319628097"],"references-count":15,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-62809-7_27","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2017]]}}}