English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Tools annual

Global: Zendy Free Plan

Global: Zendy Tools monthly

Global: Zendy Plus monthly

The following problem has been considered in [3] and [1] : For n regular languages each of which is accepted by an n-state DFA, what is the number of states of a minimum DFA that accepts th e intersection of the n languages in the worst case? Birget in [1] tried to prove that the lower boun d for the above problem is nn . Unfortunately, his proof is incorrect . In the following, we first show what is wrong in Birget's proof, and then we give two proofs for the problem . The first proof i s a modification of Birget's, which shows that nn — n + 1 is a lower bound for the problem . In the second proof, we use a very different approach and show that nn is indeed the lower bound for the problem in the worst case . With the second approach, we are able to show a more general result that given an arbitrary integer k > 0 and k nonnegative integers there exist k regular languages L 1 , . . . , L k such that L 1 is accepted by an n 1 -state DFA, . . ., Lk is accepted by an nk-state DFA and any DFA accepting nl<i<k L i needs at least n l . . . nk states . This result als o answers a question raised by Birget in Remark 2 of [1] . Let N = {1, . . . , n} for some integer n > 1 . Denote the set of all binary relations on N by Bn and the set of all total functions on N by Fn . For R1 , R2 E Bn , R I • R 2 denotes the compositio n of R 1 and R2 . Birget uses the following n regular languages in his proof in [1] :

On the state complexity of intersection of regular languages