Abstract:
The purpose of this Thesis is to study, from the mathematical point of view, a new type of questions about finite automata, questions motivated by looking at automata as toy models of physical particles. Working along the line of research initiated by Moore, two computational complementarity principles are studied, (for finite-deterministic, complete or incomplete, nondeterministic-automata with outputs but no initial states) both theoretically and experimentally; they mimic the physical complementarity and the Einstein-Podolsky-Rosen effect. Automata are studied via simulations (informally, the automaton A is simulated by the automaton B if B can perform all computations A can execute and produces the same outputs; two automata are equivalent in case they simulate each other). A new type of minimization problem will be solved and the solution is proved to be unique up to an isomorphism; the minimal automaton equivalent to a given automaton can be constructed only in terms of outputs for deterministic complete or incomplete automata, but one needs the whole internal machinery for nondeterministic automata. It happens that minimal automata are exactly the automata which may feature computational complementarity. Even if the original motivation will remain only metaphorical, the physical motivation was good to suggest new definitions and constructions (simulation, universality, complementarity) leading to new mathematical results (existence of universal finite automaton, solving in a new way the minimalization problem for nondeterministic automata).