Article Per Year (5 Year)
p-Index From 2021 - 2026
0
P-Index
This Author published in this journals
All Journal Bulletin of Electrical Engineering and Informatics
Mihail P. Sinev
Penza State Technological University
Electrical & Electronics Engineering

Published : 1 Documents Claim Missing Document
Claim Missing Document
Check
Articles

Found 1 Documents
Search

 1 
Search for a substring of characters using the theory of non-deterministic finite automata and vector-character architecture Dmitry V. Pashchenko; Dmitry A. Trokoz; Alexey I. Martyshkin; Mihail P. Sinev; Boris L. Svistunov
Bulletin of Electrical Engineering and Informatics Vol 9, No 3: June 2020
Publisher : Institute of Advanced Engineering and Science

Show Abstract | Download Original | Original Source | Check in Google Scholar | Full PDF (892.714 KB) | DOI: 10.11591/eei.v9i3.1720

Abstract

The paper proposed an algorithm which purpose is searching for a substring of characters in a string. Principle of its operation is based on the theory of non-deterministic finite automata and vector-character architecture. It is able to provide the linear computational complexity of searching for a substring depending on the length of the searched string measured in the number of operations with hyperdimensional vectors when repeatedly searching for different strings in a target line. None of the existing algorithms has such a low level of computational complexity. The disadvantages of the proposed algorithm are the fact that the existing hardware implementations of computing systems for performing operations with hyperdimensional vectors require a large number of machine instructions, which reduces the gain from this algorithm. Despite this, in the future, it is possible to create a hardware implementation that can ensure the execution of operations with hyperdimensional vectors in one cycle, which will allow the proposed algorithm to be applied in practice.
Co-Authors Alexey I. Martyshkin Boris L. Svistunov Dmitry A. Trokoz Dmitry V. Pashchenko