The Library
Groups with context-free conjugacy problems
Tools
Holt, Derek F., Rees, Sarah and Röver, Claas E. (2011) Groups with context-free conjugacy problems. International Journal of Algebra and Computation, Vol.21 (No.1-2). pp. 193-216. doi:10.1142/S0218196711006133 ISSN 0218-1967.
Research output not available from this repository.
Request-a-Copy directly from author or use local Library Get it For Me service.
Official URL: http://dx.doi.org/10.1142/S0218196711006133
Abstract
The conjugacy problem and the inverse conjugacy problem of a finitely generated group are defined, from a language theoretic point of view, as sets of pairs of words. An automaton might be obliged to read the two input words synchronously, or could have the option to read asynchronously. Hence each class of languages gives rise to four classes of groups; groups whose (inverse) conjugacy problem is an (a) synchronous language in the given class. For regular languages all these classes are identical with the class of finite groups. We show that the finitely generated groups with asynchronously context-free inverse conjugacy problem are precisely the virtually free groups. Moreover, the other three classes arising from context-free languages are shown all to coincide with the class of virtually cyclic groups, which is precisely the class of groups with synchronously one-counter (inverse) conjugacy problem. It is also proved that, for a delta-hyperbolic group and any lambda >= 1, epsilon >= 0, the intersection of the inverse conjugacy problem with the set of pairs of (lambda, epsilon)-quasigeodesics is context-free. Finally we show that the conjugacy problem of a virtually free group is an asynchronously indexed language.
Item Type: | Journal Article | ||||
---|---|---|---|---|---|
Divisions: | Faculty of Science, Engineering and Medicine > Science > Mathematics | ||||
Journal or Publication Title: | International Journal of Algebra and Computation | ||||
Publisher: | World Scientific Publishing Co. Pte. Ltd. | ||||
ISSN: | 0218-1967 | ||||
Official Date: | February 2011 | ||||
Dates: |
|
||||
Volume: | Vol.21 | ||||
Number: | No.1-2 | ||||
Page Range: | pp. 193-216 | ||||
DOI: | 10.1142/S0218196711006133 | ||||
Status: | Peer Reviewed | ||||
Publication Status: | Published |
Data sourced from Thomson Reuters' Web of Knowledge
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |