The state complexity of L^2 and L^k
| dc.creator | Rampersad, Narad | |
| dc.date | 2004-10-14 | |
| dc.date | 2005-05-12 | |
| dc.date.accessioned | 2026-07-07T12:57:19Z | |
| dc.date.available | 2026-07-07T12:57:19Z | |
| dc.description | 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^2 is n*2^n - 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. | |
| dc.description | 5 pages, 1 figure; some errors corrected | |
| dc.identifier | https://arxiv.org/abs/cs/0410032 | |
| dc.identifier | http://arxiv.org/abs/cs/0410032 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/224890 | |
| dc.subject | Computational Complexity | |
| dc.subject | Formal Languages and Automata Theory | |
| dc.subject | F.1.1 | |
| dc.title | The state complexity of L^2 and L^k | |
| dc.type | text |