|
Section
|
Computer science
|
|
Title
|
Mutual modeling of sequential and parallel word computations
|
|
Author(-s)
|
Beltyukov A.P.a,
Maslov S.G.a,
Joudakizadeh M.a
|
|
Affiliations
|
Udmurt State Universitya
|
|
Abstract
|
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, alternation
|
|
UDC
|
004.04
|
|
MSC
|
03D15, 68Q05
|
|
DOI
|
10.35634/vm240208
|
|
Received
|
16 April 2024
|
|
Language
|
Russian
|
|
Citation
|
Beltyukov A.P., Maslov S.G., Joudakizadeh M. Mutual modeling of sequential and parallel word computations, Vestnik Udmurtskogo Universiteta. Matematika. Mekhanika. Komp'yuternye Nauki, 2024, vol. 34, issue 2, pp. 299-308.
|
|
References
|
- Clote P. Nondeterministic stack register machines, Theoretical Computer Science, 1997, vol. 178, issues 1–2, pp. 37–76. https://doi.org/10.1016/S0304-3975(96)00051-5
- Loos R., Ogihara M. Complexity theory for splicing systems, Theoretical Computer Science, 2007, vol. 386, issues 1–2, pp. 132–150. https://doi.org/10.1016/j.tcs.2007.06.010
- Goldreich O. Computational complexity: a conceptual perspective, ACM SIGACT News, 2008, vol. 39, no. 3, pp. 35–39. https://doi.org/10.1145/1412700.1412710
- Tayur S. Unconventional computing: applications, hardware, algorithms, Quantum Computing, 2021, vol. 48, no. 1. https://doi.org/10.1287/orms.2021.01.14
- Teuscher C. Unconventional computing catechism, Frontiers in Robotics and AI, 2014, vol. 1, issue 10. https://doi.org/10.3389/frobt.2014.00010
- Handley W.G. Deterministic summation modulo $\mathscr{B}_n$, the semigroup of binary relations on {$0, 1,\ldots, n-1$}, Theoretical Computer Science, 1997, vol. 172, issues 1–2, pp. 135–174. https://doi.org/10.1016/S0304-3975(95)00245-6
- Esbelin H.-A. Counting modulo finite semigroups, Theoretical Computer Science, 2001, vol. 257, issues 1–2, pp. 107–114. https://doi.org/10.1016/S0304-3975(00)00112-2
- Durand A., More M. Nonerasing, counting, and majority over the linear time hierarchy, Information and Computation, 2002, vol. 174, issue 2, pp. 132–142. https://doi.org/10.1006/inco.2001.3084
|
|
Full text
|
|
+7 (3412) 91 60 92
Russian