Skip to Main content Skip to Navigation
Conference papers

Memoryless systems generate the class of all discrete systems (Extended abstract)

Erwan Beurier 1, 2 Dominique Pastor 1, 2 David Spivak 3
Lab-STICC - Laboratoire des sciences et techniques de l'information, de la communication et de la connaissance
Abstract : Discrete systems are automata that receive streams of inputs. They update their internal state and then produce outputs. These constitute the bricks used in engineering and science in general for building complex machines. Discrete systems can be thoughts as simple as needed, and then wired together to produce arbitrarily complex systems. This representation is also thought to be universal, in the sense that a full range of objects may be described as constructions made from more modest elements, from biological systems to computers or any industrial machine. This paper aims at proving that the most complex discrete systems can reduce to a set of simple mem-oryless automata, that is, automata that do not store any history of their inputs and outputs. Such simplicity makes sense from a biological point of view as well, where complex objects like the brain can be reduced to an interaction of mere cells. From connections between atomic elements emerges the complexity of systems.
Complete list of metadata
Contributor : Dominique Pastor <>
Submitted on : Thursday, July 4, 2019 - 12:18:30 PM
Last modification on : Wednesday, July 21, 2021 - 7:44:01 AM


  • HAL Id : hal-02173177, version 1


Erwan Beurier, Dominique Pastor, David Spivak. Memoryless systems generate the class of all discrete systems (Extended abstract). ACT 2019: Applied Category Theory Conference, Jul 2019, Oxford, United Kingdom. ⟨hal-02173177⟩



Record views