Effective theories for circuits and automata

DOI10.1063/1.3640747zbMATH Open1317.68094OpenAlexW2044660636WikidataQ51525584 ScholiaQ51525584MaRDI QIDQ5264344FDOQ5264344

Authors Simon DeDeo 

Publication date 27 July 2015

Published in Chaos: An Interdisciplinary Journal of Nonlinear Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1106.5778

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Analytic circuit theory (94C05)

Abstract: Abstracting an effective theory from a complicated process is central to the study of complexity. Even when the underlying mechanisms are understood, or at least measurable, the presence of dissipation and irreversibility in biological, computational and social systems makes the problem harder. Here we demonstrate the construction of effective theories in the presence of both irreversibility and noise, in a dynamical model with underlying feedback. We use the Krohn-Rhodes theorem to show how the composition of underlying mechanisms can lead to innovations in the emergent effective theory. We show how dissipation and irreversibility fundamentally limit the lifetimes of these emergent structures, even though, on short timescales, the group properties may be enriched compared to their noiseless counterparts.

• scientific article; zbMATH DE number 4117877
• scientific article; zbMATH DE number 2185688
• scientific article; zbMATH DE number 618821
• scientific article; zbMATH DE number 1059244
• Descriptional and computational complexity of the circuit representation of finite automata
• scientific article; zbMATH DE number 817189
• EFFICIENT AUTOMATA CONSTRUCTIONS AND APPROXIMATE AUTOMATA
• scientific article; zbMATH DE number 3902040
• Equational theories for automata
• Automata theory. An algorithmic approach

• scientific article; zbMATH DE number 5810075 (Why is no real title available?)
• scientific article; zbMATH DE number 3755875 (Why is no real title available?)
• A decomposition theorem for probabilistic transition systems
• Function Algebras on Finite Sets
• Invariance of complexity measures for networks with unreliable gates
• On the Krohn-Rhodes cascaded decomposition theorem
• The renormalisation group and effective field theories.

(1)

• Bootstrap methods for the empirical study of decision-making and information flows in social systems

This page was built for publication: Effective theories for circuits and automata

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5264344)