Degree of a continuous mappingIn topology, the degree of a continuous mapping between two compact oriented manifolds of the same dimension is a number that represents the number of times that the domain manifold wraps around the range manifold under the mapping. The degree is always an integer, but may be positive or negative depending on the orientations. The degree of a map was first defined by Brouwer, who showed that the degree is homotopy invariant (invariant among homotopies), and used it to prove the Brouwer fixed point theorem.
Scale-free networkA scale-free network is a network whose degree distribution follows a power law, at least asymptotically. That is, the fraction P(k) of nodes in the network having k connections to other nodes goes for large values of k as where is a parameter whose value is typically in the range (wherein the second moment (scale parameter) of is infinite but the first moment is finite), although occasionally it may lie outside these bounds. The name "scale-free" means that some moments of the degree distribution are not defined, so that the network does not have a characteristic scale or "size".
Recursive languageIn mathematics, logic and computer science, a formal language (a set of finite sequences of symbols taken from a fixed alphabet) is called recursive if it is a recursive subset of the set of all possible finite sequences over the alphabet of the language. Equivalently, a formal language is recursive if there exists a Turing machine that, when given a finite sequence of symbols as input, always halts and accepts it if it belongs to the language and halts and rejects it otherwise.
Kirchhoff's theoremIn the mathematical field of graph theory, Kirchhoff's theorem or Kirchhoff's matrix tree theorem named after Gustav Kirchhoff is a theorem about the number of spanning trees in a graph, showing that this number can be computed in polynomial time from the determinant of a submatrix of the Laplacian matrix of the graph; specifically, the number is equal to any cofactor of the Laplacian matrix. Kirchhoff's theorem is a generalization of Cayley's formula which provides the number of spanning trees in a complete graph.
Semi-Thue systemIn theoretical computer science and mathematical logic a string rewriting system (SRS), historically called a semi-Thue system, is a rewriting system over strings from a (usually finite) alphabet. Given a binary relation between fixed strings over the alphabet, called rewrite rules, denoted by , an SRS extends the rewriting relation to all strings in which the left- and right-hand side of the rules appear as substrings, that is , where , , , and are strings. The notion of a semi-Thue system essentially coincides with the presentation of a monoid.
Primitive recursive functionIn computability theory, a primitive recursive function is, roughly speaking, a function that can be computed by a computer program whose loops are all "for" loops (that is, an upper bound of the number of iterations of every loop can be determined before entering the loop). Primitive recursive functions form a strict subset of those general recursive functions that are also total functions. The importance of primitive recursive functions lies in the fact that most computable functions that are studied in number theory (and more generally in mathematics) are primitive recursive.
Computable setIn computability theory, a set of natural numbers is called computable, recursive, or decidable if there is an algorithm which takes a number as input, terminates after a finite amount of time (possibly depending on the given number) and correctly decides whether the number belongs to the set or not. A set which is not computable is called noncomputable or undecidable. A more general class of sets than the computable ones consists of the computably enumerable (c.e.) sets, also called semidecidable sets.
Alternating finite automatonIn 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.
EnumerationAn enumeration is a complete, ordered listing of all the items in a collection. The term is commonly used in mathematics and computer science to refer to a listing of all of the elements of a set. The precise requirements for an enumeration (for example, whether the set must be finite, or whether the list is allowed to contain repetitions) depend on the discipline of study and the context of a given problem. Some sets can be enumerated by means of a natural ordering (such as 1, 2, 3, 4, ...
Infinitesimal transformationIn mathematics, an infinitesimal transformation is a limiting form of small transformation. For example one may talk about an infinitesimal rotation of a rigid body, in three-dimensional space. This is conventionally represented by a 3×3 skew-symmetric matrix A. It is not the matrix of an actual rotation in space; but for small real values of a parameter ε the transformation is a small rotation, up to quantities of order ε2. A comprehensive theory of infinitesimal transformations was first given by Sophus Lie.
