论文标题
自我避免的步行和多种无上下文的语言
Self-avoiding walks and multiple context-free languages
论文作者
论文摘要
令$ g $为扎根于顶点$ o $的准传递，本地有限的，连接的图，让$ c_n（o）$是$ g $上$ g $的长度$ n $的自我避免步行的数量。我们表明，如果$ g $只有薄端，则生成函数$ f _ {\ mathrm {saw}，o}（z）= \ sum_ {n \ geq 0} c_n（o）z^n $是代数函数。特别是，这种图的结缔常数是代数数。 如果$ g $是确定性的标签，也就是说，每个（指示）的边缘都带有一个标签，以至于从同一顶点开始的任何两个边缘都具有不同的标签，那么所有单词都可以沿着$ o $ $ $ $ $的语言读取的所有单词读取的所有单词，由$ l _ {\ mathrm form y Mathrm forme togress of $ o $ forms。假设一组具有标签的图形自动形态起作用。我们表明，$ l _ {\ mathrm {saw}，o} $是$ k $ - 多数上下文的语言，并且仅当$ g $的所有末端的大小最多是$ 2K $。应用于有限生成的组的Cayley图，这说明$ l _ {\ mathrm {saw}，o} $在且仅当组几乎是免费的时是多个上下文。
Let $G$ be a quasi-transitive, locally finite, connected graph rooted at a vertex $o$, and let $c_n(o)$ be the number of self-avoiding walks of length $n$ on $G$ starting at $o$. We show that if $G$ has only thin ends, then the generating function $F_{\mathrm{SAW},o}(z)=\sum_{n \geq 0} c_n(o) z^n$ is an algebraic function. In particular, the connective constant of such a graph is an algebraic number. If $G$ is deterministically edge labelled, that is, every (directed) edge carries a label such that any two edges starting at the same vertex have different labels, then the set of all words which can be read along the edges of self-avoiding walks starting at $o$ forms a language denoted by $L_{\mathrm{SAW},o}$. Assume that the group of label-preserving graph automorphisms acts quasi-transitively. We show that $L_{\mathrm{SAW},o}$ is a $k$-multiple context-free language if and only if the size of all ends of $G$ is at most $2k$. Applied to Cayley graphs of finitely generated groups this says that $L_{\mathrm{SAW},o}$ is multiple context-free if and only if the group is virtually free.
