Geodesic
Mutual modeling of sequential and parallel word computations
Vestnik Udmurtskogo universiteta. Matematika, mehanika, kompʹûternye nauki, Tome 34 (2024) no. 2, pp. 299-308 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

The work is devoted to the connection between parallel and sequential computing. On the one hand, we consider a class of word predicates based on sequential calculations, limited in memory by constants and having polynomial time complexity. On the other hand, we consider a class of word predicates that are computable on parallel alternating machines in logarithmic time. The coincidence of the corresponding classes is proven. The direction of using the obtained results for mutual transformation and combination of calculations on molecular biosimilar sequential machines and parallel calculations on vector-matrix computers is proposed. Intended applications: real-time image processing for control tasks, analysis of large texts and other big data.
Keywords: word predicates, parallel computing, sequential computing, big data, computational complexity, biosimilar computers, vector-matrix computers
Mots-clés : alternation 
@article{VUU_2024_34_2_a7,
     author = {A. P. Bel'tyukov and S. G. Maslov and M. Joudakizadeh},
     title = {Mutual modeling of sequential and parallel word computations},
     journal = {Vestnik Udmurtskogo universiteta. Matematika, mehanika, kompʹ\^uternye nauki},
     pages = {299--308},
     year = {2024},
     volume = {34},
     number = {2},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/VUU_2024_34_2_a7/}
}
TY  - JOUR
AU  - A. P. Bel'tyukov
AU  - S. G. Maslov
AU  - M. Joudakizadeh
TI  - Mutual modeling of sequential and parallel word computations
JO  - Vestnik Udmurtskogo universiteta. Matematika, mehanika, kompʹûternye nauki
PY  - 2024
SP  - 299
EP  - 308
VL  - 34
IS  - 2
UR  - http://geodesic.mathdoc.fr/item/VUU_2024_34_2_a7/
LA  - ru
ID  - VUU_2024_34_2_a7
ER  - 
%0 Journal Article
%A A. P. Bel'tyukov
%A S. G. Maslov
%A M. Joudakizadeh
%T Mutual modeling of sequential and parallel word computations
%J Vestnik Udmurtskogo universiteta. Matematika, mehanika, kompʹûternye nauki
%D 2024
%P 299-308
%V 34
%N 2
%U http://geodesic.mathdoc.fr/item/VUU_2024_34_2_a7/
%G ru
%F VUU_2024_34_2_a7
A. P. Bel'tyukov; S. G. Maslov; M. Joudakizadeh. Mutual modeling of sequential and parallel word computations. Vestnik Udmurtskogo universiteta. Matematika, mehanika, kompʹûternye nauki, Tome 34 (2024) no. 2, pp. 299-308. http://geodesic.mathdoc.fr/item/VUU_2024_34_2_a7/

[1] Clote P., “Nondeterministic stack register machines”, Theoretical Computer Science, 178:1–2 (1997), 37–76 | DOI | MR | Zbl

[2] Loos R., Ogihara M., “Complexity theory for splicing systems”, Theoretical Computer Science, 386:1–2 (2007), 132–150 | DOI | MR | Zbl

[3] Goldreich O., “Computational complexity: a conceptual perspective”, ACM SIGACT News, 39:3 (2008), 35–39 | DOI | MR

[4] Tayur S., “Unconventional computing: applications, hardware, algorithms”, Quantum Computing, 48:1 (2021) | DOI

[5] Teuscher C., “Unconventional computing catechism”, Frontiers in Robotics and AI, 1:10 (2014) | DOI

[6] Handley W.G., “Deterministic summation modulo $\mathscr{B}_n$, the semigroup of binary relations on $\{0, 1,\ldots, n-1\}$”, Theoretical Computer Science, 172:1–2 (1997), 135–174 | DOI | MR | Zbl

[7] Esbelin H.-A., “Counting modulo finite semigroups”, Theoretical Computer Science, 257:1–2 (2001), 107–114 | DOI | MR | Zbl

[8] Durand A., More M., “Nonerasing, counting, and majority over the linear time hierarchy”, Information and Computation, 174:2 (2002), 132–142 | DOI | MR | Zbl