From automatic structures to automatic groups.
From MaRDI portal
Abstract: In this paper we introduce the concept of a Cayley graph automatic group (CGA group or graph automatic group, for short) which generalizes the standard notion of an automatic group. Like the usual automatic groups graph automatic ones enjoy many nice properties: these group are invariant under the change of generators, they are closed under direct and free products, certain types of amalgamated products, and finite extensions. Furthermore, the Word Problem in graph automatic groups is decidable in quadratic time. However, the class of graph automatic groups is much wider then the class of automatic groups. For example, we prove that all finitely generated 2-nilpotent groups and Baumslag-Solitar groups B(1,n) are graph automatic, as well as many other metabelian groups.
Recommendations
Cites work
- scientific article; zbMATH DE number 3875506 (Why is no real title available?)
- scientific article; zbMATH DE number 53151 (Why is no real title available?)
- scientific article; zbMATH DE number 53661 (Why is no real title available?)
- scientific article; zbMATH DE number 1284208 (Why is no real title available?)
- scientific article; zbMATH DE number 1302870 (Why is no real title available?)
- scientific article; zbMATH DE number 1944116 (Why is no real title available?)
- scientific article; zbMATH DE number 2133330 (Why is no real title available?)
- scientific article; zbMATH DE number 2156384 (Why is no real title available?)
- scientific article; zbMATH DE number 848082 (Why is no real title available?)
- scientific article; zbMATH DE number 3380828 (Why is no real title available?)
- scientific article; zbMATH DE number 3394125 (Why is no real title available?)
- Automata, groups, limit spaces, and tilings.
- Automatic Structures: Richness and Limitations
- Automatic groups: A guided tour
- Automatic linear orders and trees
- Combings of groups and the grammar of reparameterization.
- Definability in the monadic second-order theory of successor
- First-order and counting theories ofω-automatic structures
- Formal language theory and the geometry of 3-manifolds
- Groups of polynomial growth and expanding maps. Appendix by Jacques Tits
- Introduction to group theory. Translated from the Russian. With a new chapter.
- Logical aspects of Cayley-graphs: the group case
- Model-theoretic complexity of automatic structures
- ON A GENERALIZATION OF DEHN'S ALGORITHM
- Recursively presentable prime models
- Some two-generator one-relator non-Hopfian groups
- Three lectures on automatic structures
- Wreath products and finitely presented groups
Cited in
(51)- scientific article; zbMATH DE number 665465 (Why is no real title available?)
- Regular path systems and (bi)automatic groups.
- AUTOMATIC AND POLYNOMIAL-TIME ALGEBRAIC STRUCTURES
- Algorithms and topology of Cayley graphs for groups.
- Cayley automata
- The complexity of verbal languages over groups
- Lamplighter groups and automata
- Metric properties of Baumslag-Solitar groups.
- scientific article; zbMATH DE number 4076625 (Why is no real title available?)
- Groups defined by automata
- scientific article; zbMATH DE number 3559545 (Why is no real title available?)
- Cyclic automata
- The monoid of queue actions
- An example of an automatic graph of intermediate growth
- Thompson's group F is 1-counter graph automatic.
- C-graph automatic groups.
- Developments in Language Theory
- Nonstandard Cayley automatic representations for fundamental groups of torus bundles over the circle
- Cayley automatic groups and numerical characteristics of Turing transducers
- Cayley graph automatic groups are not necessarily Cayley graph biautomatic
- Dynamic algorithms for multimachine interval scheduling through analysis of idle intervals
- Automatic Groups Associated with Word Orders Other than Shortlex
- Cayley linear-time computable groups
- Finitely generated semiautomatic groups
- Automatic groups: A guided tour
- Finitely generated semiautomatic groups
- A combination theorem for affine tree-free groups
- Measuring closeness between Cayley automatic groups and automatic groups
- BEING CAYLEY AUTOMATIC IS CLOSED UNDER TAKING WREATH PRODUCT WITH VIRTUALLY CYCLIC GROUPS
- scientific article; zbMATH DE number 67431 (Why is no real title available?)
- Tree languages and branched groups
- On the geometry of Cayley automatic groups
- Word automatic groups of nilpotency class 2
- An automata theoretic approach to the generalized word problem in graphs of groups.
- On automatic transitive graphs
- STACS 2005
- scientific article; zbMATH DE number 7561314 (Why is no real title available?)
- DECIDABILITY AND COMPLEXITY IN AUTOMATIC MONOIDS
- Automatic groups and amalgams
- String compression in FA-presentable structures
- Homology and closure properties of autostackable groups
- Extending the synchronous fellow traveler property
- Quasi-automatic semigroups
- Geometry of the word problem for 3-manifold groups
- Higher rank lamplighter groups are graph automatic
- The inclusion structure of partially lossy queue monoids and their trace submonoids
- TWO AUTOMATIC SPANNING TREES IN SMALL CANCELLATION GROUP PRESENTATIONS
- Semiautomatic structures
- FOUNDATIONS OF ONLINE STRUCTURE THEORY
- Cayley polynomial-time computable groups
- COMBING NILPOTENT AND POLYCYCLIC GROUPS
This page was built for publication: From automatic structures to automatic groups.
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2016098)
