GlobalView

Showing items 1 - 15 of 39.

Add to Quick Collection   All 39 Results

Sort:
 Add All Items to Quick Collection
Date: 2016
Language: eng
Resource Type: journal article
Identifier: http://hdl.handle.net/1959.13/1322289
Description: We prove that the homeomorphism problem for 2-manifolds can be decided in logspace. The proof relies on Reingold's logspace solution to the undirected s,t-connectivity problem in graphs.
Full Text: Full Text
Reviewed: Reviewed
Image Thumbnail
Date: 2016
Language: eng
Resource Type: journal article
Identifier: http://hdl.handle.net/1959.13/1322811
Description: For a language L, we consider its cyclic closure, and more generally the language Ck(L), which consists of all words obtained by partitioning words from L into k factors and permuting them. We prove t... More
Full Text: Full Text
Reviewed: Reviewed
Image Thumbnail
Date: 2016
Language: eng
Resource Type: journal article
Identifier: http://hdl.handle.net/1959.13/1322818
Description: We show that, given an equation over a finitely generated free group, the set of all solutions in reduced words forms an effectively constructible EDT0L language. In particular, the set of all solutio... More
Reviewed: Reviewed
Date: 2016
Language: eng
Resource Type: journal article
Identifier: http://hdl.handle.net/1959.13/1323341
Description: It is not known whether Thompson's group F is automatic. With the recent extensions of the notion of an automatic group to graph automatic by Kharlampovich, Khoussainov and Miasnikov and then t... More
Reviewed: Reviewed
Date: 2015
Language: eng
Resource Type: journal article
Identifier: http://hdl.handle.net/1959.13/1307685
Description: We compute estimates for the word metric of Baumslag–Solitar groups in terms of the Britton's lemma normal form. As a corollary, we find lower bounds for the growth rate for the groups BS(p, q) with 1... More
Reviewed: Reviewed
Date: 2015
Language: eng
Resource Type: journal article
Identifier: http://hdl.handle.net/1959.13/1061607
Description: We prove that the class of permutations generated by passing an ordered sequence 12...n through a stack of depth 2 and an infinite stack in series is in bijection with an unambiguous context-free lang... More
Full Text: Full Text
Reviewed: Reviewed
Image Thumbnail
Date: 2015
Language: eng
Resource Type: journal article
Identifier: http://hdl.handle.net/1959.13/1293479
Description: We describe a novel algorithm for random sampling of freely reduced words equal to the identity in a finitely presented group. The algorithm is based on Metropolis Monte Carlo sampling. The algorithm ... More
Reviewed: Reviewed
Date: 2015
Language: eng
Resource Type: journal article
Identifier: http://hdl.handle.net/1959.13/1324867
Description: We describe a Metropolis Monte Carlo algorithm for random sampling of freely reduced words equal to the identity in a finitely presented group. The algorithm samples from a stretched Boltzmann distrib... More
Reviewed: Reviewed
Date: 2015
Language: eng
Resource Type: journal article
Identifier: http://hdl.handle.net/1959.13/1059759
Description: We introduce the notion of the k-closure of a group of automorphisms of a locally finite tree, and give several examples of the construction. We show that the k-closure satisfies a new property of aut... More
Full Text: Full Text
Reviewed: Reviewed
Image Thumbnail
Date: 2015
Resource Type: conference paper
Identifier: http://hdl.handle.net/1959.13/1307688
Description: We show that, given a word equation over a finitely generated free group, the set of all solutions in reduced words forms an EDT0L language. In particular, it is an indexed language in the sense of Ah... More
Full Text: Full Text
Reviewed: Reviewed
Image Thumbnail
Date: 2014
Language: eng
Resource Type: journal article
Identifier: http://hdl.handle.net/1959.13/1043495
Description: We generalize the notion of a graph automatic group introduced by Kharlampovich, Khoussainov and Miasnikov by replacing the regular languages in their definition with more powerful language classes. F... More
Full Text: Full Text
Reviewed: Reviewed
Image Thumbnail
Date: 2014
Language: eng
Resource Type: journal article
Identifier: http://hdl.handle.net/1959.13/1047455
Description: We add to the classification of groups generated by 3-state automata over a 2-letter alphabet given by Bondarenko et al., by showing that a number of the groups in the classification are non-contracti... More
Full Text: Full Text
Reviewed: Reviewed
Image Thumbnail
Date: 2014
Language: eng
Resource Type: journal article
Identifier: http://hdl.handle.net/1959.13/1042414
Description: We compute the cogrowth series for Baumslag–Solitar groups BS(N, N) = 〈a,b|aNb = baN〉, which we show to be D-finite. It follows that their cogrowth rates are algebraic numbers.
Full Text: Full Text
Reviewed: Reviewed
Image Thumbnail
Date: 2013
Language: eng
Resource Type: journal article
Identifier: http://hdl.handle.net/1959.13/938672
Description: We consider the class of finitely generated groups which have a normal form computable in logspace. We prove that the class of such groups is closed under passing to finite index subgroups, direct pro... More
Full Text: Full Text
Reviewed: Reviewed
Image Thumbnail
Creators: Elder, Murray
Date: 2012
Language: eng
Resource Type: journal article
Identifier: http://hdl.handle.net/1959.13/932967
Description: Self-similar groups are a fascinating area of current research. Here we give a short, and hopefully accessible, introduction to them.
Full Text: Full Text
Image Thumbnail