deterministic automaton

(redirected from Deterministic computation)

deterministic automaton

A finite-state automaton in which the overall course of the computation is completely determined by the program, the starting state, and the initial inputs. The class of problems solvable by such automata is the class P (see polynomial-time algorithm).
This article is provided by FOLDOC - Free Online Dictionary of Computing (
The following article is from The Great Soviet Encyclopedia (1979). It might be outdated or ideologically biased.

Deterministic Automaton


a mathematical model of a system whose states change discretely with time in such a way that every state of the system is completely defined by the previous state and the input signal. A deterministic automaton is formally described in the form of the function f(Si, aj) = ak, where si is the input signal and aj is the previous state. A typical example of a deterministic automation is a digital computer, in which the state of all registers and cells is determined by their previous state and by the input signals. Deterministic automatons are a natural form for describing the logical structure of discrete computing devices. Conversion to nondeterministic automatons is possible both by the introduction of the probabilities of a change of states and by the free selection of the next state.

The Great Soviet Encyclopedia, 3rd Edition (1970-1979). © 2010 The Gale Group, Inc. All rights reserved.
References in periodicals archive ?
If we would like to have an efficient simulation of a membrane computation with a general operating system (with a mainstream hardware), we would have serious restrictions: we would have to use a fixed number of membranes (processes), because of the fixed number of CPUs, deterministic computation with random value generation can simulate several language generating P-systems.
Among their topics are a history and brief introduction to membrane computing, deterministic computation with random G-networks, Carl Adam Petri and Petri Nets, and from rocket control to virtual design.

Full browser ?