Concept
Finite-state machine
Related concepts (42)
Transformation semigroup
In algebra, a transformation semigroup (or composition semigroup) is a collection of transformations (functions from a set to itself) that is closed under function composition. If it includes the identity function, it is a monoid, called a transformation (or composition) monoid. This is the semigroup analogue of a permutation group. A transformation semigroup of a set has a tautological semigroup action on that set. Such actions are characterized by being faithful, i.e., if two elements of the semigroup have the same action, then they are equal.
Petri net
A Petri net, also known as a place/transition (PT) net, is one of several mathematical modeling languages for the description of distributed systems. It is a class of discrete event dynamic system. A Petri net is a directed bipartite graph that has two types of elements: places and transitions. Place elements are depicted as white circles and transition elements are depicted as rectangles. A place can contain any number of tokens, depicted as black circles. A transition is enabled if all places connected to it as inputs contain at least one token.
Decision table
Decision tables are a concise visual representation for specifying which actions to perform depending on given conditions. They are algorithms whose output is a set of actions. The information expressed in decision tables could also be represented as decision trees or in a programming language as a series of if-then-else and switch-case statements. Each decision corresponds to a variable, relation or predicate whose possible values are listed among the condition alternatives.
Alternating finite automaton
In automata theory, an alternating finite automaton (AFA) is a nondeterministic finite automaton whose transitions are divided into existential and universal transitions. For example, let A be an alternating automaton. For an existential transition , A nondeterministically chooses to switch the state to either or , reading a. Thus, behaving like a regular nondeterministic finite automaton. For a universal transition , A moves to and , reading a, simulating the behavior of a parallel machine.
Quantum finite automaton
In quantum computing, quantum finite automata (QFA) or quantum state machines are a quantum analog of probabilistic automata or a Markov decision process. They provide a mathematical abstraction of real-world quantum computers. Several types of automata may be defined, including measure-once and measure-many automata. Quantum finite automata can also be understood as the quantization of subshifts of finite type, or as a quantization of Markov chains. QFAs are, in turn, special cases of geometric finite automata or topological finite automata.
Combinational logic
In automata theory, combinational logic (also referred to as time-independent logic or combinatorial logic ) is a type of digital logic which is implemented by Boolean circuits, where the output is a pure function of the present input only. This is in contrast to sequential logic, in which the output depends not only on the present input but also on the history of the input. In other words, sequential logic has memory while combinational logic does not.
Tree automaton
A tree automaton is a type of state machine. Tree automata deal with tree structures, rather than the strings of more conventional state machines. The following article deals with branching tree automata, which correspond to regular languages of trees. As with classical automata, finite tree automata (FTA) can be either a deterministic automaton or not. According to how the automaton processes the input tree, finite tree automata can be of two types: (a) bottom up, (b) top down.
Nondeterministic algorithm
In computer programming, a nondeterministic algorithm is an algorithm that, even for the same input, can exhibit different behaviors on different runs, as opposed to a deterministic algorithm. There are several ways an algorithm may behave differently from run to run. A concurrent algorithm can perform differently on different runs due to a race condition. A probabilistic algorithm's behaviors depends on a random number generator.
Espresso heuristic logic minimizer
The ESPRESSO logic minimizer is a computer program using heuristic and specific algorithms for efficiently reducing the complexity of digital logic gate circuits. ESPRESSO-I was originally developed at IBM by Robert K. Brayton et al. in 1982. and improved as ESPRESSO-II in 1984. Richard L. Rudell later published the variant ESPRESSO-MV in 1986 and ESPRESSO-EXACT in 1987. Espresso has inspired many derivatives. Electronic devices are composed of numerous blocks of digital circuits, the combination of which performs the required task.
Pumping lemma for regular languages
In the theory of formal languages, the pumping lemma for regular languages is a lemma that describes an essential property of all regular languages. Informally, it says that all sufficiently long strings in a regular language may be pumped—that is, have a middle section of the string repeated an arbitrary number of times—to produce a new string that is also part of the language.