Эквивалентность двумерных многоленточных автоматов

Abstract

Розглянуто проблему еквівалентності багатострічкових автоматів з багатовимірними стрічками, в яких рух головок монотонний у всіх напрямках (рух у зворотному напрямку неможливий). Доведено розв’язність спеціального випадку проблеми, коли розмірність стрічок менше або дорівнює двом.The paper addresses the equivalence of multitape automata with multi-dimensional tapes. Their heads move monotonically in all directions (no backward motion). The special case where the dimensions of tapes are less than or equal to 2 is proved to be solvable.