Complex Systems

Decremental Tag Systems and Random Trees Download PDF

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


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.