### Unrestricted State Complexity of Binary Operations on Regular Languages

**2016-02-03**

1602.01387 | cs.FL

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$, that of difference is $mn+m$, and
that of the product is $m2^n+2^{n-1}$.

**Login to like/save this paper, take notes and configure your recommendations**

# Related Articles

**2019-03-08**

1903.03518 | cs.FL

Several insertion operations are studied applied to languages accepted by
one-way and two-way determ… show more

**2019-03-10**

1903.06114 | cs.FL

The Thue-Morse set is the set of those nonnegative integers whose binary
expansions have an even num… show more

**2017-08-21**

1708.06228 | cs.FL

Let b be an integer strictly greater than 1. Each set of nonnegative integers
is represented in base… show more

**2018-06-12**

1806.04645 | cs.FL

In a simple pattern matching problem one has a pattern $w$ and a text $t$,
which are words over a fi… show more

**2018-06-22**

1806.08476 | cs.FL

The state complexity of the result of a regular operation is often positively
correlated with the nu… show more

**2018-07-02**

1807.00663 | cs.FL

A monster is an automaton in which every function from states to states is
represented by at least o… show more

**2017-10-16**

1710.06000 | cs.FL

The \emph{state complexity} of a regular language $L_m$ is the number $m$ of
states in a minimal det… show more

**2013-01-21**

1301.4981 | cs.FL

The article defines and studies the genus of finite state deterministic
automata (FSA) and regular l… show more

**2017-03-18**

1703.06356 | cs.FL

We study extremal and algorithmic questions of subset and careful
synchronization in monotonic autom… show more

**2015-06-01**

1506.00482 | cs.LO

This work is concerned with regular languages defined over large alphabets,
either infinite or just … show more

**2016-07-01**

1607.00259 | cs.CC

The notion of Online State Complexity, introduced by Karp in 1967, quantifies
the amount of states r… show more

**2013-04-21**

1304.5714 | cs.FL

We give a forbidden pattern characterization for the class of generalized
definite languages, show t… show more

**2017-02-14**

1702.04376 | cs.FL

In a recent paper we analyzed the space complexity of streaming algorithms
whose goal is to decide m… show more

**2015-05-07**

1505.01662 | cs.FL

Hereditarily finite (HF) set theory provides a standard universe of sets, but
with no infinite sets.… show more

**2016-02-13**

1602.04294 | cs.FL

This paper introduces time window temporal logic (TWTL), a rich expressivity
language for describing… show more

**2017-03-15**

1703.05011 | cs.SY

Complexity analysis becomes a common task in supervisory control. However,
many results of interest … show more

**2017-03-15**

1703.05016 | cs.SY

The infimal prefix-closed, controllable and observable superlanguage plays an
essential role in the … show more