Hierarchies and Undecidability Results for Iterative Arrays with Sparse Communication

Abstract : Iterative arrays with restricted internal inter-cell communication are investigated. A quantitative measure for the communication is defined by counting the number of uses of the links between cells and it is differentiated between the sum of all communications of an accepting computation and the maximum number of communications per cell occurring in accepting computations. The computational complexity of both classes of devices is investigated and put into relation. In addition, a strict hierarchy depending on the maximum number of communications per cell is established. Finally, it is shown that almost all commonly studied decidability questions are not semidecidable for iterative arrays with restricted communication and, moreover, it is not semidecidable as well whether a given iterative array belongs to a given class with restricted communication.
Document type :
Conference papers
Complete list of metadatas

Cited literature [19 references]  Display  Hide  Download

https://hal.inria.fr/hal-01824868
Contributor : Hal Ifip <>
Submitted on : Wednesday, June 27, 2018 - 4:37:27 PM
Last modification on : Wednesday, June 27, 2018 - 4:40:15 PM
Long-term archiving on : Thursday, September 27, 2018 - 1:45:09 AM

File

 Restricted access
To satisfy the distribution rights of the publisher, the document is embargoed until : 2021-01-01

Please log in to resquest access to the document

Licence


Distributed under a Creative Commons Attribution 4.0 International License

Identifiers

Citation

Andreas Malcher. Hierarchies and Undecidability Results for Iterative Arrays with Sparse Communication. 24th International Workshop on Cellular Automata and Discrete Complex Systems (AUTOMATA), Jun 2018, Ghent, Belgium. pp.100-112, ⟨10.1007/978-3-319-92675-9_8⟩. ⟨hal-01824868⟩

Share

Metrics

Record views

254