Regular Article

The complexity of concatenation on deterministic and alternating finite automata^★

Mathematical Institute, Slovak Academy of Sciences, Grešákova 6, 040 01 Košice, Slovakia.

^* Corresponding author: hosmich@gmail.com

Received: 21 November 2018

Abstract

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 m2ⁿ − k2ⁿ⁻¹ 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 ≤ k ≤ m − 1 and 1 ≤ ℓ ≤ n − 1. In the case of k ≤ m − 2, we are able to provide appropriate binary witnesses. In the case of k = m − 1 and ℓ ≥ 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 et al. [Int. J. Comput. Math. 35 (1990) 117–132].