Please use this identifier to cite or link to this item: http://hdl.handle.net/2381/38806
Title: Characterizing word problems of groups
Authors: Jones, S. A. M.
Thomas, Richard M.
First Published: 13-Sep-2016
Award date: 21-Sep-2016
Presented at: 10th International Workshop, RP 2016, Aalborg, Denmark
Start Date: 19-Sep-2016
Publisher: Springer Verlag (Germany)
Citation: Lecture Notes in Computer Science, 2016, Volume 9899 pp. 104-118, Book Title: Reachability Problems
Abstract: The word problem of a finitely generated group is a fundamental notion in group theory; it can be defined as the set of all the words in the generators of the group that represent the identity element of the group. This definition allows us to consider a word problem as a formal language and a rich topic of research concerns the connection between the complexity of this language and the algebraic structure of the corresponding group. Another interesting problem is that of characterizing which languages are word problems of groups. There is a known necessary and sufficient criterion for a language to be a word problem of a group; however a natural question is what other characterizations there are. In this paper we investigate this question, using sentences expressed in first-order logic where the relations we consider are membership of the language in question and concatenation of words. We choose some natural conditions that apply to word problems and then characterize which sets of these conditions are sufficient to guarantee that the language in question really is the word problem of a group. We finish by investigating the decidability of these conditions for the families of regular and one-counter languages.
Series/Report no.: Lecture Notes in Computer Science;9899
DOI Link: 10.1007/978-3-319-45994-3_8
ISSN: 0302-9743
ISBN: 978-3-319-45993-6
Links: http://link.springer.com/chapter/10.1007%2F978-3-319-45994-3_8
http://hdl.handle.net/2381/38806
Version: Post-print
Status: Peer-reviewed
Type: Journal Article
Rights: Creative Commons “Attribution Non-Commercial No Derivatives” licence CC BY-NC-ND, further details of which can be found via the following link: http://creativecommons.org/licenses/by-nc-nd/4.0/ Archived with reference to SHERPA/RoMEO and publisher website.
Appears in Collections:Published Articles, Dept. of Computer Science

Files in This Item:
File Description SizeFormat 
Char-word-prob.pdfPost-review (final submitted author manuscript)254.55 kBAdobe PDFView/Open


Items in LRA are protected by copyright, with all rights reserved, unless otherwise indicated.