The state complexity of L² and L^k

2004/10/14 by Rampersad, Narad
#Computational Complexity (cs.CC) #F.1.1 #FOS: Computer and information sciences #Formal Languages and Automata Theory (cs.FL)

paper · doi:10.48550/arxiv.cs/0410032

Abstract

We show that if M is a DFA with n states over an arbitrary alphabet and L = L(M), then the worst-case state complexity of L² is n*2ⁿ - 2^n-1. If, however, M is a DFA over a unary alphabet, then the worst-case state complexity of L^k is kn-k+1 for all k >= 2.

Related

• The state complexity of random DFAs
• On state complexity of unions of binary factor-free languages
• State complexity of multiple catenation
• A lower bound on the state complexity of transforming two-way nondeterministic finite automata to unambiguous finite automata
• The State Complexity of Lexicographically Smallest Words and Computing\n Successors