%0 Conference Proceedings
%T Iterative Arrays with Finite Inter-cell Communication
%+ Justus-Liebig-Universität Gießen = Justus Liebig University (JLU)
%A Kutrib, Martin
%A Malcher, Andreas
%< avec comité de lecture
%( Lecture Notes in Computer Science
%B 25th International Workshop on Cellular Automata and Discrete Complex Systems (AUTOMATA)
%C Guadalajara, Mexico
%Y Alonso Castillo-Ramirez
%Y Pedro P. B. de Oliveira
%I Springer International Publishing
%3 Cellular Automata and Discrete Complex Systems
%V LNCS-11525
%P 35-47
%8 2019-06-26
%D 2019
%R 10.1007/978-3-030-20981-0_3
%Z Computer Science [cs]Conference papers
%X Iterative arrays whose internal inter-cell communication is quantitatively restricted are investigated. The quantity of communication is measured by counting the number of uses of the links between cells. In particular, iterative arrays are studied where the maximum number of communications per cell occurring in accepting computations is drastically bounded by a constant number. Additionally, the iterative arrays have to work in realtime. We study the computational capacity of such devices. One main result is that a strict and dense hierarchy with respect to the constant number of communications exists. Due to their very restricted communication, the question arises whether the usually studied decidability problems such as, for example, emptiness, finiteness, inclusion, or equivalence become decidable for such devices. However, by reduction of Hilbert’s tenth problem it can be shown that all such decidability questions remain undecidable.
%G English
%Z TC 1
%Z WG 1.5
%2 https://inria.hal.science/hal-02312607/document
%2 https://inria.hal.science/hal-02312607/file/484947_1_En_3_Chapter.pdf
%L hal-02312607
%U https://inria.hal.science/hal-02312607
%~ IFIP-LNCS
%~ IFIP
%~ IFIP-TC
%~ IFIP-TC1
%~ IFIP-WG1-5
%~ IFIP-AUTOMATA
%~ IFIP-LNCS-11525