GROUPS THAT DO AND DO NOT HAVE GROWING CONTEXT-SENSITIVE WORD PROBLEM

DOI10.1142/S0218196708004834zbMATH Open1177.20044arXiv0801.4533OpenAlexW2039842064WikidataQ42960065 ScholiaQ42960065MaRDI QIDQ3606404FDOQ3606404

Authors: Derek F. Holt, Sarah Rees, Michael Shapiro 

Publication date: 26 February 2009

Published in: International Journal of Algebra and Computation (Search for Journal in Brave)

Abstract: We prove that a group has word problem that is a growing context-sensitive language precisely if its word problem can be solved using a non-deterministic Cannon's algorithm (the deterministic algorithms being defined by Goodman and Shapiro). We generalise their results to find many examples of groups not admitting non-deterministic Cannon's algorithms. This adds to the examples of Kambites and Otto of groups separating context-sensitive and growing context-sensitive word problems, and provides a new language-theoretic separation result.

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

Recommendations

• Developments in Language Theory
• A NOTE ON CONTEXT-SENSITIVE LANGUAGES AND WORD PROBLEMS
• Groups with poly-context-free word problem.
• On groups whose word problem is solved by a counter automaton.
• The word problem of \(\mathbb{Z}^n\) is a multiple context-free language

zbMATH Keywords

word problemDehn algorithmgrowing context-sensitive languages

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Algebraic theory of languages and automata (68Q70) Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) (20F10)

Cites Work

• ON A GENERALIZATION OF DEHN'S ALGORITHM
• A NOTE ON CONTEXT-SENSITIVE LANGUAGES AND WORD PROBLEMS

Cited In (4)

• Anisimov's theorem for inverse semigroups.
• The word problem of \(\mathbb{Z}^n\) is a multiple context-free language
• Church-Rosser groups and growing context-sensitive groups
• Developments in Language Theory

This page was built for publication: GROUPS THAT DO AND DO NOT HAVE GROWING CONTEXT-SENSITIVE WORD PROBLEM

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