You have just completed your registration at OpenAire.
Before you can login to the site, you will need to activate your account.
An e-mail will be sent to you with the proper instructions.
Important!
Please note that this site is currently undergoing Beta testing.
Any new content you create is not guaranteed to be present to the final version
of the site upon release.
For each symmetric, aperiodic probability measure $\mu$ on a finitely generated group $G$, we define a subset $A_{\mu}$ consisting of group elements $g$ for which the limit of the ratio ${\mu^{\ast n}(g)}/{\mu^{\ast n}(e)}$ tends to $1$. We prove that $A_\mu$ is a subgroup, is amenable, contains every finite normal subgroup, and $G=A_\mu$ if and only if $G$ is amenable. For non-amenable groups we show that $A_\mu$ is not always a normal subgroup, and can depend on the measure. We formulate so...
We prove that the class of permutations generated by passing an ordered sequence $12\dots n$ through a stack of depth 2 and an infinite stack in series is in bijection with an unambiguous context-free language, where a permutation of length $n$ is encoded by a string of length $3n$. It follows that the sequence counting the number of permutations of each length has an algebraic generating function. We use the explicit context-free language to compute the generating function: \begin{align*} \s...
We critically analyse a recent numerical method due to the first author, Rechnitzer and van Rensburg, which attempts to detect amenability or non-amenability in a finitely generated group by numerically estimating its asymptotic cogrowth rate. We identify two potential sources of error. We then propose a modification of the method that enables it to easily compute surprisingly accurate estimates for initial terms of the cogrowth sequence.
M. Picantin introduced the notion of Garside groups of spindle type, generalizing the 3-strand braid group. We show that, for linear Garside groups of spindle type, a normal form and a solution to the conjugacy problem are logspace computable. For linear Garside groups of spindle type with homogenous presentation we compute a geodesic normal form in logspace.
International audience; For a language $L$, we consider its cyclic closure, and more generally the language $C^{k}(L)$, which consists of all words obtained by partitioning words from $L$ into $k$ factors and permuting them. We prove that the classes of ET0L and EDT0L languages are closed under the operators $C^k$. This both sharpens and generalises Brandstädt's result that if $L$ is context-free then $C^{k}(L)$ is context-sensitive and not context-free in general for $k \geq 3$. We also show...
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-contracting. We show that the criterion we use to prove a self-similar action is non-contracting also implies that the associated self-similarity graph introduced by Nekrashevych is non-hyperbolic.
We consider the cyclic closure of a language, and its generalisation to the operators $C^k$ introduced by Brandst\"adt. We prove that the cyclic closure of an indexed language is indexed, and that if $L$ is a context-free language then $C^k(L)$ is indexed.
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 to C-graph automatic by the authors, a compelling question is whether F is graph automatic or C-graph automatic for an appropriate language class C. The extended definitions allow the use of a symbol alphabet for the normal form language, replacing the dependence on generating set. In this paper we const...
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 Aho. The question of whether a description of solution sets in reduced words as an indexed language is possible has been been open for some years, apparently without much hope that a positive answer could hold. Nevertheless, our answer goes far beyond: they are EDT0L, which is a proper subclass of ...
No project research data found
No project statistics found
Scientific Results
Chart is loading... It may take a bit of time. Please be patient and don't reload the page.
PUBLICATIONS BY ACCESS MODE
Chart is loading... It may take a bit of time. Please be patient and don't reload the page.
Publications in Repositories
Chart is loading... It may take a bit of time. Please be patient and don't reload the page.