Two-sided finite-state transductions (abbreviated version)

Abstract

A transduction, in the sense of this paper, is a n-ary word relation (which may be a function) describable by a finite directed labeled graph. The class of all n-ary transductions is co-extensive with the Kleenean closure of finite n-ary relations. The 1-ary transductions are exactly the sets recognizable by finite automata. However, for n > 1 the relations recognizable by finite automata constitute a proper subclass of the n-ary transductions. The closure properties of the class of transductions are studied. The decomposition of transductions into simpler ones is also studied.