Janusz Brzozowski and Yuli Ye

**Abstract.** The state complexity of a regular language is the number of states in the minimal deterministic automaton accepting the language. The syntactic complexity of a regular language is the cardinality of its syntactic semigroup. The syntactic complexity of a subclass of regular languages is the worst-case syntactic complexity taken as a function of the state complexity *n* of languages in that class. We prove that *n*^{n − 1} is a tight upper bound on the complexity of right ideals and prefix-closed languages, and that there exist left ideals and suffix-closed languages of syntactic complexity *n*^{n − 1} + *n* − 1, and two-sided ideals and factor-closed languages of syntactic complexity *n*^{n − 2} + (*n* − 2) 2^{n − 2} + 1.