Random walks on semaphore codes and delay de Bruijn semigroups

DOI10.1142/S0218196716500284MaRDI QIDQ5739483zbMATH OpenOpenAlexFDO

Authors Anne Schilling, John L. Rhodes, Pedro V. Silva

Publication date 15 July 2016

Published in International Journal of Algebra and Computation (Search for Journal in Brave)

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

zbMATH Keywords

random walkhitting timeright congruencessemaphore codesde Bruijn semigroupresets

Mathematics Subject Classification ID

Graph representations (geometric and intersection representations, etc.) (05C62) Random walks on graphs (05C81) Algebraic theory of languages and automata (68Q70) Representation of semigroups; actions of semigroups on sets (20M30) Varieties and pseudovarieties of semigroups (20M07) Semigroups in automata theory, linguistics, etc. (20M35)

Abstract: We develop a new approach to random walks on de Bruijn graphs over the alphabet $A$ through right congruences on $A^k$, defined using the natural right action of $A^{+}$. A major role is played by special right congruences, which correspond to semaphore codes and allow an easier computation of the hitting time. We show how right congruences can be approximated by special right congruences.

Recommendations

• scientific article; zbMATH DE number 3940346
• Random walks on finite semigroups
• Characterizations and properties of semaphore codes
• Random Walks on de Bruijn Graphs.
• scientific article; zbMATH DE number 4216772
• Tunstall Code, Khodak Variations, and Random Walks
• scientific article; zbMATH DE number 2067820
• scientific article; zbMATH DE number 3950378
• k-p-infix codes and semaphore codes

Cites work

• scientific article; zbMATH DE number 5604049 (Why is no real title available?)
• scientific article; zbMATH DE number 512864 (Why is no real title available?)
• scientific article; zbMATH DE number 3095523 (Why is no real title available?)
• Codes and automata.
• De Bruijn Sequences-A Model Example of the Interaction of Discrete Mathematics and Computer Science
• Further results on monoids acting on trees.
• MONOIDS ACTING ON TREES: ELLIPTIC AND WREATH PRODUCTS AND THE HOLONOMY THEOREM FOR ARBITRARY MONOIDS WITH APPLICATIONS TO INFINITE GROUPS
• Markov chains and mixing times. With a chapter on ``Coupling from the past by James G. Propp and David B. Wilson.
• Markov chains, \(\mathcal{R}\)-trivial monoids and representation theory
• Multivariate juggling probabilities
• Normal Recurring Decimals
• Stationary distribution and eigenvalues for a de Bruijn process
• The \(\mathfrak q\)-theory of finite semigroups.
• The semaphore codes attached to a Turing machine via resets and their various limits

Cited in

(7)

• The semaphore codes attached to a Turing machine via resets and their various limits
• Upper Bounds on Mixing Time of Finite Markov Chains
• Tunstall Code, Khodak Variations, and Random Walks
• Holonomy theorem for finite semigroups
• Mixing time for Markov chain on linear extensions
• Interview with Anne Schilling
• Unified theory for finite Markov chains

This page was built for publication: Random walks on semaphore codes and delay de Bruijn semigroups

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