|
Lyndon Word
In mathematics, in the areas of combinatorics and computer science, a Lyndon word is a nonempty string that is strictly smaller in lexicographic order than all of its rotations. Lyndon words are named after mathematician Roger Lyndon, who investigated them in 1954, calling them standard lexicographic sequences. Anatoly Shirshov introduced Lyndon words in 1953 calling them regular words. Lyndon words are a special case of Hall words; almost all properties of Lyndon words are shared by Hall words. Definitions Several equivalent definitions exist. A k-ary Lyndon word of length n > 0 is an n-character string over an alphabet of size k, and which is the unique minimum element in the lexicographical ordering in the multiset of all its rotations. Being the singularly smallest rotation implies that a Lyndon word differs from any of its non-trivial rotations, and is therefore aperiodic.; . Alternately, a word w is a Lyndon word if and only if it is nonempty and lexicographically stri ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Mathematics
Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics with the major subdisciplines of number theory, algebra, geometry, and analysis, respectively. There is no general consensus among mathematicians about a common definition for their academic discipline. Most mathematical activity involves the discovery of properties of abstract objects and the use of pure reason to prove them. These objects consist of either abstractions from nature orin modern mathematicsentities that are stipulated to have certain properties, called axioms. A ''proof'' consists of a succession of applications of deductive rules to already established results. These results include previously proved theorems, axioms, andin case of abstraction from naturesome basic properties that are considered true starting points of ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Chen–Fox–Lyndon Theorem
In mathematics, a factorisation of a free monoid is a sequence of subsets of words with the property that every word in the free monoid can be written as a concatenation of elements drawn from the subsets. The Chen–Fox–Lyndon theorem states that the Lyndon words furnish a factorisation. The Schützenberger theorem relates the definition in terms of a multiplicative property to an additive property. Let ''A''* be the free monoid on an alphabet ''A''. Let ''X''''i'' be a sequence of subsets of ''A''* indexed by a totally ordered index set ''I''. A factorisation of a word ''w'' in ''A''* is an expression :w = x_ x_ \cdots x_ \ with x_ \in X_ and i_1 \ge i_2 \ge \ldots \ge i_n. Some authors reverse the order of the inequalities. Chen–Fox–Lyndon theorem A Lyndon word over a totally ordered alphabet ''A'' is a word that is lexicographically less than all its rotations.Lothaire (1997) p.64 The Chen–Fox–Lyndon theorem states that every string may be formed in a unique ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Hall Set
In mathematics, in the areas of group theory and combinatorics, Hall words provide a unique monoid factorisation of the free monoid. They are also totally ordered, and thus provide a total order on the monoid. This is analogous to the better-known case of Lyndon words; in fact, the Lyndon words are a special case, and almost all properties possessed by Lyndon words carry over to Hall words. Hall words are in one-to-one correspondence with Hall trees. These are binary trees; taken together, they form the Hall set. This set is a particular totally ordered subset of a free non-associative algebra, that is, a free magma. In this form, the Hall trees provide a basis for free Lie algebras, and can be used to perform the commutations required by the Poincaré–Birkhoff–Witt theorem used in the construction of a universal enveloping algebra. As such, this generalizes the same process when done with the Lyndon words. Hall trees can also be used to give a total order to the elements of a ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
L (complexity)
In computational complexity theory, L (also known as LSPACE or DLOGSPACE) is the complexity class containing decision problems that can be solved by a deterministic Turing machine using a logarithmic amount of writable memory space., Definition 8.12, p. 295., p. 177. Formally, the Turing machine has two tapes, one of which encodes the input and can only be read, whereas the other tape has logarithmic size but can be read as well as written. Logarithmic space is sufficient to hold a constant number of pointers into the input and a logarithmic number of boolean flags, and many basic logspace algorithms use the memory in this way. Complete problems and logical characterization Every non-trivial problem in L is complete under log-space reductions, so weaker reductions are required to identify meaningful notions of L-completeness, the most common being first-order reductions. A 2004 result by Omer Reingold shows that USTCON, the problem of whether there exists a path ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
De Bruijn Sequence
In combinatorial mathematics, a de Bruijn sequence of order ''n'' on a size-''k'' alphabet ''A'' is a cyclic sequence in which every possible length-''n'' string on ''A'' occurs exactly once as a substring (i.e., as a ''contiguous'' subsequence). Such a sequence is denoted by and has length , which is also the number of distinct strings of length ''n'' on ''A''. Each of these distinct strings, when taken as a substring of , must start at a different position, because substrings starting at the same position are not distinct. Therefore, must have ''at least'' symbols. And since has ''exactly'' symbols, De Bruijn sequences are optimally short with respect to the property of containing every string of length ''n'' at least once. The number of distinct de Bruijn sequences is :\dfrac. The sequences are named after the Dutch mathematician Nicolaas Govert de Bruijn, who wrote about them in 1946. As he later wrote, the existence of de Bruijn sequences for each order together ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Permutation
In mathematics, a permutation of a set is, loosely speaking, an arrangement of its members into a sequence or linear order, or if the set is already ordered, a rearrangement of its elements. The word "permutation" also refers to the act or process of changing the linear order of an ordered set. Permutations differ from combinations, which are selections of some members of a set regardless of order. For example, written as tuples, there are six permutations of the set , namely (1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2), and (3, 2, 1). These are all the possible orderings of this three-element set. Anagrams of words whose letters are different are also permutations: the letters are already ordered in the original word, and the anagram is a reordering of the letters. The study of permutations of finite sets is an important topic in the fields of combinatorics and group theory. Permutations are used in almost every branch of mathematics, and in many other fields of scie ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Universal Enveloping Algebra
In mathematics, the universal enveloping algebra of a Lie algebra is the unital associative algebra whose representations correspond precisely to the representations of that Lie algebra. Universal enveloping algebras are used in the representation theory of Lie groups and Lie algebras. For example, Verma modules can be constructed as quotients of the universal enveloping algebra. In addition, the enveloping algebra gives a precise definition for the Casimir operators. Because Casimir operators commute with all elements of a Lie algebra, they can be used to classify representations. The precise definition also allows the importation of Casimir operators into other areas of mathematics, specifically, those that have a differential algebra. They also play a central role in some recent developments in mathematics. In particular, their dual provides a commutative example of the objects studied in non-commutative geometry, the quantum groups. This dual can be shown, by the Gelfand–N ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Poincaré–Birkhoff–Witt Theorem
In mathematics, more specifically in the theory of Lie algebras, the Poincaré–Birkhoff–Witt theorem (or PBW theorem) is a result giving an explicit description of the universal enveloping algebra of a Lie algebra. It is named after Henri Poincaré, Garrett Birkhoff, and Ernst Witt. The terms ''PBW type theorem'' and ''PBW theorem'' may also refer to various analogues of the original theorem, comparing a filtered algebra to its associated graded algebra, in particular in the area of quantum groups. Statement of the theorem Recall that any vector space ''V'' over a field has a basis; this is a set ''S'' such that any element of ''V'' is a unique (finite) linear combination of elements of ''S''. In the formulation of Poincaré–Birkhoff–Witt theorem we consider bases of which the elements are totally ordered by some relation which we denote ≤. If ''L'' is a Lie algebra over a field K, let ''h'' denote the canonical K-linear map from ''L'' into the universal envelopi ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Commutator Collecting Process
In group theory, a branch of mathematics, the commutator collecting process is a method for writing an element of a group as a product of generators and their higher commutators arranged in a certain order. The commutator collecting process was introduced by Philip Hall in 1934 and articulated by Wilhelm Magnus in 1937. W. Magnus (1937), "Über Beziehungen zwischen höheren Kommutatoren", ''J. Grelle'' 177, 105-115. The process is sometimes called a "collection process". The process can be generalized to define a totally ordered subset of a free non-associative algebra, that is, a free magma; this subset is called the Hall set. Members of the Hall set are binary trees; these can be placed in one-to-one correspondence with words, these being called the Hall words; the Lyndon words are a special case. Hall sets are used to construct a basis for a free Lie algebra, entirely analogously to the commutator collecting process. Hall words also provide a unique factorization of monoids ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Free Lie Algebra
In mathematics, a free Lie algebra over a field ''K'' is a Lie algebra generated by a set ''X'', without any imposed relations other than the defining relations of alternating ''K''-bilinearity and the Jacobi identity. Definition The definition of the free Lie algebra generated by a set ''X'' is as follows: : Let ''X'' be a set and i\colon X \to L a morphism of sets (function) from ''X'' into a Lie algebra ''L''. The Lie algebra ''L'' is called free on ''X'' if i is the universal morphism; that is, if for any Lie algebra ''A'' with a morphism of sets f\colon X \to A, there is a unique Lie algebra morphism g\colon L\to A such that f = g \circ i. Given a set ''X'', one can show that there exists a unique free Lie algebra L(X) generated by ''X''. In the language of category theory, the functor sending a set ''X'' to the Lie algebra generated by ''X'' is the free functor from the category of sets to the category of Lie algebras. That is, it is left adjoint to the forgetful functo ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Free Group
In mathematics, the free group ''F''''S'' over a given set ''S'' consists of all words that can be built from members of ''S'', considering two words to be different unless their equality follows from the group axioms (e.g. ''st'' = ''suu''−1''t'', but ''s'' ≠ ''t''−1 for ''s'',''t'',''u'' ∈ ''S''). The members of ''S'' are called generators of ''F''''S'', and the number of generators is the rank of the free group. An arbitrary group ''G'' is called free if it is isomorphic to ''F''''S'' for some subset ''S'' of ''G'', that is, if there is a subset ''S'' of ''G'' such that every element of ''G'' can be written in exactly one way as a product of finitely many elements of ''S'' and their inverses (disregarding trivial variations such as ''st'' = ''suu''−1''t''). A related but different notion is a free abelian group; both notions are particular instances of a free object from universal algebra. As such, free groups are defined by their universal property. History Free ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Digital Geometry
Digital geometry deals with discrete sets (usually discrete point sets) considered to be digitized models or images of objects of the 2D or 3D Euclidean space. Simply put, digitizing is replacing an object by a discrete set of its points. The images we see on the TV screen, the raster display of a computer, or in newspapers are in fact digital images. Its main application areas are computer graphics and image analysis. Main aspects of study are: * Constructing digitized representations of objects, with the emphasis on precision and efficiency (either by means of synthesis, see, for example, Bresenham's line algorithm or digital disks, or by means of digitization and subsequent processing of digital images). * Study of properties of digital sets; see, for example, Pick's theorem, digital convexity, digital straightness, or digital planarity. * Transforming digitized representations of objects, for example (A) into simplified shapes such as (i) skeletons, by repeated removal of ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
