Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
435988 | Theoretical Computer Science | 2015 | 16 Pages |
Abstract
We prove that the tight bound on the state complexity of the boundary of regular languages, defined as bd(L)=L⁎∩(L¯)⁎, is 3/8⋅4n+2n−2−2⋅3n−2−n+23/8⋅4n+2n−2−2⋅3n−2−n+2. Our witness languages are described over a five-letter alphabet. Next, we show that this bound cannot be met by any quaternary language if n≥5n≥5. However, the state complexity of boundary in the quaternary case is smaller by just one. Finally, we prove that the state complexity of boundary in the binary and ternary cases is Θ(4n)Θ(4n).
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Jozef Jirásek, Galina Jirásková,