Quotient Complexities of Atoms of Regular Languages

FC M031 , Dmat-FCUP
Monday, 8 October, 2012 - 13:30

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.

Speaker: 

Janusz Brzozowski (University of Waterloo, ON, Canada)
Error | CMUP

Error

The website encountered an unexpected error. Please try again later.