Automaticity and Rationality
Jeffrey O. Shallit · 2000
Automaticity is a measure of descriptional complexity for formal languages $L$, and measures how closely $L$ can be approximated by regular languages. I survey some of the known results and open problems on automaticity. I also discuss a measure which I call "rationality", and explain how it generalizes the well-known concept of linear complexity.