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.
Document type :
Conference papers
Domain :

Cited literature [16 references]

https://hal.inria.fr/hal-01633946
Contributor : Hal Ifip <>
Submitted on : Monday, November 13, 2017 - 3:32:24 PM
Last modification on : Monday, November 13, 2017 - 3:35:37 PM
Long-term archiving on: : Wednesday, February 14, 2018 - 3:44:47 PM

File

416473_1_En_12_Chapter.pdf
Files produced by the author(s)

Citation

Galina Jirásková, Alexander Szabari, Juraj Šebej. The Complexity of Languages Resulting from the Concatenation Operation. 18th International Workshop on Descriptional Complexity of Formal Systems (DCFS), Jul 2016, Bucharest, Romania. pp.153-167, ⟨10.1007/978-3-319-41114-9_12⟩. ⟨hal-01633946⟩

Record views