{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,2]],"date-time":"2026-07-02T14:40:56Z","timestamp":1783003256041,"version":"3.54.5"},"reference-count":48,"publisher":"EDP Sciences","issue":"2","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["RAIRO-Theor. Inf. Appl."],"published-print":{"date-parts":[[2014,4]]},"DOI":"10.1051\/ita\/2014003","type":"journal-article","created":{"date-parts":[[2014,4,17]],"date-time":"2014-04-17T08:47:11Z","timestamp":1397724431000},"page":"187-207","source":"Crossref","is-referenced-by-count":17,"title":["On the state complexity of semi-quantum finite automata"],"prefix":"10.1051","volume":"48","author":[{"given":"Shenggen","family":"Zheng","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jozef","family":"Gruska","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Daowen","family":"Qiu","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"250","published-online":{"date-parts":[[2014,4,17]]},"reference":[{"key":"R1","doi-asserted-by":"crossref","unstructured":"Ambainis A., Nayak A., Ta-Shma A. and Vazirani U., Dense quantum coding and quantum automata.J. ACM49(2002) 496\u2013511.","DOI":"10.1145\/581771.581773"},{"key":"R2","unstructured":"Ambainis A., The complexity of probabilistic versus deterministic finite automata,Proc. of the International Symposium on Algorithms and Computation (ISAAC96).Lect. Notes Comput. Sci.1178(1996) 233\u2013239."},{"key":"R3","unstructured":"Ambainis A. and Watrous J., Two-way finite automata with quantum and classical states.Theoret. Comput. Sci.287(2002) 299\u2013311."},{"key":"R4","unstructured":"A. Ambainis and R. Freivalds, One-way quantum finite automata: strengths, weaknesses and generalizations, in:Proc. of the 39th Annual Symposium on Foundations of Computer Science. IEEE Computer Society Press, Palo Alfo, California, USA (1998) 332\u2013341."},{"key":"R5","doi-asserted-by":"crossref","unstructured":"Ambainis A. and Nahimovs N., Improved constructions of quantum automata.Theoret. Comput. Sci.410(2009) 1916\u20131922.","DOI":"10.1016\/j.tcs.2009.01.027"},{"key":"R6","unstructured":"Ambainis A. and Yakaryilmaz A., Superiority of exact quantum automata for promise problems.Inform. Process. Lett.112(2012) 289\u2013291."},{"key":"R7","doi-asserted-by":"crossref","unstructured":"Bertoni A., Mereghetti C. and Palano B., Small size quantum automata recognizing some regular languages.Theoret. Comput. Sci.340(2005) 394\u2013407.","DOI":"10.1016\/j.tcs.2005.03.032"},{"key":"R8","unstructured":"Bertoni A., Mereghetti C. and Palano b.. Some formal tools for analyzing quantum automata.Theoret. Comput. Sci.356(2006) 14\u201325."},{"key":"R9","doi-asserted-by":"crossref","unstructured":"Birget J.C., State-complexity of finite-state devices, state compressibility and incompressibility.Math. Systems Theory26(1993) 237\u2013269.","DOI":"10.1007\/BF01371727"},{"key":"R10","unstructured":"Brodsky A. and Pippenger N., Characterizations of 1-way quantum finite automata.SIAM J. Comput.31(2002) 1456\u20131478."},{"key":"R11","doi-asserted-by":"crossref","unstructured":"H. Buhrman, R. Cleve and A. Wigderson, Quantum vs. classical communication and computation.Proc. of 30th Annual ACM Symposium Theory Computing(1998) 63\u201368.","DOI":"10.1145\/276698.276713"},{"key":"R12","unstructured":"Buhrman H., Cleve R., Massar S. and de Wolf R., Nonlocality and Communication Complexity.Rev. Mod. Phys.82(2010) 665\u2013698"},{"key":"R13","unstructured":"Chrobak M., Finite Automata and Unary Languages.Theoret. Comput. Sci.47(1986) 149\u2013158."},{"key":"R14","unstructured":"Dwork C. and Stockmeyer L., A time-complexity gap for two-way probabilistic finite state automata.SIAM J. Comput.19(1990) 1011\u20131023."},{"key":"R15","unstructured":"Freivalds R., On the growth of the number of states in result of determinization of probabilistic finite automata.Automatic Control Comput. Sci.3(1982) 39\u201342."},{"key":"R16","doi-asserted-by":"crossref","unstructured":"Freivalds R., Non-constructive methods for finite probabilistic automata.Int. J. Found. Comput. Sci.19(2008) 565\u2013580.","DOI":"10.1142\/S0129054108005826"},{"key":"R17","doi-asserted-by":"crossref","unstructured":"Freivalds R., Ozols M. and Mancinska L., Improved constructions of mixed state quantum automata.Theoret. Comput. Sci.410(2009) 1923\u20131931.","DOI":"10.1016\/j.tcs.2009.01.028"},{"key":"R18","unstructured":"W. Feller, An Introduction to Probability Theory and its Applications, vol. I. Wiley, New York, 1967."},{"key":"R19","unstructured":"J. Gruska, Quantum Computing. McGraw-Hill, London (1999)."},{"key":"R20","unstructured":"Gruska J., Descriptional complexity issues in quantum computing.J. Automata Languages Combinatorics5(2000) 191\u2013218."},{"key":"R21","unstructured":"J. Gruska, D.W. Qiu, and S.G. Zheng, Communication complexity of promise problems and their applications to finite automata, arXiv:1309.7739 (2013)."},{"key":"R22","unstructured":"J.E. Hopcroft and J.D. Ullman, Introduction to Automata Theory, Languages, and Computation. Addision-Wesley, New York, 1979."},{"key":"R23","doi-asserted-by":"crossref","unstructured":"G.A. Kiraz, Compressed Storage of Sparse Finite-State Transducers,Proc. of CIAA, vol. 2214 ofLect. Notes Comput. Sci.(2001) 109\u2013121.","DOI":"10.1007\/3-540-45526-4_11"},{"key":"R24","unstructured":"H. Klauck, On quantum and probabilistic communication: Las Vegas and one-way protocols.Proc. of the 32th STOC(2000) 644\u2013651."},{"key":"R25","unstructured":"Kushilevitz E., Communication Complexity.Adv. Comput.44(1997) 331\u2013360."},{"key":"R26","doi-asserted-by":"crossref","unstructured":"A. Kondacs and J. Watrous, On the power of quantum finite state automata, inProc. of 38th IEEE Annal. Sympos. Found. of Comput. Sci.(1997) 66\u201375.","DOI":"10.1109\/SFCS.1997.646094"},{"key":"R27","doi-asserted-by":"crossref","unstructured":"F. Le Gall, Exponential separation of quantum and classical online space complexity, inProc. of SPAA\u201906(2006) 67\u201373.","DOI":"10.1145\/1148109.1148119"},{"key":"R28","doi-asserted-by":"crossref","unstructured":"Liu G., Martin-Vide C., Salomaa A. and Yu S., State complexity of basic operations combined with reversal,Inf. Comput.206(2008) 1178\u2013186.","DOI":"10.1016\/j.ic.2008.03.018"},{"key":"R29","unstructured":"Mereghetti C. and Pighizzini G., Two-way automata simulations and unary languages.J. Automata, Languages and Combinatorics5(2000) 287\u2013300."},{"key":"R30","unstructured":"Mereghetti C., Palano B. and Pighizzini G., Note on the Succinctness of Deterministic, Nondeterministic, Probabilistic and Quantum Finite Automata.RAIRO: ITA35(2001) 477\u2013490."},{"key":"R31","unstructured":"Mereghetti C. and Palano B., On the size of one-way quantum finite automata with periodic behaviors.RAIRO: ITA36(2002) 277\u2013291."},{"key":"R32","unstructured":"Milani M. and Pighizzini G., Tight bounds on the simulation of unary probabilistic automata by deterministic automata,J. Automata, Languages and Combinatorics6(2001) 481\u2013492."},{"key":"R33","unstructured":"Mateusa P., Qiu D.W. and Li L.Z., On the complexity of minimizing probabilistic and quantum automata.Inform. Comput.218(2012) 36\u201353."},{"key":"R34","doi-asserted-by":"crossref","unstructured":"Moore C. and Crutchfield J. P., Quantum automata and quantum grammars.Theoret. Comput. Sci.237(2000) 275\u2013306.","DOI":"10.1016\/S0304-3975(98)00191-1"},{"key":"R35","unstructured":"A. Paz, Introduction to Probabilistic Automata. Academic Press, New York (1971)."},{"key":"R36","doi-asserted-by":"crossref","unstructured":"D. W. Qiu, Some Observations on Two-Way Finite Automata with Quantum and Classical States,ICIC 2008. In vol. 5226 ofLect. Notes Comput. Sci.(2008) 1\u20138.","DOI":"10.1007\/978-3-540-87442-3_1"},{"key":"R37","unstructured":"Rabin M. O. and Scott D., Finite automata and their decision problems.IBM J. Research Devel.3(1959) 115\u2013125."},{"key":"R38","unstructured":"M.A. Nielsen and I.L. Chuang, Quantum Computation and Quantum Information. Cambridge University Press, Cambridge, 2000."},{"key":"R39","doi-asserted-by":"crossref","unstructured":"D. W. Qiu, L.Z. Li, P. Mateus and J. Gruska, Quantum finite automata,CRC Handbook of Finite State Based Models and Applications. Edited by J.C. Wang. CRC Press (2012) 113\u2013144.","DOI":"10.1201\/b13055-7"},{"key":"R40","doi-asserted-by":"crossref","unstructured":"A. Salomaa, On the reducibility of events represented in automata. InAnnales Academiae Scientiarum Fennicae.Volume Series A of I. Math.(1964) 353.","DOI":"10.5186\/aasfm.1964.339"},{"key":"R41","unstructured":"Yu S., Zhuang Q. and Salomaa K.. The state complexity of some basic operations on regular languages.Theoret. Comput. Sci.125(1994) 315\u2013328."},{"key":"R42","unstructured":"Yu S., State Complexity: Recent Results and Open Problems.Fundamenta Informaticae64(2005) 471\u2013480."},{"key":"R43","doi-asserted-by":"crossref","unstructured":"Yakaryilmaz A. and Cem Say A.C., Unbounded-error quantum computation with small space bounds,Inform. Comput.209(2011) 873\u2013892.","DOI":"10.1016\/j.ic.2011.01.008"},{"key":"R44","unstructured":"Yakaryilmaz A. and Cem Say A.C., Succinctness of two-way probabilistic and quantum finite automata.Discrete Math. Theoret. Comput. Sci.12(2010) 19\u201340."},{"key":"R45","doi-asserted-by":"crossref","unstructured":"S.G. Zheng, D.W. Qiu, L.Z. Li and J. Gruska, One-way finite automata with quantum and classical states, vol 7300 ofLect. Notes Comput. Sci.Edited by H. Bordihn, M. Kutrib, and B. Truthe (2012) 273\u2013290.","DOI":"10.1007\/978-3-642-31644-9_19"},{"key":"R46","doi-asserted-by":"crossref","unstructured":"Zheng S.G., Qiu D.W., Gruska J., Li L.Z. and Mateus P., State succinctness of two-way finite automata with quantum and classical states,Theoret. Comput. Sci.499(2013) 98\u2013112.","DOI":"10.1016\/j.tcs.2013.06.005"},{"key":"R47","doi-asserted-by":"crossref","unstructured":"Zheng S.G., Qiu D.W. and Li L.Z., Some languages recognized by two-way finite automata with quantum and classical states.Int. J. Foundation Comput. Sci.23(2012) 1117\u20131129.","DOI":"10.1142\/S0129054112500141"},{"key":"R48","unstructured":"S.G. Zheng, J. Gruska and D.W. Qiu. Power of the interactive proof systems with verifiers modeled by semi-quantum two-way finite automata. arXiv:1304.3876 (2013)."}],"container-title":["RAIRO - Theoretical Informatics and Applications"],"original-title":[],"link":[{"URL":"http:\/\/www.rairo-ita.org\/10.1051\/ita\/2014003\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,5,2]],"date-time":"2025-05-02T12:01:26Z","timestamp":1746187286000},"score":1,"resource":{"primary":{"URL":"http:\/\/www.rairo-ita.org\/10.1051\/ita\/2014003"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,4]]},"references-count":48,"journal-issue":{"issue":"2"},"alternative-id":["ita130034"],"URL":"https:\/\/doi.org\/10.1051\/ita\/2014003","relation":{},"ISSN":["0988-3754","1290-385X"],"issn-type":[{"value":"0988-3754","type":"print"},{"value":"1290-385X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,4]]}}}