0000000000924528
AUTHOR
Maksims Dimitrijevs
Probabilistic verification of all languages
We present three protocols for verifying all languages: (i) For any unary (binary) language, there is a log-space (linear-space) interactive proof system (IPS); (ii) for any language, there is a constant-space weak-IPS (the non-members may not be rejected with high probability); and, (iii) for any language, there is a constant-space IPS with two provers where the verifier reads the input once. Additionally, we show that uncountably many binary (unary) languages can be verified in constant space and in linear (quadratic) expected time.
Uncountable Realtime Probabilistic Classes
We investigate the minimal cases for realtime probabilistic machines that can define uncountably many languages with bounded error. We show that logarithmic space is enough for realtime PTMs on unary languages. On non-unary case, we obtain the same result for double logarithmic space, which is also tight. When replacing the work tape with a few counters, we can still achieve similar results for unary linear-space two-counter automata, unary sublinear-space three-counter automata, and non-unary sublinear-space two-counter automata. We also show how to slightly improve the sublinear-space constructions by using more counters.
Ultrametrisku galīgu automātu iespējas
Maģistra darbā tiek pētīti ultrametriski galīgi automāti un to iespējas. Ultrametriski automāti ir līdzīgi varbūtiskiem automātiem, tikai varbūtību vietā tiek izmantotas amplitūdas, kas ir p-adiski skaitļi. Pēdējos divos gados tika veikti dažādi pētījumi, kuros piedalījās arī darba autors, par ultrametrisku algoritmu izmantošanas iespējām, ieskaitot to izmantošanu galīgajos automātos. Darbā tiek izpētītas dažādu ultrametrisku galīgu automātu tipu iespējas, salīdzinot tos ar citiem automātu tipiem. Maģistra darbā tiek salīdzinātas dažādi definētu ultrametrisku galīgu automātu valodu atpazīšanas iespējas. Ultrametriski galīgi automāti darbā tiek salīdzināti arī ar dažādu sarežģītību determinē…
Probabilistic computation and verification beyond Turing machines
Mūsu mērķis ir izpētīt dažādus ierobežotas kļūdas varbūtiskus modeļus, kas spēj definēt nesanumurējami daudz valodu. Mēs sākam ar stingrāko nosacījumu - sākumā apskatām minimālus modeļus, kas var atpazīt visas valodas. Mēs apskatām varbūtiskas Tjūringa mašīnas, varbūtiskus automātus ar skaitītājiem un varbūtiskus galīgus automātus ar dažādiem ierobežojumiem uz ievadgalviņu. Mēs apskatām arī konstantas telpas pārbaudītājus (verifiers), kas mijiedarbojas ar vienu un diviem pierādītājiem (provers) un pārbauda (verify) visas valodas. Pēc tam mēs pieminētajos modeļos apskatām nesanumurējami daudzu valodu atpazīšanu un pārbaudi ar ierobežotu kļūdu. Mēs pierādām arī jaunus rezultātus par kvantu au…
The minimal probabilistic and quantum finite automata recognizing uncountably many languages with fixed cutpoints
Discrete Mathematics & Theoretical Computer Science ; vol. 22 no. 1 ; Automata, Logic and Semantics ; 1365-8050
Postselecting probabilistic finite state recognizers and verifiers
In this paper, we investigate the computational and verification power of bounded-error postselecting realtime probabilistic finite state automata (PostPFAs). We show that PostPFAs using rational-valued transitions can do different variants of equality checks and they can verify some nonregular unary languages. Then, we allow them to use real-valued transitions (magic-coins) and show that they can recognize uncountably many binary languages by help of a counter and verify uncountably many unary languages by help of a prover. We also present some corollaries on probabilistic counter automata.
Uncountable classical and quantum complexity classes
It is known that poly-time constant-space quantum Turing machines (QTMs) and logarithmic-space probabilistic Turing machines (PTMs) recognize uncountably many languages with bounded error (A.C. Cem Say and A. Yakaryılmaz, Magic coins are useful for small-space quantum machines. Quant. Inf. Comput. 17 (2017) 1027–1043). In this paper, we investigate more restricted cases for both models to recognize uncountably many languages with bounded error. We show that double logarithmic space is enough for PTMs on unary languages in sweeping reading mode or logarithmic space for one-way head. On unary languages, for quantum models, we obtain middle logarithmic space for counter machines. For binary la…
Ultrametriski algoritmi dažādiem automātu tipiem
Bakalaura darbā tiek apskatīti p-adiski skaitļi un to izmantošana automātos par parametriem, kas ļauj veidot ultrametriskus automātus. Ultrametriski automāti ir līdzīgi varbūtiskiem automātiem, tikai varbūtību vietā tiek izmantotas amplitūdas, kas ir p-adiski skaitļi. Darbā tiek apskatītas ultrametrisku algoritmu izmantošanas iespējas atpazīstamo valodu klases paplašināšanai, nepieciešamo stāvokļu skaita samazināšanai un sarežģītības samazināšanai. Tiek apskatīti ultrametriski algoritmi galīgiem vienvirziena un divvirzienu automātiem, automātiem ar magazīnas atmiņu, automātiem ar vairākām galviņām un Tjūringa mašīnām. Darbā ir parādīts, ka determinētas Tjūringa mašīnas uzdevumus var reducēt…
Uncountable realtime probabilistic classes
We investigate the minimum cases for realtime probabilistic machines that can define uncountably many languages with bounded error. We show that logarithmic space is enough for realtime PTMs on unary languages. On binary case, we follow the same result for double logarithmic space, which is tight. When replacing the worktape with some limited memories, we can follow uncountable results on unary languages for two counters.
Capabilities of Ultrametric Automata with One, Two, and Three States
Ultrametric automata use p-adic numbers to describe the random branching of the process of computation. Previous research has shown that ultrametric automata can have a significant decrease in computing complexity. In this paper we consider the languages that can be recognized by one-way ultrametric automata with one, two, and three states. We also show an example of a promise problem that can be solved by ultrametric integral automaton with three states.
Daudzlietotāju tīmekļa RPG spēle
„Daudzlietotāju tīmekļa RPG spēle” – cīņu spēles portāls, kas izstrādāts cilvēkiem, kam patīk spēlēt un sazināties ar citiem cilvēkiem, kādu laiku atrodoties mākslīgā pasaulē. Tā ir laba iespēja attīstīt savu stratēģisko domāšanu un fantāziju un atrast jaunus draugus. Moderatoriem ir iespēja kontrolēt kārtību portālā un veidot jaunus ieročus un bruņu. Savukārt administrators var pārvaldīt moderatorus un spēlētājus. Spēles uzbūve ļauj projektam augt, bet lietotāja saskarne paredzēta ērtai un intuitīvai pārvietošanai pa projekta sadaļām un patīkamām cīņas procesam.