MURAL - Maynooth University Research Archive Library



    Random number selection in self-assembly


    Doty, David, Lutz, Jack H., Patitz, Mathhew J., Summers, Scott M. and Woods, Damien (2009) Random number selection in self-assembly. In: Unconventional Computation. Springer, pp. 143-157. ISBN 3-642-03744-5

    [thumbnail of dW_random.pdf]
    Preview
    Text
    dW_random.pdf

    Download (514kB) | Preview

    Abstract

    We investigate methods for exploiting nondeterminism inherent within the Tile Assembly Model in order to generate uniform random numbers. Namely, given an integer range {0,...,n − 1}, we exhibit methods for randomly selecting a number within that range. We present three constructions exhibiting a trade-off between space requirements and closeness to uniformity. The first selector selects a random number with probability Θ(1/n) using O(log2 n) tiles. The second selector takes a user-specified parameter that guarantees the probabilities are arbitrarily close to uniform, at the cost of additional space. The third selector selects a random number with probability exactly 1/n, and uses no more space than the first selector with high probability, but uses potentially unbounded space.
    Item Type: Book Section
    Keywords: Tile Type; Pseudorandom Generator; Nondeterministic Choice; Tile Assembly Model; Perfect Uniformity;
    Academic Unit: Faculty of Science and Engineering > Computer Science
    Faculty of Science and Engineering > Research Institutes > Hamilton Institute
    Item ID: 15729
    Depositing User: Damien Woods
    Date Deposited: 23 Mar 2022 12:34
    Publisher: Springer
    Refereed: Yes
    Related URLs:
    URI: https://mu.eprints-hosting.org/id/eprint/15729
    Use Licence: This item is available under a Creative Commons Attribution Non Commercial Share Alike Licence (CC BY-NC-SA). Details of this licence are available here

    Repository Staff Only (login required)

    Item control page
    Item control page

    Downloads

    Downloads per month over past year

    Origin of downloads