Urn Automata
Abstract
Urn automata are a new class of automata consisting of an input tape, a finite-state controller, and an urn containing tokens with a finite set of colors, where the finite-state controller can sample and replace tokens in the urn but cannot control which tokens it receives. We consider the computational power of urn automata, showing that an urn automaton with O(f(n)) tokens can, with high probability, simulate a probabilistic Turing machine using O(log f(n)) space and vice versa, as well as giving several technical results showing that the computational power of urn automata is not a ected by variations in parameters such as the size of the state space, the number of tokens sampled per step, and so forth. Motivated by problems in distributed computing, we consider a special class of urn automata called pairing automata that model systems of finite-state machines that interact through random pairwise encounters. We show that pairing automata recognize precisely the symmetric languages recognized by urn automata.
Document Details
- Document Type
- Technical Report
- Publication Date
- Nov 05, 2003
- Accession Number
- ADA460348
Entities
People
- Dana Angluin
- James Aspnes
- Michael J. Fischer
- Rene Peralta
- Zoe Diamadi
Organizations
- Yale University