Context-free languages and random walks on groups
type: Item
instance of: scholarly article
title: Context-free languages and random walks on groups
zbMATH Open document ID: 0637.60014
DOI: 10.1016/0012-365X(87)90167-1
author: Wolfgang Woess
published in: Discrete Mathematics
publication date: 1987-01-01T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 60B15
Mathematics Subject Classification ID: 60G50
Mathematics Subject Classification ID: 03D40
Mathematics Subject Classification ID: 68Q45
zbMATH DE Number: 4038890
zbMATH Keywords: Green function
zbMATH Keywords: random walk on a discrete group
zbMATH Keywords: context-free word problem
zbMATH Keywords: formal language theory
MaRDI profile type: Publication
cites work: Q3706278
cites work: Asymptotic Methods in Enumeration
cites work: Random walks on free products, quotients and amalgams
cites work: Q5526125
cites work: The accessibility of finitely presented groups
cites work: Wahrscheinlichkeitsmaße auf diskreten Gruppen
cites work: Q4191344
cites work: Local limits and harmonic functions for nonisotropic random walks on free groups
cites work: Marches aléatoires sur les groupes de Lie
cites work: Q4198075
cites work: Random walks on discrete groups: Boundary and entropy
cites work: Symmetric Random Walks on Groups
cites work: Groups, the theory of ends, and context-free languages
cites work: Spherical functions and local limit theorems on free groups
cites work: Isotropic random walks in a tree
cites work: Q5731217
cites work: Q5651924
cites work: Q5774182
cites work: Q3763305
full work available at URL: 0012-365x(87)90167-1
OpenAlex ID: W1992097918
Recommended article: Words in linear groups, random walks, automata and P-recursiveness
Recommended article: Rate of Escape of Random Walks on Regular Languages and Free Products by Amalgamation of Finite Groups
Recommended article: Self-avoiding walks and multiple context-free languages
Recommended article: Q4801470
Recommended article: Q3323300
Recommended article: Context-Free Groups and Bass–Serre Theory
Recommended article: Growth and ergodicity of context-free languages
Recommended article: Free group languages: Rational versus recognizable
Recommended article: Groups, the theory of ends, and context-free languages
Recommended article: Context-free pairs of groups. II: Cuts, tree sets, and random walks
description: scientific article; zbMATH DE number 4038890