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 <>
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

Please log in to resquest access to the document

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

51