{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,31]],"date-time":"2026-01-31T16:57:47Z","timestamp":1769878667585,"version":"3.49.0"},"publisher-location":"Cham","reference-count":19,"publisher":"Springer International Publishing","isbn-type":[{"value":"9783030193102","type":"print"},{"value":"9783030193119","type":"electronic"}],"license":[{"start":{"date-parts":[[2019,1,1]],"date-time":"2019-01-01T00:00:00Z","timestamp":1546300800000},"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":[[2019]]},"DOI":"10.1007\/978-3-030-19311-9_20","type":"book-chapter","created":{"date-parts":[[2019,5,20]],"date-time":"2019-05-20T10:32:32Z","timestamp":1558348352000},"page":"257-271","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["Relativizations of Nonuniform Quantum Finite Automata Families"],"prefix":"10.1007","author":[{"given":"Tomoyuki","family":"Yamakami","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2019,4,26]]},"reference":[{"key":"20_CR1","doi-asserted-by":"publisher","first-page":"129","DOI":"10.4086\/toc.2007.v003a007","volume":"3","author":"S Aaronson","year":"2007","unstructured":"Aaronson, S., Kuperberg, G.: Quantum versus classical proofs and advice. Theory Comput. 3, 129\u2013157 (2007)","journal-title":"Theory Comput."},{"key":"20_CR2","doi-asserted-by":"publisher","first-page":"165","DOI":"10.1007\/s00224-005-1263-x","volume":"39","author":"A Ambainis","year":"2006","unstructured":"Ambainis, A., Beaudry, M., Golovkins, M., Kikusts, A., Mercer, M., Th\u00e9rien, D.: Algebraic results on quantum automata. Theory Comput. Syst. 39, 165\u2013188 (2006)","journal-title":"Theory Comput. Syst."},{"key":"20_CR3","doi-asserted-by":"publisher","first-page":"431","DOI":"10.1137\/0204037","volume":"4","author":"T Baker","year":"1975","unstructured":"Baker, T., Gill, J., Solovay, R.: Relativizations of the P=?NP question. SIAM J. Comput. 4, 431\u2013442 (1975)","journal-title":"SIAM J. Comput."},{"key":"20_CR4","unstructured":"Berman, P., Lingas, A.: On complexity of regular languages in terms of finite automata. Technical report 304, Institute of Computer Science, Polish Academy of Science, Warsaw (1977)"},{"key":"20_CR5","doi-asserted-by":"publisher","first-page":"1011","DOI":"10.1137\/0219069","volume":"19","author":"C Dwork","year":"1990","unstructured":"Dwork, C., Stockmeyer, L.: A time-complexity gap for two-way probabilistic finite state automata. SIAM J. Comput. 19, 1011\u20131023 (1990)","journal-title":"SIAM J. Comput."},{"key":"20_CR6","doi-asserted-by":"publisher","first-page":"1923","DOI":"10.1016\/j.tcs.2009.01.028","volume":"410","author":"R Freivalds","year":"2009","unstructured":"Freivalds, R., Ozols, M., Man\u010dinska, L.: Improved constructions of mixed state quantum automata. Theoret. Comput. Sci. 410, 1923\u20131931 (2009)","journal-title":"Theoret. Comput. Sci."},{"key":"20_CR7","volume-title":"Quantum Computing","author":"J Gruska","year":"2000","unstructured":"Gruska, J.: Quantum Computing. McGraw-Hill, London (2000)"},{"key":"20_CR8","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":"CA Kapoutsis","year":"2009","unstructured":"Kapoutsis, C.A.: Size complexity of two-way finite automata. In: Diekert, V., Nowotka, D. (eds.) DLT 2009. LNCS, vol. 5583, pp. 47\u201366. Springer, Heidelberg (2009). \n                    https:\/\/doi.org\/10.1007\/978-3-642-02737-6_4"},{"key":"20_CR9","first-page":"205","volume":"17","author":"CA Kapoutsis","year":"2012","unstructured":"Kapoutsis, C.A.: Minicomplexity. J. Autom. Lang. Comb. 17, 205\u2013224 (2012)","journal-title":"J. Autom. Lang. Comb."},{"key":"20_CR10","doi-asserted-by":"publisher","first-page":"421","DOI":"10.1007\/s00224-013-9465-0","volume":"55","author":"CA Kapoutsis","year":"2014","unstructured":"Kapoutsis, C.A.: Two-way automata versus logarithmic space. Theory Comput. Syst. 55, 421\u2013447 (2014)","journal-title":"Theory Comput. Syst."},{"key":"20_CR11","doi-asserted-by":"publisher","first-page":"662","DOI":"10.1007\/s00224-014-9560-x","volume":"56","author":"CA Kapoutsis","year":"2015","unstructured":"Kapoutsis, C.A., Pighizzini, G.: Two-way automata characterizations of L\/poly versus NL. Theory Comput. Syst. 56, 662\u2013685 (2015)","journal-title":"Theory Comput. Syst."},{"key":"20_CR12","doi-asserted-by":"publisher","DOI":"10.1090\/gsm\/047","volume-title":"Classical and Quantum Computation","author":"A Kitaev","year":"2002","unstructured":"Kitaev, A., Shen, A., Vyalyi, M.: Classical and Quantum Computation. AMS, Providence (2002)"},{"key":"20_CR13","doi-asserted-by":"crossref","unstructured":"Sakoda, W.J., Sipser, M.: Nondeterminism and the size of two-way finite automata. In: Proceedings of STOC 1978, pp. 275\u2013286 (1978)","DOI":"10.1145\/800133.804357"},{"key":"20_CR14","doi-asserted-by":"publisher","first-page":"22","DOI":"10.1016\/j.tcs.2009.08.031","volume":"411","author":"K Tadaki","year":"2010","unstructured":"Tadaki, K., Yamakami, T., Lin, J.C.H.: Theory of one-tape linear-time Turing machines. Theor. Comput. Sci. 411, 22\u201343 (2010)","journal-title":"Theor. Comput. Sci."},{"key":"20_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"280","DOI":"10.1007\/978-3-319-19225-3_24","volume-title":"Descriptional Complexity of Formal Systems","author":"M Villagra","year":"2015","unstructured":"Villagra, M., Yamakami, T.: Quantum state complexity of formal languages. In: Shallit, J., Okhotin, A. (eds.) DCFS 2015. LNCS, vol. 9118, pp. 280\u2013291. Springer, Cham (2015). \n                    https:\/\/doi.org\/10.1007\/978-3-319-19225-3_24"},{"key":"20_CR16","doi-asserted-by":"publisher","first-page":"873","DOI":"10.1016\/j.ic.2011.01.008","volume":"279","author":"A Yakaryilmaz","year":"2011","unstructured":"Yakaryilmaz, A., Say, A.C.C.: Unbounded-error quantum computation with small space bounds. Inf. Comput. 279, 873\u2013892 (2011)","journal-title":"Inf. Comput."},{"key":"20_CR17","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). \n                    https:\/\/doi.org\/10.1007\/978-3-319-04298-5_45\n                    \n                  . A complete version is available at \n                    arXiv:1303.1717"},{"key":"20_CR18","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"134","DOI":"10.1007\/978-3-030-13435-8_10","volume-title":"LATA 2019","author":"T Yamakami","year":"2018","unstructured":"Yamakami, T.: Nonuniform families of polynomial-size quantum finite automata and quantum logarithmic-space computation with polynomial-size advice. In: Mart\u00edn-Vide, C., Okhotin, A., Shapira, D. (eds.) LATA 2019. LNCS, vol. 11417, pp. 134\u2013145. Springer, Cham (2018). \n                    https:\/\/doi.org\/10.1007\/978-3-030-13435-8_10"},{"key":"20_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"237","DOI":"10.1007\/978-3-319-94631-3_20","volume-title":"Descriptional Complexity of Formal Systems","author":"T Yamakami","year":"2018","unstructured":"Yamakami, T.: State complexity characterizations of parameterized degree-bounded graph connectivity, sub-linear space computation, and the linear space hypothesis. In: Konstantinidis, S., Pighizzini, G. (eds.) DCFS 2018. LNCS, vol. 10952, pp. 237\u2013249. Springer, Cham (2018). \n                    https:\/\/doi.org\/10.1007\/978-3-319-94631-3_20\n                    \n                  . A complete and corrected version is found at \n                    arXiv:1811.06336"}],"container-title":["Lecture Notes in Computer Science","Unconventional Computation and Natural Computation"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-030-19311-9_20","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,10,11]],"date-time":"2019-10-11T03:20:45Z","timestamp":1570764045000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-030-19311-9_20"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019]]},"ISBN":["9783030193102","9783030193119"],"references-count":19,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-19311-9_20","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019]]},"assertion":[{"value":"26 April 2019","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"UCNC","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Unconventional Computation and Natural Computation","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Tokyo","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Japan","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2019","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"3 June 2019","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"7 June 2019","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"18","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"uc2019","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"http:\/\/www.ucnc2019.uec.ac.jp\/index.html","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Single-blind","order":1,"name":"type","label":"Type","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"EasyChair","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"32","order":3,"name":"number_of_submissions_sent_for_review","label":"Number of Submissions Sent for Review","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"19","order":4,"name":"number_of_full_papers_accepted","label":"Number of Full Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"0","order":5,"name":"number_of_short_papers_accepted","label":"Number of Short Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"59% - The value is computed by the equation \"Number of Full Papers Accepted \/ Number of Submissions Sent for Review * 100\" and then rounded to a whole number.","order":6,"name":"acceptance_rate_of_full_papers","label":"Acceptance Rate of Full Papers","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"3.2","order":7,"name":"average_number_of_reviews_per_paper","label":"Average Number of Reviews per Paper","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"4","order":8,"name":"average_number_of_papers_per_reviewer","label":"Average Number of Papers per Reviewer","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Yes","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"4 abstracts of invited talks and one full paper of an invited talk are included.","order":10,"name":"additional_info_on_review_process","label":"Additional Info on Review Process","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}}]}}