The Complexity of Languages Resulting from the Concatenation Operation
| Autor: | Alexander Szabari, Galina Jirásková, Juraj Šebej |
|---|---|
| Jazyk: | angličtina |
| Rok vydání: | 2017 |
| Předmět: |
Concatenation
0102 computer and information sciences 02 engineering and technology 01 natural sciences Exponential function Combinatorics Alpha (programming language) State complexity 010201 computation theory & mathematics 0202 electrical engineering electronic engineering information engineering 020201 artificial intelligence & image processing Alphabet Algorithm Computer Science::Formal Languages and Automata Theory Mathematics |
| Zdroj: | Descriptional Complexity of Formal Systems ISBN: 9783319411132 DCFS |
| DOI: | 10.25596/jalc-2017-123 |
| Popis: | 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 deterministic finite automaton $A$ and a minimal $n$-state deterministic finite automaton $B$, both defined over an alphabet $\Sigma$ with $|\Sigma|\le 2n+4$, such that the minimal deterministic finite automaton for the language $L(A)L(B)$ has exactly $\alpha$ states. This improves a similar result in the literature that uses an exponential alphabet. Journal of Automata, Languages and Combinatorics, Volume 22, Numbers 1-3, 2017, 123-143 |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|