A note on Context Sensitive languages and Word Problems

Thumbnail Image

Date

Authors

Journal Title

Journal ISSN

Volume Title

Publisher

Abstract

Description

Anisimov and Seifert show that a group has a regular word problem ifand only if it is finite. Muller and Schupp (together with Dunwoody's accessibility result) show that a group has context free word problem if and only if it is virtually free. In this note, we exhibit a class of groups where the word problem is as close as possible to being a context sensitive language. This class includes the automatic groups and is closed under passing to finitely generated subgroups. Consequently, it is quite large, including many groups which are not finitely presented.
AMS-Tex, 3 pages, no figures

Keywords

Group Theory

Citation

URI

http://salesiana.dossiersoluciones.com/handle/123456789/152844

Consulte el texto completo en el siguiente enlace:

https://arxiv.org/abs/math/9306204
 http://arxiv.org/abs/math/9306204

Collections

arXiv