HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation
Conference papers

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
Complete list of metadata

Cited literature [19 references]  Display  Hide  Download

https://hal.inria.fr/hal-02387295
Contributor : Hal Ifip Connect in order to contact the contributor
Submitted on : Friday, November 29, 2019 - 4:35:56 PM
Last modification on : Friday, November 29, 2019 - 5:01:50 PM

File

480958_1_En_7_Chapter.pdf
Files produced by the author(s)

Licence


Distributed under a Creative Commons Attribution 4.0 International License

Identifiers

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⟩

Share

Metrics

Record views

22

Files downloads

4