Dehn's Algorithm
   HOME
*





Dehn's Algorithm
In the mathematical subject of group theory, small cancellation theory studies groups given by group presentations satisfying small cancellation conditions, that is where defining relations have "small overlaps" with each other. Small cancellation conditions imply algebraic, geometric and algorithmic properties of the group. Finitely presented groups satisfying sufficiently strong small cancellation conditions are word hyperbolic and have word problem solvable by Dehn's algorithm. Small cancellation methods are also used for constructing Tarski monsters, and for solutions of Burnside's problem. History Some ideas underlying the small cancellation theory go back to the work of Max Dehn in the 1910s. Dehn proved that fundamental groups of closed orientable surfaces of genus at least two have word problem solvable by what is now called Dehn's algorithm. His proof involved drawing the Cayley graph of such a group in the hyperbolic plane and performing curvature estimates via the ...
[...More Info...]      
[...Related Items...]     OR:     [Wikipedia]   [Google]   [Baidu]  


picture info

Group Theory
In abstract algebra, group theory studies the algebraic structures known as group (mathematics), groups. The concept of a group is central to abstract algebra: other well-known algebraic structures, such as ring (mathematics), rings, field (mathematics), fields, and vector spaces, can all be seen as groups endowed with additional operation (mathematics), operations and axioms. Groups recur throughout mathematics, and the methods of group theory have influenced many parts of algebra. Linear algebraic groups and Lie groups are two branches of group theory that have experienced advances and have become subject areas in their own right. Various physical systems, such as crystals and the hydrogen atom, and Standard Model, three of the four known fundamental forces in the universe, may be modelled by symmetry groups. Thus group theory and the closely related representation theory have many important applications in physics, chemistry, and materials science. Group theory is also ce ...
[...More Info...]      
[...Related Items...]     OR:     [Wikipedia]   [Google]   [Baidu]  


HNN-extension
In mathematics, the HNN extension is an important construction of combinatorial group theory. Introduced in a 1949 paper ''Embedding Theorems for Groups'' by Graham Higman, Bernhard Neumann, and Hanna Neumann, it embeds a given group ''G'' into another group ''G' '', in such a way that two given isomorphic subgroups of ''G'' are conjugate (through a given isomorphism) in ''G' ''. Construction Let ''G'' be a group with presentation G = \langle S \mid R\rangle , and let \alpha\colon H \to K be an isomorphism between two subgroups of ''G''. Let ''t'' be a new symbol not in ''S'', and define :G*_ = \left \langle S,t \mid R, tht^=\alpha(h), \forall h\in H \right \rangle. The group G*_ is called the ''HNN extension of'' ''G'' ''relative to'' α. The original group G is called the ''base group'' for the construction, while the subgroups ''H'' and ''K'' are the ''associated subgroups''. The new generator ''t'' is called the ''stable letter''. Key properties Since the presentation for ...
[...More Info...]      
[...Related Items...]     OR:     [Wikipedia]   [Google]   [Baidu]  


Aspherical Space
In topology, a branch of mathematics, an aspherical space is a topological space with all homotopy groups \pi_n(X) equal to 0 when n>1. If one works with CW complexes, one can reformulate this condition: an aspherical CW complex is a CW complex whose universal cover is contractible. Indeed, contractibility of a universal cover is the same, by Whitehead's theorem, as asphericality of it. And it is an application of the exact sequence of a fibration that higher homotopy groups of a space and its universal cover are same. (By the same argument, if ''E'' is a path-connected space and p\colon E \to B is any covering map, then ''E'' is aspherical if and only if ''B'' is aspherical.) Each aspherical space ''X'' is, by definition, an Eilenberg–MacLane space of type K(G,1), where G = \pi_1(X) is the fundamental group of ''X''. Also directly from the definition, an aspherical space is a classifying space for its fundamental group (considered to be a topological group when endowed with t ...
[...More Info...]      
[...Related Items...]     OR:     [Wikipedia]   [Google]   [Baidu]  


Recursion Theory
Computability theory, also known as recursion theory, is a branch of mathematical logic, computer science, and the theory of computation that originated in the 1930s with the study of computable functions and Turing degrees. The field has since expanded to include the study of generalized computability and definability. In these areas, computability theory overlaps with proof theory and effective descriptive set theory. Basic questions addressed by computability theory include: * What does it mean for a function on the natural numbers to be computable? * How can noncomputable functions be classified into a hierarchy based on their level of noncomputability? Although there is considerable overlap in terms of knowledge and methods, mathematical computability theorists study the theory of relative computability, reducibility notions, and degree structures; those in the computer science field focus on the theory of subrecursive hierarchies, formal methods, and formal languages. I ...
[...More Info...]      
[...Related Items...]     OR:     [Wikipedia]   [Google]   [Baidu]  


picture info

