%\documentclass{llncs}
\documentclass[11pt]{llncs}


%\documentclass[twoside,a4paper,11pt]{article}
\textheight 22cm
\textwidth 14cm
\topmargin -0.5cm
\oddsidemargin 1cm
\evensidemargin 1cm 


\usepackage{amssymb}
\usepackage{latexsym}
%%\usepackage{pictexwd}
%\usepackage{cite}
\input epsf
\epsfverbosetrue

\begin{document}
\pagestyle{plain}
\mainmatter 

\title{State Complexity of Union and Intersection} 
%of Regular Languages}
% and Their State Complexity}
\author{\ }
%\author{Marek Hricko\inst{1}
%\and Galina Jir\'askov\'a\inst{2}%
%\thanks{Research  supported by the VEGA grant No. 2/3164/23.}
%\and Alexander Szabari\inst{1,2}}
%
\institute{\ }
%\institute{Institute of Computer Science, P.J. \v Saf\'arik University, Jesenn\'a 5, 040 01 Ko\v sice, Slovakia \\
%\email{hricko@zoznam.sk, szabari@science.upjs.sk}
%\and Mathematical Institute, Slovak Academy of Sciences,
%Gre\v s\'akova 6, 040 01 Ko\v sice, Slovakia \\
%\email{jiraskov@saske.sk}}
%

\maketitle 

\begin{abstract}
\label{abst}
We investigate 
the state complexity and the nondeterministic state complexity of union and intersection of regular languages. 
%In both of deteministic and nodeterministic cases we show
We show that  the entire range of complexities (nondeterministic complexities, respectively) of  languages resulting from these operations, up to the known upper bounds, can be produced. We prove the results on the state complexity and the nondeterministic state complexity of union for a binary alphabet and the result on nondeterministic state complexity of intersection for a ternary alphabet.

\end{abstract}



\section{Introduction} \label{intro}
Regular languages and finite automata are among the oldest topics in computer science. Many of their properties have been extensively studied since the forties. In recent years, a renewed interest for researchers in automata theory can be observed; for a discussion, the reader may refer to \cite{hr02,yu00}. Some aspects of this area are now intensively and deeply investigated. One such aspect is the state complexity of regular languages and their operations.


The state complexity of a regular language is the number of states of its minimal deterministic finite automaton (DFA).
The nondeterministic state complexity of a regular language is the number of states of a~minimum state nondeterministic finite automaton (NFA) accepting the language.
The state complexity (the nondeterministic state complexity) of an operation on regular languages represented by DFAs (NFAs, respectively) is the number of states that are sufficient and necessary in the worst case for  a~DFA (an NFA, respectively) to accept the language resulting from the operation.

Some early results on the state complexity of regular languages  can be found in \cite{lu63,ly64,mo71}. 
The state complexity of some  operations on regular  languages was investigated in \cite{le81,bi92,bi93}. In \cite{ma70}, binary regular languages reaching the upper bounds on the union, concatenation and the star operation were presented.
The first systematic study of the complexity of regular language operations was published by Yu, Zhuang, and Salomaa \cite{yzs94}.
The state complexity of finite language operations and unary language operations was investigated in \cite{cam01,pi02}.
The nondeterministic state complexity of regular language operations was studied by Holzer and Kutrib in \cite{hk03}.
Further results on this topic are presented in \cite{do01,cam02,el02,ji05,sa04} and state-of-the-art surveys for DFAs can be found in \cite{yu01,yu02}.

In this paper, we investigate the state complexity and the nondeterministic state complexity of union and intersection of regular languages. We treat the question of how many states may the minimal DFA accepting the union or intersection of an $ m $-state DFA language and an $ n $-state DFA language have.  We deal with the same question  for nondeterministic state complexity of these two operations. Our results are as follows. The state complexity of the union or intersection of an $ m $-state DFA language and an $ n $-state DFA language may be arbitrary between $ 1 $ and $ mn. $ The nondeterministic state complexity of the union  of an $ m $-state DFA language and an $ n $-state DFA language may be arbitrary between $ 1 $ and $ m+n+1. $ The nondeterministic state complexity of the intersection  of an $ m $-state DFA language and an $ n $-state DFA language may be arbitrary between $ 1 $ and $ mn. $ We prove the results on the state complexity and the nondeterministic state complexity of union for a binary alphabet and the result on the nondeterministic state complexity of  intersection for a ternary alphabet. To prove the results in the nondeterministic case  we use
a~fooling-set lower-bound technique known from  communication complexity theory \cite{hr97}, cf. also \cite{bi92,bi93,gs96}.

The paper consists of six sections, including this introduction.
The next section contains basic definitions and notations used throughout the paper.
In Section~\ref{state},  we present our results on the
state complexity of union and intersection. Section~\ref{union-nondet} deals with the nondeterministic state complexity of union of regular languages. Section~\ref{intersec-nondet} is devoted to the nondeterministic state complexity of intersection of regular languages.
The last section contains concluding  remarks and open problems.


\section{Preliminaries}
\label{prelim}
In this section, we recall some basic definitions and notations.
For further details, the reader may refer to \cite{si97,yu97}.

Let $\Sigma $ be an alphabet and $\Sigma ^{*}$ the set of all strings over the alphabet $\Sigma $ including the empty string $\varepsilon.$ The length of a string $ w$ is denoted by $ |w|. $ 
%and the number of occurrences of a symbol $ a $ in a string $ w $ by $ \#_a (w). $
The power-set of a~finite set $A$ is denoted by~$2^{A}.$ 

A \textit{deterministic finite automaton} (DFA) is a~5-tuple
$ M=(Q,\Sigma ,\delta ,q_{0},F) $, where
$ Q $ is a~finite  set of states,
$ \Sigma $ is a~finite input alphabet,
$ \delta : Q \times \Sigma \rightarrow Q$ is the transition function,
$ q_0 \in Q $ is the initial state,  and
$ F\subseteq Q $ is the set of accepting states.
In this paper, all DFAs are assumed to be complete, i.e., the next state $ \delta(q,a) $ is defined for any state $ q $ in $ Q $ and any symbol $ a $ in $ \Sigma. $
The transition function $ \delta $ can be naturally extended to a~function from  $Q\times \Sigma ^{*}$ to $ Q . $ 
A~string $w$ in $\Sigma ^{*}$ is accepted by the DFA $M$ if the state $ \delta(q_{0},w)$ is an accepting state of the DFA $M$.

A \textit{nondeterministic finite automaton} (NFA) is a~5-tuple
$ M=(Q,\Sigma ,\delta ,q_{0},F) $, where
$Q,\Sigma,q_{0},$ and $F$ are defined as for a DFA, and
$ \delta : Q \times \Sigma \rightarrow 2^{Q}$ is the transition function which can be  extended to the domain $Q\times \Sigma ^{*}.$
A~string $w$ in $\Sigma ^{*}$ is accepted by the NFA $M$ if the set $\delta(q_{0},w)$ contains an accepting state of the NFA $ M. $ 

The \textit{language accepted by}  a~finite automaton $ M, $  denoted $ L(M), $ is the set of all strings accepted by the automaton $M$.
Two automata are said to be \textit{equivalent} if they accept the same language.

A DFA (an NFA) $ M $ is called \textit{minimal} if all DFAs (all NFAs, respectively) that are equivalent to $M$ have at least as many states as  $M.$
By a~well-known result, each regular language has  a~unique minimal DFA, up to isomorphism. However, the same result does not hold for minimal NFAs.  
It is also known \cite{rs59} that a~DFA $M=(Q,\Sigma ,\delta ,q_{0},F)$ is minimal
if (\textit{i}) all its states are reachable from the initial state $q_{0}$
and (\textit{ii}) no two of its states are equivalent (two states $p\textrm{ and }q$
are said to be \textit{equivalent} if for all $w\in \Sigma ^{*},$ $\delta (p,w)\in F\textrm{ }$
iff $\textrm{ }\delta (q,w)\in F$).

\section{Union and Intersection and Their State Complexity}
\label{state}

We start our investigations with the state complexity of the union and intersection of regular languages. It is known \cite{ma70,yzs94} that the union of an $ m $-state  DFA language and an $ n $-state DFA language can be accepted by an $ mn $-state DFA. This upper bound can be reached by the union of two binary languages \cite{ma70}. The same result for intersection follows from de Morgan's law and the fact that the state complexity of a regular language equals the state complexity of its complement. 

In this section, we show that for any integers $ m,n,\alpha $ such that
$ m\geqslant  2, n\geqslant  2, $ and
 $ 1\leqslant  \alpha \leqslant  mn,$ there exist an $ m $-state DFA language and an $ n $-state DFA language such that the minimal DFA for the union of these languages has exactly $ \alpha $ states. The same result for intersection then follows immediately. In the case of $ m=1, $ the language accepted by a $ 1 $-state DFA is either empty or equals $ \Sigma^*, $ and so we get the following result.

\begin{proposition}
\label{prop}
For any positive integer $ n, $ the state complexity of the union of a~$ 1 $-state DFA language and an $ n $-state DFA language may be either 1 or $ n. $
\end{proposition}

In the following two lemmata, we assume $ m\leqslant  n. $ The first lemma shows that all values of $ \alpha $ between $ 1 $ and $ m $ can be reached by the union of an $m$-state DFA language and an $ n $-state DFA language. The second lemma shows the same result for the values between $ m+1  $ and $m+n-2.$ To prove the results we use a unary alphabet in Lemma~\ref{l:sc:1..m} and a binary alphabet in Lemma~\ref{l:sc:m+1..m+n-2}.

