# Square, Power, Positive Closure, and Complementation on Star-Free Languages

Abstract : 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$.
Document type :
Conference papers
Domain :

Cited literature [19 references]

https://hal.inria.fr/hal-02387295
Contributor : Hal Ifip <>
Submitted on : Friday, November 29, 2019 - 4:35:56 PM
Last modification on : Friday, November 29, 2019 - 5:01:50 PM

### File

##### Restricted access
To satisfy the distribution rights of the publisher, the document is embargoed until : 2022-01-01

### Citation

Sylvie Davies, Michal Hospodár. Square, Power, Positive Closure, and Complementation on Star-Free Languages. 21th International Conference on Descriptional Complexity of Formal Systems (DCFS), Jul 2019, Košice, Slovakia. pp.98-110, ⟨10.1007/978-3-030-23247-4_7⟩. ⟨hal-02387295⟩

Record views