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 on the state complexity of concatenation can be met by ternary languages, the first of which is accepted by an -state DFA with final states, and the second one by an -state DFA with final states for arbitrary integers with and . In the case of , we are able to provide appropriate binary witnesses. In the case of and , 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 for the concatenation on alternating finite automata. This solves an open problem stated by Fellah [ (1990) 117–132].
Mots-clés : Regular languages, finite automata, concatenation, state complexity
@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 = {http://archive.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 - http://archive.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 http://archive.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. http://archive.numdam.org/articles/10.1051/ita/2018011/
[1] On equations for regular languages, finite automata, and sequential networks. Theoret. Comput. Sci. 10 (1980) 19–35 | DOI | MR | Zbl
and ,[2] Concatenation of regular languages and state complexity, ŠVK thesis. P. J. Šafárik University, Košice (2015)
,[3] Constructions for alternating finite automata. Int. J. Comput. Math. 35 (1990) 117–132 | DOI | Zbl
, , and ,[4] Introduction to Automata Theory, Languages and Computation. Addison-Wesley (1979) | MR | Zbl
, and ,[5] State complexity of concatenation and complementation. Int. J. Found. Comput. Sci. 16 (2005) 511–529 | DOI | MR | Zbl
, , and ,[6] State complexity of some operations on binary regular languages. Theoret. Comput. Sci. 330 (2005) 287–298 | DOI | MR | Zbl
,[7] Descriptional complexity of operations on alternating and boolean automata. In CSR 2012, edited by et al. Vol. 7353 of Lect. Notes Comput Sci. Springer (2012) 196–204 | MR | Zbl
,[8] Succinct representation of regular languages by boolean automata. Theoret. Comput. Sci. 13 (1981) 323–330 | DOI | MR | Zbl
,[9] On generalized language equations. Theoret. Comput. Sci. 14 (1981) 63–77 | DOI | MR | Zbl
,[10] Estimates of the number of states of finite automata. Soviet Math. Doklady 11 (1970) 1373–1375 | MR | Zbl
,[11] Finite automata and their decision problems. IBM Res. Develop. 3 (1959) 114–129 | DOI | MR | Zbl
and ,[12] Introduction to the theory of computation. Cengage Learning, Boston (2012)
,[13] Regular languages, Chapter 2. In vol. I of Handbook of Formal Languages, edited by and . Springer Heidelberg (1997) 41–110 | DOI | MR | Zbl
,[14] The state complexity of some basic operations on regular languages. Theoret. Comput. Sci. 125 (1994) 315–328 | DOI | MR | Zbl
, , and ,Cité par Sources :