×

zbMATH — the first resource for mathematics

Context-free languages and random walks on groups. (English) Zbl 0637.60014
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.

MSC:
60B15 Probability measures on groups or semigroups, Fourier transforms, factorization
60G50 Sums of independent random variables; random walks
03D40 Word problems, etc. in computability and recursion theory
68Q45 Formal languages and automata
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Aomoto, K., Spectral theory on a free group and algebraic curves, J. fac. sci. univ. Tokyo, sec. IA, 31, 297-317, (1984) · Zbl 0583.60068
[2] Bender, E.A., Asymptotic methods in enumeration, SIAM review, 16, 485-515, (1974) · Zbl 0294.05002
[3] Cartwright, D.I.; Soardi, P.M., Random walks on free products, quotients and amalgams, Nagoya math. J., 102, 163-180, (1986) · Zbl 0592.60052
[4] Chomsky, N.; Schützenberger, M.P., The algebraic theory of context-free languages, (), 118-161 · Zbl 0148.00804
[5] Dunwoody, M.J., The accessibility of finitely presented groups, Inventiones math., 81, 449-457, (1985) · Zbl 0572.20025
[6] Gerl, P., Wahrscheinlichkeitsmaβe auf disktreten gruppen, Archiv math., 31, 611-619, (1978)
[7] Gerl, P., Ein konvergenzsatz für faltungspotenzen, (), 120-125 · Zbl 0405.60011
[8] Gerl, P.; Woess, W., Local limits and harmonic functions for nonistropic walks on free groups, Probab. th. rel. fields, 71, 341-355, (1986) · Zbl 0562.60011
[9] Guivarc’h, Y.; Keane, M.; Roynette, B., Marches aléatoires sur LES groupes de Lie, () · Zbl 0367.60081
[10] Harrison, M.A., Introduction to formal language theory, (1978), Addison-Wesley London · Zbl 0411.68058
[11] Kaimanovich, V.A.; Vershik, A.M., Random walks on discrete groups: boundary and entropy, Ann. probab., 11, 457-490, (1983) · Zbl 0641.60009
[12] Kesten, H., Symmetric random walks on groups, Trans. amer. math. soc., 92, 336-354, (1959) · Zbl 0092.33503
[13] Kuich, W.; Salomaa, A., Semerings, automata, languages, (1985), Springer Berlin
[14] Muller, D.E.; Schupp, P.E., Groups, the theory of ends, and context-free languages, J. comp. syst. sci., 26, 295-310, (1983) · Zbl 0537.20011
[15] Picardello, M.A., Spherical functions and local limit theorems on free groups, Ann. math. pur. appl., 33, 177-191, (1983) · Zbl 0527.60011
[16] Sawyer, S., Isotropic random walks in a tree, Z. wahrsch. verw. gebiete, 42, 279-292, (1978) · Zbl 0362.60075
[17] Spitzer, F., Principles of random walk, (1964), Van Nostrand Princeton · Zbl 0119.34304
[18] Stallings, J., Group theory and three-dimensional manifolds, (1971), Yale Univ. Press New Haven · Zbl 0241.57001
[19] Steger, T., Harmonic analysis for an anisotropic random walk on a homogeneous tree, ()
[20] van der Waerden, B.L., Einführung in die algebraische geometrie, (1939), Springer Berlin · Zbl 0021.25001
[21] Woess, W., Nearest neighbour random walks on free products of discrete groups, Boll. un. mat. it., 5-B, 961-982, (1986) · Zbl 0627.60012
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.