Decremental Tag Systems and Random Trees
Patrick Bahls, Mark McClure, Josh Knox · Complex Systems · 2009
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. 1.