Zobrazeno 1 - 5
of 5
pro vyhledávání: '"Maksims Dimitrijevs"'
Publikováno v:
Discrete Mathematics & Theoretical Computer Science, Vol vol. 22 no. 1, Iss Automata, Logic and Semantics (2020)
It is known that 2-state binary and 3-state unary probabilistic finite automata and 2-state unary quantum finite automata recognize uncountably many languages with cutpoints. These results have been obtained by associating each recognized language wi
Externí odkaz:
https://doaj.org/article/8d285fbc2e3a4d7692d6dae9d7ce0b4a
Publikováno v:
Descriptional Complexity of Formal Systems ISBN: 9783319602516
DCFS
DCFS
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 r
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::50e339f1a49bf39878b92a0fd8621ed4
https://doi.org/10.1142/s012905411950028x
https://doi.org/10.1142/s012905411950028x
Publikováno v:
RAIRO - Theoretical Informatics and Applications. 52:111-126
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
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::b84893313e0dfd591531f9d18639adbe
https://doi.org/10.1051/ita/2018012
https://doi.org/10.1051/ita/2018012
Autor:
Maksims Dimitrijevs, Kristine Cipola
Publikováno v:
Baltic Journal of Modern Computing. 4
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::9e3da235d93ef83cedea789ccbf2dd03
https://doi.org/10.22364/bjmc.2016.4.4.19
https://doi.org/10.22364/bjmc.2016.4.4.19
Autor:
Maksims Dimitrijevs
Publikováno v:
Lecture Notes in Computer Science ISBN: 9783662491911
SOFSEM
SOFSEM
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 langu
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::814660a138167328a53c7a0e0bc942bd
https://doi.org/10.1007/978-3-662-49192-8_21
https://doi.org/10.1007/978-3-662-49192-8_21
