Deterministic automata simulation, universality and minimality

Annals of Pure and Applied Logic 90 (1-3):263-276 (1997)


Finite automata have been recently used as alternative, discrete models in theoretical physics, especially in problems related to the dichotomy between endophysical/intrinsic and exophysical/ extrinsic perception . These studies deal with Moore experiments; the main result states that it is impossible to determine the initial state of an automaton, and, consequently, a discrete model of Heisenberg uncertainty has been suggested. For this aim the classical theory of finite automata — which considers automata with initial states — is not adequate, and a new approach is necessary. A study of finite deterministic automata without initial states is exactly the aim of this paper. We will define and investigate the complexity of various types of simulations between automata. Minimal automata will be constructed and proven to be unique up to an isomorphism. We will build our results on an extension of Myhill-Nerode technique; all constructions will make use of “automata responses” to simple experiments only, i.e., no information about the internal machinery will be considered available.

Download options


    Upload a copy of this work     Papers currently archived: 72,743

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library


Added to PP

7 (#1,075,902)

6 months
1 (#387,390)

Historical graph of downloads
How can I increase my downloads?

Author's Profile

Cristian S. Calude
University of Auckland

References found in this work

Remarks on the Mind-Body Question.E. Wigner - 2003 - In John Heil (ed.), Philosophy of Mind: A Guide and Anthology. Oxford University Press.
Against ”Measurement'.J. S. Bell - 2004 - In Speakable and Unspeakable in Quantum Mechanics. Cambridge University Press. pp. 213--231.

Add more references

Citations of this work

No citations found.

Add more citations