Groups whose word problems are not semilinear

DOI10.1515/gcc-2018-0010zbMath1491.20079arXiv1804.09609OpenAlexW2963046438WikidataQ125863229 ScholiaQ125863229MaRDI QIDQ2317163

Robert Kropholler, Saul Schleimer, Robert H. Gilman

Publication date: 8 August 2019

Published in: Groups, Complexity, Cryptology (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1804.09609

zbMATH Keywords

word problemgroup theoryformal languages

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Generators, relations, and presentations of groups (20F05) Geometric group theory (20F65) Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) (20F10) Hyperbolic groups and nonpositively curved groups (20F67)

Related Items (6)

The word problem of \(\mathbb{Z}^n\) is a multiple context-free language ⋮ Groups whose word problems are accepted by abelian \(G\)-automata ⋮ On the word problem for free products of semigroups and monoids ⋮ Unnamed Item ⋮ Closure properties in the class of multiple context-free groups ⋮ Non-finitely generated maximal subgroups of context-free monoids

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The virtual Haken conjecture (with an appendix by Ian Agol, Daniel Groves and Jason Manning).
• The genus zero Gromov-Witten invariants of the symmetric square of the plane
• Multipass automata and group word problems
• A context-free and a 1-counter geodesic language for a Baumslag-Solitar group
• Groups, the theory of ends, and context-free languages
• Research announcement: The structure of groups with a quasiconvex hierarchy.
• On multiple context-free grammars
• Transductions des langages de Chomsky
• The word problem of \(\mathbb{Z}^n\) is a multiple context-free language
• Automorphisms of graph groups.
• Groups with poly-context-free word problem.
• MIX is a 2-MCFL and the word problem in \(\mathbb{Z}^2\) is captured by the IO and the OI hierarchies
• Special cube complexes
• 3-manifold groups
• Parsing Beyond Context-Free Grammars
• GROUPS WITH CONTEXT-FREE CONJUGACY PROBLEMS
• GROUPS WITH CONTEXT-FREE REDUCED WORD PROBLEM
• On the geometry and dynamics of diffeomorphisms of surfaces
• Some two-generator one-relator non-Hopfian groups
• Three dimensional manifolds, Kleinian groups and hyperbolic geometry
• Presentations for subgroups of Artin groups
• Graph Classes: A Survey
• Finite degrees of ambiguity in pattern languages
• LENGTH AND AREA FUNCTIONS ON GROUPS AND QUASI-ISOMETRIC HIGMAN EMBEDDINGS
• CONTEXT-FREE GROUPS AND THEIR STRUCTURE TREES
• ON GROUPS PRESENTED BY MONADIC REWRITING SYSTEMS WITH GENERATORS OF FINITE ORDER
• The co-word problem for the Higman-Thompson group is context-free
• GROUPS AND SEMIGROUPS WITH A ONE-COUNTER WORD PROBLEM

This page was built for publication: Groups whose word problems are not semilinear