Local Search in Non-deterministic Finite Automata with Extensions

Abstract

In this work we present the theoretical approach over solving the back-reference problem in regular expression matching within the almost polynomial time using local search within the memory, while within the growth of capturing groups we obtain the exponential results: for this purpose we develop the modified matching algorithm operating on non-deterministic finite automata within the modified search algorithm and presence of the specific method also over extended regular expressions. This is made due to the algorithm which can be adjusted for approximate searching allowing us to imply extended operators and features of modern regular expressions like intersection, subtraction and complement, as well as back-references. The review of past work on this issues is also done: to the present time there is no discrete algorithm in systems like automata for local search. Thus, we obtain the new result of matching the pattern locally while the simulating algorithm works as usual. The obtained result also refers to the membership problem with local bound which can be set in the main algorithm presented in this article.