An atom of a regular language $L$ with $n$ (left) quotients is a non-empty intersection of uncomple
An atom of a regular language $L$ with $n$ (left) quotients is a non-empty intersection of uncomplemented or complemented quotients of $L$, where each of the $n$ quotients appears in a term of the intersection. The quotient complexity of $L$, which is the same as the state complexity of $L$, is the number of quotients of $L$. We prove that, for any language $L$ with quotient complexity $n$, the quotient complexity of any atom of L with r complemented quotients has an upper bound of 2^n-1 if r=0 or r=n, and 1+\sum_{k=1}^{r} \sum_{h=k+1}^{k+n-r} C_{h}^{n} \cdot C_{k}^{h} otherwise, where C_j^i is the binomial coefficient. For each n>=1, we exhibit a language whose atoms meet these bounds.

Date and Venue

Start Date
Venue
FC M031 , Dmat-FCUP

Speaker

Janusz Brzozowski (University of Waterloo, ON, Canada)

Area

Semigroups, Automata and Languages