TY - JOUR

T1 - On the state complexity of operations on two-way finite automata

AU - Jirásková, Galina

AU - Okhotin, Alexander

N1 - Publisher Copyright: © 2016 Elsevier Inc.

PY - 2017/4/1

Y1 - 2017/4/1

N2 - The paper investigates the effect of basic language-theoretic operations on the number of states in two-way deterministic finite automata (2DFAs). If m and n are the number of states in the 2DFAs recognizing the arguments of the following operations, then their result requires the following number of states: at least m+n−o(m+n) and at most 4m+n+const for union; at least m+n−o(m+n) and at most m+n+1 for intersection; at least Ω(mn)+2Ω()log⁡m and at most 2mm+1⋅2nn+1 for concatenation; at least 1n2n2−1 and at most 2O(nn+1) for Kleene star, square and projections; between n+1 and n+2 for reversal; exactly 2n for inverse homomorphisms. All results are obtained by first establishing high lower bounds on the number of states in any 1DFAs recognizing these languages, and then using these bounds to reason about the size of any equivalent 2DFAs.

AB - The paper investigates the effect of basic language-theoretic operations on the number of states in two-way deterministic finite automata (2DFAs). If m and n are the number of states in the 2DFAs recognizing the arguments of the following operations, then their result requires the following number of states: at least m+n−o(m+n) and at most 4m+n+const for union; at least m+n−o(m+n) and at most m+n+1 for intersection; at least Ω(mn)+2Ω()log⁡m and at most 2mm+1⋅2nn+1 for concatenation; at least 1n2n2−1 and at most 2O(nn+1) for Kleene star, square and projections; between n+1 and n+2 for reversal; exactly 2n for inverse homomorphisms. All results are obtained by first establishing high lower bounds on the number of states in any 1DFAs recognizing these languages, and then using these bounds to reason about the size of any equivalent 2DFAs.

KW - Descriptional complexity

KW - State complexity

KW - Two-way automata

UR - http://www.scopus.com/inward/record.url?scp=85008450588&partnerID=8YFLogxK

U2 - 10.1016/j.ic.2016.12.007

DO - 10.1016/j.ic.2016.12.007

M3 - Article

VL - 253

SP - 36

EP - 63

JO - Information and Computation

JF - Information and Computation

SN - 0890-5401

IS - 1

ER -