{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,2,19]],"date-time":"2024-02-19T02:10:01Z","timestamp":1708308601747},"reference-count":20,"publisher":"Wiley","issue":"6","license":[{"start":{"date-parts":[[2007,3,21]],"date-time":"2007-03-21T00:00:00Z","timestamp":1174435200000},"content-version":"vor","delay-in-days":6653,"URL":"http:\/\/onlinelibrary.wiley.com\/termsAndConditions#vor"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Systems &amp; Computers in Japan"],"published-print":{"date-parts":[[1989,1]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>This paper discusses the basic properties of the probabilistic push\u2010down automaton (PPDA). Intuitively speaking, PPDA is obtained by adding a probabilistic property to the nondeterministic transition of the nondeterministic push\u2010down automaton (NPDA). According to the property of the error in the accepting condition, PPDA is classified into a two\u2010sided error PPDA, a one\u2010sided error PPDA, and bounded error PPDA. Moreover, the acception error is considered not only for 1\/2, but also for an arbitrary cut\u2010point, to discuss the relations among classes of languages. Major results are as follows.<\/jats:p><jats:p>The class of languages accepted by bounded error PPDA is not the same as that accepted by NPDA. In the case of two\u2010sided error PPDA and the bounded error PPDA, the class of acceptable languages does not depend on the cut\u2010point. In the case of a one\u2010sided PPDA, the class of acceptable languages depends to some extent on the cut\u2010point. In other words, there exists an infinite hierarchy. Kolmogorov complexity is used in the proof of the major theorem.<\/jats:p>","DOI":"10.1002\/scj.4690200602","type":"journal-article","created":{"date-parts":[[2007,11,14]],"date-time":"2007-11-14T12:21:19Z","timestamp":1195042879000},"page":"11-20","source":"Crossref","is-referenced-by-count":0,"title":["Probabilistic automata push\u2010down"],"prefix":"10.1002","volume":"20","author":[{"given":"Zhi\u2010Zhong","family":"Chen","sequence":"first","affiliation":[]},{"given":"Takumi","family":"Kasai","sequence":"additional","affiliation":[]}],"member":"311","published-online":{"date-parts":[[2007,3,21]]},"reference":[{"key":"e_1_2_1_2_2","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(79)90045-X"},{"key":"e_1_2_1_3_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(83)80060-6"},{"key":"e_1_2_1_4_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(77)90074-2"},{"key":"e_1_2_1_5_2","doi-asserted-by":"crossref","unstructured":"M.ChrobakandM.Li.k + 1 Heads are Better Chan k for PDA's. Proc. 27th Annual IEEE Symposium on FOCS pp.361\u2013367(1986).","DOI":"10.1109\/SFCS.1986.27"},{"key":"e_1_2_1_6_2","doi-asserted-by":"publisher","DOI":"10.1137\/0206049"},{"key":"e_1_2_1_7_2","first-page":"1","volume-title":"Algorithms and Complexity, New Direction and Recent Results","author":"Karp R. M.","year":"1976"},{"key":"e_1_2_1_8_2","unstructured":"T.Kasai.Complexity Theory. Kindai\u2010kagakusha (1986)."},{"key":"e_1_2_1_9_2","doi-asserted-by":"crossref","unstructured":"W.Paul.On\u2010line simulation of k + 1 tapes by k tapes require nonlinear time. Proc. 23rd Annual IEEE Symposium on FOCS pp.53\u201356(1982).","DOI":"10.1109\/SFCS.1982.31"},{"key":"e_1_2_1_10_2","doi-asserted-by":"crossref","unstructured":"W.Paul J.Seiferas andJ.Simon.An information\u2010theoretic approach to time bounds for on\u2010line computations. Proc. 12th Symposium on Theory of Computing pp.357\u2013367(1980).","DOI":"10.1145\/800141.804685"},{"key":"e_1_2_1_11_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(63)90290-0"},{"key":"e_1_2_1_12_2","first-page":"21","volume-title":"Algorithms and Complexity, New Direction and Recent Results","author":"Rabin M. O.","year":"1976"},{"key":"e_1_2_1_13_2","doi-asserted-by":"publisher","DOI":"10.1137\/0209024"},{"key":"e_1_2_1_14_2","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(84)90066-7"},{"issue":"2","key":"e_1_2_1_15_2","first-page":"273","article-title":"Fast probabilistic algorithms for verification of polynomial identities","volume":"27","author":"Schwartz J. T.","year":"1980","journal-title":"J. Assoc. Comput. Mach."},{"key":"e_1_2_1_16_2","doi-asserted-by":"crossref","unstructured":"U.Shoning.Probabilistic complexity classes and lowness. 2nd Annual Structure in Complexity Theory pp.2\u20138(1987).","DOI":"10.1109\/PSCT.1987.10319246"},{"key":"e_1_2_1_17_2","doi-asserted-by":"publisher","DOI":"10.1137\/0206006"},{"key":"e_1_2_1_18_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(68)90360-4"},{"key":"e_1_2_1_19_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(82)80019-3"},{"key":"e_1_2_1_20_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(86)80044-4"},{"key":"e_1_2_1_21_2","doi-asserted-by":"crossref","unstructured":"S.Zachos.Probabilistic quantifiers adversaries and complexity classes. 1st Annual Structure in Complexity Theory pp.383\u2013400(1986).","DOI":"10.1007\/3-540-16486-3_112"}],"container-title":["Systems and Computers in Japan"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2Fscj.4690200602","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/scj.4690200602","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,2,19]],"date-time":"2024-02-19T01:56:46Z","timestamp":1708307806000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/scj.4690200602"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1989,1]]},"references-count":20,"journal-issue":{"issue":"6","published-print":{"date-parts":[[1989,1]]}},"alternative-id":["10.1002\/scj.4690200602"],"URL":"https:\/\/doi.org\/10.1002\/scj.4690200602","archive":["Portico"],"relation":{},"ISSN":["0882-1666","1520-684X"],"issn-type":[{"value":"0882-1666","type":"print"},{"value":"1520-684X","type":"electronic"}],"subject":[],"published":{"date-parts":[[1989,1]]}}}