The complexity of concatenation on deterministic and alternating finite automata

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

doi:10.1051/ita/2018011

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 $ℓ$ final states for arbitrary integers $m, n, k, ℓ$ with $1 \leq k \leq m - 1$ and $1 \leq ℓ \leq n - 1$ . In the case of $k \leq m - 2$ , we are able to provide appropriate binary witnesses. In the case of $k = m - 1$ and $ℓ \geq 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 $𝑒𝑡 𝑎𝑙 .$ [ $𝐼𝑛𝑡 . 𝐽 . 𝐶𝑜𝑚𝑝𝑢𝑡 . 𝑀𝑎𝑡ℎ .$ $35$ (1990) 117–132].

MR Zbl

DOI : 10.1051/ita/2018011

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

Affiliations des auteurs :

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

@article{ITA_2018__52_2-3-4_153_0,
     author = {Hospod\'ar, Michal and Jir\'askov\'a, Galina},
     title = {The complexity of concatenation on deterministic and alternating finite automata},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     pages = {153--168},
     publisher = {EDP-Sciences},
     volume = {52},
     number = {2-3-4},
     year = {2018},
     doi = {10.1051/ita/2018011},
     mrnumber = {3915306},
     zbl = {1486.68096},
     language = {en},
     url = {https://www.numdam.org/articles/10.1051/ita/2018011/}
}

TY  - JOUR
AU  - Hospodár, Michal
AU  - Jirásková, Galina
TI  - The complexity of concatenation on deterministic and alternating finite automata
JO  - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY  - 2018
SP  - 153
EP  - 168
VL  - 52
IS  - 2-3-4
PB  - EDP-Sciences
UR  - https://www.numdam.org/articles/10.1051/ita/2018011/
DO  - 10.1051/ita/2018011
LA  - en
ID  - ITA_2018__52_2-3-4_153_0
ER  -

%0 Journal Article
%A Hospodár, Michal
%A Jirásková, Galina
%T The complexity of concatenation on deterministic and alternating finite automata
%J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
%D 2018
%P 153-168
%V 52
%N 2-3-4
%I EDP-Sciences
%U https://www.numdam.org/articles/10.1051/ita/2018011/
%R 10.1051/ita/2018011
%G en
%F ITA_2018__52_2-3-4_153_0

Hospodár, Michal; Jirásková, Galina. The complexity of concatenation on deterministic and alternating finite automata. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 52 (2018) no. 2-3-4, pp. 153-168. doi : 10.1051/ita/2018011. https://www.numdam.org/articles/10.1051/ita/2018011/

Bibliographie
Cité par

[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

Cité par Sources :