Microsoft Word - S. Shokurian_3.doc Mathematical Problems of Computer Science 34, 2010. 13 Multidimensional Tapes and Multitape Automata: Recent Results and Beyond Samvel Shoukourian IT Educational and Research Center Yerevan State University Possible implications of three recent results in theory of automata and automata languages [1] are discussed. The first result is the theorem [2], which states that the equivalence problem of multidimensional multitape automata can be reduced to the equivalence problem of one- dimensional multitape automata and, thus, is also solvable. As a corollary to this, we also get, that the functional equivalence problem in the class of program schemata on a nondegenerate basis of rank unity is solvable. Although the equivalence problem of program schemata on a nondegenerate basis was investigated actively by many researchers the latter problem was open since early 60-ies [3]. Introduction of a special binary coding for elements of a free partially commutative semigroup and its justification [4] leads to consideration of a multidimensional tape cells instead of semigroup elements and, therefore, to an opportunity of their comparison as integer vectors when analyzing behaviors of two automata on a given semigroup. Specifically, it becomes possible to measure the distance between two automata during their movement on different representations of the same element of the semigroup. For the introduced coding the movement of automata on words containing more non-commutative symbols is “faster” than on words containing more commutative symbols: the distance between the initial cell and the reached cell is less in the latter case. Coding brings to the second result - a new combinatorial proof of the equivalence problem of deterministic finite multitape automata [5]. Notions of an essential diagonal of a length i for a multidimensional tape and a set of states reached by an automaton at a given essential diagonal are introduced. It is shown that for if there are essential diagonals d1 and d2 with repeating sets of reached states and for each state and each cell achieved in the considered state in d1 then there is a path from that cell to a cell in d2 where the same state is reached. Moreover, if automata are equivalent and representations of a given semigroup element that automata move on are different, then the distance between cells achieved in d1 by these automata and the distance between corresponding cells achieved in d2 coincide. In 1973 M. Bird proved that the equivalence problem for two-tape automata is solvable [5]. In 1991 T. Harju and J. Karhumäki proved the solvability of the equivalence problem for multitape automata without any restriction on the number of tapes [6]. It is based on a purely algebraic technique. Per T. Harju “the main argument of the proof uses an embedding result for ordered groups into division rings”. The suggested purely combinatorial proof of solvability [7] is similar to the solution suggested by M. Bird [5], but instead of a transformation of source automata to a commutative 14 diagram, the commutativity assumptions are taken into account via a special multidimensional tape [3][4] used for coding execution traces. The third result is the application of the developed technique for solving another automata related problem [8] open since early 70-ies [9, 10]: when is the problem of equivalence for regular expressions over a partially commutative alphabet solvable? The obtained results directly lead to consideration of the following open problems: 1. The introduced trace coding can be used for representation of sets of word tuples accepted by multitape automata. Semantics of operations used in the obtained description, which we call an extended regular expression, should be adjusted to operations introduced within coding. Basing on this new notation for regular expressions problems of analysis and synthesis for multitape automata can be considered similarly to corresponding theorems for ordinary automata. 2. Minimization problem for multitape automata can be considered as well. Instead of equivalence classes based on the length of words in the case of one-tape automata the equivalence classes here should be considered in connection with the length of essential diagonals of the multidimensional tape. References 1. M.O. Rabin, D. Scott, Finite automata and their decision problems, IBM J. Res. Dev. 3 (2) (1959) 114–125. 2. H.A. Grigorian, S.K. Shoukourian, The Equivalence Problem of Multidimensional Multitape Automata, J. Comput. System Sci. 74 (7) (208) 1131–1138. 3. M.S. Paterson, Equivalence Problems in a Model of Computation, Ph.D. Thesis, Cambridge University, 1967. 4. А.Б.Годлевский, А.А.Летичевский, С.К.Шукурян, О сводимости проблемы функциональной эквивалентности схем программ над невырожденным базисом ранга единица к эквивалентности автоматов с многомерными лентами, Кибернетика и системный анализ, № 6, с. 1-7, 1980. 5. Bird, M.: The equivalence problem for deterministic two-tape automata J. Comput. System Sci. 4 (3) (1973) 220–249. 6. Harju T., Karhumäki J., The equivalence problem of multitape finite automata, Theoret. Comput. Sci. 78 (2) (1991) 347–355. 7. 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, Proceedings of International Conference “Languages and Automata: Theory and Application LATA’2010, Trier”, Lecture Notes in Computer Science 6031, pp. 392–402, 2010. 8. A. С. Шукурян, Эквивалентность регулярных выражений над частично коммутативным алфавитом, Кибернетика и системный анализ, №3, стр. 3-11, 2009. 9. В. Н. Редько, Об алгебре коммутативных событий, Украинский математический журнал, 16, № 2, стр. 185-195, 1964. 10. В. А. Тузов,Проблемы разрешения для граф-схем с перестановочными операторами. II, Кибернетика, №5, стр. 28-32, 1971.