Decremental Tag Systems and Random Trees
Patrick Bahls
Mark McClure
Department of Mathematics
University of North Carolina at Asheville
Asheville, NC 28804
Josh Knox
Department of Mathematics
Morehead State University
Morehead, KY 40351
Abstract
We introduce a variation of Post's tag systems that leads to a finite state machine. Our system is simpler than those considered by Post, in that there are only finitely many states. It is more complicated, in that any given state can evolve in multiple directions. Most importantly, we are able to analyze the system fairly completely and use it to investigate the properties of certain types of randomly generated trees.
