\begin{enumerate}gin{document}

\title{Quotient Complexity of  Bifix-, Factor-, and Subword-Free Regular Languages
\thanks{This work was supported by the Natural Sciences and Engineering Research Council of Canada under grant no.\ OGP0000871 and by 
the Slovak Research and Development Agency under contract
APVV-0035-10 ``Algorithms, Automata, and Discrete Data Structures''.
}}

 \author{Janusz Brzozowski$^1$
   \quad Galina Jir\'askov\'a$^2$
   \quad Baiyu Li$^1$
   \quad Joshua Smith$^1$}

\date{}

\maketitle

\begin{enumerate}gin{center}
\vskip-20pt
 {\normalsize $^1$ David R. Cheriton School of Computer Science, University of Waterloo,}\\
 {\normalsize Waterloo, ON, Canada N2L 3G1 }\\
 {\normalsize {\tt \{brzozo@,b5li@,j45smith@student.math.\}uwaterloo.ca }}

 {\normalsize$^2$  Mathematical Institute, Slovak Academy of Sciences,}\\
 {\normalsize Gre\v{s}\'akova 6, 040 01 Ko\v{s}ice, Slovakia}\\
 {\normalsize {\tt jiraskov@saske.sk}}

\end{center}

\begin{enumerate}gin{abstract}
\label{***abst}
A language $L$ is prefix-free if,
whenever  words $u$ and $v$ are in $L$ and $u$ is a prefix of $v$, then $u=v$.
Suffix-, 
factor-, and subword-free languages 
are defined similarly, where ``subword"  means ``subsequence". 
A language is bifix-free if it is both prefix- and suffix-free.
We study the quotient complexity, more commonly known as state complexity, 
of  operations in the classes of  bifix-, factor-, and subword-free regular languages. 
We find tight upper bounds on the quotient 
complexity
of  intersection, union, difference, symmetric difference, 
concatenation, star,  and reversal 
in these three classes of languages.

\end{abstract}

\pagestyle{plain}
\pagenumbering{arabic}

{settable}ction{Introduction}
\label{***intro}
The state complexity of a regular language $L$ 
is the number of states  in the minimal deterministic finite automaton (dfa) 
accepting $L$~\cite{Yu01}.
This complexity is the same as the quotient complexity~\cite{Brz10} of $L$, 
which is the number of distinct left quotients of $L$. 
We prefer quotient complexity since it is more closely related to properties of languages.
The quotient complexity of an operation in a class ${\mathcal C}$ of regular languages 
is the worst-case quotient complexity of the language resulting  from the operation, 
taken as a function of the quotient complexities of the operands in class  ${\mathcal C}$. 
For surveys on state and quotient complexity see~\cite{Brz10,Yu01}.

One of the first results concerning the state complexity of an operation 
is the 1966 theorem by Mirkin~\cite{Mir66}, 
who showed that the bound  $2^n$ for the reversal of an $n$-state dfa can be attained.
In 1970 Maslov~\cite{Mas70} stated without proof the bounds 
on the complexities of union, concatenation,  star, 
and several other operations in the class of regular languages, 
and gave languages meeting these bounds. 
In 1994 these operations, along with intersection, reversal, and left and right quotients, 
were studied in detail by Yu, Zhuang and Salomaa~\cite{YZS94}.

Results exist also for proper subclasses of the class of regular languages: unary~\cite{PiSh02,YZS94}, 
finite~\cite{CCSY01,HaSa08,Yu01}, cofinite~\cite{BGN10}, 
prefix-free~\cite{HSW09,JiKr10}, suffix-free~\cite{Cmo11,HaSa09,JiOl09}, 
ideal~\cite{BJL10}, and closed~\cite{BJZ10}.
The bounds can vary considerably.

Free languages  (with the exception of $\{\eps\}$, where $\eps$ is the empty word) 
are  codes, which constitute an important class 
of languages and have applications in such areas 
as cryptography, data compression, and information transmission. 
They have been studied extensively; see, for example,~\cite{BPR10,JuKo97}.
In particular, \emptyseth{prefix} and \emptyseth{suffix codes}~\cite{BPR10} 
are prefix-free and suffix-free languages, respectively, 
\emptyseth{infix codes}~\cite{Shy01,ShTh74} are factor-free, 
and \emptyseth{hypercodes}~\cite{Shy01,ShTh74} are subword-free, 
where by subword we mean subsequence.
Moreover, free languages are special cases of convex languages~\cite{AnBr09,Thi73}.
We are interested only in regular free languages.

The state complexities of intersection, union, concatenation,  star, and reversal  
were first studied by Han, K.~Salomaa, and Wood~\cite{HSW09} for prefix-free languages, 
and  by Han and K.~Salomaa~\cite{HaSa09} for suffix-free languages.
In the present paper, these results are extended to bifix-, factor- and subword-free languages. 
In particular, we obtain tight upper bounds on the complexities 
of intersection, union, difference, symmetric difference, star, concatenation, and reversal 
in these three classes of free languages. 

{settable}ction{Preliminaries}
\label{***prelim}

It is assumed that the reader is familiar with finite automata 
and regular languages as treated in~\cite{Per90,Yu97}, for example.
If $\Sigma$ is a finite non-empty alphabet, 
then $\Sigma^*$ is the set of all  words over this alphabet,
with $\eps$ as the empty word. 
For $w\in\Sigma^*$,  let $|w|$ be the length of $w$.
A~language is any subset of $\Sigma^*$.

The following set operations are defined on languages:  
\emptyseth{complement} ($\overline{L}=\Sigma^*{settable}tminus L$),  
\emptyseth{union}  ($K\cup L$),  
\emptyseth{intersection} ($K\cap L$),  
\emptyseth{difference} ($K{settable}tminus L$), and 
\emptyseth{symmetric difference} ($K\oplus L$). 
A general \emptyseth{boolean operation} with two arguments is denoted by $K\circ L$. 

We also  define the 
\emptyseth{product,} usually called  \emptyseth{concatenation} or \emptyseth{catenation,}
($KL=\{w\in \Sigma^*\mid w=uv, u\in K, v\in L\}$),
(Kleene) \emptyseth{star} ($L^*=\begin{enumerate}gin{itemize}gcup_{i\ge 0}L^i$ with $L^0=\{\eps\}$), and 
\emptyseth{positive closure} ($L^+=\begin{enumerate}gin{itemize}gcup_{i\ge 1}L^i$).

The reverse $w^R$ of a word $w\in\Sigma^*$ is defined inductively as follows: 
$\eps^R=\eps$, and $(wa)^R=aw^R$ for every symbol $a$ in $\Sigmama$
and every word $w$ in $\Sigmama^*$.
The \emptyseth{reverse} of a language $L$ is denoted by $L^R$ and 
is defined as $L^R=\{w^R\mid w\in L\}$.

\emptyseth{Regular languages} over $\Sigma$ 
are languages that can be obtained from the \emptyseth{set of basic languages} 
$\{\emptyset,\{\eps\}\} \cup \{\{a\}\mid  a\in \Sigma\}$,  
using a finite number of operations of union, product,  and  star. 
We use regular expressions to represent languages.
If $E$ is a regular expression, then ${\mathcal L}(E)$ is the language denoted by that expression. 
For example, the regular expression  $E=(\eps\cup a)^* b$ denotes language $L={\mathcal L}(E)=(\{\eps\}\cup\{a\})^*\{b\}$. 
We usually do not distinguish notationally between regular languages and regular expressions.

Whenever convenient, we derive upper bounds on the state complexity 
of operations on free languages following the approach of~\cite{Brz10}.
A \emptyseth{quotient} of a language $L$ by a word $w$ 
is defined as $L_w=\{x\in \Sigma^* \mid wx \in L \}$. 
The number of distinct quotients of a language  
is called its \emptyseth{quotient complexity}  and is denoted by $\kappa(L)$. 

Quotients of regular languages~\cite{Brz64,Brz10} 
can be computed as follows:
First, the \emptyseth{$\eps$-function}  $L^\eps$ of a regular language $L$ is
 $L^\eps=\emptysettyset$ if $\eps\not\in L$, and
 $L^\eps=\eps$ if $\eps\in L$.
The \emptyseth{quotient by a letter} $a$ in $\Sigmama$ 
is computed by  induction:
 $b_a=\emptysettyset$ if $b\in \{\emptysettyset,\eps\}$ or $b\in\Sigmama$ and $b\not= a$,
 and
 $b_a=\eps$ if $b=a$;
 $(\overline{L})_a =\overline{L_a};\,
 (K\circ L)_a = K_a\circ L_a; \,
 (KL)_a = K_aL \cup K^\eps L_a;\,
 (L^*)_a = L_aL^*$.
The quotient by a word $w$ in $\Sigmama^*$  is computed by
induction on the length of $w$:
 $L_\eps =  L$
 and $L_{wa} = (L_w)_a$.
A~quotient $L_w$ is \emptyseth{accepting} if $\eps\in L_w$; 
otherwise it is \emptyseth{rejecting}.

A \emptyseth{deterministic finite automaton} (dfa) 
is a quintuple ${\mathcal D}=(Q,\Sigmama,\delta,q_0,F)$, where 
$Q$ is a finite set of \emptyseth{states,} 
$\Sigmama$ is a finite \emptyseth{alphabet,} 
$\delta:Q\times\Sigmama\rightarrow Q$ is the \emptyseth{transition function,} 
$q_0$ is the \emptyseth{initial state}, and 
$F\subseteq Q$ is the set of \emptyseth{final} or \emptyseth{accepting states\/}. 
As usual, the transition function is extended to  $Q\times\Sigmama^*$. 
The dfa ${\mathcal D}$ accepts a word $w$ in $\Sigmama^*$ if ${\delta}(q_0,w)\in F$. 
The set of all words accepted by ${\mathcal D}$ is $L({\mathcal D})$. 
By the \emptyseth{language of a state} $q$ of ${\mathcal D}$ 
we mean the language $L_q$ accepted 
by the automaton $(Q,\Sigmama,\delta,q,F)$. 
A state is \emptyseth{empty} if its language is empty.

The \emptyseth{quotient automaton} of a regular language $L$ is the
dfa ${\mathcal D}=(Q, \Sigma, \delta, q_0,F)$, where 
$Q=\{L_w\mid w\in\Sigma^*\}$, 
$\delta(L_w,a)=L_{wa}$, 
$q_0=L_\eps$,  
$F=\{L_w\mid \eps\in L_w\}$.
This  is the minimal dfa accepting $L$. 
Hence the quotient complexity of $L$ is equal to the state complexity of $L$, 
and we call it simply  \emptyseth{complexity}.

{settable}ction{Free Languages}
\label{***freeprops}

If $u,v,w,x\in \Sigma^*$ and $w=uxv$, then 
$u$ is a \emptyseth{prefix} of $w$, 
$x$ is a \emptyseth{factor} of $w$, and 
$v$ is a \emptyseth{suffix} of $w$. 
Both $u$ and $v$ are also factors of $w$. 
If $w=u_0v_1u_1\cdots v_nu_n$, where $u_i,v_i \in \Sigma^*$, then 
$v=v_1v_2\cdots v_n$ is a \emptyseth{subword} of $w$. 
Every factor of $w$ is also a subword of $w$.

A language $L$ is \emptyseth{prefix-free} 
(respectively, \emptyseth{suffix-, factor-,} or \emptyseth{subword-free}) 
if, whenever  words $u$ and $v$ are in $L$ and $u$ is a prefix 
(respectively, suffix, factor, or subword) of $v$, then $u=v$.  
Additionally, $L$ is \emptyseth{bifix-free} if it is both prefix and suffix-free. 
All subword-free languages are factor-free, 
and all factor-free languages are bifix-free. 
For convenience, we refer to prefix-, suffix-, bifix-, factor-, and subword-free languages together as 
\emptyseth{free} languages.

If $\eps$ is a quotient of $L$,
then $L$ also has the empty quotient,
since $\eps_a=\emptyset$, for all $a$ in $\Sigma$.
We say that a quotient $L_w$ is \emptyseth{uniquely reachable} 
if $L_w=L_x$ implies that $w=x$.
We now restate two propositions from~\cite{HaSa09,HSW09}
in our terminology. 

\begin{enumerate}gin{proposition}\label{prop:pf}
A non-empty  language is prefix-free if and only if it
 has exactly one accepting quotient and that quotient is $\eps$.
\end{proposition}

\begin{enumerate}gin{proposition}\label{prop:sf}
 The quotient by $\eps$  of a non-empty suffix-free language
 is uniquely reachable, and the language has the empty quotient.
\end{proposition}

Let $L$ be any language. 
If $(L_u)_x =L_v$ for some words $u,v$ and a non-empty word $x$,
then $L_v$ is \emptyseth{positively reachable} from $L_u$, 
and we denote this by $L_u \to~L_v$.
The relation $\to$ is transitive.
The next proposition uses this relation to characterize finite languages. 
 
\begin{enumerate}gin{proposition}\label{prop:finite}
 If $L$ is any  language
 with the set of quotients 
 $\{L_1,L_2,\ldots,L_n\}$, and $u,v\in\Sigma^*$,
 then the following are equivalent:\\
 1. $L$ is finite.\\
 2. $L_u\to L_v$ and $L_v\to L_u$ if and only if $L_u=L_v=\emptyset$.\\
 3. There exists a total order $\preceq$ on the set of quotients:

       $L=L_1 \preceq L_2\preceq \cdots \preceq L_{n-1} \preceq L_n=\emptyset$\\
       which satisfies the condition that $(L_i)_a=L_j$
       implies \mbox{$L_i\prec L_j$ or $L_i=L_j=L_n$.} 
\end{proposition}

\begin{enumerate}gin{proof}
 Suppose $L$ is a finite language.
 If $L_u\to L_v$ and $L_v\to L_u$,
 then $(L_u)_x=L_v$ and $(L_v)_y=L_u$,
 for some words $x$ and $y$.
 If also $L_u\neq \emptyset$,
 then $u(xy)^kw\in L$ for every nonnegative $k$ and any word $w$ in $L_u$,
 which contradicts that $L$ is finite. 
 Note also that  $L_u\neq \emptyset$ if $L_v\neq \emptyset$.
 If $L_u=L_v=\emptyset$, then $(L_u)_a=L_u$ for every $a$ in $\Sigma$,
 and we have $L_u\to L_u$.
 Thus (1) implies (2).

 Now suppose  that $L$ is infinite and $\kappa(L)=n$.
 Then there is a word $uxv$ \mbox{in $L$}  of length at least $n$
 such that $L_u=L_{ux}$
 and $x\in\Sigma^+$.
 Thus $L_u\to L_u$ and $L_u\neq \emptyset$,
 showing that (2) cannot hold.
 Hence (2) implies (1).

 If (1) holds, we can take the reflexive  closure $\to'$ of the relation $\to$.
 Then the relation $\to'$ is a partial order,
 and we can use any total order $\preceq$
 consistent with relation $\to'$ to get~(3). 
 Conversely, if (3) holds, then $L$ cannot be infinite,
 by the same argument as was used to prove that (2) implies (1).
\end{proof}

Since every subword-free language is finite,
we get the next lemma, 
which we use later to prove that upper bounds on the quotient complexity 
of some operations on subword-free languages 
cannot be reached if the alphabet of the language 
does not have sufficiently many letters.

\begin{enumerate}gin{lemma}\label{lem:letter}
 Let $L$ be a subword-free language with $\kappa(L)=n$, where $n\ge4$.
 Let the distinct quotients 
 $L=L_\eps=L_1,L_2,\dots,L_{n-2},L_{n-1}=\eps, L_n=\emptysettyset$ of $L$ 
 be ordered as in Proposition \ref{prop:finite}. 
 If $L_w=L_2$ for some word $w$, then $|w|=1$.
\end{lemma}

\begin{enumerate}gin{proof}
 Since $n\ge4$, the quotients $L$ and  $L_2$ are not empty.
 Let $v$ be a word in~$L_2$.
 If $L_w=L_2$, then $w$ cannot be $\eps$ because $L_2\neq L_1$.
 If $|w|>1$, 
 then $w=ua$ for a letter $a $ and a non-empty word $u$.
 Then $L_u\neq L$ since $L$ is uniquely reachable.
 If~$L_u=L_2$, then $uv\in L$ and $uav\in L$,  and language $L$ is not subword-free.
 Thus, if $L_u=L_i$, for some~$i$, 
 then $i> 2$, $L_{w}=(L_u)_a=(L_i)_a=L_j$ where $j\ge i > 2$, 
 contradicting that $L_{w}= L_2$. 
 Thus $w$ must be a one-letter word.
\end{proof}

Finally, we describe a simple method of constructing free languages.

\begin{enumerate}gin{proposition}\label{prop:construct}
 Let $L \subseteq \Sigma^*$  be any language,
 and let $a \notin \Sigma$.  Then
 (1)  $aL$ is suffix-free,
 (2) $La$ is prefix-free,
 (3) $aLa$ is factor-free.
\end{proposition}

\begin{enumerate}gin{proof}

 (1) Every proper suffix of a word in $aL$
 is a word over the alphabet $\Sigmama$,
 and so is not in $aL$.
 Therefore $aL$ is suffix-free.\\
 (2) The proof is dual to that of (1).\\
 (3) Every proper factor of a word in $aLa$
 contains at most one $a$
  and therefore is not in $aLa$.
\end{proof}

{settable}ction{Boolean Operations}
\label{***bool}

The complexity of boolean operations,
in the class of prefix- and suffix-free regular languages,
except for the difference and symmetric difference of suffix-free languages,
was studied in \cite{HaSa09,HSW09,JiKr10,JiOl09}.
It was shown that for prefix-free languages,
the tight bounds for union, intersection, difference, and symmetric difference
are $mn-2$, $mn-2(m+n-3)$, $mn-(m+2n-4)$, and $mn-2$, respectively.
For  union and  intersection of suffix-free languages, the tight bounds are
$mn-(m+n-2)$ and 
$mn-2(m+n-3)$, respectively.
 The bounds for difference and symmetric difference 
are  $mn-(m+2n-4)$ and
 $mn-(m+n-2)$, respectively, and the bounds for all four boolean operations
 are met by binary suffix-free languages~\cite{Cmo11}.
 The next two theorems provide results
for boolean operations on bifix-, \mbox{factor-,} and subword-free languages.

\begin{enumerate}gin{theorem}[\bf Boolean Operations: Bifix- and Factor-Free Languages]\label{thm:bifix,factor}
 Let $K$ and $L$  be bifix- or factor-free languages
 over an alphabet~$\Sigmama$
 with $\kappa(K)=m$ and $\kappa(L)=n$, where $m,n\ge4$. Then\\
   \hglue10pt  1. $\kappa(K\cap L)\le mn-3(m+n-4)$;\\ 
   \hglue10pt  2. $\kappa(K{settable}tminus L)\le mn-(2m+3n-9)$;\\ 
   \hglue10pt  3. $\kappa(K\cup L), \kappa(K\oplus L)\le mn-(m+n)$.\\ 

 All the bounds are tight if $|\Sigmama|\ge3$.
\end{theorem}

\begin{enumerate}gin{proof} 
 Since $K$ and $L$ are bifix-free,
 by unique reachability we get a reduction of $m+n-2$ from the general bound $mn$.
 Moreover, both languages $K$ and $L$ have $\eps$ and $\emptysettyset$  as quotients.
 For intersection,
 we have $\emptysettyset \cap L_w=K_w\cap \emptysettyset = \emptysettyset$,
 and the quotients $\eps \cap L_w$ and $K_w\cap \eps$
 are either empty or equal to $\eps$.
 This gives the upper bound. 
 For difference,
 we eliminate $m+n-2$ quotients by unique reachability,
 $n-2$ quotients by the fact that $\emptyset{settable}tminus L_w=\emptyset$
 (keeping only one representative $\emptyset{settable}tminus\emptyset$),
 $m-2$ quotients by the fact that $K_w{settable}tminus \emptyset= K_w{settable}tminus\eps$
 (keeping $K_w{settable}tminus\emptyset$ as a representative),
 and $n-3$ more quotients by the rule $\eps{settable}tminus L_w=\eps$,
 for a total reduction of $(2m+3n-9)$.
  For union,
 we have the unique reachability reduction of $m+n-2$,
 and a further reduction of 2
 by the rule
 $\eps\cup\eps=\eps\cup\emptysettyset=\emptysettyset \cup\eps=\eps$.
  For symmetric difference,
 we note that 
 $\eps \oplus \eps=\emptysettyset \oplus \emptysettyset=\emptysettyset$
 and $\eps \oplus \emptysettyset=\emptysettyset \oplus \eps =\eps$.

 For tightness, 
 consider  $K=a(c^*(a\cup b))^{m-3}$, 
 $L=a(b^*(a\cup c))^{n-3}$; see
 Figure~\ref{fig:factor}.
 If $w\in K$, then $w=av$ for some word $v$ containing $m-3$ 
 occurences of symbols from $\{a,b\}$ and ending in $a$ or $b$.
 This means that no proper factor of $w$ \nopagebreak is in $K$,
 and so $K$ is factor-free.
 A similar proof applies to $L$.
 
 \begin{enumerate}gin{figure}[b]
 \begin{enumerate}gin{center}
 \input factor_new.eepic
 \end{center}
 \caption{Factor-free languages meeting the upper bounds for boolean operations.}
 \label{fig:factor}
 \end{figure}

\label{factor}
\begin{enumerate}gin{figure}[h]
\begin{enumerate}gin{center}
\input crossprod.eepic
\end{center}
\caption{Cross product automaton for boolean operations
         on factor-free languages from Figure~\ref{fig:factor};
         $m=5, n=6$.}
\label{fig:cross}
\end{figure}

 In the cross-product automaton of Figure~\ref{fig:cross}
for the boolean operations on languages $K$ and $L$,
 all the states are reached from the initial state $(1,1)$
 by a word in $ab^*c^*\cup ac^*b^*$, except for  state $(m-1,n-1)$
 which is reached from state $(m-2,n-2)$ by $a$.

 For intersection,
 the only accepting state  
 is $(m-1,n-1)$.
 All the rejecting states in rows $m-1$ and $m$
 and columns $n-1$ and $n$
are empty.
 The word $a$ is accepted only from 
 $(m-2,n-2)$,
  word $b^{m-2-i}c^{n-2-j}a$  ($2\le i\le m-2$, $2\le j\le n-2$)
 only from state
 $(i,j)$,
 and the word $ab^{n-4}c^{n-4}a$ only from state (1,1).
 This  gives $mn-3(m+n-4)$ reachable and pairwise distinguishable states.
  
 For difference,
 all the states of the cross-product automaton in row $m-1$, except for $(m-1,n-1)$,
 are accepting and accept $\eps$.
 All the states in row $m$,
as well as state $(m-1,n-1)$ are empty.
 Moreover, states $(i,n-1)$ and $(i,n)$ with $2\le i \le m-2$ are equivalent.
 The word $ab^{m-3}$ is accepted only from $(1,1)$.
 Now let
 $(i,j)$ and $(k,\ell)$, 
 where $2\le i \le n-1, 2\le j \le m-2$,
 be two distinct states. 
 If $i<k$, then $c^nb^{m-1-i}$
 is accepted from $(i,j)$ but not from $(k,\ell)$.
 If $i=k$ and $j<\ell$, then $b^{m-2-i}c^{n-2-j}a$
 is not accepted from $(i,j)$
 but is accepted from $(k,\ell)$.
 This means that $mn-(2m+3n-9)$ states  are pairwise distinguishable.

 For union,
 all the states in row $m-1$ and in column $n-1$ are accepting,
 and moreover, the three states $(m,n-1)$, $(m-1,n-1)$, and $(m-1,n)$
 are equivalent.
 The word $ab^{m-3}$ is accepted only from $(1,1)$.
 Consider two distinct rejecting states $(i,j)$ and $(k,\ell)$.
 If $i<k$, then $c^nb^{m-1-i}$ is accepted from $(i,j)$ but not from $(k,\ell)$.
 If $j<\ell$, then $b^mc^{n-1-j}$ is accepted from $(i,j)$ but not from $(k,\ell)$.
 Now consider two distinct accepting states different from $(m,n-1)$ and $(m-1,n)$.
 By $c$, the two states either  go to two states 
 one of which is accepting and the other rejecting, 
 or to two distinct rejecting, and hence distinguishable, states.
 This proves distinguishability of $mn-(m+n)$ states.
 
 The proof for symmetric difference is the same as for union,
 except that  state $(m-1,n-1)$ is empty and states $(m,n-1)$ and $(m-1,n)$ are equivalent.
\end{proof}

The next result shows that the upper bounds 
for intersection and difference of factor-free languages 
are also tight in the binary case.

\begin{enumerate}gin{proposition} [\bf Intersection and Difference: Binary Factor-Free Languages]
\label{prop5}

 There exist binary factor-free languages $K$ and $L$
 with $\kappa(K) = m$ and $\kappa(L) = n$, where $m,n \ge 6$,
 such that\\
   \hglue10pt  1.  $\kappa(K \cap L) \ge mn-3(m+n-4)$ and \\
   \hglue10pt  2.  $\kappa(K {settable}tminus L)\ge mn-(2m+3n-9)$.
\end{proposition}

\begin{enumerate}gin{proof}
 Let $K$ and $L$
 be the binary factor-free languages accepted
 by the quotient automata of Figure~\ref{fig:binary_inter_diff}.
\begin{enumerate}gin{figure}[t]
 \centering
 \input{factor_binary.eepic}
 \caption{Binary factor-free witnesses  for intersection and difference.
         Missing transitions in the automaton accepting $K$ ($L$)  all go to the empty state $m$ ($n$).}
 \label{fig:binary_inter_diff}
\end{figure}

\begin{enumerate}gin{figure}[t]
 \centering
 \input{difference_factor_bin.eepic}
 \caption{Cross-product automaton for $m=6,n=7$. Missing transitions all go to state $(7,6)$.}
 \label{fig:binFacProd}
\end{figure}

 In the corresponding cross-product automaton of Figure~\ref{fig:binFacProd},
 except for $(1,1)$, no states in row 1 or column 1 are reachable.
 Also, states $(m-1,2)$ and $(m,2)$ are unreachable, as are the states in column $n-1$, except $(3,n-1)$, $(m-1,n-1)$, and $(m,n-1)$. The remaining states are all reachable.
 
 For intersection, the only accepting state is $(m-1,n-1)$,
 and all the other states in the last two rows and columns
 are empty.
 We will prove that states $(1,1)$, $(i,j)$ with $2\le i\le m-2$ and $2\le j\le n-2$, $(m-1,n-1)$,
 and $(m,n)$, which represents all the empty states, are all distinguishable.
 Then it follows that
 $\kappa(K\cap L) \ge (m-3)(n-3)+3=mn-3(m+n-4)$.
 
 State $(m,n)$ is the only empty state in our set.
 We show that for each other rejecting state $(i,j)$,
 there exists a word $w_{ij}$ 
 that is accepted only from state $(i,j)$.
 We have $w_{m-2,n-2}=a$ because word $a$ is accepted only from state $(m-2,n-2)$.
 Since only one transition on letter $b$ goes to state  $(m-2,n-2)$,
 and it goes from state $(m-3,n-2)$, the word $ba$
 is accepted only from state $(m-3,n-2)$. 
 Therefore $w_{m-3,n-2}=ba=bw_{m-2,n-2}$.
 For similar reasons we have

\begin{enumerate}gin{tabular}{ll}
 $w_{i,n-2}=bw_{i+1,n-2}$  & for $i=2,3,\ldots,m-3$,\\
 $w_{3j}=aw_{3,j+1}$       & for $j=2,3,\ldots,n-3$,\\
 $w_{2j}=bw_{3j}$          & for $j=2,3,\ldots,n-3$,\\
 $w_{m-2,j}=bw_{2j}$       & for $j=2,3,\ldots,n-3$,\\
 $w_{ij}=bw_{i+1,j}$       & for $i=4,5,\ldots,m-3$ and $j=2,3,\ldots,n-3$,\\
 $w_{11}=aw_{22}$,         &
\end{tabular}\\

\begin{enumerate}gin{itemize}gskip
\noindentdent
 which proves that $mn-3(m+n-4)$ states  are pairwise distinguishable.

 In the case of difference,
 all the states in row $m$, as well as state $(m-1,n-1)$ are empty.
 All the other states in row $m-1$ accept $\eps$, and so are equivalent.
 For each $i$ with $2\le i \le m-2$, 
 states $(i,n-1)$ and $(i,n)$ are equivalent.
 Among the other reachable states consider two distinct states $p$ and $q$.
 If they are in different rows,
 then by a word in $b^*$ we can send  $p$ to a state $p'$ in row 3,
 and $q$  to a state $q'$ that is not in row 3.
 Now by $a^n$, state $q'$ goes to the empty state,
 while $p'$ goes to state $(3,n)$ that is not empty.
 Two distinct states in the same row go by a word in $b^*$ to row 3. 
 Then, by a word in $a^*$, the first goes to 
 state $(3,n-2)$ while  the second to $(3,n)$,
 and now $b^{m-2-3}a$ distinguishes them.
 In summary,  $\kappa(K{settable}tminus L) \ge (m-3)(n-3) +m-3 +3=mn-(2m+3n-9)$.
\end{proof}

The next proposition gives  lower bounds for union and symmetric difference
of binary bifix-free languages.

\begin{enumerate}gin{proposition} [\bf Union, Symmetric Difference: Binary Bifix-Free Languages; Lower Bound]
\label{prop6}
 Let $m,n \ge 6$. 
 There exist binary bifix-free languages $K$ and $L$
 with $\kappa(K) = m$ and $\kappa(L) = n$ 
 such that
 $\kappa(K \cup L), \kappa(K \oplus L) \ge mn-(m+n)-2$.
\end{proposition}

\begin{enumerate}gin{proof}
  Consider the binary languages 
 \begin{enumerate}gin{eqnarray*}
   K &=& a( (ba^*)^{m-5}b \cup a) (b ((ba^*)^{m-5}b \cup a) )^* a,\\
   L &=& a(a\cup b)^{n-4} (b(a\cup b)^{n-4})^* a.
 \end{eqnarray*}
 Quotient automata for $m=7$ and $n=6$ are shown in Figure~\ref{fig:xxx}.
Since both languages have  $\eps$ as the only accepting 
 quotient, they are prefix-free. Since the reverse automata are deterministic, the 
 reversed languages also have  $\eps$ as the only accepting quotient, and so are 
 prefix-free. Thus both languages are bifix-free.
 
\begin{enumerate}gin{figure}[t]
\begin{enumerate}gin{center}
\input{binary_bifix_KL.eepic}
\end{center}
\caption{Binary bifix-free languages meeting the bound $mn-(m+n)-2$
            for union and symmetric difference.}
\label{fig:xxx}
\end{figure}
\begin{enumerate}gin{figure}[t]
\begin{enumerate}gin{center}
\input{bifix_bin_product.eepic}
\end{center}
\caption{Cross-product automaton for automata from Figure~\ref{fig:xxx}, 
        where dashed-transitions are on input $b$, and unspecified transitions go to
         state (7,6).}         
\label{fig:zzz}
\end{figure}
 The cross-product automaton is shown in Figure~\ref{fig:zzz}. 
 States in row~1 and column~1 
 are unreachable, with the exception of the initial state (1,1).
 Also, states $(2,n-1)$ and  $(m-1,2)$ are unreachable. 
 The initial state $(1,1)$ goes to state $(2,2)$ by $a$
 and then to state $(3,3)$ by $b$.
 From $(3,3)$, all the other states in row 3, except for $(3,2)$ are reached by $a$-transitions.
 Next, state $(3,n-2)$ goes to state $(4,2)$ by $b$,
 and then to $(4,j)$ by $a^{j-2}$ ($3 \le j \le n$).
 In this way, all the states in rows $4,5,\ldots,m-3$ can be reached.
 State $(m-3,n-2)$ goes to state $(m-2,2)$ by $b$, and states  $(m-2,j)$ with $j\ge3$,
 except for state $(m-2,n-1)$ that is reached from $(2,n-2)$ by $a$,
 are reached from  states  $(m-3,j-1)$ by $b$.
 States $(2,j)$ with $j\ge3$, except for $(2,n-1)$,
 are reached from    $(m-2,j-1)$ by $b$.
 State $(2,n-2)$ goes to  $(3,2)$ by $b$.
 From states in row $m-2$ all reachable states in row $m-1$ 
 are reached by $a$. State $(m,2)$ is reached by $b$ from $(m-1,n-2)$; 
 from here, all the other states is row $m$ are reached by words in $a^*$.
 
 For union, the three accepting states $(m-1,n-1),(m-1,n)$ and $(m,n-1)$
are equivalent.
 Consider the other reachable states.
 First, let $p=(i,j)$ and $q=(k,\ell)$ be two rejecting states with $i<k$.
 We can use $b$-transi\-tions to get  $p$
 into a state $p'$ in row 3, and $q$ into a state $q'$  in a row $i$ with $i\neq 3$.
 By $a^n$, state $p'$ goes to  $(3,n)$, 
 while $q'$ goes to $(i,n)$.
 Now  $b^{m-2-3}a$ is accepted from $(3,n)$ but not from $(i,n)$.
 Next, let $p$ and $q$ be two distinct rejecting states in the same row.
 If they are in the last row,
 then a word in $a^*$ distinguishes them.
 Otherwise, we can get them
 into states $(3,j)$ and $(3,\ell)$ with $j<\ell$,
 using $b$-transitions. Now  $(3,j)$ accepts $a^{n-1-j}$
 while  $(3,\ell)$ goes to the rejecting state $(3,n)$.
 Finally, consider two distinct accepting states
 different from $(m-1,n)$, $(m,n-1)$.
 By $b$, they go to two distinct rejecting, and so distinguishable,  states.
 The proof for symmetric difference is similar,
 except that now state  $(m-~1,n-~1)$ is empty.
\end{proof}

We now show that the upper bound for union of binary bifix-free languages
is the same as the lower bound
in the proposition above.

\begin{enumerate}gin{proposition}[\bf Union: Binary Bifix-Free Languages; Upper Bound]
\label{prop7}
 Let \linebreak $m,n\ge 4$
 and let $K$ and $L$ be binary bifix-free languages
 with $\kappa(K)=m$ and $\kappa(L)=n$. Then $\kappa(K\cup L)\le mn-(m+n)-2$.
\end{proposition}

\begin{enumerate}gin{proof}
  Let $K$  be a bifix-free  language
 accepted by the quotient automaton 
 ${\mathcal A}$   over $\{a,b\}$
 with states $1,2,\ldots,m$, where 1 is the initial state,
 $m-1$  is the only accepting state and it accepts only $\eps$,
 and $m$  is the empty state.
 Let $L$ be a similar language
 accepted by ${\mathcal B}$ with states  $1,2,\ldots,n$,
 initial state 1, state $n-1$ accepting $\varepsilon$, and empty state $n$.
 
 Construct the corresponding cross-product automaton
 with states $(i,j)$,
 where $i$ is a state of ${\mathcal A}$ and $j$ is a state of ${\mathcal B}$.
 In this cross-product automaton,
 we cannot go from columns $n-1$ and $n$, 
 as well as from rows $m-1$ and $m$,
 back to any state $(i,j)$ with $i<m-1$ or $j<n-1$.

 If state 1 of ${\mathcal A}$ goes by both inputs $a$ and $b$
 to a state in $\{m-1,m\}$, then no row $i$ with $i<m-1$ can be reached.
 Therefore, if the bound is to be met,
 at least one input, say $a$,
 takes state 1 to a state $i$ with $i<m-1$.
 Suppose also that $b$ takes 1 to a state in $\{m-1,m\}$. 
 A~similar condition applies to $L$.
  Suppose that input $b$ takes state 1 of ${\mathcal B}$ to a state $j$ with $j<n-1$,
 and $a$, to a state in $\{n-1,n\}$.
 Then no state $(i,j)$ with $i<m-1$ or $j<n-1$ can be reached.
 It follows that, without loss of generality,
 each automaton must take its initial state by $a$
 to a state that is neither accepting nor empty;
 for convenience, let this state be 2 in both automata.
 Then no other transition by $a$ may go to state 2 in the two automata,
 otherwise they would not be suffix-free.

 It follows that  in the cross-product automaton,
 all the states in row 2 and column~2, except for $(2,2)$,
 must be reached from some states by input $b$.
 Thus, if all the states are reachable,
 there must be an incoming transition by $b$ to each state $i$ with $i\ge 2$ in ${\mathcal A}$
 and $j$ with $j\ge 2$ in ${\mathcal B}$.
 In particular, if  state $(m-1,2)$ or $(2,n-1)$  is reachable,
 then some state, say $p_1$ (respectively $q_1$)
 different from $m-1$ (respectively  $n-1$) 
 must go to state $m-1$ (respectively $n-1$) in ${\mathcal A}$ (respectively ${\mathcal B}$).
 Now since $p_1$ goes to $m-1$ by $b$, it cannot go anywhere else by $b$.
 Thus there must be some other state $p_2$ not in $\{p_1,m-1,m\}$
 that goes to $p_1$ by $b$.
 Then there must be a state $p_3$ not in $\{p_2,p_1,m-1,m\}$ that goes to $p_2$ by $b$,
  and so on.
  Eventually, we have
  $$
  p_{m-3} \stackrel{b}{\rightarrow} p_{m-4} \stackrel{b}{\rightarrow} \cdots 
          \stackrel{b}{\rightarrow} p_3 
          \stackrel{b}{\rightarrow} p_2 
          \stackrel{b}{\rightarrow} p_1 
          \stackrel{b}{\rightarrow} m-1
          \stackrel{b}{\rightarrow} m,
 $$
 where all the states are pairwise distinct,
 and no state, except possibly state 1, goes by $b$ to state $p_{m-3}$.
 
 First assume state 1 goes to state $p_{m-3}$ by $b$.
 If $p_{m-3}=2$, then state 1 goes to state 2 by $a$ and by $b$.
 This means that there is no other transition to state 2,
 and so row 2 is not reachable in the cross-product automaton.
 If $p_{m-3}>2$ and 1 goes to  $p_{m-3}$ by $b$,
 then no other state goes to $p_{m-3}$ by $b$ because of suffix-freeness,
 and so  row $p_{m-3}$ may only be reached by $a$'s.
 However, in such a case state $(p_{m-3},2)$ is unreachable,
 since it is in row $p_{m-3}$ that can be reached only by $a$'s
 and at the same time in column 2 that can be reached only by $b$'s.

 Now assume that there is no transition by $b$ going to state $p_{m-3}$.
 If $p_{m-3}\ge3$, then $(p_{m-3},2)$  is unreachable.
 If $p_{m-3}=2$, then the whole row  2, except for $(2,2)$ is unreachable.
 The same considerations hold for automaton ${\mathcal B}$.
 This gives the desired upper bound $mn-(m+n)-2$. 
\end{proof}

We finally consider union and symmetric difference
of binary factor-free languages,
and give  upper bounds. 
We conjecture that the bounds are tight.

\begin{enumerate}gin{proposition} [\bf Union, Symmetric Difference: 
Binary Factor-Free Languages]
\label{prop8}
 Let $m,n \ge 6$. There exist binary factor-free languages $K$ and $L$
 with $\kappa(K) = m$ and $\kappa(L) = n$ such that
 $\kappa(K \cup L), \kappa(K \oplus L) 
 \ge mn-(m+n)-\min\{m-3,n-3\}$.
 We conjecture that this is largest bound for binary factor-free languages.
\end{proposition}

\begin{enumerate}gin{proof}
 Consider binary languages
   $K = a(b^*a)^{m-3}$, and
   $L = (a\cup b)(ba^*)^{n-4}b$.
 Quotient automata for $K$ and $L$ are shown in Figure~\ref{fig:yyy}. 

 \begin{enumerate}gin{figure}[b]
 \centering
  \input{factor_bin_KL.eepic}
 \caption{Binary factor-free languages $K$ and $L$ meeting
   quotient complexity $mn - (m+n) - (m-3)$ 
   for union and symmetric difference.}
 \label{fig:yyy}
 \end{figure}

 To show that the languages are factor free,
 observe that every word $w$ in $K$ has exactly $m-2$  $a$'s, 
 while every proper factor of $w$ has less than $m-2$  $a$'s.
 Thus $K$ is factor-free. 
 For $L$, every word $w$ in $L$ either has $a$ as a prefix and has $n-3$  $b$'s,
 or has  $n-2$  $b$'s.
 However, every proper factor of $w$ either has $a$ as a prefix and has $n-4$
  $b$'s, or has $n-3$  $b$'s. Thus $L$ is also factor-free.

\begin{enumerate}gin{figure}[t]
\begin{enumerate}gin{center}
\input{union_factorfree.eepic}
\end{center}
\caption{Cross-product automaton for automata from Figure~\ref{fig:yyy}; 
 $m = 6$, $n = 7$.}
\label{fig:binfactorfreeunion}
\end{figure} 

 
Construct the cross-product automaton for language $K\cup L$;
 see Figure~\ref{fig:binfactorfreeunion}.
 
 Consider the following family $\mathcal{R}$
 of $mn-(m+n)-(m-3)$ states: 
 \begin{enumerate}gin{eqnarray*}
   \mathcal{R} = \{(1,1),(2,2)\}  &\cup& \{(i,j)\mid 2\le i\le m-2, 3\le j\le n\} \cup\\
                                  & & \{(m-1,j)\mid 3\le j\le n-2\} \cup\\
                                  & & \{(m,j)\mid 2\le j\le n\},
 \end{eqnarray*}
 and let  us show that all states in $\mathcal{R}$
 are reachable and pairwise distinguishable.  
 The initial state $(1,1)$ goes to state $(2,2)$ by $a$,
 then to state $(2,3)$ by $b$,
 and then to state $(i,j)$ with $2\le i\le m-2$ and $3\le j\le n$ by $a^{i-2}b^{j-3}$.
 Each state $(m-2,j)$ with $3\le j\le n-2$ goes to state $(m-1,j)$ by $a$.
 State $(m,j)$ with $2\le j\le n$ is reached from the initial state $(1,1)$ by $b^{j-1}$.
 Thus all the states in $\mathcal{R}$ are reachable.

 For distinguishability, notice that 
 $a^{m-1}$ is accepted only from state $(1,1)$.
 Among the other states,
 two rejecting states in two distinct rows
 go to two distinc states in column $n$ by $b^n$,
 and the two states in column $n$ are  distinguished by a word in $a^*$.
 Two rejecting states in the same row $i$ go  by a word in $b^*$
 to states $(i,n-1)$ and $(i,n)$ that are distinguished by $\eps$.
 Two distinct accepting states in family $\mathcal{R}$ go by $b$
 either to two states, one of which is accepting and the other rejecting,
 or to two distinct rejecting, and so distinguishable, states.

 The proof for symmetric difference is exactly the same;
 notice that the languages are disjoint,
 and so their symmetric difference is the same as their union.

  Since union is a commutative operation,
 we may assume $m\le n$,
 and then the lower bound for  binary factor-free languages
 is $mn-(m+n)-(m-3)$.
 We did some computations
 by  enumerating all the binary factor-free
 automata in the case of $m,n \le 6$.
 The following table contains all the enumerated results:

\begin{enumerate}gin{itemize}gskip
\centerline{
 \begin{enumerate}gin{tabular}{l|lll}
  $m/n$    &$4$    & 5  &  6\\
 \hline
 $4$  & 7   &   &  \\
 $5$  & 10  &   13 & \\
 $6$  & 13  &  17  & 21
 \end{tabular}}
\begin{enumerate}gin{itemize}gskip 

\noindentdent
 All the entries, except for 21 ($m = n = 6$),
 are the same as for binary bifix-free languages.
 In case $m = n = 6$, 
 the complexity of union of binary factor-free languages is 21, that is $mn - (m+n) - (m-3)$.
 Thus it is the same as our lower bound.
 This is confirmed by the partial
 enumeration for $m = 6$ and $n = 7$,
 where we used
 a partial list of binary factor-free automata for $n = 7$.
 
 After quite a few unsuccessful attempts
 to get a larger value by the union of binary factor-free languages,
 we conjecture that $mn - (m+n) - (m-3)$
 is an upper bound if $m\le n$.
\end{proof}

We now turn our attention to subword-free languages.
The next theorem gives tight bounds for all four boolean operations
and shows that the bounds cannot be met using a fixed alphabet.

\begin{enumerate}gin{theorem}[\bf Boolean Operations: Subword-Free Languages]\label{thm:subword}
 Let $K$ and $L$  be subword-free languages
 over an alphabet $\Sigmama$
 with $\kappa(K)=m$ and $\kappa(L)=n$,  
 where $m,n\ge4$.
Then\\
1. $\kappa(K\cup L), \kappa(K\oplus L)\le mn-(m+n)$,
                 and the bound is tight if $|\Sigmama|\ge m+n-3$; \\
2. $\kappa(K\cap L)\le mn-3(m+n-4)$,
                 and the bound is tight if $|\Sigmama|\ge m+n-7$;\\
3. $\kappa(K{settable}tminus L)\le mn-(2m+3n-9)$,
                 and the bound is tight if $|\Sigmama|\ge m+n-6$.\\
Moreover, the bounds cannot be met for smaller alphabets.
\end{theorem}

\begin{enumerate}gin{proof}
 Since subword-free languages are bifix-free,
 all the upper bounds apply.
 To prove tightness, let 
 $\Sigmama=\{a,b,c\}\cup\{d_i\mid 3\le i \le m-1\}\cup\{e_j\mid 3\le j \le n-1\} $.
 Consider the languages $K$ and $L$ defined by the following quotient equations:

 \begin{enumerate}gin{tabular}{lcl}
 $K_1$ &=& $(a\cup b \cup e_3\cup\cdots\cup e_{n-1})K_2
 \cup \begin{enumerate}gin{itemize}gcup_{i=3}^{m-1}d_iK_i$,\\
 $K_i$ &=& $ aK_{i+1}\cup d_{i+1}K_{m-1}$ 
                               
            $i=2, 3,\ldots, m-3$,\\
 $K_{m-2}$&=&$(a\cup b\cup d_{m-1}\cup e_3\cup e_4\cup\cdots\cup e_{n-1})K_{m-1}$,\\
 $K_{m-1}$&=&$\eps$,\\
 $K_{m}$&=&$\emptysettyset$, \\
 &&\\
 $L_1 $&=& $(a\cup c\cup  d_3\cup \cdots\cup d_{m-1})L_2
 \cup \begin{enumerate}gin{itemize}gcup_{j=3}^{n-1}e_jL_j$,\\
 $L_j$ &=&  $aL_{j+1}\cup e_{j+1}L_{n-1}$ 
                   \qquad \qquad \qquad \qquad \quad $j=2, 3,\ldots, n-3$,\\
 $L_{n-2}$&=&$(a\cup c\cup e_{n-1}\cup d_3\cup d_4\cup\cdots\cup d_{m-1})L_{n-1}$,\\
 $L_{n-1}$&=&$\eps$,\\
 $L_{n}$&=&$\emptysettyset$. 
 \end{tabular}

 \begin{enumerate}gin{itemize}gskip
 \noindentdent
 Figure~\ref{fig:booleansub}
 shows the quotient automata for languages $K$ and $L$ if $m=5$ and $n=6$.
 All the omited transitions go to the empty states $m$ and $n$.
\begin{enumerate}gin{figure}[t]
 \begin{enumerate}gin{center}
 \input booleansub.eepic
 \end{center}
 \caption{Subword-free witness languages for boolean operations; $m=5$, $n=6$.}
 \label{fig:booleansub}
 \end{figure}
 
 Let us show that languages 
 $K$ and $L$ are subword-free. 
 For this purpose, let
 $$\Gamma=\{a,b,e_3,e_4,\ldots, e_{n-1}\}, \text{ and }
 \Delta=\{d_3,d_4,\ldots, d_{m-1}\}.$$
 Notice that no word in $\Gamma^*$ of length less than $m-2$ is in $K$.
 Now let $w$ be a word in language $K$. 
 Then word $w$ either contains no letter from $\Delta$, 
 or  contains at most two such letters.
 If $w$ contains no letter from $\Delta$,
 then $w$ is a word in $\Gamma^*$
 of length $m-2$, and so no its proper subword is in $K$.
 If $w$ contains exactly one letter from $\Delta$, then
   either $w=ud_i$ for some word $u$  in $\Gamma^*$ of length $i-2$,
   or $w=d_iv$ for some word $v$  in $\Gamma^*$ of length $m-1-i$.
 In both cases, no proper subword of $w$ is in language $K$.
 Finally, if $w$ contains two letters from $\Delta$,
 then $w=d_ia^{k}d_{i+k+1}$ where $k\ge 0$ and $3\le i <i+k+1\le m-2$.
 No proper subword of such a word is in language $K$.
 This means that language $K$ is subword-free.
 The proof for language $L$ is similar.

 Figure~\ref{fig:boolean_sbw_prod} depicts
 the cross-product automaton of the dfa's
 for languages $K$ and $L$ defined in Figure~\ref{fig:booleansub},
 where we show only the transitions necessary
 to prove reachability and those caused by $b$ and $c$.
 In the cross-product automaton,
 states in the first row and the first column, except for the initial state   $(1,1)$,
 are unreachable. Now consider the remaining states.
 All the states in the second row and the second column
 are reached from  $(1,1)$ by symbols in $\Sigmama$.
 Each other state  is reached from a state
 in the second row or second column by a word in $a^*$.

 \begin{enumerate}gin{figure}[t]
 \begin{enumerate}gin{center}
 \input KunionL.eepic
 \end{center}
 \caption{Reachability in the cross-product automaton
          for the union of languages from Figure~\ref{fig:booleansub}
          and transitions by $b$  and $c$.}
 \label{fig:boolean_sbw_prod}
 \end{figure}

 For union,
 all the states in row $m-1$ and in column $n-1$
 are accepting, and the three states 
 $(m,n-1)$, $(m-1,n-1)$, and $(m-1,n)$ 
 accept only $\eps$, and so
are equivalent.
 These three states are distinguishable from all other accepting states,
 since each of the other accepting states accepts at least one non-empty word. 
 Now let $(i,j)$ and $(k,\ell)$ be two distinct states 
 other than the three states accepting only word $\eps$.
 First assume that $i<k$.
 If $i=m-1$, then 
 state $(i,j)$ is accepting while  state $(k,\ell)$ is rejecting.
 If $i\le m-2$, then $a^{m-2-i}b$ is accepted from  state  $(i,j)$,
 but not from  state  $(k,\ell)$.
 Symmetrically, if $j<\ell$,
 then either $\eps$ or $a^{n-2-j}c$ distinguishes the two states.
 Therefore all the  $mn-(m+n)$ 
 states are pairwise distinguishable.

 For symmetric difference,  $(m-1,n-1)$ is empty;
 the rest of the proof is the same as for union.

 For intersection,
 the only accepting state is $(m-1,n-1)$,
 and all the rejecting states in the last two rows and last two columns are empty.
 Next, the word $a$ is accepted only from state $(m-2,n-2)$,
 the word $d_i$ ($3\le i \le n-2$)
 is accepted only from state $(i-1,n-2)$,
 while the word $e_j$ ($3\le i \le m-2$),
 only from state $(m-2,j-1)$.
 This means that for each state $(i,j)$,
 there exists a word in 
 $a^*(a\cup d_3 \cup \cdots \cup d_{m-2}\cup e_3 \cup \cdots \cup e_{n-2})$
 that is accepted only from $(i,j)$.
 So we get $mn-3(m+n-4)$ pairwise distinguishable states.
 Notice, that here we do not use transitions by symbols $b,c,d_{m-1},e_{n-1}$,
 and so we can simply omit these symbols
 to get witness languages over an alphabet of size $m+n-7$.

 For difference,
 all the states in row $m-1$, except for state $(m-1,n-1)$,
 are accepting and accept $\eps$.
 All the states in the last row, as well as state $(m-1,n-1)$,
 are empty, and states $(i,n-1)$ and $(i,n)$ with $2\le i \le m-2$
 are equivalent.
 States in different rows (up to row $m-1$)
 are distinguished by a word in $a^*b$.
 States in row $m-2$ are distinguished 
 by a word in $a\cup e_3\cup e_4 \cup \cdots \cup e_{n-2}$ 
 because $a$ distinguishes states $(m-2,n-2)$ and $(m-2,n-1)$,
 and if $2\le j<\ell\le n-1$ and $j\neq n-2$, 
 then word $e_{j+1}$ is not accepted from $(m-2,j)$ 
 but is accepted from $(m-2,\ell)$.
 Next, states $(i,n-2)$  and $(i,n-1)$ with $2\le i \le m-3$
 are distinguished by $d_{i+1}$.
 Finally, if two distinct states are in the same row,
 then there is a word in $a^*$,
 by which the two states either go to two distinct states in row $m-2$, or
 to two states $(i,n-2)$ and $(i,n-1)$ with $2\le i \le m-3$. 
 In both cases the resulting states are distinguishable,
 which proves the distinguishability of $mn-(2m+3n-9)$ states.
 Notice that now we do not use transitions by $c, d_{m-1}, e_{n-1}$,
 and so the bound is met for an alphabet of size $m+n-6$.

 We now show that the upper bounds cannot be met using smaller alphabets.
 Let the quotients of $K$ and $L$  be 
 $K=K_1,K_2,\dots,K_{m-2},K_{m-1}=\eps, K_{m}=\emptyset,$  and
 $L=L_\eps=L_{1},L_{2},\dots,L_{n-2},L_{n-1}=\eps, L_{n}=\emptyset,$
 ordered  as in Proposition~\ref{prop:finite}. 
 By Lemma~\ref{lem:letter},
 all the quotients of the form $K_2\cup L_i$ or $K_j\cup L_2$
 must  be reached by letters if the bound is to hold,
 and this is impossible if the size of the alphabet
 is  smaller than the number of such quotients. 
\end{proof}

{settable}ction{Product and Star}
\label{***prod}

The complexity of product of prefix-free languages is $m+n-2$~\cite{HSW09}.
For suffix-free languages,
the complexity  is $(m-1)2^{n-1}+1$~\cite{HaSa09}. 
Since bifix-free languages are prefix-free, 
and the witness prefix-free languages $a^{m-2}$ and $a^{n-2}$
are also subword-free, and we have the following result.

\begin{enumerate}gin{theorem}[\bf Product]\label{thm: prod1}
 If $K$ and $L$ are bifix-free with $\kappa(K)=m$ and $\kappa(L)=n$,
 where $m,n\ge2$,
 then $\kappa(KL)\leq m+n-2$.
 Furthermore, there are unary subword-free languages that meet this bound.
\end{theorem}

The complexity of star is $n$ for prefix-free languages~\cite{HSW09}, 
and $2^{n-2}+1$ for suffix-free languages  \cite{HaSa09}. 
We now extend these results to bifix-, factor-, and subword-free languages.
The quotient of $L^*$ by $\eps$ is $L^*=\eps\cup LL^*$, 
and the  following formula holds for a quotient of $L^*$ 
by a non-empty word $w$~\cite{Brz10}:
$$
    (L^*)_w=(L_w\cup \begin{enumerate}gin{itemize}gcup_{\substack{w=uv\\ \;\;u,v\in\Sigma^+}}
            (L^*)_u ^\eps L_v)L^*.
$$

\begin{enumerate}gin{theorem}[\bf Star]\label{thm: star1}
 If $L$ is bifix-free with $\kappa(L)=n$,
 where $n\ge3$,
 then $\kappa(L^*)\leq n-1$. 
 Furthermore, there are binary subword-free languages that meet this bound.
\end{theorem}

\begin{enumerate}gin{proof}
 Assume that $L$ is bifix-free.
 Then it is prefix-free, has only one accepting quotient, namely $\eps$,
 and has the empty quotient, by Proposition~\ref{prop:pf}.
 Moreover, since $L$ is suffix-free,
 the quotient $L$ is uniquely reachable by $\eps$, by Proposition~\ref{prop:sf}.

 Let $L_w$ be a  non-empty quotient of $L$ by a non-empty word $w$.
 Let us show that $(L^*)^\eps_u=\emptysettyset$
 for every proper non-empty prefix $u$ of $w$.
 Assume for contradiction 
 that $\eps \in (L^*)_u$, where
 $w=uv$ for some non-empty words \mbox{$u$ and $v$.}
 Then $u \in L^*$,
 and  so there exist words $x$ in $L$ and  $y$ in $L^*$ such that $u=xy$.
 This gives $L_w=L_{xyv}=\eps_{yv}=\emptysettyset$
 because $x\in L$ implies  $L_x=\eps$. 
 This is a contradiction,
 and so we must have $(L^*)_u^\eps=\emptysettyset$.
 Hence, if $L_w$ is  non-empty,
 then $(L^*)_w=L_wL^*$, by the equation above. 
 Now if $L_w$ is accepting, then $L_w=\eps$,
 and so $(L^*)_w=L^*=(L^*)_\eps$.
 There are $n-2$ choices for 
 rejecting and non-empty quotients $L_w$.
 But, for a non-empty word $w$, we have $L_w\neq L$
 since $L$ is uniquely reachable by $\eps$.
 This reduces the number of choices to $n-3$ (since we have $n\ge3$).
 If $L_w=\emptyset$, then by the  observation above,
 $(L^*)_w = (L^*)^\eps_u L_v L^*$,
 where $w=uv$ and $v$ is the shortest word such that $L_v\neq \emptyset$.
 Such a quotient is either empty or has already been counted.
 In total, there are at most $n-1$ quotients of $L^*$.

 The  subword-free language $a^{n-2}$ over the alphabet $\{a,b\}$
 meets the bound since the language $(a^{n-2})^*$ has $n-2$ quotients
 of the form $a^{n-2-i}(a^{n-2})^*$ for $i=1,2,\dots,n-2$,
 and it has the empty quotient, for a total of $n-1$.
\end{proof}

{settable}ction{Reversal}
\label{***rev}

The last operation we consider is reversal. 
In \cite{HaSa09,HSW09} it was shown 
that the complexity of reversal is $2^{n-2}+1$ for suffix-free or prefix-free languages.
We show that this bound can be reduced  for bifix-free languages.
We use the standard method of reversing 
the quotient dfa ${\mathcal D}$ of $L$ to obtain an nfa ${\mathcal N}$ for $L^R$, 
and then we use  subset construction to find the dfa ${\mathcal D}^R$ for $L^R$.

\begin{enumerate}gin{theorem}[\bf Reversal: Bifix- and Factor-Free Languages]\label{thm:rev1}
 If $L$ is a bifix-free language  with $\kappa(L)=n$,
 where $n\ge3$,
 then  $\kappa(L^R)\leq 2^{n-3}+2$.
 Moreover, there exist ternary factor-free languages that meet this bound.
\end{theorem}

\begin{enumerate}gin{proof}
 If $L$ is bifix-free, then so is $L^R$.
 Since $L$ is prefix-free,
 it has exactly one accepting quotient, $\eps$, and also has the empty quotient.
 
 Consider the quotient automaton ${\mathcal D}$ for $L$,
 and remove the empty quotient and all the transitions to the empty quotient.
 Reverse this incomplete dfa
 to get an $(n-1)$-state nfa ${\mathcal N}$ for $L^R$.
 Apply the subset construction to ${\mathcal N}$ to get
 a dfa ${\mathcal D}^R$ for $L^R$.
 The initial state of dfa ${\mathcal D}^R$
 is the singleton set $\{f\}$,
 where $f$ is the $\eps$ quotient in quotient automaton ${\mathcal D}$.
 No other subset containing state $f$ is reachable in ${\mathcal D}^R$
 since no transition goes to state $f$ in nfa ${\mathcal N}$.
 This gives at most $2^{n-2}+1$ reachable states.
 However, language $L^R$ is prefix-free,
 and so all the accepting states of ${\mathcal D}^R$
 accept only the empty word,
 and can be merged into one state.
 Hence $\kappa(L^R)\leq 2^{n-3}+2$.
 
 If $n=3$ or $n=4$, then factor-free languages $a$ and $aa$, respectively,
 meet the bounds.
 
If $n\ge5$, then  consider the language $L=cKc$,
 where $K$  is  a regular language over the alphabet  $\{a,b\}$
 with $\kappa(K)=n-3$
 meeting the upper bound $2^{n-3}$ for  reversal \cite{Seb10}.
 The quotient automaton of  $L$ without the empty state 
 is shown in  Figure~\ref{fig:seb3}.
 \begin{enumerate}gin{figure}[t]
 \begin{enumerate}gin{center}
 \input sebej3.eepic
 \end{center}
 \caption{The ternary factor-free language meeting the $2^{n-3}+2$ bound for reversal.}  
 \label{fig:seb3}
 \end{figure}
 
 By Proposition~\ref{prop:construct},
 language $L$ is factor-free, and $\kappa(L)=n$.
 Since $\kappa(K^R)=2^{n-3}$,
 there exists a set $S$ of $2^{n-3}$ words over $\{a,b\}$
 that define distinct quotients of language $K^R$.
 Then the quotients of  $cK^Rc$
 by $2^{n-3}+2$ words $\eps$, $cw$ with $w\in S$,
 and $cuc$ for some word $u$ in $K^R$,
 are distinct as well.
 This gives $\kappa(L^R)=2^{n-3}+2$.
\end{proof}

\begin{enumerate}gin{theorem}[\bf Reversal: Subword-Free Languages]\label{thm:rev_sbw}
 If $L$ is a subword-free language  over an alphabet $\Sigmama$
 with $\kappa(L)=n$,
 where $n\ge4$,
 then $\kappa(L^R) \le 2^{n-3}+2$.
 The bound is tight if $|\Sigmama|\ge2^{n-3}-1$,
 but cannot be met for smaller alphabets.
 The bound cannot be met if  $L$
 contains a word of length at least 3.
\end{theorem} 

\begin{enumerate}gin{proof}
 Suppose $L $ is a subword-free language such that $\kappa(L^R) = 2^{n-3}+2$.
 Let ${\mathcal D}=(Q,\Sigma,\delta,s,f)$ be the quotient dfa
 of  $L$ with  $Q=\{s,q_1,\dots,q_{n-3},f,e\}$ as the state set,
 where $e$ and $f$ correspond to the quotients $\emptyset$ and $\eps$.
 Construct a dfa ${\mathcal D}^R$ for $L^R$
 as in the proof of Theorem \ref{thm:rev1}.
 If $\kappa(L^R) = 2^{n-3}+2$,
 then the state $\{q_1,q_2,\dots,q_{n-3}\}$ must be reachable.
 Therefore there must exist a non-empty word $v$ such that,
 for all $q_i$, we have ${\delta}(q_i, v)=f$.
 Now suppose there exists a word $w$ in $L$ such that $|w|>2$.
 Let $w=abx$ where $a,b \in \Sigma$ and $x \in \Sigma^+$.
 Also suppose $\delta(s, a)=q_i$ and $\delta(q_i, b)=q_j$.
 Then we have $av, abv\in L$, showing that $L$ is not subword-free,
 which is a contradiction.
 Hence, if any word in $L$ has length at least 3,
 then $\kappa(L^R) < 2^{n-3}+2$.
 Now note that, if all the words in $L$ have length at most 2,
 the only possible quotients of $L^R$
 are $L^R$, $(L^R)_a$ for all $a \in \Sigma$, $\eps$, and $\emptyset$.
 Therefore $\kappa(L^R) \leq |\Sigma| + 3$,
 and the second claim follows.

 Now consider tightness.
 If $n=3$, then the bound is met
 by the unary subword-free language $a$.
 Let $n\ge 4$  and $\ell=2^{n-3}-1$.
 Also let $\Sigma=\{a_1,a_2,\dots,a_\ell\}$, and let
 $S_1, S_2, \ldots, S_\ell$ 
 be all the non-empty subsets of $\{1,2,\ldots,n-3\}$.
 Now let
 $$
    L^R= a_1 (\begin{enumerate}gin{itemize}gcup_{j\in S_1} a_j) \cup 
         a_2 (\begin{enumerate}gin{itemize}gcup_{j\in S_2} a_j) \cup \cdots \cup
         a_\ell (\begin{enumerate}gin{itemize}gcup_{j\in S_\ell} a_j).
 $$
 Since $L^R$ only contains two-letter words,
 languages $L^R$ and $L$ are subword-free.
 The quotients of $L^R$ are
 $L^R$,
 $(L^R)_{a_i}=\begin{enumerate}gin{itemize}gcup_{j\in S_i} a_j$ for  $i=1,2,\ldots,\ell$,
 $ \eps$, and 
 $\emptysettyset$.
 Therefore $\kappa(L^R)=l+3=2^{n-3}+2$. 
 But for $L$, the only possible and distinct quotients are
 $L$,
 $L_{a_i}$ for $i=1,2,\ldots,n-3$,
 $\eps$, and $\emptysettyset$.
 Thus $\kappa(L)=n$.
\end{proof}

{settable}ction{Conclusions}
\label{***conc}

Our  results are summarized in Tables~\ref{tab:bool} and~\ref{tab:gen}, 
where ``B-, F-free'' stands for  bifix-free and factor-free, 
and ``S-free'' for subword-free.
The bounds for operations on prefix-free languages are from \cite{HaSa09,JiKr10},
for operations  on suffix-free languages 
from \cite{Cmo11,HSW09,JiOl09},
and those for regular languages, from~\cite{Lei81,Mas70,YZS94}.
For languages over a unary alphabet $\Sigma=\{a\}$, 
the concepts prefix-, suffix-, factor-, and subword-free coincide, 
and $L$ is free with  $\kappa(L)=n$ if and only if $L=\{a^{n-2}\}$.

In the case of subword-free languages 
the size of the alphabet cannot be decreased.
In the other cases,  whenever the size of the alphabet is greater than~2,
we do not know whether or not the bounds are tight for smaller alphabets.

The fact that our bounds usually  apply only when $m,n\ge3$ 
is not a limitation, 
since bifix-free languages with smaller quotient complexities are simple. 
For $n=1$, we have only $\emptyset$,
for $n=2$, only $\eps$, and for $n=3$, a subset of $\Sigma$. 
The~complexities of operations on such languages can be computed directly.

{settable}tlength{\extrarowheight}{2pt}
\begin{enumerate}gin{table}[ht]
\begin{enumerate}gin{center}
\begin{enumerate}gin{scriptsize}
$
\begin{enumerate}gin{array}{| l | cc | cc | cc | }  
\hline
    &  K\cup L,  K \oplus L  &|\Sigma|   & K\cap L      &|\Sigma|   & K{settable}tminus L &|\Sigma|\\
\hline\hline
\txt{free unary} &\max(m,n)  &         & m=n          &         & m            &    \\
\hline\hline
\txt{prefix}     &mn-2       & 2       & mn-2(m+n-3)  &  2      & mn-(m+2n-4)  & 2  \\
\hline\hline 
\txt{suffix}     &mn-(m+n-2) & 2       & mn-2(m+n-3)  & 2       & mn-(m+2n-4)  & 2  \\
\hline\hline
\txt{B-, F-free} &mn-(m+n)   & 3       & mn-3(m+n-4)  & 2       & mn-(2m+3n-9) & 2  \\
\hline\hline
\txt{S-free}     &mn-(m+n)   & s_1     & mn-3(m+n-4)  & s_2     & mn-(2m+3n-9) & s_3\\
\hline\hline
\txt{regular }   &mn         & 2       & mn           & 2       & mn           &  2 \\
\hline
\end{array}
$
\end{scriptsize}
\end{center}
\caption{Complexities of boolean operations on free languages; 
           $s_1=m+n-3$, $s_2=m+n-7,s_3=m+n-6$.}
\label{tab:bool}
\end{table}

\begin{enumerate}gin{table}[ht]
\begin{enumerate}gin{center}
\begin{enumerate}gin{scriptsize}
$
\begin{enumerate}gin{array}{| l |cc|cc|cc|}
\hline
                  &  KL         &|\Sigma|& L^*          &|\Sigma|&  L^R       &|\Sigma|       \\
\hline\hline
\txt{free unary}  & m+n-2          &   & n               &   & 2^{n-2}+1  &             \\
\hline\hline
\txt{prefix-free} & m+n-2          & 1 & n               & 2 & 2^{n-2}+1  & 3           \\
\hline\hline 
\txt{suffix-free} & (m-1)2^{n-1}+1 & 3 & 2^{n-2}+1       & 2 & 2^{n-2}+1  & 3           \\
\hline\hline 
\txt{B-, F-free}  & m+n-2          & 1 & n-1             & 2 &\ 2^{n-3}+2 & 3           \\
\hline\hline
\txt{S-free}      & m+n-2          & 1 & n-1             & 2 & 2^{n-3}+2  &\ 2^{n-3}-1 \ \\
\hline\hline
\txt{regular}     & (2m-1)2^{n-1}  & 2 &\ 2^{n-1}+2^{n-2}& 2 & 2^n        &  2           \\
\hline
\end{array}
$
\end{scriptsize}
\end{center}
\caption{Complexities of product, star, and reversal of free languages.}
\label{tab:gen}
\end{table}

\vskip-60pt

\providecommand{\noopsort}[1]{}
\begin{enumerate}gin{thebibliography}{10}

\begin{enumerate}gin{itemize}bitem{AnBr09}
Ang, T., Brzozowski, J.:
\newblock Languages convex with respect to binary relations, and their closure
  properties.
\newblock Acta Cybernet. \textbf{19}(2) (2009)  445--464

\begin{enumerate}gin{itemize}bitem{BGN10}
Bassino, F., Giambruno, L., Nicaud, C.:
\newblock Complexity of operations on cofinite languages.
\newblock In L\'opez-Ortiz, A., ed.: Proceedings of the 9th Latin American
  Theoretical Informatics Symposium, $($LATIN\/$)$. Volume 6034 of LNCS,
  Springer (2010)  222--233

\begin{enumerate}gin{itemize}bitem{BPR10}
Berstel, J., Perrin, D., Reutenauer, C.:
\newblock Codes and Automata (Encyclopedia of Mathematics and its
  Applications).
\newblock Cambridge University Press (2010)

\begin{enumerate}gin{itemize}bitem{Brz64}
Brzozowski, J.:
\newblock Derivatives of regular expressions.
\newblock J. ACM \textbf{11}(4) (1964)  481--494

\begin{enumerate}gin{itemize}bitem{Brz10}
Brzozowski, J.:
\newblock Quotient complexity of regular languages.
\newblock In Dassow, J., Pighizzini, G., Truthe, B., eds.: Proceedings of the
  11th International Workshop on Descriptional Complexity of Formal Systems,
  Magdeburg, Germany, Otto-von-Guericke-Universit{\"a}t (2009)  25--42. To
  appear in J. Autom. Lang. Comb. (Extended abstract at {\tt
  http://arxiv.org/abs/0907.4547}).

\begin{enumerate}gin{itemize}bitem{BJL10}
Brzozowski, J., Jir{\'a}skov{\'a}, G., Li, B.:
\newblock Quotient complexity of ideal languages.
\newblock In L\'opez-Ortiz, A., ed.: Proceedings of the 9th Latin American
  Theoretical Informatics Symposium, $($LATIN\/$)$. Volume 6034 of LNCS,
  Springer (2010)  208--211

\begin{enumerate}gin{itemize}bitem{BJZ10}
Brzozowski, J., Jir{\'a}skov{\'a}, G., Zou, C.:
\newblock Quotient complexity of closed languages.
\newblock In Ablayev, F., Mayr, E.W., eds.: Proceedings of the 5th
  International Computer Science Symposium in Russia, $($CSR\/$)$. Volume 6072
  of LNCS, Springer (2010)  84--95

\begin{enumerate}gin{itemize}bitem{CCSY01}
C\^ampeanu, C., Culik~II, K., Salomaa, K., Yu, S.:
\newblock State complexity of basic operations on finite languages.
\newblock In Boldt, O., J{\"u}rgensen, H., eds.: Revised Papers from the 4th
  International Workshop on Automata Implementation, $($WIA\/$)$. Volume 2214
  of LNCS, Springer (2001)  60--70

\begin{enumerate}gin{itemize}bitem{Cmo11}
Cmorik, R.:
\newblock State complexity of basic operations on binary and ternary
  suffix-free languages.
\newblock Manuscript (2011)

\begin{enumerate}gin{itemize}bitem{HaSa08}
Han, Y.S., Salomaa, K.:
\newblock State complexity of union and intersection of finite languages.
\newblock Internat.\ J.\ Found.\ Comput.\ Sci. \textbf{19}(3) (2008)  581--595

\begin{enumerate}gin{itemize}bitem{HaSa09}
Han, Y.S., Salomaa, K.:
\newblock State complexity of basic operations on suffix-free regular
  languages.
\newblock Theoret. Comput. Sci. \textbf{410}(27-29) (2009)  2537--2548

\begin{enumerate}gin{itemize}bitem{HSW09}
Han, Y.S., Salomaa, K., Wood, D.:
\newblock Operational state complexity of prefix-free regular languages.
\newblock In {\'E}sik, Z., F{\"u}l{\"o}p, Z., eds.: Automata, Formal Languages,
  and Related Topics, University of Szeged, Hungary (2009)  99--115

\begin{enumerate}gin{itemize}bitem{JiKr10}
Jir\'askov\'a, G., Krausov\'a, M.:
\newblock Complexity in prefix-free regular languages.
\newblock In McQuillan, I., Pighizzini, G., Trost, B., eds.: Proceedings of the
  12th International Workshop on Descriptional Complexity of Formal Systems
  $($DCFS\/$)$, University of Saskatchewan (2010)  236--244

\begin{enumerate}gin{itemize}bitem{JiOl09}
Jir\'askov\'a, G., Olej\'ar, P.:
\newblock State complexity of union and intersection of binary suffix-free
  languages.
\newblock In Bordihn, H., Freund, R., Holzer, M., Kutrib, M., Otto, F., eds.:
  Proc. of the Workshop on Non-Classical Models for Automata and Applications
  $($NCMA\/$)$, Austrian Computer Society (2009)  151--166

\begin{enumerate}gin{itemize}bitem{JuKo97}
J\"{u}rgensen, H., Konstantinidis, S.:
\newblock Codes.
\newblock In Rozenberg, G., Salomaa, A., eds.: Handbook of Formal Languages,
  Volume 1: Word, Language, Grammar.
\newblock Springer (1997)  511--607

\begin{enumerate}gin{itemize}bitem{Lei81}
Leiss, E.:
\newblock Succinct representation of regular languages by boolean automata.
\newblock Theoret. Comput. Sci. \textbf{13} (2009)  323--330

\begin{enumerate}gin{itemize}bitem{Mas70}
Maslov, A.N.:
\newblock Estimates of the number of states of finite automata.
\newblock Dokl. Akad. Nauk SSSR \textbf{194} (1970)  1266--1268 (Russian).
  English translation: Soviet Math. Dokl. {\bf 11} (1970) 1373--1375.

\begin{enumerate}gin{itemize}bitem{Mir66}
Mirkin, B.G.:
\newblock On dual automata.
\newblock Kibernetika (Kiev) \textbf{2} (1966)  7--10 (Russian). English
  translation: Cybernetics {\bf 2} (1966) 6--9.

\begin{enumerate}gin{itemize}bitem{Per90}
Perrin, D.:
\newblock Finite automata.
\newblock In van Leewen, J., ed.: Handbook of Theoretical Computer Science.
  Volume~B.
\newblock Elsevier (1990)  1--57

\begin{enumerate}gin{itemize}bitem{PiSh02}
Pighizzini, G., Shallit, J.:
\newblock Unary language operations, state complexity and $\text{J}$acobsthal's
  function.
\newblock Internat.\ J.\ Found.\ Comput.\ Sci. \textbf{13} (2002)  145--159

\begin{enumerate}gin{itemize}bitem{Shy01}
Shyr, H.J.:
\newblock Free Monoids and Languages.
\newblock Hon Min Book Co, Taiwan (2001)

\begin{enumerate}gin{itemize}bitem{ShTh74}
Shyr, H.J., Thierrin, G.:
\newblock Hypercodes.
\newblock Inform. and Control \textbf{24} (1974)  45--54

\begin{enumerate}gin{itemize}bitem{Thi73}
Thierrin, G.:
\newblock Convex languages.
\newblock In Nivat, M., ed.: Automata, Languages and Programming.
\newblock North-Holland (1973)  481--492

\begin{enumerate}gin{itemize}bitem{Seb10}
\v{S}ebej, J.:
\newblock Reversal of regular languages and state complexity.
\newblock In Pardubsk\'a, D., ed.: Proc. 10th ITAT, \v{S}af\'arik University,
  Ko\v{s}ice (2010)  47--54

\begin{enumerate}gin{itemize}bitem{Yu97}
Yu, S.:
\newblock Regular languages.
\newblock In Rozenberg, G., Salomaa, A., eds.: Handbook of Formal Languages.
  Volume~1.
\newblock Springer (1997)  41--110

\begin{enumerate}gin{itemize}bitem{Yu01}
Yu, S.:
\newblock State complexity of regular languages.
\newblock J. Autom. Lang. Comb. \textbf{6} (2001)  221--234

\begin{enumerate}gin{itemize}bitem{YZS94}
Yu, S., Zhuang, Q., Salomaa, K.:
\newblock The state complexities of some basic operations on regular languages.
\newblock Theoret. Comput. Sci. \textbf{125} (1994)  315--328

\end{thebibliography}

\end{document}