%0 Conference Proceedings
%T The Complexity of Languages Resulting from the Concatenation Operation
%+ Slovak Academy of Sciences (SAS)
%+ P.J. Safarik University
%A Jirásková, Galina
%A Szabari, Alexander
%A Šebej, Juraj
%< avec comité de lecture
%( Lecture Notes in Computer Science
%B 18th International Workshop on Descriptional Complexity of Formal Systems (DCFS)
%C Bucharest, Romania
%Y Cezar Câmpeanu
%Y Florin Manea
%Y Jeffrey Shallit
%I Springer International Publishing
%3 Descriptional Complexity of Formal Systems
%V LNCS-9777
%P 153-167
%8 2016-07-05
%D 2016
%R 10.1007/978-3-319-41114-9_12
%Z Computer Science [cs]Conference papers
%X 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.
%G English
%Z TC 1
%Z WG 1.2
%2 https://inria.hal.science/hal-01633946/document
%2 https://inria.hal.science/hal-01633946/file/416473_1_En_12_Chapter.pdf
%L hal-01633946
%U https://inria.hal.science/hal-01633946
%~ IFIP-LNCS
%~ IFIP
%~ IFIP-TC
%~ IFIP-TC1
%~ IFIP-WG
%~ IFIP-DCFS
%~ IFIP-LNCS-9777
%~ IFIP-WG1-2