%0 Conference Proceedings
%T Square, Power, Positive Closure, and Complementation on Star-Free Languages
%+ School of Computer Science [Waterloo] (UWO)
%+ Slovak Academy of Sciences (SAS)
%A Davies, Sylvie
%A Hospodár, Michal
%< avec comité de lecture
%( Lecture Notes in Computer Science
%B 21th International Conference on Descriptional Complexity of Formal Systems (DCFS)
%C Košice, Slovakia
%Y Michal Hospodár
%Y Galina Jirásková
%Y Stavros Konstantinidis
%I Springer International Publishing
%3 Descriptional Complexity of Formal Systems
%V LNCS-11612
%P 98-110
%8 2019-07-17
%D 2019
%R 10.1007/978-3-030-23247-4_7
%Z Computer Science [cs]Conference papers
%X We examine the deterministic and nondeterministic state complexity of square, power, positive closure, and complementation on star-free languages. For the state complexity of square, we get a non-trivial upper bound $$(n-1)2^n - 2(n-2)$$ and a lower bound of order $${\Theta }(2^n)$$. For the state complexity of the k-th power in the unary case, we get the tight upper bound $$k(n-1)+1$$. Next, we show that the upper bound kn on the nondeterministic state complexity of the k-th power is met by a binary star-free language, while in the unary case, we have a lower bound $$k(n-1)+1$$. For the positive closure, we show that the deterministic upper bound $$2^{n-1}+2^{n-2}-1$$, as well as the nondeterministic upper bound n, can be met by star-free languages. We also show that in the unary case, the state complexity of positive closure is $$n^2-7n+13$$, and the nondeterministic state complexity of complementation is between $$(n-1)^2+1$$ and $$n^2-2$$.
%G English
%Z TC 1
%Z WG 1.02
%2 https://inria.hal.science/hal-02387295/document
%2 https://inria.hal.science/hal-02387295/file/480958_1_En_7_Chapter.pdf
%L hal-02387295
%U https://inria.hal.science/hal-02387295
%~ IFIP-LNCS
%~ IFIP
%~ IFIP-TC
%~ IFIP-TC1
%~ IFIP-WG
%~ IFIP-DCFS
%~ IFIP-WG1-2
%~ IFIP-LNCS-11612