The Complexity of Languages Resulting from the Concatenation Operation - Descriptional Complexity of Formal Systems (DCFS 2016) Access content directly
Conference Papers Year : 2016

The Complexity of Languages Resulting from the Concatenation Operation

Galina Jirásková
  • Function : Author
  • PersonId : 1011781
Alexander Szabari
  • Function : Author
  • PersonId : 1022720
Juraj Šebej
  • Function : Author
  • PersonId : 1022721

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.
Fichier principal
Vignette du fichier
416473_1_En_12_Chapter.pdf (118.43 Ko) Télécharger le fichier
Origin : Files produced by the author(s)
Loading...

Dates and versions

hal-01633946 , version 1 (13-11-2017)

Licence

Attribution

Identifiers

Cite

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⟩
56 View
103 Download

Altmetric

Share

Gmail Facebook X LinkedIn More