Some notes on an idea for defining better computational complexity for finite languages, using regular languages: here.
Edit: Something I didn’t justify very well is why I called this computational complexity; it might be more appropriately called description complexity. But because regular expressions admit efficient evaluation roughly corresponding to their size, description complexity of the minimum regex can be taken as a proxy for the minimum computational resources required, if we restrict computation to that which is expressible using regular languages.
Edited on .