Complexity of Atoms, Combinatorially
classification
💻 cs.FL
keywords
atomsbrzozowskiboundscomplexityintroducedlanguageregulartamm
read the original abstract
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 2013. In 2014, Brzozowski and Davies characterized the regular languages meeting these bounds. To achieve these results, they used the so-called "atomaton" 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.
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.