Asymptotic properties of finitely generated subgroups of free groups, and of finite group presentations, can be considered in several fashions, depending on the way these objects are represented and on the distribution assumed on these representation
s: here we assume that they are represented by tuples of reduced words (generators of a subgroup) or of cyclically reduced words (relators). Classical models consider fixed size tuples of words (e.g. the few-generator model) or exponential size tuples (e.g. Gromovs density model), and they usually consider that equal length words are equally likely. We generalize both the few-generator and the density models with probabilistic schemes that also allow variability in the size of tuples and non-uniform distributions on words of a given length.Our first results rely on a relatively mild prefix-heaviness hypothesis on the distributions, which states essentially that the probability of a word decreases exponentially fast as its length grows. Under this hypothesis, we generalize several classical results: exponentially generically a randomly chosen tuple is a basis of the subgroup it generates, this subgroup is malnormal and the tuple satisfies a small cancellation property, even for exponential size tuples. In the special case of the uniform distribution on words of a given length, we give a phase transition theorem for the central tree property, a combinatorial property closely linked to the fact that a tuple freely generates a subgroup. We then further refine our results when the distribution is specified by a Markovian scheme, and in particular we give a phase transition theorem which generalizes the classical results on the densities up to which a tuple of cyclically reduced words chosen uniformly at random exponentially generically satisfies a small cancellation property, and beyond which it presents a trivial group.
This text is devoted to the theory of varieties, which provides an important tool, based in universal algebra, for the classification of regular languages. In the introductory section, we present a number of examples that illustrate and motivate the
fundamental concepts. We do this for the most part without proofs, and often without precise definitions, leaving these to the formal development of the theory that begins in Section 2. Our presentation of the theory draws heavily on the work of Gehrke, Grigorieff and Pin (2008) on the equational theory of lattices of regular languages. In the subsequent sections we consider in more detail aspects of varieties that were only briefly evoked in the introduction: Decidability, operations on languages, and characterizations in formal logic.
We show that one can define and effectively compute Stallings graphs for quasi-convex subgroups of automatic groups (textit{e.g.} hyperbolic groups or right-angled Artin groups). These Stallings graphs are finite labeled graphs, which are canonically
associated with the corresponding subgroups. We show that this notion of Stallings graphs allows a unified approach to many algorithmic problems: some which had already been solved like the generalized membership problem or the computation of a quasi-convexity constant (Kapovich, 1996); and others such as the computation of intersections, the conjugacy or the almost malnormality problems. Our results extend earlier algorithmic results for the more restricted class of virtually free groups. We also extend our construction to relatively quasi-convex subgroups of relatively hyperbolic groups, under certain additional conditions.
Monotone systems of polynomial equations (MSPEs) are systems of fixed-point equations $X_1 = f_1(X_1, ..., X_n),$ $..., X_n = f_n(X_1, ..., X_n)$ where each $f_i$ is a polynomial with positive real coefficients. The question of computing the least no
n-negative solution of a given MSPE $vec X = vec f(vec X)$ arises naturally in the analysis of stochastic models such as stochastic context-free grammars, probabilistic pushdown automata, and back-button processes. Etessami and Yannakakis have recently adapted Newtons iterative method to MSPEs. In a previous paper we have proved the existence of a threshold $k_{vec f}$ for strongly connected MSPEs, such that after $k_{vec f}$ iterations of Newtons method each new iteration computes at least 1 new bit of the solution. However, the proof was purely existential. In this paper we give an upper bound for $k_{vec f}$ as a function of the minimal component of the least fixed-point $muvec f$ of $vec f(vec X)$. Using this result we show that $k_{vec f}$ is at most single exponential resp. linear for strongly connected MSPEs derived from probabilistic pushdown automata resp. from back-button processes. Further, we prove the existence of a threshold for arbitrary MSPEs after which each new iteration computes at least $1/w2^h$ new bits of the solution, where $w$ and $h$ are the width and height of the DAG of strongly connected components.
The computational function of a matchgate is represented by its character matrix. In this article, we show that all nonsingular character matrices are closed under matrix inverse operation, so that for every $k$, the nonsingular character matrices of
$k$-bit matchgates form a group, extending the recent work of Cai and Choudhary (2006) of the same result for the case of $k=2$, and that the single and the two-bit matchgates are universal for matchcircuits, answering a question of Valiant (2002).
