Descriptional Complexity of Machines with Limited Resources.

Abstract

Over the last 30 years or so many results have appeared on the descriptional complexity of machines with limited resources. Since these results have appeared in a variety of different contexts, o rgo4 here is to pro vide a survey o these results. Particular emphasis is put o limiting reso rces (e.g., no ndeterminism, ambiguity,lo o ahead, etc.) fo vario s types o finite state machines, pushdo wn auto mata, parsers and cellular auto mata ando n the e#ect it haso n their descriptio nal co mplexity. We also address the questio no f how descriptional complexity might help in the future to solve practical issues, such as software reliability.