|
Muller–Schupp Theorem
In mathematics, the Muller–Schupp theorem states that a finitely generated group ''G'' has context-free word problem if and only if ''G'' is virtually free. The theorem was proved by David Muller and Paul Schupp in 1983.David E. Muller, and Paul E. Schupp''Groups, the theory of ends, and context-free languages''. Journal of Computer and System Sciences 26 (1983), no. 3, 295–310 Word problem for groups Let ''G'' be a finitely generated group with a finite marked generating set ''X'', that is a set ''X'' together with the map \pi:X\to G such that the subset \pi(X)\subseteq G generates ''G''. Let \Sigma_X:=X\sqcup X^ be the group alphabet and let \Sigma_X^\ast be the free monoid on \Sigma_X, that is \Sigma_X^\ast is the set of all words (including the empty word) over the alphabet \Sigma_X. The map \pi: X\to G extends to a surjective monoid homomorphism, still denoted by \pi, \pi: \Sigma_X^\ast\to G. The ''word problem'' \mathcal W(G,X) of ''G'' with respect to ''X'' is defi ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Finitely Generated Group
In algebra, a finitely generated group is a group ''G'' that has some finite generating set ''S'' so that every element of ''G'' can be written as the combination (under the group operation) of finitely many elements of ''S'' and of inverses of such elements. By definition, every finite group is finitely generated, since ''S'' can be taken to be ''G'' itself. Every infinite finitely generated group must be countable but countable groups need not be finitely generated. The additive group of rational numbers Q is an example of a countable group that is not finitely generated. Examples * Every quotient of a finitely generated group ''G'' is finitely generated; the quotient group is generated by the images of the generators of ''G'' under the canonical projection. * A subgroup of a finitely generated group need not be finitely generated. * A group that is generated by a single element is called cyclic. Every infinite cyclic group is isomorphic to the additive group of the integers ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Finitely Presented 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] |
Push-down Automaton
In the theory of computation, a branch of theoretical computer science, a pushdown automaton (PDA) is a type of automaton that employs a stack. Pushdown automata are used in theories about what can be computed by machines. They are more capable than finite-state machines but less capable than Turing machines (see below). Deterministic pushdown automata can recognize all deterministic context-free languages while nondeterministic ones can recognize all context-free languages, with the former often used in parser design. The term "pushdown" refers to the fact that the stack can be regarded as being "pushed down" like a tray dispenser at a cafeteria, since the operations never work on elements other than the top element. A stack automaton, by contrast, does allow access to and operations on deeper elements. Stack automata can recognize a strictly larger set of languages than pushdown automata. A nested stack automaton allows full access, and also allows stacked values to be ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Grushko Theorem
In the mathematical subject of group theory, the Grushko theorem or the Grushko–Neumann theorem is a theorem stating that the rank (that is, the smallest cardinality of a generating set) of a free product of two groups is equal to the sum of the ranks of the two free factors. The theorem was first obtained in a 1940 article of Grushko and then, independently, in a 1943 article of Neumann. Statement of the theorem Let ''A'' and ''B'' be finitely generated groups and let ''A''∗''B'' be the free product of ''A'' and ''B''. Then :rank(''A''∗''B'') = rank(''A'') + rank(''B''). It is obvious that rank(''A''∗''B'') ≤ rank(''A'') + rank(''B'') since if X is a finite generating set of ''A'' and ''Y'' is a finite generating set of ''B'' then ''X''∪''Y'' is a generating set for ''A''∗''B'' and that , ''X'' ∪ ''Y'', ≤ , ''X'', + , ''Y'', . The opposite inequality, rank(''A''∗''B'') ≥ rank(''A'') + rank(''B''), requires proof. Grushko, but not Neumann, proved a mor ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Torsion-free Group
In mathematics, specifically in ring theory, a torsion element is an element of a module that yields zero when multiplied by some non-zero-divisor of the ring. The torsion submodule of a module is the submodule formed by the torsion elements. A torsion module is a module that equals its torsion submodule. A module is torsion-free if its torsion submodule comprises only the zero element. This terminology is more commonly used for modules over a domain, that is, when the regular elements of the ring are all its nonzero elements. This terminology applies to abelian groups (with "module" and "submodule" replaced by "group" and "subgroup"). This is allowed by the fact that the abelian groups are the modules over the ring of integers (in fact, this is the origin of the terminology, that has been introduced for abelian groups before being generalized to modules). In the case of groups that are noncommutative, a ''torsion element'' is an element of finite order. Contrary to the commuta ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
European Journal Of Combinatorics
European, or Europeans, or Europeneans, may refer to: In general * ''European'', an adjective referring to something of, from, or related to Europe ** Ethnic groups in Europe ** Demographics of Europe ** European cuisine, the cuisines of Europe and other Western countries * ''European'', an adjective referring to something of, from, or related to the European Union ** Citizenship of the European Union ** Demographics of the European Union In publishing * ''The European'' (1953 magazine), a far-right cultural and political magazine published 1953–1959 * ''The European'' (newspaper), a British weekly newspaper published 1990–1998 * ''The European'' (2009 magazine), a German magazine first published in September 2009 *''The European Magazine'', a magazine published in London 1782–1826 *''The New European'', a British weekly pop-up newspaper first published in July 2016 Other uses * * Europeans (band), a British post-punk group, from Bristol See also * * * Europe (disam ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Journal Of Pure And Applied Algebra
The ''Journal of Pure and Applied Algebra'' is a monthly peer-reviewed scientific journal covering that part of algebra likely to be of general mathematical interest: algebraic results with immediate applications, and the development of algebraic theories of sufficiently general relevance to allow for future applications. Its founding editors-in-chief were Peter J. Freyd (University of Pennsylvania) and Alex Heller (City University of New York). The current managing editors are Eric Friedlander (University of Southern California), Charles Weibel (Rutgers University), and Srikanth Iyengar (University of Utah). Abstracting and indexing The journal is abstracted and indexed in Current Contents/Physics, Chemical, & Earth Sciences, Mathematical Reviews, PASCAL, Science Citation Index, Zentralblatt MATH, and Scopus. According to the ''Journal Citation Reports'', the journal has a 2016 impact factor The impact factor (IF) or journal impact factor (JIF) of an academic journal is a s ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Inventiones Mathematicae
''Inventiones Mathematicae'' is a mathematical journal published monthly by Springer Science+Business Media. It was established in 1966 and is regarded as one of the most prestigious mathematics journals in the world. The current managing editors are Camillo De Lellis (Institute for Advanced Study, Princeton) and Jean-Benoît Bost (University of Paris-Sud Paris-Sud University (French: ''Université Paris-Sud''), also known as University of Paris — XI (or as Université d'Orsay before 1971), was a French research university distributed among several campuses in the southern suburbs of Paris, in ...). Abstracting and indexing The journal is abstracted and indexed in: References External links *{{Official website, https://www.springer.com/journal/222 Mathematics journals Publications established in 1966 English-language journals Springer Science+Business Media academic journals Monthly journals ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Martin Dunwoody
Martin John Dunwoody (born 3 November 1938) is an emeritus professor of Mathematics at the University of Southampton, England. He earned his PhD in 1964 from the Australian National University. He held positions at the University of Sussex before becoming a professor at the University of Southampton in 1992. He has been emeritus professor since 2003. Dunwoody works on geometric group theory and low-dimensional topology. He is a leading expert in splittings and accessibility of discrete groups, groups acting on graphs and trees, JSJ-decompositions, the topology of 3-manifolds and the structure of their fundamental groups. Since 1971 several mathematicians have been working on Wall's conjecture, posed by Wall in a 1971 paper, which said that all finitely generated groups are accessible. Roughly, this means that every finitely generated group can be constructed from finite and one-ended groups via a finite number of amalgamated free products and HNN extensions over finite sub ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Regular Language
In theoretical computer science and formal language theory, a regular language (also called a rational language) is a formal language that can be defined by a regular expression, in the strict sense in theoretical computer science (as opposed to many modern regular expressions engines, which are augmented with features that allow recognition of non-regular languages). Alternatively, a regular language can be defined as a language recognized by a finite automaton. The equivalence of regular expressions and finite automata is known as Kleene's theorem (after American mathematician Stephen Cole Kleene). In the Chomsky hierarchy, regular languages are the languages generated by Type-3 grammars. Formal definition The collection of regular languages over an alphabet Σ is defined recursively as follows: * The empty language Ø is a regular language. * For each ''a'' ∈ Σ (''a'' belongs to Σ), the singleton language is a regular language. * If ''A'' is a regular language, ''A''* ( ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Normal Subgroup
In abstract algebra, a normal subgroup (also known as an invariant subgroup or self-conjugate subgroup) is a subgroup that is invariant under conjugation by members of the group of which it is a part. In other words, a subgroup N of the group G is normal in G if and only if gng^ \in N for all g \in G and n \in N. The usual notation for this relation is N \triangleleft G. Normal subgroups are important because they (and only they) can be used to construct quotient groups of the given group. Furthermore, the normal subgroups of G are precisely the kernels of group homomorphisms with domain G, which means that they can be used to internally classify those homomorphisms. Évariste Galois was the first to realize the importance of the existence of normal subgroups. Definitions A subgroup N of a group G is called a normal subgroup of G if it is invariant under conjugation; that is, the conjugation of an element of N by an element of G is always in N. The usual notation for this re ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Graph Of Groups
In geometric group theory, a graph of groups is an object consisting of a collection of groups indexed by the vertices and edges of a graph, together with a family of monomorphisms of the edge groups into the vertex groups. There is a unique group, called the fundamental group, canonically associated to each finite connected graph of groups. It admits an orientation-preserving action on a tree: the original graph of groups can be recovered from the quotient graph and the stabilizer subgroups. This theory, commonly referred to as Bass–Serre theory, is due to the work of Hyman Bass and Jean-Pierre Serre. Definition A graph of groups over a graph is an assignment to each vertex of of a group and to each edge of of a group as well as monomorphisms and mapping into the groups assigned to the vertices at its ends. Fundamental group Let be a spanning tree for and define the fundamental group to be the group generated by the vertex groups and elements for each edge of with ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
