# The Complexity of Languages Resulting from the Concatenation Operation

Abstract : We prove that for all m, n, and $\alpha$ with $1 \le \alpha \le f(m,n)$, where f(m, n) is the state complexity of the concatenation operation, there exist a minimal m-state DFA A and a minimal n-state DFA B, both defined over an alphabet $\varSigma$ with $|\varSigma |\le 2n+4$, such that the minimal DFA for the language L(A)L(B) has exactly $\alpha$ states. This improves a similar result in the literature that uses an exponential alphabet.
Type de document :
Communication dans un congrès
Cezar Câmpeanu; Florin Manea; Jeffrey Shallit. 18th International Workshop on Descriptional Complexity of Formal Systems (DCFS), Jul 2016, Bucharest, Romania. Springer International Publishing, Lecture Notes in Computer Science, LNCS-9777, pp.153-167, 2016, Descriptional Complexity of Formal Systems. 〈10.1007/978-3-319-41114-9_12〉
Domaine :

Littérature citée [16 références]

https://hal.inria.fr/hal-01633946
Contributeur : Hal Ifip <>
Soumis le : lundi 13 novembre 2017 - 15:32:24
Dernière modification le : lundi 13 novembre 2017 - 15:35:37
Document(s) archivé(s) le : mercredi 14 février 2018 - 15:44:47

### Fichier

416473_1_En_12_Chapter.pdf
Fichiers produits par l'(les) auteur(s)

### Citation

Galina Jirásková, Alexander Szabari, Juraj Šebej. The Complexity of Languages Resulting from the Concatenation Operation. Cezar Câmpeanu; Florin Manea; Jeffrey Shallit. 18th International Workshop on Descriptional Complexity of Formal Systems (DCFS), Jul 2016, Bucharest, Romania. Springer International Publishing, Lecture Notes in Computer Science, LNCS-9777, pp.153-167, 2016, Descriptional Complexity of Formal Systems. 〈10.1007/978-3-319-41114-9_12〉. 〈hal-01633946〉

### Métriques

Consultations de la notice