In mathematics and theoretical computer science, a pattern is an unavoidable pattern if it is unavoidable on any finite alphabet.
Like a word, a pattern (also called term) is a sequence of symbols over some alphabet.
The minimum multiplicity of the pattern is where is the number of occurrence of symbol in pattern . In other words, it is the number of occurrences in of the least frequently occurring symbol in .
Given finite alphabets and , a word is an instance of the pattern if there exists a non-erasing semigroup morphism such that , where denotes the Kleene star of . Non-erasing means that for all , where denotes the empty string.
A word is said to match, or encounter, a pattern if a factor (also called subword or substring ) of is an instance of . Otherwise, is said to avoid , or to be -free. This definition can be generalized to the case of an infinite , based on a generalized definition of "substring".
A pattern is unavoidable on a finite alphabet if each sufficiently long word must match ; formally: if . Otherwise, is avoidable on , which implies there exist infinitely many words over the alphabet that avoid .
By Kőnig's lemma, pattern is avoidable on if and only if there exists an infinite word that avoids . [1]
Given a pattern and an alphabet . A -free word is a maximal -free word over if and match .
A pattern is an unavoidable pattern (also called blocking term) if is unavoidable on any finite alphabet.
If a pattern is unavoidable and not limited to a specific alphabet, then it is unavoidable for any finite alphabet by default. Conversely, if a pattern is said to be avoidable and not limited to a specific alphabet, then it is avoidable on some finite alphabet by default.
A pattern is -avoidable if is avoidable on an alphabet of size . Otherwise, is -unavoidable, which means is unavoidable on every alphabet of size . [2]
If pattern is -avoidable, then is -avoidable for all .
Given a finite set of avoidable patterns , there exists an infinite word such that avoids all patterns of . [1] Let denote the size of the minimal alphabet such that avoiding all patterns of .
The avoidability index of a pattern is the smallest such that is -avoidable, and if is unavoidable. [1]
Given alphabet , Zimin words (patterns) are defined recursively for and .
All Zimin words are unavoidable. [4]
A word is unavoidable if and only if it is a factor of a Zimin word. [4]
Given a finite alphabet , let represent the smallest such that matches for all . We have following properties: [5]
is the longest unavoidable pattern constructed by alphabet since .
Given a pattern over some alphabet , we say is free for if there exist subsets of such that the following hold:
For example, let , then is free for since there exist satisfying the conditions above.
A pattern reduces to pattern if there exists a symbol such that is free for , and can be obtained by removing all occurrence of from . Denote this relation by .
For example, let , then can reduce to since is free for .
A word is said to be locked if has no free letter; hence can not be reduced. [6]
Given patterns , if reduces to and reduces to , then reduces to . Denote this relation by .
A pattern is unavoidable if and only if reduces to a word of length one; hence such that and . [7] [4]
Given a simple graph , a edge coloring matches pattern if there exists a simple path in such that the sequence matches . Otherwise, is said to avoid or be -free.
Similarly, a vertex coloring matches pattern if there exists a simple path in such that the sequence matches .
The pattern chromatic number is the minimal number of distinct colors needed for a -free vertex coloring over the graph .
Let where is the set of all simple graphs with a maximum degree no more than .
Similarly, and are defined for edge colorings.
A pattern is avoidable on graphs if is bounded by , where only depends on .
There exists an absolute constant , such that for all patterns with . [8]
Given a pattern , let represent the number of distinct symbols of . If , then is avoidable on graphs.
Given a pattern such that is even for all , then for all , where is the complete graph of vertices. [8]
Given a pattern such that , and an arbitrary tree , let be the set of all avoidable subpatterns and their reflections of . Then . [8]
Given a pattern such that , and a tree with degree . Let be the set of all avoidable subpatterns and their reflections of , then . [8]
In physics, the cross section is a measure of the probability that a specific process will take place when some kind of radiant excitation intersects a localized phenomenon. For example, the Rutherford cross-section is a measure of probability that an alpha particle will be deflected by a given angle during a collision with an atomic nucleus. Cross section is typically denoted σ (sigma) and is expressed in units of area, more specific in barns. In a way, it can be thought of as the size of the object that the excitation must hit in order for the process to occur, but more exactly, it is a parameter of a stochastic process.
In probability theory, a normaldistribution is a type of continuous probability distribution for a real-valued random variable. The general form of its probability density function is
In the theory of computation, a branch of theoretical computer science, a pushdown automaton (PDA) is a type of automaton that employs a stack.
In quantum mechanics, the uncertainty principle is any of a variety of mathematical inequalities asserting a fundamental limit to the accuracy with which the values for certain pairs of physical quantities of a particle, such as position, x, and momentum, p, can be predicted from initial conditions.
In mathematics, a Gaussian function, often simply referred to as a Gaussian, is a function of the form
In the theory of computation, a branch of theoretical computer science, a deterministic finite automaton (DFA)—also known as deterministic finite acceptor (DFA), deterministic finite-state machine (DFSM), or deterministic finite-state automaton (DFSA)—is a finite-state machine that accepts or rejects a given string of symbols, by running through a state sequence uniquely determined by the string. Deterministic refers to the uniqueness of the computation run. In search of the simplest models to capture finite-state machines, Warren McCulloch and Walter Pitts were among the first researchers to introduce a concept similar to finite automata in 1943.
In particle physics, Fermi's interaction is an explanation of the beta decay, proposed by Enrico Fermi in 1933. The theory posits four fermions directly interacting with one another. This interaction explains beta decay of a neutron by direct coupling of a neutron with an electron, a neutrino and a proton.
A finite-state transducer (FST) is a finite-state machine with two memory tapes, following the terminology for Turing machines: an input tape and an output tape. This contrasts with an ordinary finite-state automaton, which has a single tape. An FST is a type of finite-state automaton (FSA) that maps between two sets of symbols. An FST is more general than an FSA. An FSA defines a formal language by defining a set of accepted strings, while an FST defines relations between sets of strings.
In coding theory, block codes are a large and important family of error-correcting codes that encode data in blocks. There is a vast number of examples for block codes, many of which have a wide range of practical applications. The abstract definition of block codes is conceptually useful because it allows coding theorists, mathematicians, and computer scientists to study the limitations of all block codes in a unified way. Such limitations often take the form of bounds that relate different parameters of the block code to each other, such as its rate and its ability to detect and correct errors.
In general relativity, the Gibbons–Hawking–York boundary term is a term that needs to be added to the Einstein–Hilbert action when the underlying spacetime manifold has a boundary.
In condensed matter physics and crystallography, the static structure factor is a mathematical description of how a material scatters incident radiation. The structure factor is a critical tool in the interpretation of scattering patterns obtained in X-ray, electron and neutron diffraction experiments.
In 3-dimensional topology, a part of the mathematical field of geometric topology, the Casson invariant is an integer-valued invariant of oriented integral homology 3-spheres, introduced by Andrew Casson.
Expected shortfall (ES) is a risk measure—a concept used in the field of financial risk measurement to evaluate the market risk or credit risk of a portfolio. The "expected shortfall at q% level" is the expected return on the portfolio in the worst of cases. ES is an alternative to value at risk that is more sensitive to the shape of the tail of the loss distribution.
A ratio distribution is a probability distribution constructed as the distribution of the ratio of random variables having two other known distributions. Given two random variables X and Y, the distribution of the random variable Z that is formed as the ratio Z = X/Y is a ratio distribution.
Contact mechanics is the study of the deformation of solids that touch each other at one or more points. A central distinction in contact mechanics is between stresses acting perpendicular to the contacting bodies' surfaces and frictional stresses acting tangentially between the surfaces. This page focuses mainly on the normal direction, i.e. on frictionless contact mechanics. Frictional contact mechanics is discussed separately. Normal stresses are caused by applied forces and by the adhesion present on surfaces in close contact even if they are clean and dry.
Stress majorization is an optimization strategy used in multidimensional scaling (MDS) where, for a set of nm-dimensional data items, a configuration X of n points in r(<<m)-dimensional space is sought that minimizes the so-called stress function . Usually r is 2 or 3, i.e. the (n x r) matrix X lists points in 2- or 3-dimensional Euclidean space so that the result may be visualised. The function is a cost or loss function that measures the squared differences between ideal distances and actual distances in r-dimensional space. It is defined as:
Experimental uncertainty analysis is a technique that analyses a derived quantity, based on the uncertainties in the experimentally measured quantities that are used in some form of mathematical relationship ("model") to calculate that derived quantity. The model used to convert the measurements into the derived quantity is usually based on fundamental principles of a science or engineering discipline.
In computer science, more specifically in automata and formal language theory, nested words are a concept proposed by Alur and Madhusudan as a joint generalization of words, as traditionally used for modelling linearly ordered structures, and of ordered unranked trees, as traditionally used for modelling hierarchical structures. Finite-state acceptors for nested words, so-called nested word automata, then give a more expressive generalization of finite automata on words. The linear encodings of languages accepted by finite nested word automata gives the class of visibly pushdown languages. The latter language class lies properly between the regular languages and the deterministic context-free languages. Since their introduction in 2004, these concepts have triggered much research in that area.
In the geometry of numbers, the Klein polyhedron, named after Felix Klein, is used to generalize the concept of continued fractions to higher dimensions.
In the mathematical field of group theory, an Artin transfer is a certain homomorphism from an arbitrary finite or infinite group to the commutator quotient group of a subgroup of finite index. Originally, such mappings arose as group theoretic counterparts of class extension homomorphisms of abelian extensions of algebraic number fields by applying Artin's reciprocity maps to ideal class groups and analyzing the resulting homomorphisms between quotients of Galois groups. However, independently of number theoretic applications, a partial order on the kernels and targets of Artin transfers has recently turned out to be compatible with parent-descendant relations between finite p-groups, which can be visualized in descendant trees. Therefore, Artin transfers provide a valuable tool for the classification of finite p-groups and for searching and identifying particular groups in descendant trees by looking for patterns defined by the kernels and targets of Artin transfers. These strategies of pattern recognition are useful in purely group theoretic context, as well as for applications in algebraic number theory concerning Galois groups of higher p-class fields and Hilbert p-class field towers.