On relations defined by generalized finite automata
CC Elgot, JE Mezei - IBM Journal of Research and …, 1965 - ieeexplore.ieee.org
CC Elgot, JE Mezei
IBM Journal of Research and development, 1965•ieeexplore.ieee.orgA 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 notion of n-ary transduction 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 automata constitute a proper subclass of the n-ary transductions. The 2-ary
length-preserving transductions constitute the equilibrium (potential) behavior of 1 …
describable by a finite directed labeled graph. The notion of n-ary transduction 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 automata constitute a proper subclass of the n-ary transductions. The 2-ary
length-preserving transductions constitute the equilibrium (potential) behavior of 1 …
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 notion of n-ary transduction 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 automata constitute a proper subclass of the n-ary transductions. The 2-ary length-preserving transductions constitute the equilibrium (potential) behavior of 1-dimensional, bilateral iterative networks. The immediate consequence relation of various primitive deductive (respectively computational) systems, such as Post normal systems (respectively Turing machines) are examples of transductions. Other riches deductive systems have immediate consequence relations which are not transductions. The closure properties of the class of transductions are studied. The decomposition of transductions into simpler ones is also studied.
ieeexplore.ieee.org