Algorithm
In mathematics and computer science, an algorithm () is a finite sequence of rigorous instructions, typically used to solve a class of specific Computational problem, problems or to perform a computation. Algorithms are used as specifications for performing calculations and data processing. More advanced algorithms can perform automated deductions (referred to as automated reasoning) and use mathematical and logical tests to divert the code execution through various routes (referred to as automated decision-making). Using human characteristics as descriptors of machines in metaphorical ways was already practiced by Alan Turing with terms such as "memory", "search" and "stimulus". In contrast, a Heuristic (computer science), heuristic is an approach to problem solving that may not be fully specified or may not guarantee correct or optimal results, especially in problem domains where there is no well-defined correct or optimal result. As an effective method, an algorithm ca ...
[...More Info...]      
[...Related Items...]     OR:     [Wikipedia]   [Google]   [Baidu]  




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. An algorithm that solves a problem in nondeterministic polynomial time can run in polynomial time or exponential time depending on the choices it makes during execution. The nondeterministic algorithms are often used to find an approximation to a solution, when the exact solution would be too costly to obtain using a deterministic one. The notion was introduced by Robert W. Floyd in 1967. Use Often in computational theory, the term "algorithm" refers to a deterministic algorithm. A nondeterministic algorithm is different from its more familiar determi ...
[...More Info...]      
[...Related Items...]     OR:     [Wikipedia]   [Google]   [Baidu]  


Mathematische Zeitschrift
''Mathematische Zeitschrift'' (German for ''Mathematical Journal'') is a mathematical journal for pure and applied mathematics published by Springer Verlag. It was founded in 1918 and edited by Leon Lichtenstein together with Konrad Knopp, Erhard Schmidt, and Issai Schur. Past editors include Erich Kamke, Friedrich Karl Schmidt, Rolf Nevanlinna, Helmut Wielandt, and Olivier Debarre Olivier Debarre (born 1959) is a French mathematician who specializes in complex algebraic geometry.Debarr ...
.


External links

* * Mathematics journals Publications established in 1918 {{math ...
[...More Info...]      
[...Related Items...]     OR:     [Wikipedia]   [Google]   [Baidu]  


picture info

Fundamental Group
In the mathematical field of algebraic topology, the fundamental group of a topological space is the group of the equivalence classes under homotopy of the loops contained in the space. It records information about the basic shape, or holes, of the topological space. The fundamental group is the first and simplest homotopy group. The fundamental group is a homotopy invariant—topological spaces that are homotopy equivalent (or the stronger case of homeomorphic) have isomorphic fundamental groups. The fundamental group of a topological space X is denoted by \pi_1(X). Intuition Start with a space (for example, a surface), and some point in it, and all the loops both starting and ending at this point— paths that start at this point, wander around and eventually return to the starting point. Two loops can be combined in an obvious way: travel along the first loop, then along the second. Two loops are considered equivalent if one can be deformed into the other without breakin ...
[...More Info...]      
[...Related Items...]     OR:     [Wikipedia]   [Google]   [Baidu]  


picture info

Free Abelian Group
In mathematics, a free abelian group is an abelian group with a basis. Being an abelian group means that it is a set with an addition operation that is associative, commutative, and invertible. A basis, also called an integral basis, is a subset such that every element of the group can be uniquely expressed as an integer combination of finitely many basis elements. For instance the two-dimensional integer lattice forms a free abelian group, with coordinatewise addition as its operation, and with the two points (1,0) and (0,1) as its basis. Free abelian groups have properties which make them similar to vector spaces, and may equivalently be called free the free modules over the integers. Lattice theory studies free abelian subgroups of real vector spaces. In algebraic topology, free abelian groups are used to define chain groups, and in algebraic geometry they are used to define divisors. The elements of a free abelian group with basis B may be described in several equivalent ...
[...More Info...]      
[...Related Items...]     OR:     [Wikipedia]   [Google]   [Baidu]  


picture info

Van Kampen Diagram
In the mathematical area of geometric group theory, a Van Kampen diagram (sometimes also called a Lyndon–Van Kampen diagram ) is a planar diagram used to represent the fact that a particular word in the generators of a group given by a group presentation represents the identity element in that group. History The notion of a Van Kampen diagram was introduced by Egbert van Kampen in 1933. This paper appeared in the same issue of American Journal of Mathematics as another paper of Van Kampen, where he proved what is now known as the Seifert–Van Kampen theorem. The main result of the paper on Van Kampen diagrams, now known as the ''van Kampen lemma'' can be deduced from the Seifert–Van Kampen theorem by applying the latter to the presentation complex of a group. However, Van Kampen did not notice it at the time and this fact was only made explicit much later (see, e.g.Aleksandr Yur'evich Ol'shanskii. ''Geometry of defining relations in groups.'' Translated from the 1989 Russia ...
[...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]  


Presentation Of A Group
In mathematics, a presentation is one method of specifying a group. A presentation of a group ''G'' comprises a set ''S'' of generators—so that every element of the group can be written as a product of powers of some of these generators—and a set ''R'' of relations among those generators. We then say ''G'' has presentation :\langle S \mid R\rangle. Informally, ''G'' has the above presentation if it is the "freest group" generated by ''S'' subject only to the relations ''R''. Formally, the group ''G'' is said to have the above presentation if it is isomorphic to the quotient of a free group on ''S'' by the normal subgroup generated by the relations ''R''. As a simple example, the cyclic group of order ''n'' has the presentation :\langle a \mid a^n = 1\rangle, where 1 is the group identity. This may be written equivalently as :\langle a \mid a^n\rangle, thanks to the convention that terms that do not include an equals sign are taken to be equal to the group identity. S ...
[...More Info...]      
[...Related Items...]     OR:     [Wikipedia]   [Google]   [Baidu]