Unrestricted state complexity of binary operations on regular languages

Abstract: I study the state complexity of binary operations on regular languages over different alphabets. It is well known that if

L'_{m}

and

L_{n}

are languages restricted to be over the same alphabet, with

m

and

n

quotients, respectively, the state complexity of any binary boolean operation on

L'_{m}

and

L_{n}

is

m n

, and that of the product (concatenation) is

(m - 1) 2^{n} + 2^{n - 1}

. In contrast to this, I show that if

L'_{m}

and

L_{n}

are over their own different alphabets, the state complexity of union and symmetric difference is

m n + m + n + 1

, that of intersection is

m n

, that of difference is

m n + m

, and that of the product is

m 2^{n} + 2^{n - 1}

.

Recommendations

Cites work

Cited in

(8)

This page was built for publication: Unrestricted state complexity of binary operations on regular languages