pith. sign in

arxiv: 1404.6632 · v3 · pith:E7NN3VPQnew · submitted 2014-04-26 · 💻 cs.FL

Complexity of Atoms, Combinatorially

classification 💻 cs.FL
keywords atomsbrzozowskiboundscomplexityintroducedlanguageregulartamm
0
0 comments X
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.