Zobrazeno 1 - 10
of 60
pro vyhledávání: '"Rūsiņš Freivalds"'
Publikováno v:
Natural Computing. 11:81-94
In classical computation, a "write-only memory" (WOM) is little more than an oxymoron, and the addition of WOM to a (deterministic or probabilistic) classical computer brings no advantage. We prove that quantum computers that are augmented with WOM c
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::0c712afe3ba11892cf3ef2b3fdaac48a
https://doi.org/10.1007/s11047-011-9270-0
https://doi.org/10.1007/s11047-011-9270-0
Publikováno v:
Information Processing Letters. 110:410-413
Öz bulunamadı.
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::37d0317e4e397ebd31e86d34255c2ccd
https://doi.org/10.1016/j.ipl.2010.03.011
https://doi.org/10.1016/j.ipl.2010.03.011
Autor:
Rūsiņš Freivalds
Publikováno v:
International Journal of Foundations of Computer Science. 19:565-580
Size (the number of states) of finite probabilistic automata with an isolated cut-point can be exponentially smaller than the size of any equivalent finite deterministic automaton. However, the proof is non-constructive. The result is presented in tw
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::b523373d2b0efabc5ac62e57709f3c63
https://doi.org/10.1142/s0129054108005826
https://doi.org/10.1142/s0129054108005826
Computing with New Resources : Essays Dedicated to Jozef Gruska on the Occasion of His 80th Birthday
Professor Jozef Gruska is a well known computer scientist for his many and broad results. He was the father of theoretical computer science research in Czechoslovakia and among the first Slovak programmers in the early 1960s. Jozef Gruska introduced
Publikováno v:
Lecture Notes in Computer Science ISBN: 9783319171418
TAMC
TAMC
B.A. Trakhtenbrot proved that in frequency computability (introduced by G. Rose) it is crucially important whether the frequency exceeds \(\frac{1}{2}\). If it does then only recursive sets are frequency-computable. If the frequency does not exceed \
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::771e0301a881a0dd2a33b8f478686898
https://doi.org/10.1007/978-3-319-17142-5_6
https://doi.org/10.1007/978-3-319-17142-5_6
Autor:
Rūsiņš Freivalds
Publikováno v:
Unconventional Computation and Natural Computation ISBN: 9783319218182
UCNC
UCNC
We introduce a notion of ultrametric automata and Turing machines using p-adic numbers to describe random branching of the process of computation. These automata have properties similar to the properties of probabilistic automata but complexity of pr
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::e48dd41e3b4237c78d7141fd74a2fc07
https://doi.org/10.1007/978-3-319-21819-9_2
https://doi.org/10.1007/978-3-319-21819-9_2
Publikováno v:
Descriptional Complexity of Formal Systems ISBN: 9783319192246
DCFS
DCFS
K. Iwama and R. Freivalds considered query algorithms where the black box contains a permutation. Since then several authors have compared quantum and deterministic query algorithms for permutations. It turns out that the case of \(n\)-permutations w
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::a5c472deb6937a2d6f031643a725540f
https://doi.org/10.1007/978-3-319-19225-3_15
https://doi.org/10.1007/978-3-319-19225-3_15
This two-volume set of LNCS 7965 and LNCS 7966 constitutes the refereed proceedings of the 40th International Colloquium on Automata, Languages and Programming, ICALP 2013, held in Riga, Latvia, in July 2013. The total of 124 revised full papers pres
Autor:
Rūsiņš Freivalds, Thomas Zeugmann
Publikováno v:
SOFSEM 2014: Theory and Practice of Computer Science ISBN: 9783319042978
SOFSEM
SOFSEM
We study active learning of classes of recursive functions by asking value queries about the target function f, where f is from the target class. That is, the query is a natural number x, and the answer to the query is f(x). The complexity measure in
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::ff06445641efc16902eeba1de372b750
https://doi.org/10.1007/978-3-319-04298-5_22
https://doi.org/10.1007/978-3-319-04298-5_22