Bernátsky, L. 1997. Regular expression star-freeness is PSPACE-complete. Acta Cybernetica. 13, 1 (Jan. 1997), 1-21.