Groups with poly-context-free word problem.

DOI10.1515/GCC-2014-0002MaRDI QIDQ2249563zbMATH OpenOpenAlexFDO

Authors Tara Brough

Publication date 2 July 2014

Published in Groups - Complexity - Cryptology (Search for Journal in Brave)

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

zbMATH Keywords

direct products of free groupsintersections of context-free languagesmetabelian groupspoly-context-free languagessemilinear setstorsion-free soluble groupsword problem

Mathematics Subject Classification ID

Free nonabelian groups (20E05) Subgroup theorems; subgroup growth (20E07) Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) (20F10) Solvable groups, supersolvable groups (20F16) Formal languages and automata (68Q45)

Abstract: We consider the class of groups whose word problem is poly-context-free; that is, an intersection of finitely many context-free languages. We show that any group which is virtually a finitely generated subgroup of a direct product of free groups has poly-context-free word problem, and conjecture that the converse also holds. We prove our conjecture for several classes of soluble groups, including metabelian groups and torsion-free soluble groups, and present progress towards resolving the conjecture for soluble groups in general. Some of the techniques introduced for proving languages not to be poly-context-free may be of independent interest.

Recommendations

• GROUPS WITH CONTEXT-FREE CO-WORD PROBLEM
• Context-Free Groups and Bass–Serre Theory
• GROUPS WITH CONTEXT-FREE REDUCED WORD PROBLEM
• Context-free irreducible word problems in groups.
• The word problem of \(\mathbb{Z}^n\) is a multiple context-free language

Cited in

(26)

• Parallel poly-pushdown groups
• Computing presentations for subgroups of polycyclic groups and of context-free groups
• Non-finitely generated maximal subgroups of context-free monoids
• Groups whose word problems are not semilinear
• Context-free word problem semigroups
• MIX is a 2-MCFL and the word problem in \(\mathbb{Z}^2\) is captured by the IO and the OI hierarchies
• The (nested) word problem
• On a class of poly-context-free groups generated by automata
• Groups with context-free conjugacy problems.
• GROUPS WITH CONTEXT-FREE REDUCED WORD PROBLEM
• scientific article; zbMATH DE number 5155120 (Why is no real title available?)
• GROUPS THAT DO AND DO NOT HAVE GROWING CONTEXT-SENSITIVE WORD PROBLEM
• On a subclass of context-free groups
• C-graph automatic groups.
• Multipass automata and group word problems
• Anisimov's theorem for inverse semigroups.
• Finitely generated soluble groups and their subgroups.
• GROUPS WITH CONTEXT-FREE CO-WORD PROBLEM
• Groups whose word problems are accepted by abelian G-automata
• Groups with context-free Diophantine problem
• Free products of semigroups and monoids with a deterministic context-free word problem
• The power of a single qubit: two-way quantum finite automata and the word problem
• Quaternionic lattices and the poly-context-free word problem
• The word problem and growth of groups
• Commutative semigroups with a context-free word problem
• Groups, the theory of ends, and context-free languages

This page was built for publication: Groups with poly-context-free word problem.

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2249563)