Related Research Articles
In mathematics, a semigroup is an algebraic structure consisting of a set together with an associative internal binary operation on it.
In mathematics, Gromov–Hausdorff convergence, named after Mikhail Gromov and Felix Hausdorff, is a notion for convergence of metric spaces which is a generalization of Hausdorff convergence.
In mathematics, the von Neumann conjecture stated that a group G is non-amenable if and only if G contains a subgroup that is a free group on two generators. The conjecture was disproved in 1980.
Geometric group theory is an area in mathematics devoted to the study of finitely generated groups via exploring the connections between algebraic properties of such groups and topological and geometric properties of spaces on which these groups act.
In a cellular automaton, a Garden of Eden is a configuration that has no predecessor. It can be the initial configuration of the automaton but cannot arise in any other way. John Tukey named these configurations after the Garden of Eden in Abrahamic religions, which was created out of nowhere.
In mathematics, a locally compact topological group G has property (T) if the trivial representation is an isolated point in its unitary dual equipped with the Fell topology. Informally, this means that if G acts unitarily on a Hilbert space and has "almost invariant vectors", then it has a nonzero invariant vector. The formal definition, introduced by David Kazhdan (1967), gives this a precise, quantitative meaning.
In group theory, more precisely in geometric group theory, a hyperbolic group, also known as a word hyperbolic group or Gromov hyperbolic group, is a finitely generated group equipped with a word metric satisfying certain properties abstracted from classical hyperbolic geometry. The notion of a hyperbolic group was introduced and developed by Mikhail Gromov (1987). The inspiration came from various existing mathematical theories: hyperbolic geometry but also low-dimensional topology, and combinatorial group theory. In a very influential chapter from 1987, Gromov proposed a wide-ranging research program. Ideas and foundational material in the theory of hyperbolic groups also stem from the work of George Mostow, William Thurston, James W. Cannon, Eliyahu Rips, and many others.
Wolfram code is a widely used numbering system for one-dimensional cellular automaton rules, introduced by Stephen Wolfram in a 1983 paper and popularized in his book A New Kind of Science.
In mathematics, a quasi-isometry is a function between two metric spaces that respects large-scale geometry of these spaces and ignores their small-scale details. Two metric spaces are quasi-isometric if there exists a quasi-isometry between them. The property of being quasi-isometric behaves like an equivalence relation on the class of metric spaces.
In computer science, more precisely, in the theory of deterministic finite automata (DFA), a synchronizing word or reset sequence is a word in the input alphabet of the DFA that sends any state of the DFA to one and the same state. That is, if an ensemble of copies of the DFA are each started in different states, and all of the copies process the synchronizing word, they will all end up in the same state. Not every DFA has a synchronizing word; for instance, a DFA with two states, one for words of even length and one for words of odd length, can never be synchronized.
In symbolic dynamics and related branches of mathematics, a shift space or subshift is a set of infinite words that represent the evolution of a discrete system. In fact, shift spaces and symbolic dynamical systems are often considered synonyms. The most widely studied shift spaces are the subshifts of finite type and the sofic shifts.
Rostislav Ivanovich Grigorchuk is a mathematician working in different areas of mathematics including group theory, dynamical systems, geometry and computer science. He holds the rank of Distinguished Professor in the Mathematics Department of Texas A&M University. Grigorchuk is particularly well known for having constructed, in a 1984 paper, the first example of a finitely generated group of intermediate growth, thus answering an important problem posed by John Milnor in 1968. This group is now known as the Grigorchuk group and it is one of the important objects studied in geometric group theory, particularly in the study of branch groups, automaton groups and iterated monodromy groups. Grigorchuk is one of the pioneers of asymptotic group theory as well as of the theory of dynamically defined groups. He introduced the notion of branch groups and developed the foundations of the related theory. Grigorchuk, together with his collaborators and students, initiated the theory of groups generated by finite Mealy type automata, interpreted them as groups of fractal type, developed the theory of groups acting on rooted trees, and found numerous applications of these groups in various fields of mathematics including functional analysis, topology, spectral graph theory, dynamical systems and ergodic theory.
John Robert Stallings Jr. was a mathematician known for his seminal contributions to geometric group theory and 3-manifold topology. Stallings was a Professor Emeritus in the Department of Mathematics at the University of California at Berkeley where he had been a faculty member since 1967. He published over 50 papers, predominantly in the areas of geometric group theory and the topology of 3-manifolds. Stallings' most important contributions include a proof, in a 1960 paper, of the Poincaré Conjecture in dimensions greater than six and a proof, in a 1971 paper, of the Stallings theorem about ends of groups.
The Curtis–Hedlund–Lyndon theorem is a mathematical characterization of cellular automata in terms of their symbolic dynamics. It is named after Morton L. Curtis, Gustav A. Hedlund, and Roger Lyndon; in his 1969 paper stating the theorem, Hedlund credited Curtis and Lyndon as co-discoverers. It has been called "one of the fundamental results in symbolic dynamics".
In mathematics, the Ax–Grothendieck theorem is a result about injectivity and surjectivity of polynomials that was proved independently by James Ax and Alexander Grothendieck.
In mathematics, a surjunctive group is a group such that every injective cellular automaton with the group elements as its cells is also surjective. Surjunctive groups were introduced by Gottschalk (1973). It is unknown whether every group is surjunctive.
Stochastic cellular automata or probabilistic cellular automata (PCA) or random cellular automata or locally interacting Markov chains are an important extension of cellular automaton. Cellular automata are a discrete-time dynamical system of interacting entities, whose state is discrete.
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.
In the mathematics of graph theory and finite groups, a prime graph is an undirected graph defined from a group. These graphs were introduced in a 1981 paper by J. S. Williams, credited to unpublished work from 1975 by K. W. Gruenberg and O. Kegel.
References
- Ceccherini-Silberstein, Tullio; Coornaert, Michel (2010), Cellular Automata and Groups, Springer Monographs in Mathematics, Springer-Verlag, doi:10.1007/978-3-642-14034-1, ISBN 978-3-642-14033-4, MR 2683112, Zbl 1218.37004 .
- Cornulier, Yves (2011), "A sofic group away from amenable groups", Mathematische Annalen, 350 (2): 269–275, arXiv: 0906.3374 , doi:10.1007/s00208-010-0557-8, MR 2794910, S2CID 12966793, Zbl 1247.20039 .
- Gromov, M. (1999), "Endomorphisms of symbolic algebraic varieties", Journal of the European Mathematical Society , 1 (2): 109–197, doi: 10.1007/PL00011162 , MR 1694588, Zbl 0998.14001 .
- Weiss, Benjamin (2000), "Sofic groups and dynamical systems" (PDF), Sankhyā , Series A, 62 (3): 350–359, MR 1803462, Zbl 1148.37302 .