The complexity of concatenation on deterministic and alternating finite automata

Hospodár, Michal¹  ; Jirásková, Galina¹ 

¹

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 52 (2018) no. 2-3-4, pp. 153-168

Résumé

We study the state complexity of the concatenation operation on regular languages represented by deterministic and alternating finite automata. For deterministic automata, we show that the upper bound $m{2}^n-k{2}^{n-1}$ on the state complexity of concatenation can be met by ternary languages, the first of which is accepted by an $m$-state DFA with $k$ final states, and the second one by an $n$-state DFA with $\ell$ final states for arbitrary integers $m,n,k,\ell$ with $1\le k\le m-1$ and $1\le \ell \le n-1$. In the case of $k\le m-2$, we are able to provide appropriate binary witnesses. In the case of $k=m-1$ and $\ell \ge 2$, we provide a lower bound which is smaller than the upper bound just by one. We use our binary witnesses for concatenation on deterministic automata to describe binary languages meeting the upper bound $2^m+n+1$ for the concatenation on alternating finite automata. This solves an open problem stated by Fellah $\mathrm{𝑒𝑡}\mathrm{𝑎𝑙}.$ [$\mathrm{𝐼𝑛𝑡}.𝐽.\mathrm{𝐶𝑜𝑚𝑝𝑢𝑡}.\mathrm{𝑀𝑎𝑡ℎ}.$ $\mathbf{35}$ (1990) 117–132].

Détail

DOI : 10.1051/ita/2018011

Classification : 68Q19, 68Q45
Keywords: Regular languages, finite automata, concatenation, state complexity