Kvantu un varbūtisko automātu darba spējas

Abstract

Anot¹acija ņSis darbs apvieno p¹et¹³jumus par diviem autom¹atu veidiem: varb¹utiskajiem apgrieņzamajiem autom¹atiem (PRA), kas ir saist¹³ti ar kvantu gal¹³gajiem auto- m¹atiem (QFA), un vienvirziena kvantu autom¹atiem ar skait¹³t¹aju (Q1CA), kas ir l»oti ierobeņzots kvantu autom¹atu modelis, kam atbilstoņsa kvantu sist¹ema nav gal¹³ga. Darba m¹erk»is ir aprakst¹³t valodu klases, ko paz¹³st ņsie autom¹ati, un sal¹³dzin¹at kvantu un varb¹utiskos autom¹atus. M¹es pied¹av¹ajam varb¹utisk¹a apgrieņzama autom¹ata modeli. M¹es p¹et¹am vienvirziena PRA gan ar klasisko (C-PRA) v¹ardu akcept¹eņsanu, gan ar ap- st¹adin¹aņsanu (DH-PRA). M¹es par¹ad¹am valodu klases a¤1 a¤2 : : : a¤n paz¹³ņsanu ar PRA. M¹es par¹ad¹am vai valodu klase, ko paz¹³st PRA, ir sl¹egta pret B¹ula oper¹acij¹am. M¹es par¹ad¹am visp¹ar¹³gas valodu klases, ko C-PRA un DH-PRA nepaz¹³st. M¹es apskat¹am v¹ajas apgrieņzam¹³bas de¯n¹³ciju un par¹ad¹am atņsk»ir¹³bu no apgrieņzam¹³bas. M¹es pied¹av¹ajam vispar¹³gu kvantu vienvirziena autom¹ata modeli ar skai- t¹³t¹aju (Q1CA). M¹es pier¹ad¹am ka ņsis modelis apmierina transform¹acijas uni- tarit¹ates principu. Tiek pied¹av¹ats speci¹als Q1CA veids - vienk¹arņsais Q1CA, kas l»auj konstru¹et autom¹atu piem¹erus konkr¹et¹am valod¹am. M¹es par¹ad¹am vair¹aku kontekstatkar¹³go valodu paz¹³ņsanu ar Q1CA. M¹es pier¹ad¹am ka past¹av valodas, ko paz¹³st Q1CA, bet ko nepaz¹³st varb¹utiskais autom¹ats ar skait¹³t¹aju.

The thesis assembles research on two models of automata - probabilistic reversible (PRA) that appear very similar to 1-way quantum ¯nite automata (1-QFA) and quantum one-way one counter automata (Q1CA), that is the most restricted model of non-¯nite space quantum automata. The objective of the research is to describe classes of languages recognizable by these models and compare related quantum and probabilistic automata. We propose the model of probabilistic reversible automata. We study both one-way PRA with classical (1-C-PRA) and decide and halt (1-DH- PRA) acceptance. We show recognition of general class of languages Ln = a¤1a¤2 : : : a¤n with probability 1 ¡ ". We show whether the classes of languages they recognize are closed under boolean operations and describe general class of languages not recognizable by these automata in terms of \forbidden con- structions" for the minimal deterministic automaton of the language. We also consider \weak" reversibility as equivalent de¯nition for 1-way automata and show the di®erence from ordinary reversibility in 1.5-way case. We propose the general notion of quantum one-way one counter au- tomata(Q1CA). We describe well-formedness conditions for the Q1CA that ensure unitarity of its evolution. A special kind of Q1CA, called simple, that satis¯es the well-formedness conditions is introduced. We show recognition of several non context free languages by Q1CA. We show that there is a lan- guage that can be recognized by quantum one-way one counter automaton, but not by the probabilistic one counter automaton.