# 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 mn, 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 $mn+m+n+1$, that of intersection is $mn+1$, that of difference is $mn+m+1$, and that of the product is $m2^n+2^{n-1}$.
Keywords :
Document type :
Conference papers
Domain :

Cited literature [11 references]

https://hal.inria.fr/hal-01633951
Contributor : Hal Ifip <>
Submitted on : Monday, November 13, 2017 - 3:32:40 PM
Last modification on : Monday, November 13, 2017 - 3:35:35 PM
Long-term archiving on: : Wednesday, February 14, 2018 - 4:02:41 PM

### File

416473_1_En_5_Chapter.pdf
Files produced by the author(s)

### Citation

Janusz Brzozowski. Unrestricted State Complexity of Binary Operations on Regular Languages. 18th International Workshop on Descriptional Complexity of Formal Systems (DCFS), Jul 2016, Bucharest, Romania. pp.60-72, ⟨10.1007/978-3-319-41114-9_5⟩. ⟨hal-01633951⟩

Record views