An Approximate Method for Calculating the Distance Between Regular Languages for Multitape Finite Automata

Authors

  • Tigran A. Grigoryan Yerevan State University

DOI:

https://doi.org/10.51408/1963-0060

Keywords:

Multitape finite automata, Regular languages, Metric space

Abstract

Sets of word tuples, accepted by multitape finite automata and a metric space for languages accepted by these automata, are considered. These languages are represented using the same notation as the known notation of regular expressions for languages accepted by one-tape automata. The only difference is the interpretation of the ”concatenation” operation in the notation. An algorithm is proposed for calculating the introduced distance between regular languages accepted by multitape finite automata.

Author Biography

Tigran A. Grigoryan, Yerevan State University

IT Educational and Research Center

References

M. O. Rabin and D. S. Scott, “Finite Automata and Their Decision Problems”, IBM J. Res. Dev., vol. 3, no. 2, pp. 114–125, 1959.

M. Bird, “The Equivalence Problem for Deterministic Two-Tape Automata”, J. Comput. Syst. Sci., vol. 7, no. 2, pp. 218–236, 1973.

T. Harju and J. Karhumaki, “The Equivalence Problem of Multitape Finite Automata”, Theor. Comput. Sci., vol. 78, no. 2, pp. 347-355, 1991.

B. G. Mirkin, ”On the theory of multitape automata”, Cybernetics, vol. 2, no. 5, pp. 9-14, 1966. doi:10.1007/BF01073664.

P. H. Starke, “On the Representability of Relations by Deterministic and Nondeterministic MultiTape Automata”, International Symposium on Mathematical Foundations of Computer Science, pp. 114-124, 1975.

A. A. Letichevsky, A. S. Shoukourian and 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, pp. 392–402, 2010.

T. A. Grigoryan, “Some Results on Regular Expressions for Multitape Finite Automata”, Proceedings of the YSU: Physical and Mathematical Sciences, vol. 53, no. 2, pp. 82-90, 2019.

V. M. Glushkov, “The Abstract Theory of Automata”, Russian Mathematical Surveys, vol. 16, no. 5, pp. 1-53, 1961.

A. B. Godlevskii, A. A. Letichevskii and S. K. Shukuryan, “Reducibility of programscheme functional equivalence on a nondegenerate basis of rank unity to the equivalence of automata with multidimensional tapes”, Cybernetics, vol. 16, no. 6, pp. 793-799, 1980.

A. H. Clifford and G. B. Preston, The Algebraic Theory of Semigroups, Second Edition, ser. Mathematical Surveys and Monographs, American Mathematical Society, vol. 7.1, 1961.

H. A. Grigoryan and S. K. Shoukourian. ”Polynomial algorithm for equivalence problem of deterministic multitape finite automata”, Theor. Comput. Sci., vol. 833, pp. 120-132, 2020.

F. Hausdorff, Set Theory, Fourth Edition, Chelsea Pub Co, 1991.

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

Downloads

Published

2020-12-25

How to Cite

Grigoryan, T. A. . (2020). An Approximate Method for Calculating the Distance Between Regular Languages for Multitape Finite Automata. Mathematical Problems of Computer Science, 54, 69–79. https://doi.org/10.51408/1963-0060