Computation on binary tree-networks
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).
- Modal functions for concise definition of state machines and products
- On simulation in automata networks
- A practical fixed-parameter algorithm for constructing tree-child networks from multiple binary trees
- Complete simulation of automata networks
- scientific article; zbMATH DE number 2186525 (Why is no real title available?)
- Sur quelques classes d’applications de N² dans les ensembles finis
- scientific article; zbMATH DE number 4078823 (Why is no real title available?)
- ASYNCHRONOUS AUTOMATA NETWORKS CAN EMULATE ANY SYNCHRONOUS AUTOMATA NETWORK
This page was built for publication: Computation on binary tree-networks
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1082077)
