Computation on binary tree-networks (Q1082077)

In this paper networks \(N=(G,X)\) of n finite state automata are considered having the same nonempty state-set X, and being connected according to a directed graph G of order n. It is shown that for any finite set X, the set \(A(X^ n)\) of mappings from \(X^ n\) into itself is computable on N iff N contains an automaton which can directly receive informations from any automaton of the network. Then the case of binary tree networks (BTN) is considered, i.e. the case where G is a tree and \(X=\{0,1\}\). It is proved that a non-bijective mapping \(F\in A(X^ n)\) from \(X^ n\) into itself is computable on a BTN iff \(\sum_{x}\lfloor | F^{-1}(x)| /2\rfloor \geq 2^{n-p-1}\), where p is the maximum number of pending vertices of a caterpillar of G, and \(\lfloor a\rfloor\) denotes the greatest integer lower than or equal to a. The paper generalizes the results of the author's paper in J. Comput. Syst. Sci. 26, 269-277 (1983; Zbl 0508.94025).