*
Share This
Automaton table
table started by
Freebase Web Team for the Computer Science Base
There is no user-contributed description yet.
x
Add another type with the property you want to view.
| x name | x image | x Language class recognized | x article |
|---|---|---|---|
| x Turing machine |
|
Recursively enumerable language |
Turing machines are basic abstract symbol-manipulating devices. They were hypothesized in the Church's thesis (1936) that any computable function can be can be computed by a Turing machine. Since the definition of "computable function" is not...
|
| x Deterministic finite state machine |
|
Regular language |
In the theory of computation, a deterministic finite state machine (also known as deterministic finite state automaton (DFSA) or deterministic finite automaton (DFA) ) is a finite state machine where for each pair of state and input symbol there is...
|
| x Nondeterministic finite state machine |
|
Regular language |
In the theory of computation, a nondeterministic finite state machine or nondeterministic finite automaton (NFA) is a finite state machine where for each pair of state and input symbol there may be several possible next states. This distinguishes it...
|
| x Pushdown automaton |
|
Context-free language |
In automata theory, a pushdown automaton (PDA) is a finite automaton that can make use of a stack containing data.
Pushdown automata differ from normal finite state machines in two ways:
Pushdown automata choose a transition by indexing a table by...
|
| x Deterministic pushdown automaton | Deterministic context-free language |
In automata theory, a pushdown automaton is a finite automaton with an additional stack of symbols; its transitions can take the top symbol on the stack and depend on its value, and they can add a new top symbol to the stack. A deterministic...
|
|
| x Aperiodic finite state automaton | Star-free language |
An aperiodic finite-state automaton is a finite-state automaton whose transition monoid is aperiodic.
A regular language is star-free if and only if it is accepted by an automaton with a finite and aperiodic transition monoid. This celebrated result...
|
|
| x Embedded pushdown automaton | Mildly context-sensitive language |
An embedded pushdown automaton or EPDA is a computational model that parse languages in the tree-adjoining grammar (TAG). It is similar to the context-free grammar-parsing pushdown automaton, except that instead of using a stack (data structure) to...
|
|
| x Nested stack automaton | Indexed language |
In automata theory, a nested stack automaton is a finite automaton that can make use of a stack containing data which can be additional stacks. A nested stack automaton may read its stack, in addition to pushing or popping it. A nested stack...
|
|
| x Linear bounded automaton | Context-sensitive language |
A linear bounded automaton (plural linear bounded automata, abbreviated LBA) is a restricted form of a non-deterministic Turing machine. It possesses a tape made up of cells that can contain symbols from a finite alphabet, a head that can read from...
|
|
| x Decider | Recursive language |
In computability theory, a machine that always halts—also called a decider (Sipser, 1996) or a total Turing machine (Kozen, 1997)—is a Turing machine that halts for every input.
Because it always halts, the machine is able to decide whether a given...
|
|
| x Parity automaton |
A parity automaton is a variant of a finite state automaton that accepts infinite inputs. Unlike usual finite state automata, there is no set of final states; instead, each state is assigned a natural number. It accepts an infinite input sequence if...
|
||
| x Büchi automaton | Omega-regular language |
A Büchi automaton is the extension of a finite state automaton to infinite inputs. It accepts an infinite input sequence iff there exists a run of the automaton (in case of a deterministic automaton, there is exactly one possible run) which visits ...
|
|
| x Kripke structure |
A Kripke structure is a type of nondeterministic finite state machine proposed by Saul Kripke in 1963, used in model checking to represent the behaviour of a system. It is basically a graph whose nodes represent the reachable states of the system...
|
||
| x Tree walking automaton |
A tree walking automaton (TWA) is a type of finite automaton that deals with tree structures rather than strings.
The following article deals with tree walking automata. For a different notion of tree automaton, closely related to regular tree...
|
||
| x Pebble automaton |
In information science, a pebble automaton is an extension of tree walking automata which allows the automaton to use a finite amount of "pebbles", used for marking tree node. The result is a model stronger than ordinary tree walking automata, but...
|
||
| x Quantum finite automata |
In quantum computing, quantum finite automata or QFA are a quantum analog of probabilistic automata. They are related to quantum computers in a similar fashion as finite automata are related to Turing machines. Several types of automata may be...
|
||
| x Learning Automata |
A branch of the theory of Adaptive control is devoted to learning automata surveyed by Narendra and Thathachar which were originally described explicitly as finite state automata.
Philip Aranzulla and John Mellor.
Narendra K., Thathachar M.A.L.,...
|
||
| x Levenshtein automaton |
In computer science, Levenshtein automata are a family of finite state automata that can recognize the set V of all words in a formal language for which the Levenshtein distance to an arbitrary word W does not exceed a particular constant. A...
|
||
| x Lattice gas automaton |
Lattice gas automata (LGA) or lattice gas cellular automata (LGCA) methods are a series of cellular automata methods used to simulate fluid flows. It was the precursor to the lattice Boltzmann methods. From the LGCA, it is possible to derive the...
|
||
| x Continuous spatial automata |
Continuous spatial automata, unlike cellular automata, have a continuum of locations. The state of a location is a finite number of real numbers. Time is also continuous, and the state evolves according to differential equations. One important...
|
||
| x Semiautomaton |
In theoretical computer science, a semiautomaton is an automaton having only an input, and no output. It consists of a set Q of states, a set Σ called the input alphabet, and a function T: Q × Σ → Q called the transition function.
Associated to any...
|
||
| x Probabilistic automaton |
In mathematics and computer science, the probabilistic automaton (PA) is a generalization of the non-deterministic finite automaton; it includes the probability of a given transition into the transition function, turning it into a transition matrix...
|
||
| x Continuous automaton |
A continuous automaton can be described as a cellular automaton extended so the valid states a cell can take are not just discrete (for example, the states consist of integers between 0 and 3), but continuous, for example, the real number range [0,1...
|
||
