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.

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].

Classification : 68Q19, 68Q45
Mots clés : Regular languages, finite automata, concatenation, state complexity

[1] J. Brzozowski and E. Leiss, On equations for regular languages, finite automata, and sequential networks. Theoret. Comput. Sci. 10 (1980) 19–35 | DOI | MR | Zbl

[2] E. Dorčák, Concatenation of regular languages and state complexity, ŠVK thesis. P. J. Šafárik University, Košice (2015)

[3] A. Fellah, H. Jürgensen, and S. Yu, Constructions for alternating finite automata. Int. J. Comput. Math. 35 (1990) 117–132 | DOI | Zbl

[4] J.E. Hopcroft, and J.D. Ullman, Introduction to Automata Theory, Languages and Computation. Addison-Wesley (1979) | MR | Zbl

[5] J. Jirásek, G. Jirásková, and A. Szabari, State complexity of concatenation and complementation. Int. J. Found. Comput. Sci. 16 (2005) 511–529 | DOI | MR | Zbl

[6] G. Jirásková, State complexity of some operations on binary regular languages. Theoret. Comput. Sci. 330 (2005) 287–298 | DOI | MR | Zbl

[7] G. Jirásková, Descriptional complexity of operations on alternating and boolean automata. In CSR 2012, edited by E. Hirsch et al. Vol. 7353 of Lect. Notes Comput Sci. Springer (2012) 196–204 | MR | Zbl

[8] E. Leiss, Succinct representation of regular languages by boolean automata. Theoret. Comput. Sci. 13 (1981) 323–330 | DOI | MR | Zbl

[9] E. Leiss, On generalized language equations. Theoret. Comput. Sci. 14 (1981) 63–77 | DOI | MR | Zbl

[10] A.N. Maslov, Estimates of the number of states of finite automata. Soviet Math. Doklady 11 (1970) 1373–1375 | MR | Zbl

[11] M. Rabin and D. Scott, Finite automata and their decision problems. IBM Res. Develop. 3 (1959) 114–129 | DOI | MR | Zbl

[12] M. Sipser, Introduction to the theory of computation. Cengage Learning, Boston (2012)

[13] S. Yu, Regular languages, Chapter 2. In vol. I of Handbook of Formal Languages, edited by G. Rozenberg and A. Salomaa. Springer Heidelberg (1997) 41–110 | DOI | MR | Zbl

[14] S. Yu, Q. Zhuang, and K. Salomaa, The state complexity of some basic operations on regular languages. Theoret. Comput. Sci. 125 (1994) 315–328 | DOI | MR | Zbl