\begin{lemma} \label{l:sc:1..m}
For any integers $m,n,\alpha$ such that $1\leqslant \alpha \leqslant m \leqslant n$, there exist a minimal DFA $A$ of $m$ states and 
a minimal DFA $B$ of $n$ states such that the minimal DFA for the language $L(A)\cup L(B)$ has $\alpha$ states.
\end{lemma}
%\newpage
\begin{proof}
Let $m,n,$ and $\alpha$ be arbitrary but fixed integers with 
$1\leqslant \alpha \leqslant m \leqslant n$. Let $\Sigma=\{a\}$.
%Define an $ m $- state DFA  $A=(Q_A,\Sigma,\delta_A,q_0,F_A,)$, where $Q_A=\{q_0,q_1,\dots,q_{m-1}\},$ $F_A=\{q_{m-1}\}$ and for any $ i\in \{ 0,1,\ldots,m-1 \}, $
%\[
%\delta(q_i,a)=\left\{  \begin{array}{ll}
%q_{i+1},  & \textrm{if $i<m-1,$} \\
%q_{m-1},  & \textrm{if $i=m-1.$} 
%\end{array} \right.
%\]
Let $ A=( \{q_0,q_1,\dots,q_{m-1}\},\Sigma,\delta_A,q_0,\{q_{m-1}\}),$ where $\delta(q_i,a)=q_{i+1}$ for $i=0,1,\ldots, n-2 ,$ and $ \delta(q_{m-1},a)=q_{m-1}.$ 
The DFA $ A $ accepts 
% be the minimal  DFA  for 
the language 
$\{a^i \mid i\geqslant  m-1  \} $ 
%shown in Fig.~\ref{f1}.  
%The DFA $ A $ is indeed minimal 
%since no two its different states are equivalent: if $ 0\le i < j \le m-1, $  then the string $ a^{m-1-j} $ distinguishes states $ q_i $ and $ q_j. $
%%since the states $ q_i $ and $ q^j $ with $ i<j $ are distinguished by 
%(the the string $ a^{m-1-j}$ 
%distinguishes states $ q_i $ and $ q_j $ with $ i<j). $
%%$it does not contain equivalent states.
%The DFA $ A, $ 
% accepts the language $ L(A)=\{a^i \mid i\ge m-1  \} $ and
%is shown  in Fig.~\ref{f1}. This automaton is minimal 
% since it does not contain equivalent states.
and is minimal 
 since it does not contain equivalent states.
%\begin{figure}[htbp]
%\begin{center}
% \epsfxsize300pt
%\ \epsfbox{f1.eps} 
%\caption{The deterministic finite automaton $ A. $} 
%\label{f1}
%\end{center}
%\end{figure}
%
%\noindent
In the case of $ \alpha=m=n, $ we set $ B=A $ and then the lemma follows.
Otherwise, 
%define an $ n $-state DFA $B=(Q_B,\Sigma,\delta_B,p_0,F_B)$, where $Q_B=\{p_0,p_1,\dots,p_{n-1}\}$,
%$F_B=\{p_{\alpha-1},\dots,p_{n-2}\}$ and for any $ i\in \{ 0,1,\ldots,n-1 \}, $
%\[
%\delta(p_i,a)=\left\{  \begin{array}{ll}
%p_{i+1},  & \textrm{if $i<m-1,$} \\
%p_{m-1},  & \textrm{if $i=m-1.$} 
%\end{array} \right.
%\]
let $ B=(\{p_0,p_1,\dots,p_{n-1}\},\Sigma,\delta_B,p_0,
\{p_{\alpha-1},p_{\alpha},\dots,p_{n-2}\} ),$
where 
$ \delta_B(p_i,a)=p_{i+1} $ for $ i=0,1,\ldots, n-2, $ and 
$\delta_B(p_{n-1},a)=p_{n-1}.$ The DFA $ B $ is the minimal DFA for   the language
 %be the minimal DFA for the language
$ \{a^i \mid \alpha -1 \leqslant  i\leqslant  n-2  \}. $ 
% shown in Fig.~\ref{f2} 
%(note that no two different states of the DFA $ B $ are equivalent).
%The DFA $ B $ is minimal since no two its different states are equivalent. 
%DFA for the language $ L(B)=\{a^i \mid \alpha -1 \le i\le n-2  \} $ and is shown in Fig.~\ref{f2}.
%\begin{figure}[htbp]
%\begin{center}
% \epsfxsize350pt
%\ \epsfbox{f2.eps} 
%\caption{The deterministic finite automaton $ B. $} 
%\label{f2}
%\end{center}
%\end{figure}
%
%\noindent
The union of the languages accepted by the DFA $ A $ and $ B $ is the language
$L(A) \cup L(B) =\{ a^i \mid i \geqslant  \alpha -1\}.$
The minimal DFA for this language has $ \alpha $ states.
\qed
\end{proof}




\begin{lemma} \label{l:sc:m+1..m+n-2}
For any integers $m,n,\alpha$ such that $2\leqslant  m\leqslant  n$ and $m+1\leqslant  \alpha \leqslant  m+n-2,$ there exist a minimal  DFA $A$ of $m$ states and a minimal  DFA $B$ of  $n$ states such that the minimal DFA for the language $L(A) \cup L(B)$ has $\alpha$ states.
\end{lemma}

\begin{proof}
Let $m,n,$ and $\alpha$ be arbitrary but fixed integers such that
$2\leqslant  m\leqslant  n$ and $m+1\leqslant  \alpha \leqslant  m+n-2.$ Then $\alpha$ can be expressed as
$\alpha=m+k,$ where $1\leqslant  k \leqslant  n-2.$ Let $\Sigma=\{a,b\}.$

%Define an $n$-state DFA $B=(Q_B,\Sigma,\delta_B,p_0,F_B)$, where
%$Q_B=\{p_0,p_1,\ldots,p_{n-1},\}$
%$F_B=\{p_k,p_{n-2}\},$
%and for any $i\in \{0,1,\ldots,n-1\}$ and any $X\in \Sigma,$
%
%\[
%\delta_B(p_i,X)=\left\{  \begin{array}{ll}
%p_{k+1},         & \textrm{if $i=0$ and $X=a,$}\\
%p_{i+1},         & \textrm{if $k+1\le i\le n-2$ and $X=a,$}\\
%p_{i+1},         & \textrm{if $0\le i\le k-1$ and $X=b,$}\\
%p_k,             & \textrm{if $i=k$ and $X=b,$}\\   
%p_{n-1},         & \textrm{otherwise.}
%\end{array} \right.
%\]
%
Let
$ B $ be the minimal $ n $-state DFA over  $ \Sigma $ for
%$=(\{p_0,p_1,\ldots,p_{n-1},\},\Sigma,\delta_B,p_0,\{p_k,p_{n-2}\}   ) $ be the minimal DFA for
the language $\{b^i \mid i\geqslant  k\} \cup \{a^{n-k-2}\}.$ 
%shown in Fig.~\ref{f3} (here, all nondefined transitions go to dead state $ p_{n-1}). $
%% The DFA $ B $ is minimal since no two its different states are equivalent.
%The NFA $B$ accepts the language $\{b^i \mid i\ge k\} \cup \{a^{n-k-2}\}$ and is shown in Fig.??? It is the minimal DFA for this language since no two of its states are equivalent.
%
%\begin{figure}[htbp]
%\begin{center}
% \epsfxsize300pt
%\ \epsfbox{f3.eps} 
%\caption{The minimal DFA $ B $ for the language $\{b^i \mid i\ge k\} \cup \{a^{n-k-2}\}.$ } 
%\label{f3}
%\end{center}
%\end{figure}
%
%\begin{figure}[htbp]
%\begin{center}
% \epsfxsize220pt
%\ \epsfbox{f3a.eps} 
%\caption{The DFA $ B ;$ nondefined transitions go to dead state $ p_{n-1}. $}
%\label{f3}
%\end{center}
%\end{figure}
%
To define the DFA $A$ we will consider two cases:

\begin{enumerate}
\item[(i)]
$m\leqslant  n-k.$ Let $ A$
%=(\{q_0,q_1,\ldots,q_{m-1},\},\Sigma,\delta_A,q_0,\{q_{m-2}\}) $ 
be the minimal $ m $-state DFA  over the alphabet $ \Sigma $ for the language $ \{a^i \mid i\geqslant  m-2\}.$ 
%shown in Fig.~\ref{f5}~(left); here, all nondefined transitions go to dead state $ q_{m-1}. $ 
Since $m\leqslant  n-k,$  the union of the languages accepted by the DFA $A$ and $B$ is the languauge
$L(A) \cup L(B) = \{a^i \mid i\geqslant  m-2\} \cup \{b^i \mid i\geqslant  k\}.$
The minimal DFA 
 for this language has $m+k$ states. 
%and is shown in Fig.~\ref{f5} (right).

%Then define an $m$ state DFA $A=(Q_A,\Sigma,\delta_A,q_0,F_A)$, where
%$Q_A=\{q_0,q_1,\ldots,q_{m-1},\}$
%$F_A=\{q_{m-2}\},$
%and for any $i\in \{0,1,\ldots,m-1\}$ and any $X\in \Sigma,$
%
%
%\[
%\delta_A(q_i,X)=\left\{  \begin{array}{ll}
%q_{i+1},       & \textrm{if $i\le m-3$ and $X=a$,}\\
%q_{m-2},       & \textrm{if $i=m-2$ and $X=a,$}\\
%q_{m-1},       & \textrm{otherwise.}
%\end{array} \right.
%\]
%
%The DFA $A$ accepts the language $ \{a^i \mid i\ge m-2\}$ and is shown in Fig.~\ref{f4}. 
%
%\begin{figure}[htbp]
%\begin{center}
% \epsfxsize400pt
%\ \epsfbox{f5a.eps} 
%\caption{The  DFA $ A $ and $ C;$ nondefined transitions go to dead states $ q_{m-1} $ and  $ r_{m-1}.$}
%\label{f5}
%\end{center}
%\end{figure}
%
%It is the minimal DFA for this language since no two of its states are equivalent.




\item[(ii)]
$m > n-k.$ 
%Then define an $m$ state DFA $A=(Q_A,\Sigma,\delta_A,q_0,F_A)$, where
%$Q_A=\{q_0,q_1,\ldots,q_{m-1},\}$
%$F_A=\{q_{m-2}\},$
%and for any $i\in \{0,1,\ldots,m-1\}$ and any $X\in \Sigma,$
%
%
%\[
%\delta_A(q_i,X)=\left\{  \begin{array}{ll}
%q_{i+1},       & \textrm{if $i\le m-2$ and $X=a$,}\\
%%q_{m-2},       & \textrm{if $i=m-2$ and $X=a,$}\\
%q_{m-1},       & \textrm{otherwise.}
%\end{array} \right.
%\]
Let $ A$
%'=(\{q_0,q_1,\ldots,q_{m-1}\},\Sigma,\delta_A,q_0,\{q_{m-2}\} )$ 
be the minimal $ m $-state DFA over the alphabet $ \Sigma $ for the language $ \{a^{m-2}\}.$  
%shown in Fig.~\ref{f6}~(left).
%The DFA $A$ accepts the language $ \{a^{m-2}\}$ and is shown in Fig. ???
%It is the minimal DFA for this language since no two of its states are equivalent.
%
Since $m> n-k,$  the union of the languages accepted by the DFA $A$ and $B$ is the languauge
$L(A) \cup L(B) = \{a^{n-k-2},a^{m-2}\} \cup \{b^i \mid i\geqslant  k\}.$
The minimal DFA  for this language has $m+k$ states. 
%and is shown in Fig.~\ref{f6}~(right).
\qed      
\end{enumerate}

%\begin{figure}[htbp]
%\begin{center}
% \epsfxsize400pt
%\ \epsfbox{f5b.eps} 
%\caption{The DFA $ A' $ and $ C'; $ nondefined transitions go to dead states $ q_{m-1} $ and  $ r_{m-1}.$ } 
%\label{f6}
%\end{center}
%\end{figure}
%

\end{proof}

The next lemma shows that all the values between $ m+n-1 $ and $ mn $ can be reached by the union of an $ m $-state DFA language and an $ n $-state DFA language over a ternary alphabet.

\begin{lemma} \label{l:sc:m+n-1..mn}
For any integers $m,n,\alpha$ with $ m\geqslant  2, n\geqslant  2, $ and $m+n-1\leqslant  \alpha \leqslant  mn,$ there exist a~minimal DFA $A$ of $m$ states  and a minimal  DFA $B$ of $n$ states such that the minimal DFA for the language $L(A) \cup L(B)$ has $\alpha$ states.
\end{lemma}
\begin{proof}
Let $m,n,$ and $\alpha$ be arbitrary but fixed integers such that
$ m\geqslant  2, n\geqslant  2, $ and 
$m+n-1\leqslant  \alpha \leqslant  mn.$ Then $\alpha$ can be expressed as
$\alpha =m+s(n-1)+t,$ where $1\leqslant  s \leqslant  m-1$ and 
$0\leqslant  t \leqslant  n-1.$ Let $\Sigma = \{a,b,c\}.$

Define an $m$-state DFA $A=(Q_A,\Sigma,\delta_A,q_0,F_A)$, where
$Q_A=\{q_0,q_1,\ldots,q_{m-1}\},$
$F_A=\{q_{m-1}\},$
and for any $i\in \{0,1,\ldots,m-1\}$ and any $X\in \Sigma,$


\[
\delta_A(q_i,X)=\left\{  \begin{array}{ll}
q_{(i+1) \bmod m},       & \textrm{if  $X=a$,}\\
q_{i},                 & \textrm{if $i< s$ and $X=b,$}\\
q_{0},                 & \textrm{if $i\geqslant  s$ and $X=b,$}\\
q_{i},                 & \textrm{if $i=s$ and $X=c,$}\\
q_0,                   & \textrm{if $i\neq s$ and $X=c.$}
\end{array} \right.
\]



Define an $n$-state DFA $B=(Q_B,\Sigma,\delta_B,p_0,F_B)$, where
$Q_B=\{p_0,p_1,\ldots,p_{n-1}\},$
$F_B=\{p_{n-1}\},$
and for any $i\in \{0,1,\ldots,n-1\}$ and any $X\in \Sigma,$

\[
\delta_B(p_i,X)=\left\{  \begin{array}{ll}
%p_i,             & \textrm{if $s=m-1,\ i\leqslant  t,$ and $X=a,$}\\ 
p_0,               & \textrm{if $X=a,$}\\
p_{(i+1) \bmod n}, & \textrm{if $X=b,$}\\
p_{i+1},         & \textrm{if $ i< t$ and $X=c,$}\\
%p_{i+1},         & \textrm{if $0\leqslant  i\leqslant  k-1$ and $X=b,$}\\
%p_k,             & \textrm{if $i=k$ and $X=b,$}\\    
p_{0},         & \textrm{if $ i\geqslant  t$ and $X=c.$}
\end{array} \right.
\]


The DFA $A$ and $B$ are shown in Fig.~\ref{f4}.
% (however, if $ s=m-1, $ then there are loops on reading symbol $ a $ in states $ p_0,p_1,\ldots,p_t $). 
Both automata are minimal since the string $ a^{m-1-j} $ distinguishes states $ q_i $ and $ q_j $ with $ i<j, $ and the string $ b^{n-1-j} $ distinguishes states $ p_i $ and $ p_j $ with $ i<j .$ 

\begin{figure}[htbp]
\begin{center}
 \epsfxsize420pt
\ \epsfbox{f4.eps} 
\caption{The deterministic finite automata $ A $ and $ B. $} 
\label{f4}
\end{center}
\end{figure}



Let $C=(Q_A \times Q_B,\Sigma,\delta,[q_0,p_0],F)$ be the cross-product of automata $ A $ and $ B $ accepting the language  $L(A) \cup L(B)$. We are going to prove that the DFA $C$ has exactly $\alpha$ reachable states no two of which are equivalent.
Let ${\mathcal R}$ be the following set of states of the DFA $C$
$$  {\mathcal R}=  \{[q_i,p_0]\mid 0\leqslant  i< m\}
\cup 
%\{[q_0,p_j] \mid 0\le j \le n-1\}
 \{[q_i,p_j]\mid 0\leqslant  i< s, 1\leqslant  j < n\}
 \cup
\{[q_s,p_j]\mid 1\leqslant  j \leqslant  t\}.$$
There are $m+s(n-1)+t$ states in the set ${\mathcal R}$. Any state in $ {\mathcal R } $ is reachable in the DFA $C$ because we have:\\
$[q_i,p_0]=\delta([q_0,p_0],a^i)$ for $i=0,1,\ldots,m-1,$\\
$[q_i,p_j]=\delta([q_0,p_0],a^ib^j)$ for $i=0,1,\ldots,s-1$ and $j=1,2,\ldots,n-1,$ and\\
$[q_s,p_j]=\delta([q_0,p_0],a^sc^j)$ for $j=1,2,\ldots,t.$

To prove that no other state is reachable in the DFA $C$ note that the initial state $ [q_0,p_0] $ of the DFA $ C $ is in $ {\mathcal R } $ and
for any state $[q,p]$ in $ {\mathcal R } $ and any symbol $X$ in $\Sigma$ the state $\delta([q,p],X)$ is  in  $ {\mathcal R } $ as well.

To prove that no two different states in $ {\mathcal R } $ are equivalent let $[q_i,p_j]$ and $[q_k,p_l]$ be two different states in $ {\mathcal R }. $
Then,  either $ i\neq k $ or $ j\neq l. $ In the first case, these states are distinguished by the string $ a^{m-1-i}, $ 
and in the second case by the string $ b^{n-1-j} .$
% these states, and in the second case 
% In the case of $ s<m-1, $  the string $ a^{m-1-k} $ distinguishes them if $ i<k $ and the string $ b^{n-1-l} $ distinguishes them if $ j<l. $ The string $ ab^{n-1-j} $ distinguishes the state $ [q_{m-1},p_i] $ and $ [q_{m-1},p_j] $ with $ i<j $ in the case of $ s=m-1 $ and $ t<n-1. $ In the case of $ s=m-1 $ and $ t=n-1, $ the string $ ba^{m-1-j}  $ distinguishes states $ [q_i,p_{n-1}] $ and $ [q_j,p_{n-1}] $ with $ i<j. $
\qed
\end{proof}

To prove the result in the lemma above we used a three-letter alphabet. The next lemma shows that the same result holds for a binary alphabet as well.

\begin{lemma} \label{l:sc:binary}
For any integers $m,n,\alpha$ with $ m \geqslant 2, $ $ n \geqslant 2, $ and $m+n-1\leqslant  \alpha \leqslant  mn,$ there exist a~minimal binary DFA $A$ of $m$ states  and a minimal binary  DFA $B$ of $n$ states such that the minimal DFA for the language $L(A) \cup L(B)$ has $\alpha$ states.
\end{lemma}
\begin{proof}
Let $m,n,$ and $\alpha$ be arbitrary but fixed integers such that
$ m \geqslant 2, $ $ n \geqslant 2, $ and
$m+n-1\leqslant  \alpha \leqslant  mn.$ Let $ \Sigma=\{ a,b \}. $

First, let $ \alpha $ can be expressed as $\alpha = rm+sn-rs$  for some integers $ r $ and $ s $ such that $ 1\leqslant  r \leqslant  n $ and $ 1\leqslant  s \leqslant  m. $

Define an $ m $-state DFA $ A_{rs}=(\{q_0,q_1,\ldots,q_{m-1}  \},\Sigma,\delta_A^{(rs)} ,q_0,\{ q_{m-1}  \}),$ where for any $ i\in \{0,1,\ldots,m-1  \} $ and any $ X\in \Sigma ,$
\[
\delta_A^{(rs)}(q_i,X)=  \left\{  \begin{array}{ll}
q_{(i+1)\bmod m},  & \textrm{if $X=a,$} \\
q_{i},  & \textrm{if $i < s$ and $ X=b, $}\\
q_{0},  & \textrm{if $i\geqslant  s$ and $ X=b. $}
\end{array} \right.
\]

Define an $ n $-state DFA $ B_{rs}=(\{p_0,p_1,\ldots,p_{n-1}  \},\Sigma,\delta_B^{(rs)} ,p_0,\{ p_{n-1}  \}),$ where for any $ i\in \{0,1,\ldots,n-1  \} $ and any $ X\in \Sigma ,$
\[
\delta_B^{(rs)}(p_i,X)=  \left\{  \begin{array}{ll}
p_{(i+1)\bmod n},  & \textrm{if $X=b,$} \\
p_{i},  & \textrm{if $i < r$ and $ X=a, $}\\
p_{0},  & \textrm{if $i\geqslant  r$ and $ X=a. $}
\end{array} \right.
\]

Let $C_{rs}=(Q,\Sigma,\delta^{(rs)},[q_0,p_0],F)$ be the cross-product of automata 
$ A_{rs} $ and $B_{rs}$ accepting
the language  $L(A) \cup L(B)$. We are going to prove that the DFA $C_{rs}$ has exactly $\alpha$ reachable states no two of which are equivalent.
Let ${\mathcal R}_{rs}$ be the following set of states: %of the DFA $C_{rs}$
$  {\mathcal R}_{rs}=  \{[q_i,p_j]\mid 0\leqslant  i\leqslant  s-1 \textrm{ or } 0 \leqslant  j \leqslant  r-1\}.$
There are $rm+sn-rs$ states in the set ${\mathcal R}_{rs}$. Any state in $ {\mathcal R }_{rs} $ is reachable in the DFA $C_{rs}$ because we have
$[q_i,p_j]=\delta([q_0,p_0],a^ib^j)$ if $ i\leqslant  s-1, $ and
$[q_i,p_j]=\delta([q_0,p_0],b^ja^i)$ if  $ j\leqslant  r-1. $
To prove that no other state is reachable in the DFA $C_{rs}$ note that the initial state $ [q_0,p_0] $ of the DFA $ C_{rs} $ is in $ {\mathcal R }_{rs} $ and
for any state $[q,p]$ in $ {\mathcal R }_{rs} $ and any symbol $X$ in $\Sigma$ the state $\delta([q,p],X)$ is  in  $ {\mathcal R }_{rs} $ as well.

To prove that no two different states in $ {\mathcal R }_{rs} $ are equivalent let $[q_i,p_j]$ and $[q_k,p_l]$ be two different states in $ {\mathcal R }_{rs}. $ We will consider four cases:
\begin{enumerate}
\item[(i)]
$ r<n  $ and $s<m. $ The string $ a^{m-1-i} $ distinguishes states $[q_i,p_j]$ and $[q_k,p_l]$ if $ i\neq k $ and the string $ b^{n-1-j} $ distinguishes these states if $ j\neq l. $ 
\item[(ii)]
$r<n  $ and $s=m . $ The string $ ab^{n-1-i} $ distinguishes  states $ [q_{m-1},p_i] $ and $ [q_{m-1},p_j] $ with $ i\neq j. $  The other pairs of states can be distiguished as in case (i).
\item[(iii)]
$ r=n $ and $s<m . $ The string $ ba^{m-1-i}  $ distinguishes states $ [q_i,p_{n-1}] $ and $ [q_j,p_{n-1}] $ with $ i\neq j. $ The other pairs of states can be distiguished as in case (i).
\item[(iv)]
$ r=n $ and $s=m . $ The string $ ab^{n-1-i} $ distinguishes  states $ [q_{m-1},p_i] $ and $ [q_{m-1},p_j] $ with $ i\neq j. $ The string $ ba^{m-1-i}  $ distinguishes states $ [q_i,p_{n-1}] $ and $ [q_j,p_{n-1}] $ with $ i\neq j. $ The string $ a $ distinguishes states $[q_{m-1},p_i] $ and
$ [q_j,p_{n-1}]. $ The other pairs of states can be distiguished as in case (i).
\end{enumerate}

Now, let $ r $ and $ s $ be an arbitrary integers such that $ r<n $ and $ s<m. $ Let $ t $ be an integer such that $ 1\leqslant  t \leqslant  \min \{m-s,n-r  \}-1. $ We are going to define binary automata $ A $ and $ B $
  such that the minimal DFA for the language $ L(A)\cup L(B) $ has $ rm+sn-rs+t $ states.

Define an $ m $-state DFA $ A=(\{q_0,q_1,\ldots,q_{m-1}  \},\Sigma,\delta_A ,q_0,\{ q_{m-1}  \}),$ where\\
$ \delta_A(q_{s+i},b)=q_{s+i-1}, $ if $ i\leqslant  t $ and $ i $ is odd,
and 
$ \delta_A(q_{i},X)=\delta_A^{(rs)}(q_{i},X), $ otherwise.

Define an $ n $-state DFA $ B=(\{p_0,p_1,\ldots,p_{n-1}  \},\Sigma,\delta_B ,p_0,\{ p_{n-1}  \}),$ where \\
$ \delta_B(p_{r+i},a)=p_{r+i-1}, $ if $ i\leqslant  t $ and $ i $ is even,
and 
$ \delta_B(p_{i},X)=\delta_B^{(rs)}(p_{i},X), $ otherwise.\\
Then, the set of reachable and pairwise inequivalent states of the cross-product automaton for the language $ L(A)\cup L(B) $ is
$ {\mathcal R }_{rs} \cup \{[q_s,p_{r+j}] \mid j\leqslant  t \textrm{ and $j$ is even}  \}
\cup\{  [q_{s+i},p_r] \mid i\leqslant  t \textrm{ and  $i$ is odd} \}.$

Finally, note that if $ t= \min \{m-s,n-r  \},$ say $ t=m-s, $ then
$rm+sn-rs+t=(r+1)m+sn-(r+1)s,$
%$$rm+sn-rs+t=rm+sn-rs+m-s=(r+1)m+sn-(r+1)s,$$
i.e., $rm+sn-rs+t$ is the size of the minimal DFA for the language 
$ L(A_{r+1s}) \cup L(B_{r+1s} ).$ This completes our proof.
\qed
\end{proof}

As a corollary of the four lemmata above, we get the following result.

\begin{theorem} \label{t:sc:union}
For any integers $m,n,\alpha$ such that $ m\geqslant  2, $ $ n\geqslant  2, $ and $1\leqslant  \alpha \leqslant  mn,$ there exist a~minimal binary DFA $A$ of $m$ states  and a minimal binary  DFA $B$ of $n$ states such that the minimal DFA for the language $L(A) \cup L(B)$ has $\alpha$ states.
\qed
\end{theorem}

The same result for intersection follows from de Morgan's law and the fact that the state complexity of a regular language equals the state complexity of its complement. 

\begin{theorem}
For any integers $m,n,\alpha$ such that $ m\geqslant  2, $ $ n\geqslant  2, $ and $1\leqslant  \alpha \leqslant  mn,$ there exist a~minimal binary DFA $A$ of $m$ states  and a minimal binary  DFA $B$ of $n$ states such that the minimal DFA for the language $L(A) \cap L(B)$ has $\alpha$ states.
\qed
\end{theorem}



\section{Union and Its Nondeterministic State Complexity}
\label{union-nondet}

We now turn our attention to the nondeterministic state complexity of the union of regular languages. It is known \cite{hk03} that the union of an $ m $-state NFA language and an $ n $-state NFA language can be accepted by an $ (m+n+1) $-state NFA and this upper bound can be reached by the union of two binary regular languages.

In this section, we show that the nondeterministic complexity of the union of an $ m $-state NFA language and an $ n $-state NFA language may be arbitrary between $1$ and $m+n+1$ except for the case of $ m=1 $ and $ n=1. $ To prove the result we use a fooling-set lower-bound technique known from communication complexity theory \cite{hr97}, cf. also \cite{bi92,bi93,gs96}. After defining a fooling set, we give a lemma from \cite{bi92} describing the lower-bound technique. 
%For the sake of completeness, we recall its proof in Appendix.

\begin{definition}
A set of pairs of strings $ \{ (x_i,y_i)\mid i=1,2,\ldots,n\} $ is said to be a~\textit{fooling set} for a regular language $L$ if for any $ i $ and $ j $ in $ \{ 1,2,\ldots,n\}, $\\
(1) the string $x_{i}y_{i}$ is in the language $ L,$   and\\
(2) if $i\neq j,$ then at least one of the strings $x_{i}y_{j}$ and $x_{j}y_{i}$ is not in the language $ L.$
\end{definition}

\begin{lemma}[Birget \cite{bi92}] \label{fool}
Let a set of pairs $ \{ (x_i,y_i)\mid i=1,2,\ldots,n \}$ be a~fooling set for a regular language $ L.$
Then any NFA for the language  $ L $ needs at least $ n $ states.
\end{lemma}



%\proof{
%\begin{proof}
%Let $M =(Q,\Sigma,\delta,q_0,F)$ be any NFA accepting the language $L.$
%Since $x_{i}y_{i}\in L ,$ there is a state $p_i$ in $ Q$ such that
%$p_i \in \delta(q_0,x_i) \textrm{ and } \delta(p_i,y_i)\cap F \ne \emptyset$
%(i.e., $ p_i $ is a state on an accepting computation  on $x_iy_i$ that is reached after reading $x_i$).
%Assume that a fixed choice of $p_i$ has been made for any $i$ in $\{ 1,2,\ldots,n\}.$
%We prove that $ p_i\ne p_j $ for $ i\ne j. $
%Suppose by contradiction that
%$p_{i}=p_{j}$ for some $ i\ne j .$
%Then the NFA $M$ accepts both strings $ x_iy_j $ and $ x_jy_i $ which contradicts  the assumption that the set $\{ (x_i,y_i)\mid 1\le i \le n \}$ is a fooling set for the language $L.$
%Hence the NFA  $M$ has at least $n$ states. 
%\qed
%\end{proof}
%%
%%\begin{example}
%
%%\noindent
%\begin{example}
%Let $n \ge 1,$ let $L_n=\{ w\in \left\{ a,b\right\} ^{*}\mid 
%\#_{a}(w) \equiv 0 \bmod n\},$ 
%and let
%${\mathcal A}_n=\{ (a^{i},a^{n-i})\mid i=1,2,\ldots,n\} .$
%Note that for any $ i $ and $ j $ in $ \{ 1,2,\ldots,n\},$ \\
%(1) $a^{i}a^{n-i}=a^n$ and the string $ a^n $ is in the language $ L_n,$ and \\
%(2) if $i< j,$  then $a^{i}a^{n-j}=a^{n-(j-i)}$ and the string  $ a^{n-(j-i)} $ is not in the language $L_n$ since $ 0< n-(j-i)<n. $\\
%Hence the set ${\mathcal A} _n$ is a fooling set for the language $L_n,$ and so any NFA for the language $L_n$ needs at least $n$ states. 
%\qed 
%\end{example}
%
%
%

The following lemma shows that all the values up to the minimum of $ m $ and $n $ can be reached by the union of an  $ m $-state  and an $ n $-state NFA languages.


\begin{lemma} \label{l:ncu:1..m}
For any integers $m,n,\alpha$ such that $1\leqslant  \alpha \leqslant  m \leqslant  n$, there exist a minimal NFA $A$ of $m$ states and 
a minimal NFA $B$ of $n$ states such that  minimal NFAs for the language $L(A)\cup L(B)$ have $\alpha$ states.
\end{lemma}

\begin{proof}
Let $m,n,$ and $\alpha$ be arbitrary but fixed integers such that 
$1\leqslant  \alpha \leqslant  m \leqslant n$. Let $\Sigma=\{a\}$.

Let $ A=(\{q_0,q_1,\dots,q_{m-1}\},\Sigma,\delta_A,q_0,\{q_{m-1}\}), $ where $ \delta_A(q_i,a)=\{q_{i+1}\} $ if $0\leqslant  i\leqslant  m-2, $ and 
$\delta_A(q_{m-1},a)=\{q_{m-1}\},$  
be an $ m $-state NFA accepting the language $ \{a^i\mid i\geqslant  m-1  \}. $ %shown in Fig.~\ref{g1}. 
To prove that the NFA $ A  $ is minimal consider a set of pairs %of strings
$ \{(a^{i-1},a^{m-i}) \mid i=1,2,\ldots,m \}. $ It is a fooling set for the language $ L(A) $ because for any $ i $ and $ j $ in $ \{ 1,2,\ldots,m \}, $
(1) $a^{i-1}a^{m-i}=a^{m-1}$ and the string $ a^{m-1} $ is in the language $ L(A), $ and
(2) if $ i<j, $ then $ a^{i-1}a^{m-j}=a^{m-1-(j-i)} $ and the string $a^{m-1-(j-i)}  $ is not in the language $ L(A) $ since $ m-1-(j-i)<m-1. $
By Lemma~\ref{fool}, any NFA for the language $ L(A) $ needs at least $ m $ states, and so the NFA $ A $ is minimal.
%\begin{figure}[htbp]
%\begin{center}
% \epsfxsize300pt
%\ \epsfbox{f1.eps} 
%\caption{The deterministic finite automaton $ A. $} 
%\label{g1}
%\end{center}
%\end{figure}
%

Let $ B=(\{p_0,p_1,\dots,p_{n-1}\},\Sigma,\delta_B,p_0,
\{p_{\alpha-1},p_{\alpha},\dots,p_{n-1}\} ),$
where 
$ \delta_B(p_i,a)=\{p_{i+1}\} $ if $ 0\leqslant  i\leqslant  n-2, $ and 
$\delta_B(p_{n-1},a)=\emptyset,$ 
 be an $ n $-state NFA accepting the language 
$ \{a^i\mid \alpha -1 \leqslant  i\leqslant  n-1  \}. $ 
%shown in Fig.~\ref{g2}. 
To prove that the NFA $ B  $ is minimal consider a set of pairs %of strings
$ \{(a^{i-1},a^{n-i}) \mid i=1,2,\ldots,n  \}. $ It is a fooling set for the language $ L(B) $ because  for any $ i $ and $ j $ in $ \{ 1,2,\ldots,n\}, $
(1) $a^{i-1}a^{n-i}=a^{n-1}$ and the string $ a^{n-1} $ is in the language $ L(B), $ and
(2) if $ i<j, $ then $ a^{j-1}a^{n-i}=a^{n-1+j-i} $ and the string $a^{n-1+j-i}  $ is not in the language $ L(B) $ since $ n-1+j-i>n-1. $
By Lemma~\ref{fool}, any NFA for the language $ L(B) $ needs at least $ n $ states, and so the NFA $ B $ is minimal.

%\begin{figure}[htbp]
%\begin{center}
% \epsfxsize300pt
%\ \epsfbox{g2.eps} 
%\caption{The deterministic finite automaton $ B. $} 
%\label{g2}
%\end{center}
%\end{figure}





The union of the languages accepted by the NFA $ A $ and $ B $ is the language $ L(A)\cup L(B)=\{a^i\mid i\geqslant  \alpha -1 \}. $ As shown in the case of the DFA $ A, $ minimal NFAs for this language have $ \alpha $ states.
\qed
\end{proof}

The next two lemmata deal with the cases of $ m=1 $ and $ m=2. $ Note that the nondeterministic state complexity of two $ 1 $-state NFAs may be $1$ or $3.$ 

\begin{lemma} \label{l:ncu:m=1}
For any integers $ n,\alpha $ such that $ n \geqslant 2 $ and $ 2 \leqslant \alpha \leqslant n+1,$ there exist a $1$-state NFA $ A $ and a minimal $ n$-state NFA $B$ such that minimal NFAs for the language $ L(A)\cup L(B) $ have $ \alpha $ states.
\end{lemma}
\begin{proof}
%Let $ n $ be an arbitrary but fixed integer with
Let $ n\geqslant 2 $  and let $ A $ be a $ 1 $-state NFA for the language $ a^*. $
If $ \alpha=2, $ let $ B $ be a minimal $ n$-state NFA for the language 
$ \{a^{n-2} \} \cup \{ba^i \mid i\geqslant 0\} .$ 
%(the set of pairs of strings $ \{(a^i,a^{n-2-i})\mid i=0,1,\ldots,n-2  \}\cup \{(b,a^n ) \} $ is a fooling set for the language $ L(B)). $ 
Then, $ L(A)\cup L(B)=a^* \cup ba^*,$ minimal NFAs for which have $ 2 $ states.
If $3 \leqslant \alpha \leqslant n+1,$ 
let $ B $ be a minimal $ n $-state NFA for the language 
$ \{b^{\alpha -2}\}\cup\{ a^{n-\alpha+2}\}.$ Then, $ L(A)\cup L(B)=a^*\cup \{b^{ \alpha-2} \}. $ Minimal NFAs for this language have $ \alpha $ states.
\qed
\end{proof}

\begin{lemma} \label{l:ncu:m=2}
For any integers $ n,\alpha $ such that $ n\geqslant 2 $ and $ 3 \leqslant \alpha \leqslant n+1, $ there exist a~minimal $ 2 $-state NFA $ A $ and a minimal $ n $-state NFA $  B $ such that minimal NFAs for the language $ L(A)\cup L(B)$ have $ \alpha $  states.
\end{lemma}
\begin{proof}
Let $ n\geqslant 2$ and $ 3 \leqslant \alpha \leqslant n+1. $ 
Let $ A $ be a minimal $ 2 $-state NFA for the language $a^+.$ Let $ B $ be a minimal $ n $-state NFA for the language $ \{b^{\alpha -2}\}\cup\{ a^{n-\alpha-2}\}.$ Then, $ L(A)\cup L(B)=a^+\cup \{b^{ \alpha-2} \}.$ Minimal NFAs for this language have $ \alpha $ states.
\qed
\end{proof}

In the next lemma, we assume $ m $ and $ n $ to be at least 3 and show that all values between $ m+1 $ and $ m+n-2 $ can be reached by the union of appropriate NFAs.

\begin{lemma} \label{l:ncu:m+1..m+n-2}
For any integers $m,n,\alpha$ such that $3 \leqslant  m \leqslant n$ and $m+1 \leqslant \alpha \leqslant m+n-2,$ there exist a minimal  NFA $A$ of $m$ states and a minimal  NFA $B$ of $n$ states such that  minimal NFAs for the language $L(A) \cup L(B)$ have $\alpha$ states.
\end{lemma}
\begin{proof}
%Let $m,n,$ and $\alpha$ be arbitrary but fixed integers such that
Let $3 \leqslant m \leqslant n$ and $m+1 \leqslant \alpha \leqslant m+n-2.$ Then $\alpha$ can be expressed as
$\alpha=m+k,$ where $1 \leqslant k \leqslant n-2.$ Let $\Sigma=\{a,b\}.$
Let $ B $ be an $ n $-state NFA accepting the language 
$\{ a^{n-k-1} , b^{k+1} \}. $ %shown in Fig.~\ref{g3}.
The NFA $ B $ is minimal since the set of pairs
$\{(a^{i-1},a^{n-k-i}) \mid i=1,2,\ldots,n-k \}  \cup
\{(b^i,b^{k+1-i}) \mid i=1,2,\ldots,k  \}$
is a fooling set for the language $ L(B). $
%\begin{figure}[htbp]
%\begin{center}
% \epsfxsize200pt
%\ \epsfbox{g3.eps} 
%\caption{The nondeterministic finite automaton $ B. $} 
%\label{g3}
%\end{center}
%\end{figure}
%\noindent
%
To define the DFA $A$ we will consider two cases:
\begin{enumerate}
\item[(i)]
$m \leqslant n-k$. Let $ A $ be a minimal $ m$-state NFA for the language
$ \{a^i\mid i \geqslant m-1 \} .$ 
%see Fig.~\ref{g1}.
 The union of the languages accepted by the NFA $ A $ and $ B $ is the language
% $ L(A)\cup L(B)=
$\{ a^i\mid i \geqslant m-1  \}\cup \{b^{k+1}  \}$ 
which is accepted by an $ (m+k) $-state NFA $ C $ shown in Fig.~\ref{g4} (left).
The NFA $ C $ is minimal since the set %of pairs of strings
$\{(a^{i-1},a^{m-i}) \mid i=1,2,\ldots,m\}  \cup
\{(b^i,b^{k+1-i}) \mid i=1,2,\ldots,k  \}$
is a fooling set for the language 
$ L(A) \cup L(B). $
\begin{figure}[htbp]
\begin{center}
 \epsfxsize400pt
\ \epsfbox{g4a.eps} 
\caption{The nondeterministic finite automata $ C $ and $ C'. $} 
\label{g4}
\end{center}
\end{figure}

\item[(ii)]
$m> n-k$. Let $ A $ be a minimal $ m$-state NFA for the language
$ \{a^{m-1}\} .$ The union of  languages accepted by the NFAs $ A $ and $ B $ is the language
% $ L(A)\cup L(B)=
$\{ a^{n-k-1},a^{m-1},b^{k+1}  \}$ 
which is accepted by an $ (m+k) $-state NFA $ C' $ shown in Fig.~\ref{g4} (right).
The NFA $ C' $ is minimal since the set of pairs of strings
$\{(a^{i-1},a^{m-i}) \mid i=1,2,\ldots,m\}  \cup
\{(b^i,b^{k+1-i}) \mid i=1,2,\ldots,k  \}$
is a fooling set for the language $ L(A) \cup L(B). $
\qed

%\begin{figure}[htbp]
%\begin{center}
% \epsfxsize200pt
%\ \epsfbox{g5.eps} 
%\caption{The nondeterministic finite automaton $ C'. $} 
%\label{g5}
%\end{center}
%\end{figure}
%




\end{enumerate}
\end{proof}


The next two lemmata deal with the cases of $ \alpha=m+n-1$ and $ \alpha=m+n. $ 

\begin{lemma} \label{l:ncu:m+n-1}
For any integers $ m ,n $ such that $m \geqslant 2 $ and $ n \geqslant 2, $
there exist a minimal NFA $A$ of $m$ states and a minimal  NFA $B$ of $n$ states such that  minimal NFAs for the language $L(A) \cup L(B)$ have $m+n-1$ states.
\end{lemma}

\begin{proof}
%Let $ m $ and $ n $ be arbitrary but fixed integers such that 
Let $m \geqslant 2, $ $ n \geqslant 2,$  and let $ \Sigma =\{a,b  \}.$ 
Let $ A $ be an $m$-state NFA shown in Fig.~\ref{g6} (left) and let $ B $ be an $ n$-state NFA shown in Fig.~\ref{g6} (right). Both automata are minimal since the set of pairs of strings $ \{(a^{i-1},a^{m-i}) \mid i=1,2,\ldots,m \} $ is a fooling set for the language $ L(A) $ and the set % of pairs %of strings
$ \{(b^{i-1},b^{n-i}) \mid i=1,2,\ldots,n \} $ is a fooling set for the language $ L(B). $ 
\begin{figure}[htbp]
\begin{center}
 \epsfxsize400pt
\ \epsfbox{g6.eps} 
\caption{The nondeterministic finite automata $ A $ and $ B. $} 
\label{g6}
\end{center}
\end{figure}
%\begin{figure}[htbp]
%\begin{center}
% \epsfxsize200pt
%\ \epsfbox{g6b.eps} 
%\caption{The nondeterministic finite automaton $ B. $} 
%\label{g6b}
%\end{center}
%\end{figure}
\noindent
The language $ L(A)\cup L(B) $ is accepted by an $ (m+n-1) $-state NFA. 
%$ C $ shown in Fig.~\ref{g6c}. The NFA $ C$ is minimal 
Since the set %of pairs of strings 
$\{(a^{i-1}a^{m-i}\mid i=1,2,\ldots,m-1  \} \cup \{(a^{m-1},a^{m-1})  \}
\cup \{( b^{i},b^{n-1-i}) \mid i=1,2,\ldots,n-1 \}$
is a fooling set for the language 
$ L(A)\cup L(B), $ minimal NFAs for this language have $m+n-1$ states. \qed
%\begin{figure}[htbp]
%\begin{center}
% \epsfxsize200pt
%\ \epsfbox{g6c.eps} 
%\caption{The nondeterministic finite automaton $ C. $} 
%\label{g6c}
%\end{center}
%\end{figure}
%

\end{proof}

\begin{lemma} \label{l:ncu:m+n}
For any positive integers $ m ,n $ such that $ n \geqslant 2, $
there exist a minimal NFA $A$ of $m$ states and a minimal  NFA $B$ of $n$ states such that  minimal NFAs for the language $L(A) \cup L(B)$ have $m+n$ states.
\end{lemma}

\begin{proof}
%Let $ m $ and $ n $ be arbitrary but fixed positive integers 
Let $ m \geqslant 1, $ $n \geqslant 2, $
and let $ \Sigma =\{a,b  \}.$ 
Let $ A $ be a minimal $ m $-state NFA %over the alphabet $ \Sigma $ 
for the language $ \{a^m  \}^* $
and let $ B $ be a minimal $ n $-state NFA %over $ \Sigma $ 
for the language
$ \{b^{n-1}  \}. $ Then the union of the languages accepted by the NFA $ A $ and $ B $ is accepted by an $ (m+n) $-state NFA. 
%$ C $ shown in Fig.~\ref{g7}. The NFA $ C $ is minimal 
Since the set of pairs %of strings
$ \{(a^i,a^{m-1} )\mid i=1,2,\ldots,m-1 \}\cup \{(a^m,a^m)  \}
\cup \{(b^{i-1},b^{n-i} )\mid i=1,2,\ldots,n \}$
is a fooling set for the language $ L(A)\cup L(B), $ minimal NFAs for this language have $ m+n $ states.
%\begin{figure}[htbp]
%\begin{center}
% \epsfxsize250pt
%\ \epsfbox{g7.eps} 
%\caption{The nondeterministic finite automaton $ C. $} 
%\label{g7}
%\end{center}
%\end{figure}
\qed
\end{proof}

The following result is proved in \cite{hk03}.
\begin{lemma} \label{l:ncu:m+n+1}
For any positive integers $ m,n, $ 
minimal NFAs for the union of languages $ \{ a^m \}^* $ and $ \{b^n  \}^* $ have $ m+n+1 $ states.
\end{lemma}

As a corollary of the lemmata above, we get the following result.

\begin{theorem} \label{t:ncu}
For any positive integers $m,n,\alpha$ such that $ m \geqslant 2 $ or $ n \geqslant  2, $ and $ 1 \leqslant  \alpha \leqslant m+n+1,$ there exist a minimal binary NFA $ A  $ of $ m $ states and a minimal binary NFA $ B $ of $ n $ states such that minimal NFAs for the language $ L(A)\cup L(B) $ have  $ \alpha $ states.
\qed
\end{theorem}

\section{Intersection and Its Nondeterministic State Complexity}
\label{intersec-nondet}

In this section, we study the nondeterministic state complexity of the intersection of regular languages. The intersection of an $ m $-state NFA language and an $ n $-state NFA language can be accepted by an $ mn $-state NFA and this upper bound is known to be tight for a binary alphabet \cite{hk03}. We show 
that the nondeterministic state complexity of the intersection of an $ m $-state NFA language and an $ n $-state NFA language may be arbitrary between $ 1 $ and $ mn. $ We prove the result for a ternary alphabet.

\begin{lemma} \label{l:nci:1..m}
For any  integers $m,n,\alpha$ such that $1 \leqslant \alpha \leqslant m \leqslant n,$ there exist a~minimal NFA $A$ of $m$ states and 
a minimal NFA $B$ of $n$ states such that  minimal NFAs for the language $L(A)\cap L(B)$ have $\alpha$ states.
\end{lemma}

\begin{proof}
%Let $ m,n, $ and $ \alpha $ be arbitrary but fixed integers such that 
Let $1\leqslant \alpha \leqslant m \leqslant n$ and
let  $ A $ and $ B $ be $ m $-state and $ n $-state NFAs accepting languages 
$ \{a,b  \}^{\alpha -1}\cup \{a^{m-1}  \} $ and
$ \{a,b  \}^{\alpha -1}\cup \{b^{n-1}  \}, $ respectively. 
%see Fig.~\ref{g8}.
%\begin{figure}[htbp]
%\begin{center}
% \epsfxsize300pt
%\ \epsfbox{g8.eps} 
%\caption{The nondeterministic finite automata $ A $ and $ B. $} 
%\label{g8}
%\end{center}
%\end{figure}
Both NFAs are minimal since the sets of pairs of strings
$ \{(a^{i-1},a^{m-i})\mid i=1,2,\ldots,m  \} $ and
$ \{(b^{i-1},b^{n-i})\mid i=1,2,\ldots,n  \} $ are fooling sets for the languages $ L(A)  $ and $L(B), $  respectively. The intersection of these languages is the language %$ L(A)\cap L(B)=
$\{a,b  \}^{\alpha -1}. $ Minimal NFAs for this language have $ \alpha $ states.
\qed
\end{proof}

%\begin{lemma} 
%\label{lni2}
%For any  integers $m,n,\alpha$ such that 
%$ m\le n $ and $m+1\leq \alpha \leq m + n-1,$
% there exist a minimal NFA $A$ of $m$ states and 
%a minimal NFA $B$ of $n$ states such that  minimal NFAs for the language $L(A)\cap L(B)$ have $\alpha$ states.
%\end{lemma}
%
%\begin{proof}
%Let $ m,n, $ and $ \alpha $ be arbitrary but fixed integers such that 
%$ m\le n $ and $m+1\leq \alpha \leq m + n-1.$
%Then $ \alpha $ can be expressed as $ \alpha=m+t, $ where $ 1\le t\le n-1. $
%Let $ \Sigma=\{a,b,c  \}. $
%
%Define an $ m $-state NFA $ A=(Q_A,\Sigma,\delta_A,q_0,F_A), $ where
%$Q_A=\{q_0,q_1,\ldots,q_m-1  \},$
%$ F_A=\{q_0 \} $
%and for any $i\in \{0,1,\ldots,m-1\}$ and any $X\in \Sigma,$
%
%
%\[
%\delta_A(q_i,X)=\left\{  \begin{array}{ll}
%\{q_{(i+1) \bmod m}\},       & \textrm{if  $X=a$,}\\
%%q_{i},                 & \textrm{if $i\le s-1$ and $X=b,$}\\
%%q_{i},                 & \textrm{if $i=s$ and $X=c,$}\\
%\{q_0\},                   &\textrm{if $i=0$ and $X=c,$}\\ 
%\emptyset,               &  \textrm{otherwise.}
%\end{array} \right.
%\]
%
%
%
%Define an $n$-state DFA $B=(Q_B,\Sigma,\delta_B,p_0,F_B)$, where
%$Q_B=\{p_0,p_1,\ldots,p_{n-1},\}$
%$F_B=\{p_{0}\},$
%and for any $i\in \{0,1,\ldots,n-1\}$ and any $X\in \Sigma,$
%
%\[
%\delta_B(p_i,X)=\left\{  \begin{array}{ll}
%\{p_0\},             & \textrm{if $i=0$ and $X=a,$}\\ 
%\{p_{(i+1) \bmod n}\}, & \textrm{if $X=b,$}\\
%\{p_{i+1}\},         & \textrm{if $ i\le t-1$ and $X=c,$}\\
%%p_{i+1},         & \textrm{if $0\le i\le k-1$ and $X=b,$}\\
%\{p_0\},             & \textrm{if $i=t$ and $X=c,$}\\    
%\emptyset,        & \textrm{otherwise.}
%\end{array} \right.
%\]
%
%
%The NFA $A$ and $B$ are shown in Fig.~\ref{g9}. Both automata are minimal since the sets of pairs of strings 
%$ \{(a^{i-1},a^{m-i})\mid i=1,2,\ldots,m  \} $ and
%$ \{(b^{i-1},a^{n-i})\mid i=1,2,\ldots,n  \} $ are fooling sets for the languages  $ L(A) $ and $ L(B), $ respectively.
%\begin{figure}[htbp]
%\begin{center}
% \epsfxsize380pt
%\ \epsfbox{g9.eps} 
%\caption{The nondeterministic finite automata $ A $ and $ B. $} 
%\label{g9}
%\end{center}
%\end{figure}
%
%Let $C=(Q_A \times Q_B,\Sigma,\delta,[q_0,p_0],F)$ be the product automaton for the language  $L(A) \cap L(B).$ Let $ {\mathcal R } $ be the following set of states.
%$${\mathcal R }=\{[q_i,p_0]\mid i=1,2,\ldots,m  \}
%\cup \{[q_0,p_j]\mid j=1,2,\ldots,t  \}.$$
%Any state in $ {\mathcal R } $ is reachable in the NFA $ C $ because
%$ [q_i,p_0]=\delta([q_0,p_0],a) $ for $ i=0,1,\ldots, m-1$ and 
%$ [q_0,p_j]=\delta([q_0,p_0],c) $ for $ j=1,2,\ldots, t.$ Next, no other state in $ Q_A \times Q_B $ is reachable in the NFA $ C $ because  the initial state  $[q_0,p_0]$ of the NFA $ C $ is in $ {\mathcal R } $ and for any state $ s $ in $ {\mathcal R } $ and any symbol $ X $ in $ \Sigma $ either the state $ \delta(s,X) $ is in $ {\mathcal R } $ or is equal to the empty set. Thus the language $L(A) \cap L(B)$ is accepted by an 
%$ (m+t) $-state NFA. To prove the Lemma consider the set of pairs of strings
%$$\{ (a^{i},a^{m-i})\mid i=0,1,\ldots,m-1  \}
%\cup \{ (c^{j},c^{t+1-j})\mid j=1,2,\ldots,t  \}.$$
%It is a fooling set for the language  $L(A) \cap L(B)$ because\\
%(1) the strings $ a^m $ and $ c^{t+1} $ are in the language $L(A) \cap L(B),$ and\\
%(2) if $0\le i<j\le m-1, $ then the string $ a^{i}a^{m-j} $ is not in the language $ L(A), $ if $ 1\le i < j \le t, $ then the string $c^{i}c^{t+1-j}$
%is not in the language $ L(B), $ and finally, if $ i\in \{0,1,\ldots,m-1  \} $ and $ j\in \{1,2,\ldots,t \} ,$ then the string $ c^ja^{m-i} $ is not in the language $ L(B). $ \\
%By Lemma~\ref{fool}, any NFA for the language $L(A) \cap L(B)$ needs at least $ m+t $ states which completes our proof.
%\qed
%\end{proof}

\begin{lemma} \label{l:nci:m..mn}
For any positive integers $m,n,\alpha$ such that $ m\leqslant n $ and  $m\leqslant \alpha \leqslant mn,$ there exist a minimal  NFA $A$ of $m$ states and a minimal  NFA $B$ of $n$ states such that minimal NFAs for the language $L(A) \cap L(B)$ have $\alpha$ states.

\end{lemma}
\begin{proof}
Let $m,n,$ and $\alpha$ be arbitrary but fixed positive integers such that $ m\leqslant n $ and
$m\leqslant \alpha \leqslant mn.$ Then $\alpha$ can be expressed as
$\alpha =m+s(n-1)+t,$ where $0\leqslant s \leqslant m$ and $0\leqslant t <n-1.$ Let $\Sigma = \{a,b,c\}.$

Define an $ m $-state NFA $ A=(Q_A,\Sigma,\delta_A,q_0,F_A), $ where
$Q_A=\{q_0,q_1,\ldots,q_{m-1}  \},$
$ F_A=\{q_0 \} $
and for any $i\in \{0,1,\ldots,m-1\}$ and any $X\in \Sigma,$


\[
\delta_A(q_i,X)=\left\{  \begin{array}{ll}
\{q_{(i+1) \bmod m}\},       & \textrm{if  $X=a$,}\\
\{q_{i}\},                 & \textrm{if $i\leqslant s-1$ and $X=b,$}\\
\{q_{i}\},                 & \textrm{if $i=s$ and $X=c,$}\\
%\{q_0\},                   &\textrm{if $i=0$ and $X=c,$}\\ 
\emptyset,               &  \textrm{otherwise.}
\end{array} \right.
\]

Define an $n$-state DFA $B=(Q_B,\Sigma,\delta_B,p_0,F_B)$, where
$Q_B=\{p_0,p_1,\ldots,p_{n-1}\},$
$F_B=\{p_{0}\},$
and for any $i\in \{0,1,\ldots,n-1\}$ and any $X\in \Sigma,$

\[
\delta_B(p_i,X)=\left\{  \begin{array}{ll}
\{p_0\},             & \textrm{if $i=0$ and $X=a,$}\\ 
\{p_{(i+1) \bmod n}\}, & \textrm{if $X=b,$}\\
\{p_{i+1}\},         & \textrm{if $ i\leqslant t-1$ and $X=c,$}\\
%p_{i+1},         & \textrm{if $0\le i\leqslant k-1$ and $X=b,$}\\
\{p_0\},             & \textrm{if $i=t$ and $X=c,$}\\    
\emptyset,        & \textrm{otherwise.}
\end{array} \right.
\]

The NFA $A$ and $B$ are shown in Fig.~\ref{g10}. Both automata are minimal since the sets of pairs of strings 
$ \{(a^{i},a^{m-i})\mid i=0,1,\ldots,m-1  \} $ and
$ \{(b^{i},b^{n-i})\mid i=0,1,\ldots,n-1  \} $ are fooling sets for the languages  $ L(A) $ and $ L(B), $ respectively.
\begin{figure}[htbp]
\begin{center}
 \epsfxsize400pt
\ \epsfbox{g10.eps} 
\caption{The nondeterministic finite automata $ A $ and $ B. $} 
\label{g10}
\end{center}
\end{figure}

Let $C=(Q_A \times Q_B,\Sigma,\delta,[q_0,p_0],F),$
% where $ \delta([q,p],a)=[\delta_A(q,a),\delta_B(p,a) $ and $ F=F_A\times F_B, $ 
be the cross-product  of automata $ A $ and $ B $ accepting the language  $L(A) \cap L(B).$ Let $ {\mathcal R } $ be the following set of states.

${\mathcal R }=\{[q_i,p_0]\mid 0\leqslant i< m  \} 
\cup \{[q_i,p_j]\mid 0\leqslant i< s, 1\leqslant j< n  \}
\cup  \{[q_s,p_j]\mid 1\leqslant j\leqslant t\}.$
%see Fig.~\ref{g11}.
%\begin{figure}[htbp]
%\begin{center}
% \epsfxsize300pt
%\ \epsfbox{g11.eps} 
%\caption{The nondeterministic finite automaton $ C. $ } 
%\label{g11}
%\end{center}
%\end{figure}
Any state in $ {\mathcal R } $ is reachable in the NFA $ C $ because we have
$ [q_i,p_0] \in \delta([q_0,p_0],a^i) $ for $ i=0,1,\ldots, m-1,$ 
$ [q_i,p_j] \in \delta([q_0,p_0],a^ib^j) $ for $ i=0,1,\ldots,s-1 $ and $ j=1,2,\ldots, n-1,$ and
$ [q_s,p_j] \in \delta([q_0,p_0],a^sc^j) $ for $ j=1,2,\ldots,t. $
 Next, no other state in $ Q_A \times Q_B $ is reachable in the NFA $ C $ because  the initial state  $[q_0,p_0]$ of the NFA $ C $ is in $ {\mathcal R } $ and for any state $ [q,p] $ in $ {\mathcal R } $ and any symbol $ X $ in $ \Sigma $ either  $ \delta([q,p],X)\subseteq  {\mathcal R } $ or $ \delta([q,p],X)=\emptyset. $
%is equal to the empty set. 
Thus the language $L(A) \cap L(B)$ is accepted by an 
$ (m+s(n-1)+t) $-state NFA. To prove the lemma consider the following sets of pairs of strings:

${\mathcal A }=\{ (a^{i},a^{m-i})\mid i=0,1,\ldots,m-1  \},$

$ {\mathcal B }_k=\{ (a^{k}b^i,b^{n-i}a^{m-k})\mid i=1,2,\ldots,n-1  \}, \textrm{ for } k=0,1,\ldots,s-1,$

${\mathcal C }=\{ (a^sc^{i},c^{t+1-i}a^{m-s})\mid i=1,2,\ldots,t  \}.$\\
Let $ {\mathcal D} ={\mathcal A }\cup {\mathcal B }_0\cup {\mathcal B }_1\cup \cdots \cup {\mathcal B }_{s-1}\cup {\mathcal C }.$
We will show that the set $ {\mathcal D } $ is a fooling set for the language $ L(A) \cap L(B). $ We need to show that\\
(1) for any pair $ (x_i,y_i) $ in $ {\mathcal D }, $ the string $ x_iy_i $ is in the language $ L(A) \cap L(B), $ and\\
(2) for any two different pairs $ (x_i,y_i) $ and $ (x_j,y_j)$ in $ {\mathcal D } ,$ at least one of the strings $ x_iy_j $ and $ x_jy_i $ is not in the language $ L(A) \cap L(B). $ 

To prove (1) note that the strings $ a^m,\ a^kb^na^{m-k}\ (k=0,1,\ldots,s-1), $ and $ a^sc^{t+1}a^{m-s} $ are in the language $ L(A) \cap L(B). $ 

To prove (2) we have six cases to consider: 
\begin{enumerate}
\item[(i)]
Both pairs are in $ {\mathcal A }. $ Let $ 0\leqslant i <j \leqslant  m-1. $ Then the string $ a^{i}a^{m-j} $ is not in the language $ L(A) $ since $0< m-j+i<m. $
\item[(ii)]
Both pairs are in $ {\mathcal B }_k $ for some $ k \ (0\leqslant  k \leqslant  s-1).$ Let $ 1\leqslant  i < j\leqslant  n-1. $ Then the string $a^{k}b^ib^{n-j}a^{m-k}$ is not in the language $ L(B) $ since $ 0<n-j+i<n. $
\item[(iii)]
Both pairs are in $ {\mathcal C }.$ Let $ 1\leqslant  i < j \leqslant  t. $ Then the string $ a^sc^{i}c^{t+1-j}a^{m-s} $ is not in the language $ L(B) $ since $0< t+1-j+i <t+1.$
\item[(iv)]
The first pair is in $ {\mathcal A } $ and the second in some $ {\mathcal B }_k $  (or in $ {\mathcal C}). $ Then the string $ a^kb^ia^{m-j} $ (the string $a^sc^{i}a^{m-j}$, respectively) is not in the language $ L(B) $ since $ 1\leqslant  i \leqslant  n-1 $  ($1\leqslant  i \leqslant  t,$ respectively).
\item[(v)]
The first pair is in some $ {\mathcal B }_k $ and the second in some $ {\mathcal B }_l $ with $0\leqslant  k<l\leqslant  s-1. $ Then the string $ a^kb^ib^{n-j}a^{m-l} $ is not in the language $ L(A) $ since $ 0<k+m-l<m. $
\item[(vi)]
The first pair is in some $ {\mathcal B }_k $ and the second in $ {\mathcal C. } $ Then the string $ a^sc^ib^{n-j}a^{m-k} $ is not in the language $ L(A) $ since 
$ i \geqslant 1$ and $ n-j \geqslant 1. $
\end{enumerate}

Thus we have shown that the set $ {\mathcal D } $ is a fooling set for the language $ L(A)\cap L(B). $ By Lemma~\ref{fool}, any NFA for the language $ L(A)\cap L(B) $ needs at least $ m+s(n-1)+t $ states and our proof is complete.
\qed
\end{proof}

As a  corollary of the two lemmata above, we get the following result.

\begin{theorem} \label{t:nci}
For any positive integers $ m,n,\alpha $ such that $ 1\leqslant  \alpha \leqslant  mn,$
there exist a~minimal  NFA $A$ of $m$ states and a minimal  NFA $B$ of $n$ states such that minimal NFAs for the language $L(A) \cap L(B)$ have exactly $\alpha$ states.
\qed
\end{theorem}


\section{Conclusions}
\label{conclu}

In this paper, we investigated the state complexity and the nondeterministic state complexity of union and intersection of regular languages. In the deterministic case, we showed that the entire range of complexities between $ 1 $ and $ mn $ can be obtained by the union (intersection, respectively) of an $ m $-state DFA language and an $ n $-state DFA language for any integers $ m $ and $ n $ such that $ m\geqslant  2$  and $ n\geqslant  2. $ Next, we proved that the nondeterministic state complexity of the union of an $ m $-state NFA language and an $ n $-state NFA language may be arbitrary between $ 1 $ and $ m+n+1, $ except for the case of $ m=1 $ and $n=1.$ To prove these results we used a binary alphabet. In the case of a unary alphabet, similar results probably do not hold.
Finally, we showed that the nondeterministic state complexity of the intersection of an $ m $-state NFA language and an $ n $-state NFA language may be arbitrary between $ 1 $ and $ mn. $ We proved the last result for a ternary alphabet. The question whether this result holds likewise for a binary alphabet remains open. 

\begin{thebibliography}{00}
\label{biblio}

%\bibitem{bl77} P. Berman and A. Lingas,
   %\textit{On the complexity of regular languages in terms of finite automata,}
   %Technical Report 304, Polish Academy of Sciences, 1977.
\bibitem{bi92} J. C. Birget,
   Intersection and union of regular languages and state complexity,
  \textit{Inform. Process. Lett.} \textbf{43} (1992) 185--190.
\bibitem{bi93} J. C. Birget,
   Partial orders on words, minimal elements of regular languages, and state complexity,
   \textit{Theoret. Comput. Sci.} \textbf{119} (1993) 267--291.
\bibitem{cam01} C. C\^{a}mpeanu, K. Culik~II, K. Salomaa, and   S. Yu, 
   State complexity of basic operations on finite languages,
   in: O. Boldt, H. J\"urgensen (Eds.),
   \textit{Proc. 4th International Workshop on Implementing Automata (WIA'99),}
   LNCS 2214, Springer-Verlag, Heidelberg, 2001, pp. 60--70.
\bibitem{cam02} C. C\^{a}mpeanu, K. Salomaa, and  S. Yu, 
   Tight lower bound for the state complexity of shuffle of regular languages,
   \textit{J.~Autom. Lang.  Comb.} \textbf{7} (2002) 303--310.
%\bibitem{ch86} M. Chrobak,
   %Finite automata and unary languages,
   %\mbox{\textit{Theoret. Comput. Sci.}} \textbf{47} (1986) 149--158.
\bibitem{do01} M. Domaratzki,
   State complexity and proportional removals,
   \textit{J.~Autom. Lang.  Comb.} \textbf{7} (2002)  455--468.
\bibitem{el02} K. Ellul, B. Krawetz, J. Shallit,  and  M. W. Wang, 
   Regular expressions: new results and open problems,
   \textit{J.~Autom. Lang.  Comb.}, to appear.  %\textbf{7} (2002)  455--468.
\bibitem{gs96} I. Glaister and J. Shallit,
   A lower bound technique for the size of nondeterministic finite automata,
   \textit{Inform. Process. Lett.} \textbf{59} (1996) 75--77.
%\bibitem{hol01} M.~Holzer,K.~Salomaa, and S.~Yu,
%   On the state complexity of k-entry deterministic finite automata,
%   \textit{J.~Autom. Lang. Comb.} \textbf{6} (2001) 453--466.
%\bibitem{hk01} M. Holzer and M. Kutrib,
   %State complexity of basic operations on nondeterministic finite automata,
   %in: \mbox{J.M. Champarnaud,} \mbox{D. Maurel} (Eds.),
   %\textit{Implementation and Application  of Automata (CIAA 2002),}
   %LNCS 2608, Springer-Verlag, Heidelberg,  2003, pp. 148--157.
%\bibitem{hk02} M. Holzer and M. Kutrib,
   %Unary language operations and their nondeterministic state complexity,
   %in: \mbox{M. Ito,} \mbox{M. Toyama} (Eds.),
   %\textit{Developments in Language Theory (DLT 2002),}
   %LNCS 2450, Springer-Verlag, Heidelberg, 2003, pp. 162--172.
\bibitem{hk03} M. Holzer and M. Kutrib,
   Nondeterministic descriptional complexity of regular languages,
   \textit{Internat. J. Found. Comput. Sci.} \textbf{14} (2003) 1087-1102.
\bibitem{hr97} J. Hromkovi\v c,
   \textit{Communication Complexity and Parallel Computing,}
   Springer-Verlag, Berlin, Heidelberg,  1997.
\bibitem{hr02} J. Hromkovi\v c,
   Descriptional complexity of finite automata: concepts and open problems,
   \textit{J.~Autom. Lang. Comb.} \textbf{7} (2002)  519--531.
%\bibitem{hr02a} J. Hromkovi\v c, S. Seibert,J. Karhum\"aki, H. Klauck, and G. Schnitger,}
   %Communication complexity method for measuring nondeterminism in finite automata,
   %\textit{Inform. and Comput.} \textbf{172} (2002)  202--217.
%\bibitem{ji03} G. Jir\'askov\'a,
   %Note on minimal automata and uniform communication protocols,
   %in: \mbox{C. Martin-Vide,}  \mbox{V. Mitrana} (Eds.),
   %\textit{Grammars and Automata for String Processing: From Mathematics and Computer   Science to Biology, and Back,}
   %Taylor and Francis, London, 2003, pp. 163--170.
%\bibitem{ji03a} G. Jir\'askov\'a,
   %State complexity of some operations on regular languages,
   %in: \mbox{E. Csuhaj-Varj\'u,} \mbox{C. Kintala,} \mbox{D. Wotschke,}
   %\mbox{Gy. Vaszil} (Eds.),
   %\textit{Proc. 5th Workshop Descriptional Complexity of Formal Systems,}
   %MTA SZTAKI, Budapest, 2003, pp. 114--125.
\bibitem{ji05} G. Jir\'askov\'a,
   State complexity of some operations on binary regular languages,
   \textit{Theoret. Comput. Sci.} \textbf{330} (2005) 287--298.
\bibitem{le81} E. Leiss,
   Succinct representation of regular languages by boolean automata,
   \textit{Theoret. Comput. Sci.} \textbf{13} (1981) 323--330.
\bibitem{lu63} O. B. Lupanov,
   A comparison of two types of finite automata,
   \textit{Problemy Kibernetiki,} \textbf{9} (1963) 321-326 (in Russian).
\bibitem{ly64} Yu. I. Lyubich,
   Estimates for optimal determinization of nondeterministic autonomous automata, 
   \textit{Sibirskii Matematichskii Zhurnal,} \textbf{5} (1964) 337-355 (in Russian).
%\bibitem{mf71} A.R. Meyer and M.J. Fischer,
   %Economy of description by automata, grammars and formal systems,
   %in: \textit{Proc. 12th Annual Symposium on Switching and Automata Theory,}
   %1971, pp. 188--191.
\bibitem{ma70} A. N. Maslov,
   Estimates of the number of states of finite automata,
   \textit{Dokl. Akad. Nauk SSSR,} \textbf{194} (1970) 1266--1268 (in Russian). 
   English translation: \textit{Soviet Math. Dokl.} \textbf{11} (1970) 1373--1375.
\bibitem{mo71} F. R. Moore,
   On the bounds for state-set size in the proofs of equivalence
   between deterministic, nondeterministic, and two-way finite automata,
   \textit{IEEE Trans. Comput.}   \textbf{20} (1971) 1211--1214.
%\bibitem{pi01} G. Pighizzini,
     %Unary language concatenation and its state complexity,
     %in: \mbox{S. Yu,} \mbox{A. Pun} (Eds.),
     %\textit{Implementation and Application of Automata: 5th International    
     %Conference, CIAA 2000,}
     %LNCS 2088, Springer-Verlag, 2001, pp. 252--262.
\bibitem{pi02} G. Pighizzini and J. Shallit, 
     Unary language operations, state complexity and Jacobsthal's function,
     \textit{Internat. J.  Found. Comput. Sci.} \textbf{13} (2002) 145--159.
\bibitem{rs59} M. Rabin and D. Scott,
     Finite automata and their decision problems,
     \textit{IBM Res. Develop.} \textbf{3} (1959) 114--129.
%\bibitem{ss78} W. J. Sakoda and M. Sipser, 
     %Nondeterminism and the size of two-way finite automata,
     %in: \textit{Proc. 10th Annual ACM Symp. on Theory of Computing,}
     %1978, pp. 275--286.
\bibitem{sa04} A. Salomaa, D. Wood, and S. Yu,
     On the state complexity of reversals of regular languages,
     \textit{Theoret. Comput. Sci.} \textbf{320} (2004) 315--329.
\bibitem{si97} M. Sipser,
     \textit{Introduction to the theory of computation,}
     PWS Publishing Company,   Boston, 1997.
\bibitem{yzs94} S.~Yu, Q.~Zhuang, and K.~Salomaa,
     The state complexity of some basic operations on regular languages,
     \textit{Theoret. Comput. Sci.} \textbf{125} (1994) 315--328.
\bibitem{yu97} S.~Yu,
     Chapter~2: Regular languages,
     in: \mbox{G.~Rozenberg,} \mbox{A.~Salomaa,} (Eds.),
     \textit{Handbook of Formal Languages - Vol. I,}
     Springer-Verlag, Berlin, New York, 1997,  pp. 41--110.
\bibitem{yu00} S.~Yu,
     A renaissance of automata theory?
     \textit{Bull. Eur. Assoc. Theor. Comput. Sci. EATCS}  \textbf{72} (2000)         
     270--272.
\bibitem{yu01} S.~Yu,
     State complexity of regular languages,
     \textit{J.~Autom. Lang. Comb.} \textbf{6} (2001) 221--234.
\bibitem{yu02} S.~Yu,
     State complexity of finite and infinite regular languages,
     \textit{Bull. Eur. Assoc. Theor. Comput. Sci. EATCS}  \textbf{76} (2002) 
     142--152.
\end{thebibliography}



\end{document}