Geodesic
Some results on regular expressions for multitape finite automata
Proceedings of the Yerevan State University. Physical and mathematical sciences, Tome 53 (2019) no. 2, pp. 82-90.

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

We consider sets of word tuples accepted by multitape finite automata. We use the known notation for regular expressions that describes languages accepted by one-tape automata. Nevertheless, the interpretation of the “concatenation” operation is different in this case. The algebra of events for multitape finite automata is defined in the same way as for one-tape automata. It is shown that the introduced algebra is a Kleene algebra. It is also shown that some known results for the algebra of events accepted by one-tape finite automata are valid in this case too.
Keywords: Regular expressions, algebra of events, multitape finite automata. 
@article{UZERU_2019_53_2_a1,
     author = {T. A. Grigoryan},
     title = {Some results on regular expressions for multitape finite automata},
     journal = {Proceedings of the Yerevan State University. Physical and mathematical sciences},
     pages = {82--90},
     publisher = {mathdoc},
     volume = {53},
     number = {2},
     year = {2019},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/UZERU_2019_53_2_a1/}
}
TY  - JOUR
AU  - T. A. Grigoryan
TI  - Some results on regular expressions for multitape finite automata
JO  - Proceedings of the Yerevan State University. Physical and mathematical sciences
PY  - 2019
SP  - 82
EP  - 90
VL  - 53
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/UZERU_2019_53_2_a1/
LA  - en
ID  - UZERU_2019_53_2_a1
ER  - 
%0 Journal Article
%A T. A. Grigoryan
%T Some results on regular expressions for multitape finite automata
%J Proceedings of the Yerevan State University. Physical and mathematical sciences
%D 2019
%P 82-90
%V 53
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/UZERU_2019_53_2_a1/
%G en
%F UZERU_2019_53_2_a1
T. A. Grigoryan. Some results on regular expressions for multitape finite automata. Proceedings of the Yerevan State University. Physical and mathematical sciences, Tome 53 (2019) no. 2, pp. 82-90. http://geodesic.mathdoc.fr/item/UZERU_2019_53_2_a1/

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

[2] V. M. Glushkov, “The Abstract Theory of Automata”, Russian Mathematical Surveys, 16:5 (1961) | DOI | MR

[3] B. G. Mirkin, “On the Theory of Multitape Automata”, Cybernetics and Systems Analysis, 2:5 (1966), 9–14 | MR

[4] A. B. Godlevskiï, A. A. Letichevskiï, S. K. Shukuryan, “Reducibility of Program-Scheme Functional Equivalence on a Nondegenerate Basis of Rank Unity to the Equivalence of Automata with Multidimensional Tapes”, Cybernetics and Systems Analysis, 16:6 (1980), 793–799 | MR

[5] P. H. Starke, “On the Representability of Relations by Deterministic and Nondeterministic Multi-Tape Automata”, Mathematical Foundations of Computer Science, International Symposium on Mathematical Foundations of Computer Science, Springer, Berlin, 1975, 114–124 | MR

[6] 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 | MR

[7] V. G. Bodnarchuk, “Systems of Equations in the Algebra of Events”, USSR Computational Mathematics and Mathematical Physics, 3:6 (1963), 1470–1487 (in Russian) | MR

[8] D. Kozen, “A Completeness Theorem for Kleene Algebras and the Algebra of Regular Events”, Inform. and Comput., 110:2 (1994), 366–390 | MR

[9] V. Pratt, “Dynamic Algebras as a Well-Behaved Fragment of Relation Algebras”, International Conference on Algebraic Logic and Universal Algebra in Computer Science, 1988, 77–110