6533b7d2fe1ef96bd125e5a1
RESEARCH PRODUCT
Kvantu vaicājumu sarežģītība bezkonteksta gramatikām
Ansis Zvirbulissubject
magazīnas automātsbezkonteksta valodaDatorzinātnebezkonteksta gramatikakvantu vaicājumu algoritmikvantu vaicājumu sarežģītībadescription
Bezkonteksta gramatikas un to ģenerētās valodas ir plaši pētīta tēma datorzinātnē. Tām ir dažādi praktiski pielietojumi, piemēram, XML valodā. Savukārt kvantu skaitļošana, it sevišķi kvantu vaicājumu algoritmi, ir datorzinātnes nozare, kas par spīti popularitātei, ir vēl neizpētīta un neskaidra. Šī darba mērķis ir aplūkot vārda piederības problēmu bezkonteksta valodai no kvantu vaicājumu algoritmu puses. Konkrētāk - darbā tika izvirzīti divi uzdevumi. Pirmais uzdevums bija atrast bezkonteksta valodu ar kvantu vaicājumu sarežģītību O(N^c), kur c0 vai pierādīt par tādas neesamību. Otrais uzdevums - uzrādīt intuitīvi saprotamu bezkonteksta valodas konstrukciju, kas ļauj konstruēt valodu ar kvantu vaicājumu sarežģītību O(N^c), kur c∈[1/2;1]. Šajā darbā pirmo uzdevumu neizdevās atrisināt, taču rezultātā tika veikts uz novērojumiem balstīts minējums, ka šādas bezkonteksta valodas neeksistē. Savukārt otro uzdevumu izdevās atrisināt - tika atrasta subjektīvi saprotama konstrukcija, kas ļauj uzkonstruēt bezkonteksta valodu ar kvantu vaicājumu sarežģītību O(N^c), kur c ir patvaļīgs racionāls skaitlis intervālā [1/2;1].
| year | journal | country | edition | language |
|---|---|---|---|---|
| 2019-01-01 |