Some Results on Regular Events for Multitape Finite Automata: A Preliminary Report

Alexander Godlevsky, Hayk Grigoryan, Tigran Grigoryan, Samvel Shoukourian, The Formal Language Theory Column by Giovanni Pighizzini


A new representation of languages for multitape finite automata is con- sidered based on a special binary coding of elements in a free partially com- mutative semigroup. The mentioned coding was used previously for solution of several problems in theory of automata. An overview of these results, as well as, related works are presented.

Some new results based on this representation, which are currently un- der review, are formulated. They include: a new characterization for com- mutation classes of free partially commutative semigroups (trace monoids); a metric, based on the introduced characterization, and a metric space for regular events over a free partially commutative semigroup; the synthesis of a multitape finite automaton for a given regular expression; and a method for the approximate calculation of distance between regular events for multitape finite automata.

Full Text:



  • There are currently no refbacks.