A complete solution of the minimisation problem for a set of binary two-tape automata

摘要

In this paper we complete the solution of the minimisation problem for a set of binary two-tape automata. The beginning of the solution was published in Discrete Mathematics and Applications 18 (2008), pp. 271-292.The minimisation problem consists of finding all minimal automata in each equivalence class of a considered set. The search is performed by means of equivalent transformations of automata. The solution of the problem is based on an appropriate partition of the equivalence class.This research was supported by the Russian Foundation for Basic Research, grant 06-01-00106.