Self-avoiding walks and multiple context-free languages

DOI10.5070/C63160431MaRDI QIDQ5886265zbMATH OpenOpenAlexFDO

Authors Florian Lehner, Christian Lindorfer

Publication date 31 March 2023

Published in Combinatorial Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2010.06974

zbMATH Keywords

Cayley graphformal languagemultiple context free languageself avoiding walkvirtually free group

Mathematics Subject Classification ID

Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) (20F10) Formal languages and automata (68Q45)

Recommendations

• The language of self-avoiding walks
• The Language of Self-Avoiding Walks
• Context-free languages and random walks on groups
• Counting self-avoiding walks on free products of graphs
• Context-free pairs of groups. II: Cuts, tree sets, and random walks

Cites work

• A Stallings type theorem for quasi-transitive graphs
• Analytic combinatorics
• Analytic models and ambiguity of context-free languages
• Automorphisms and endomorphisms of infinite locally finite graphs
• Comparing consecutive letter counts in multiple context-free languages
• Counting self-avoiding walks on free products of graphs
• Cutting up graphs
• Formulae and asymptotics for coefficients of algebraic functions
• Graph minors. III. Planar tree-width
• Groups, the theory of ends, and context-free languages
• Growth and ergodicity of context-free languages
• scientific article; zbMATH DE number 3148803 (Why is no real title available?)
• scientific article; zbMATH DE number 3932372 (Why is no real title available?)
• scientific article; zbMATH DE number 3976367 (Why is no real title available?)
• scientific article; zbMATH DE number 3588051 (Why is no real title available?)
• scientific article; zbMATH DE number 1024108 (Why is no real title available?)
• scientific article; zbMATH DE number 3238653 (Why is no real title available?)
• scientific article; zbMATH DE number 3381862 (Why is no real title available?)
• Lectures on self-avoiding walks
• MIX is a 2-MCFL and the word problem in \(\mathbb{Z}^2\) is captured by the IO and the OI hierarchies
• On Cayley graphs of virtually free groups.
• On multiple context-free grammars
• Random self-avoiding walks on one-dimensional lattices
• Random Walks on Infinite Graphs and Groups
• S-functions for graphs
• Self-avoiding walks and connective constants
• Self-avoiding walks, the language of science, and Fibonacci numbers
• The connective constant of the honeycomb lattice equals \(\sqrt{2+\sqrt 2}\)
• The Hadwiger number of infinite vertex-transitive graphs
• The language of self-avoiding walks
• The theory of ends, pushdown automata, and second-order logic
• The word problem of \(\mathbb{Z}^n\) is a multiple context-free language
• Über die Maximalzahl fremder unendlicher Wege in Graphen
• Vertex cuts
• Vertex-transitive graphs and accessibility

Cited in

(8)

• Context-free languages and random walks on groups
• Weighted self-avoiding walks
• The language of self-avoiding walks
• Two-ended quasi-transitive graphs
• Self-avoiding walks and their languages
• Self-avoiding walks on Cayley graphs through the lens of symbolic dynamics
• Self-avoiding walk is ballistic on graphs with more than one end
• Counting self-avoiding walks on free products of graphs

This page was built for publication: Self-avoiding walks and multiple context-free languages

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5886265)