Skip to Main content Skip to Navigation
Conference papers

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
Complete list of metadata

Cited literature [16 references]  Display  Hide  Download

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)

Licence


Distributed under a Creative Commons Attribution 4.0 International License

Identifiers

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⟩

Share

Metrics

Record views

94

Files downloads

188