Complexity of atoms, combinatorially

• Atoms of a regular language were introduced by Brzozowski and Tamm in 2011.
• Brzozowski and Davies characterized the “most complex” languages, having the most possible and most complex atoms.
• We give an alternative proof of their characterization, applying a different approach.

Atoms of a (regular) language L were introduced by Brzozowski and Tamm in 2011 as intersections of complemented and uncomplemented quotients of L. They derived tight upper bounds on the complexity of atoms in 2012. In 2014, Brzozowski and Davies characterized the regular languages meeting these bounds. To achieve these results, they used the so-called “átomaton” of a language, introduced by Brzozowski and Tamm in 2011.In this note we give an alternative proof of their characterization, via a purely combinatorial approach.