Geodesic
Мeasurement of distance between regular events for multitape automata based on a new characterization of equivalence classes
Proceedings of the Yerevan State University. Physical and mathematical sciences, Tome 55 (2021) no. 1, pp. 72-80.

Voir la notice de l'article provenant de la source Math-Net.Ru

In this paper several problems related to the implementation of the method for the approximate calculation of distance between regular events for multitape finite automata are considered and resolved. An algorithm of matching for the considered regular expressions is suggested and results of the algorithm application to some specific regular expressions are adduced. The proposed method can be used not only for the mentioned implementation, but also separately.
Keywords: regular expressions, distance of regular events, string matching, multitape finite automata. 
@article{UZERU_2021_55_1_a8,
     author = {T. A. Grigoryan and M. S. Hayrapetyan},
     title = {{\CYRM}easurement of  distance between regular events for multitape automata based on a new characterization of equivalence classes},
     journal = {Proceedings of the Yerevan State University. Physical and mathematical sciences},
     pages = {72--80},
     publisher = {mathdoc},
     volume = {55},
     number = {1},
     year = {2021},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/UZERU_2021_55_1_a8/}
}
TY  - JOUR
AU  - T. A. Grigoryan
AU  - M. S. Hayrapetyan
TI  - Мeasurement of  distance between regular events for multitape automata based on a new characterization of equivalence classes
JO  - Proceedings of the Yerevan State University. Physical and mathematical sciences
PY  - 2021
SP  - 72
EP  - 80
VL  - 55
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/UZERU_2021_55_1_a8/
LA  - en
ID  - UZERU_2021_55_1_a8
ER  - 
%0 Journal Article
%A T. A. Grigoryan
%A M. S. Hayrapetyan
%T Мeasurement of  distance between regular events for multitape automata based on a new characterization of equivalence classes
%J Proceedings of the Yerevan State University. Physical and mathematical sciences
%D 2021
%P 72-80
%V 55
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/UZERU_2021_55_1_a8/
%G en
%F UZERU_2021_55_1_a8
T. A. Grigoryan; M. S. Hayrapetyan. Мeasurement of  distance between regular events for multitape automata based on a new characterization of equivalence classes. Proceedings of the Yerevan State University. Physical and mathematical sciences, Tome 55 (2021) no. 1, pp. 72-80. http://geodesic.mathdoc.fr/item/UZERU_2021_55_1_a8/

[1] M. O. Rabin, D. Scott, “Finite Automata and Their Decision Problems”, IBM J. Research and Development, 3:2 (1959), 115–125 | DOI | MR | Zbl

[2] A. A. Letichevsky, A. S. Shoukourian, S. K. Shoukourian, “The Equivalence Problem of Deterministic Multitape Finite Automata: a New Proof of Solvability Using a Multidimensional Tape”, International Conference on Language and Automata Theory and Applications, Lecture Notes in Comput. Sci., Springer, Berlin, 2010, 392–402 | DOI | MR | Zbl

[3] H. A. Grigoryan, S. K. Shoukourian, “The Equivalence Problem of Multidimensional Multitape Automata”, J. Comput. Syst. Sci., 74:7 (2008), 1131–1138 | DOI | MR

[4] H. A. Grigoryan, S. K. Shoukourian, “Polynomial Algorithm for Equivalence Problem of Deterministic Multitape Finite Automata”, Theor. Comput. Sci., 833 (2020), 120–132 | DOI | MR | Zbl

[5] A. B. Godlevsky, H. A. Grigoryan, T. A. Grigoryan, S. K. Shoukourian, “Some Results on Regular Events for Multitape Finite Automata: A Preliminary Report”, Bull. EATCS, 144 (2021) | DOI

[6] V. G. Bodnarchuk, “The Metrical Space of Events. Part I”, Cybernetics, 1:1 (1965), 20–24 | DOI

[7] T. A. Grigoryan, “An Approximate Method for Calculating the Distance between Regular Languages for Multitape Finite Automata”, Mathematical Problems of Computer Science, 54 (2020), 69–79 | DOI | MR

[8] H. Tamm, On Minimality and Size Reduction of One-Tape and Multitape Finite Automata, Univ. Helsinki, Helsinki, Finland, 2004 | Zbl

[9] H. Bunke, “Edit Distance of Regular Languages”, Analysis and Information Retrieval, 5th Annual Symposium on Document (Las Vegas, Nevada, April 15-17, 1996), 113–124 | DOI

[10] V. I. Levenshtein, “Binary Codes Capable of Correcting Deletions, Insertions and Reversals”, Sov. Phys. Dokl., 163:4 (1965), 845–848 (in Russian) | MR | Zbl

[11] A. V. Aho, R. Sethi, J. D. Ullman, Compilers: Principles, Techniques and Tools, Addison-Wesley Series in Computer Science, World Student Series Edition, 1986

[12] H. A. Grigoryan, S. K. Shoukourian, “Polynomial Algorithm for Equivalence Problem of Deterministic Multitape Finite Automata”, Theor. Comput. Sci., 833 (2020), 120–132 | DOI | MR | Zbl