Several measures of the complexity of a regular expression are defined. (Star height and number of alphabetical symbols are two of them.) Upper and lower estimates for the complexities of expressions for certain sets of paths on graphs are derives.
Ehrenfeucht, Andrzej and Zeiger, Paul, "Complexity Measures for Regular Expressions ; CU-CS-066-75" (1975). Computer Science Technical Reports. 64.