An Approximate Method for Calculating the Distance Between Regular Languages for Multitape Finite Automata
DOI:
https://doi.org/10.51408/1963-0060Keywords:
Multitape finite automata, Regular languages, Metric spaceAbstract
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.
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
How to Cite
Issue
Section
License
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.
