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

Abstract

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.