We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
The complexity of concatenation on deterministic and alternating finite automata.
- Authors
Bordihn, Henning; Nagy, Benedek; Vaszil, György; Hospodár, Michal; Jirásková, Galina
- 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 m2n − k2n−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 ≤ 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 2m + 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].
- Subjects
FINITE state machines; DETERMINISTIC finite automata; STATISTICAL matching; ARBITRARY constants; TERNARY logic
- Publication
RAIRO - Theoretical Informatics & Applications, 2018, Vol 52, Issue 2-4, p153
- ISSN
2804-7346
- Publication type
Article
- DOI
10.1051/ita/2018011