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

DOI10.1142/S0218196708004834MaRDI QIDQ3606404zbMATH OpenOpenAlexWikidataFDO

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)

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

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)

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.

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

Cites work

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

Cited in

(5)

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

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)