✦ LIBER ✦

Context-free languages and random walks on groups

✍ Scribed by Wolfgang Woess

Publisher: Elsevier Science
Year: 1987
Tongue: English
Weight: 435 KB
Volume: 67
Category: Article
ISSN: 0012-365X
DOI: 10.1016/0012-365x(87)90167-1

No coin nor oath required. For personal study only.

✦ Synopsis

The Green function of an arbitrary, finitely supported random walk on a discrete group with context-free word problem is algebraic. It is shown how this theorem can be deduced from basic results of formal language theory. Context-free groups are precisely the finite extensions of free groups.

📜 SIMILAR VOLUMES

On commutative context-free languages

✍ J. Beauquier; M. Blattner; M. Latteux 📂 Article 📅 1987 🏛 Elsevier Science 🌐 English ⚖ 620 KB

Characters and Random Walks on Finite Cl

Characters and Random Walks on Finite Classical Groups

✍ David Gluck 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 447 KB

Let G be a finite group and E a generating set for G. Let P be a probability measure on G whose support is E. We define a random walk on G as follows. At the zeroth stage, we set w 0 =1. At the k th stage, we set w k =w k&1 x, where x # E is chosen with probability P(x). For g # G, the probability t

Generating words in a context-free langu

Generating words in a context-free language uniformly at random

✍ Harry G. Mairson 📂 Article 📅 1994 🏛 Elsevier Science 🌐 English ⚖ 412 KB

On Generalizing the Cut-off Phenomenon f

On Generalizing the Cut-off Phenomenon for Random Walks on Groups

✍ J.S. Rosenthal 📂 Article 📅 1995 🏛 Elsevier Science 🌐 English ⚖ 517 KB

Random Walk in an Alcove of an Affine We

Random Walk in an Alcove of an Affine Weyl Group, and Non-colliding Random Walks on an Interval

✍ David J. Grabiner 📂 Article 📅 2002 🏛 Elsevier Science 🌐 English ⚖ 159 KB

We use a reflection argument, introduced by Gessel and Zeilberger, to count the number of k-step walks between two points which stay within a chamber of a Weyl group. We apply this technique to walks in the alcoves of the classical affine Weyl groups. In all cases, we get determinant formulas for th

Random walks on random simple graphs

✍ Martin Hildebrand 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 676 KB

This paper looks at random regular simple graphs and considers nearest neighbor random walks on such graphs. This paper considers walks where the degree d of each vertex is around (logn)", where a is a constant which is at least 2 and where n is the number of vertices. By extending techniques of Dou