Deterministic automata simulation, universality and minimality |
| |
Authors: | Cristian Calude Elena Calude Bakhadyr Khoussainov |
| |
Affiliation: | Computer Science Department, The University of Auckland, Private Bag 92109, Auckland, New Zealand |
| |
Abstract: | 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 (see, for instance [3, 6, 18–21]). 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. |
| |
Keywords: | Automata simulations Universal automaton Minimal automaton |
本文献已被 ScienceDirect 等数据库收录! |
|