Counter Machines and Distributed Automata

Abstract : We prove the equivalence of two classes of counter machines and one class of distributed automata. Our counter machines operate on finite words, which they read from left to right while incrementing or decrementing a fixed number of counters. The two classes differ in the extra features they offer: one allows to copy counter values, whereas the other allows to compute copyless sums of counters. Our distributed automata, on the other hand, operate on directed path graphs that represent words. All nodes of a path synchronously execute the same finite-state machine, whose state diagram must be acyclic except for self-loops, and each node receives as input the state of its direct predecessor. These devices form a subclass of linear-time one-way cellular automata.
Document type :
Conference papers
Complete list of metadatas

Cited literature [22 references]  Display  Hide  Download

https://hal.inria.fr/hal-01824873
Contributor : Hal Ifip <>
Submitted on : Wednesday, June 27, 2018 - 4:37:50 PM
Last modification on : Thursday, April 4, 2019 - 1:21:57 AM
Long-term archiving on: Thursday, September 27, 2018 - 1:10:44 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

Olivier Carton, Bruno Guillon, Fabian Reiter. Counter Machines and Distributed Automata. 24th International Workshop on Cellular Automata and Discrete Complex Systems (AUTOMATA), Jun 2018, Ghent, Belgium. pp.13-28, ⟨10.1007/978-3-319-92675-9_2⟩. ⟨hal-01824873⟩

Share

Metrics

Record views

566