\documentclass[envcountsame]{llncs}
 
\begin{document}

\title{ The Parameterized Complexity of \\
	 Intersection and Composition Operations on \\
	 Sets of Finite-State Automata }
\author{H.\ Todd Wareham}

\institute{Department of Computer Science, Memorial University of Newfoundland,
             \\ St. John's, NF, Canada A1B 3X5 \\
	     \email{harold@cs.mun.ca}
}

\maketitle
%
\begin{abstract}
This paper uses parameterized complexity analysis
to delimit  possible non-polynomial time algorithmic behaviors for the 
finite-state acceptor intersection and  finite-state transducer intersection and
composition problems. One important result derived as part of these analyses is
the first proof of the $NP$-hardness of the finite-state transducer composition
problem for both general and $p$-subsequential transducers.
\end{abstract}

\section{Introduction}

Certain applications of finite-state automata are most naturally stated in 
terms of the intersection or composition of a set of automata \cite{KK94,Kur94}.
One approach to solving these problems is to use state Cartesian product 
constructions \linebreak \cite[pp.\ 59-60]{HU79} to build the automaton associated with
the intersection or composition and then answer the query relative to a 
determinized and/or minimized version of that automaton. Though such
queries as emptiness or membership can typically be answered in time and space
linear in the size of the derived \linebreak automaton,  the automaton may have 
$O(|Q|^{|A|})$ states, where $|A|$ is the number of automata in the
set and $|Q|$ is the maximum number of states in any automaton in the set.
This is to be expected, as many problems on sets of automata are 
$NP$-hard and hence do not have polynomial-time algorithms unless $P = NP$.
However, are there other 
non-polynomial time algorithmic options for solving such problems, {\em e.g.},
an algorithm
whose non-polynomial time complexity term is purely a function of $|Q|$
and $|\Sigma|$, where $|\Sigma|$ is the size of the language-alphabet? Knowledge
of such options would be useful in practice for choosing the most \linebreak efficient 
algorithm in situations in which one or more of the characteristics of the 
problem are of bounded value,
{\em e.g.}, $|Q| \leq 4$ and $|\Sigma| \leq 26$.

In this paper, techniques from the theory of parameterized computational
complexity \cite{DF99} are used to determine part of the range of possible non-polynomial
time algorithmic behaviors for the finite-state acceptor intersection
and finite-state transducer intersection and composition problems. These 
analyses generalize and simplify results given in \cite{War99}. One important 
result derived as part of these analyses is the first proof of the 
$NP$-hardness of the finite-state transducer composition problem
for both general and $p$-subsequential transducers.

\subsection{Terminology}

A {\bf finite state acceptor (FSA)} is a 5-tuple $\langle Q, \Sigma, 
\delta, s, F \rangle$ where $Q$ is a set of states, $\Sigma$ is an 
alphabet, $\delta: Q \times \{\Sigma \cup \{\epsilon\}\} \times Q$ is 
a transition relation, $s \in Q$ is the start state, and $F \subseteq 
Q$ is a set of final states.  If $\delta$ has no entries of the form 
$(q,\epsilon,q')$
and is also a function, {\em i.e.}, for each $q \in Q$ and $s \in
\Sigma$ there is at most one state $q' \in Q$ such that $(q,s,q') \in 
\delta$, the FSA is a {\bf deterministic finite-state acceptor (DFA)}.

A {\bf finite state transducer (FST)} is a 6-tuple $\langle Q, \Sigma_i, 
\Sigma_o, \delta, s, F \rangle$ where $Q$ is a set of states, $\Sigma_i$
and $\Sigma_o$ are the input and output alphabets, respectively,  
$\delta: Q \times \Sigma_i^* \times \Sigma_o^*
\times Q$ is a transition relation, $s \in Q$ is the 
start state, and $F \subseteq Q$ is a set of final states. 
There are several possible definitions of determinism  for FST; types of 
interest here are:

\begin{itemize}
\item{
{\bf $i$-Deterministic FST (sequential FST \cite{Moh97})}: For each 
$q \in Q$ and $x \in \Sigma_i^*$, there is at most one $y \in \Sigma_o^*$
and $q' \in Q$ such that $(q,x,y,q') \in \delta$. 
}
\item{
{\bf $i/o$-Deterministic FST}: For each $q \in Q$, $x \in \Sigma_i^*$ 
and $y \in \Sigma_o^*$, there is at most one $q' \in Q$ such that 
$(q,x,y,q') \in \delta$. 
}
\end{itemize}

\noindent
All FST in this paper are restricted to singleton labels that
are $\epsilon$-free, {\em i.e.}, $\delta: Q \times \Sigma_i \times \Sigma_o
\times Q$. Note that such FST 
will always produce output strings of the same length as the input string, 
\cite[Lemma 3.3]{KK94}. 

\section{Parameterized Complexity Analysis}

The theory of $NP$-completeness \cite{GJ79} proposes a class $NP$ of decision 
problems that is conjectured to properly include the class $P$ of decision
problems that have polynomial-time algorithms. For a given decision problem
$\Pi$, if 
every problem in $NP$ reduces\footnote{
Given decision problems $\Pi$ and $\Pi'$, $\Pi$ {\bf reduces to}
$\Pi'$, {\em i.e.}, $\Pi \leq_m \Pi'$, if there is an algorithm $A$ that
transforms an instance $x$ of $\Pi$ into an instance $y$ of $\Pi'$ such that 
$A$ runs in time polynomial in the size of $x$ and
$x$ has a solution if and only if $y$ has a solution, {\em i.e.}, $x \in \Pi$
if and only if $y \in \Pi'$.
}
to $\Pi$, {\em i.e.},  $\Pi$ is {\bf $NP$-hard}, then
$\Pi$ does not have a polynomial-time algorithm unless $P = NP$.

It may still be possible to solve $NP$-hard problems by
invoking non-polynomial time algorithms that are
effectively polynomial time because their non-polynomial
terms are purely functions of sets of aspects of the
problems that are of bounded size or value in instances of those
problems encountered in practice, where an \linebreak {\bf aspect} of a problem
is some (usually numerical) characteristic that can be \linebreak
derived from instances of that problem, {\em i.e.}, $|Q|$, $|\Sigma|$, and
$|A|$ in the case of finite-state automaton intersection and composition
problems. The theory of parameterized computational complexity 
\cite{DF99} provides explicit mechanisms for analyzing the effects
of both individual aspects and sets of aspects on problem complexity. 

\begin{definition}
A {\bf parameterized problem} $\Pi \subseteq \Sigma^* \times \Sigma^*$ has
instances of the form $(x,y)$, where $x$ is called the
{\bf main part} and $y$ is called the {\bf parameter}.
\end{definition}

\begin{definition}
A parameterized problem $\Pi$ is {\bf fixed-parameter tractable} if 
there  exists an  algorithm $A$ to determine if instance $(x,y)$ is in $\Pi$ 
in time \linebreak $f(y) \cdot |x|^{\alpha}$, where  $f : \Sigma^+ \mapsto \cal{N}$
is an arbitrary function and $\alpha$ is a constant independent of $x$
and $y$. 
\end{definition}

\noindent
Given a decision problem $\Pi$ with a parameter $p$, 
let $\langle p \rangle$-$\Pi$ denote the parameterized problem associated with $\Pi$ 
that is based on parameter $p$ and let $\langle p_c \rangle$-$\Pi$ denote the subproblem
of $\langle p \rangle$-$\Pi$ in which $p$ has value $c$ for some constant $c \geq 0$.
One can 
establish that a parameterized problem $\Pi$ is not fixed-parameter
tractable by using a  parametric reduction\footnote{
Given parameterized problems $\Pi$ and $\Pi'$, $\Pi$ {\bf parametrically
reduces to} $\Pi'$ if there is an algorithm 
$A$ that transforms an instance $(x,y)$ of $\Pi$ into an instance
$(x',y')$ of $\Pi'$ such that $A$ runs in time $f(y)|x|^{\alpha}$ time for an 
arbitrary function $f$ and a constant $\alpha$ independent of both $x$ and $y$,
$y' = g(y)$ for some arbitrary function $g$, and
$(x,y) \in \Pi$ if and only if $(x',y') \in \Pi'$.
}
to show that $\Pi$ is hard for any of the classes of the {\bf W-hierarchy} 
$= \{FPT, W[1], W[2],$ $\ldots, W[P], XP\}$ except 
$FPT$, where $FPT$ is the class of fixed-parameter tractable parameterized 
problems (see \cite{DF99} for details).
These classes are related as follows:
$$FPT \subseteq W[1] \subseteq W[2] \subseteq \cdots \subseteq W[P] 
      \subseteq \cdots \subseteq XP$$
If a parameterized problem is $\cal{C}$-hard for any class $\cal{C}$ in the 
$W$-hierarchy above $FPT$ then that problem is not fixed-parameter tractable 
unless $FPT = \cal{C}$.  

The following lemmas will be used in the analyses given in the next section.

\begin{lemma}
{ \bf [16, Lemma 2.1.25]}
Given decision problems $\Pi$ and $\Pi'$ with \linebreak parameters $p$ and $p'$,
respectively,  if $\Pi \leq_m \Pi'$ such that $p' = g(p)$ for an \linebreak
arbitrary function $g$, then $\langle p \rangle$-$\Pi$ parametrically reduces to
$\langle p' \rangle$-$\Pi'$.
%
\label{Lem_PCT_red_dp}
\end{lemma}

\begin{lemma}
{\bf [16, Lemma 2.1.35]}
Given a set $S$ of aspects of a decision problem $\Pi$, if $\Pi$
is $NP$-hard when the value of every aspect $s \in S$ is fixed, then
the parameterized problem $\langle S \rangle$-$\Pi$ is not in $XP$ unless $P = NP$.
%
\label{Lem_PCT_XP}
\end{lemma}

\section{Results}

The analyses in this section will focus on the following three problems:

\vspace*{0.07in}

\noindent
{\sc Bounded DFA Intersection} (BDFAI) \\
{\it Instance:}~~ A set $A$ of DFA over 
		   an alphabet $\Sigma$ and a positive integer $k$. \\
{\it Question:}~~ Is there a string $x \in \Sigma^k$ that is accepted by 
                   each DFA in $A$? 

\vspace*{0.07in}

\noindent
{\sc $i/o$-deterministic FST Intersection (FST-I)} \\
{\it Instance:}~~ A set $A$ of $i/o$-deterministic FST, all of whose input and 
		   output alphabets are $\Sigma_i$ and $\Sigma_o$, respectively,
		   and a string $u \in \Sigma_i^+$. \\
{\it Question:}~~ Is there a string $s \in \Sigma_o^{|u|}$
                   such that the string-pair $u/s$ is accepted by each
                   FST in $A$?

%\vspace*{0.07in}
\newpage

\noindent
{\sc $i/o$-deterministic FST Composition (FST-C)} \\
{\it Instance:}~~ A set $A$ of $i/o$-deterministic FST, all of whose input and 
		   output alphabets are $\Sigma$,  a composition-order $O$ on
		   these FST, and a string $u \in \Sigma^+$. \\
{\it Question:}~~ Is there
                   a sequence of strings $\{s_0,s_1,\ldots,s_{|A|}\}$ with $s_0
		    = u$ and $s_i \in \Sigma^{|u|}$ for $1 \leq i \leq |A|$ such
                   that for the ordering $\{a_1,a_2,\ldots,a_{|A|}\}$ of $A$ 
		   under $O$ and $1 \leq i \leq |A|$, 
		   $s_{i - 1}/s_i$ is accepted by $a_i$?

\vspace*{0.07in}

\noindent
The version of problem {\sc BDFAI} in which $x \in \Sigma^*$ is 
$PSPACE$-complete \cite{Koz77} and problem {\sc FST-I} is $NP$-hard by a slight
modification of the reduction given in \linebreak \cite[Section 5.5.1]{BBR87}. All 
parameterized complexity analyses given in
this section will be done relative to the following aspects: the number
of finite-state automata in $A$ ($|A|$), the required length of the 
result-string ($k$ in the case of {\sc BDFAI}, $|u|$ in the case of 
{\sc FST-I} and {\sc FST-C}), the maximum number of states of 
any finite-state automaton in $A$ ($|Q|$), and the size of the alphabet 
($|\Sigma|$ in the case of {\sc BDFAI} and {\sc FST-C}, $|\Sigma_i|$ 
{\em and} $|\Sigma_o|$ in the case of {\sc FST-I}).


\subsection{Bounded DFA Intersection}

\label{Sct_PhnBDI}

\noindent
Hardness results will be derived via reductions from 
the following problems:

\vspace*{0.07in}

\noindent
{\sc Longest common subsequence} (LCS) \cite[Problem SR10]{GJ79} \\
{\sl Instance:}~~ A set of strings $X = \{x_1$,\ldots, $x_k\}$ 
over an alphabet $\Sigma$, an integer $m$. \\
{\sl Question:}~~ Is there a string $y \in \Sigma^m$
		that is a subsequence of $x_i$ for $i=1,\ldots,k$?

\vspace*{0.07in}

\noindent
{\sc Dominating set} \cite[Problem GT2]{GJ79} \\
{\sl Instance:}~~ A graph $G = (V,E)$, an integer $k$. \\
{\sl Question:}~~ Is there a set of vertices $V' \subseteq V$, $|V'| \leq 
		   k$, such that each vertex in $V$ is either in $V'$ or
                   adjacent to a vertex in $V'$?

\vspace*{0.07in}

\noindent
Note that all reductions below are phrased in terms of
BDFAI${}_R$, the restricted version of BDFAI in which $k \leq |Q|$.

\begin{lemma}
{\rm LCS} $\leq_m$ {\rm BDFAI${}_R$}.
%
\label{Lem_BDFAI_red_LCS}
%
\end{lemma}
%
\begin{proof}
Given an instance $\langle X, k, \Sigma, m \rangle$ of LCS, construct the 
following instance $\langle A', \Sigma', k' \rangle$ of BDFAI${}_R$:  Let $\Sigma' = 
\Sigma$ $k' = m$, and $A'$ be created by applying to each
string $x \in X$ the algorithm in
\cite{Bae91} which produces a DFA on $|x| + 1$ states that recognizes all 
subsequences of a string $x$. Note that in the constructed instance of 
BDFAI${}_R$, $|A'| = k$, $k' = m$, and $|\Sigma'| = |\Sigma|$; moreover,
$k' = m < |Q|$.
\qed \end{proof}

\begin{lemma}
{\sc Dominating set} $\leq_m$ {\rm BDFAI${}_R$}.
%
\label{Lem_BDFAI_red_DS}
%
\end{lemma}
%
\begin{proof}
Given an instance $\langle G = (V,E), k \rangle$ of {\sc Dominating 
set}, construct the following instance $\langle A', \Sigma', k' \rangle$ 
of BDFAI${}_R$: Let $\Sigma' = V$ be an alphabet such that each vertex
$v \in V$ has a distinct corresponding symbol in $\Sigma'$, and 
let $k' = k$. For each $v \in V$, let $adj(v)$ be the set of vertices in
$V$ that are adjacent to $v$ in $G$ (including $v$ itself) and 
$nonadj(v) = V - adj(v)$. For each  vertex $v \in V$, construct a 
two-state DFA $A_v = \langle \{q_1,q_2\}, \Sigma', \delta, q_1, \{q_2\}
\rangle$ with transition  relation $\delta = \{ (q_1,v',q_1) ~ | ~ v' 
\in nonadj(v) \} \cup \{ (q_1,v',q_2) ~ |  ~ v' \in adj(v) \}
\cup  \{ (q_2,v',q_2) ~ | \linebreak v' \in V \}$. Let $A'$ be 
the set consisting of all DFA $A_v$ corresponding to vertices $v \in V$ plus
the $k + 1$ state DFA that recognizes all strings in ${\Sigma'}^k$.
Note that in the constructed instance of BDFAI${}_R$, $|A'| = |\Sigma'| + 1 = 
|V| + 1$, $k' = k$, and $|Q| = k + 1$; moreover, $k' = k \leq |V|$ and
$k' = k < |Q|$.
\qed \end{proof}

\begin{lemma}
{\rm BDFAI${}_R$} $\leq_m$ {\rm BDFAI${}_R$} such that $|\Sigma| = 2$.
%
\label{Lem_BDFAI_red_BDFAI}
%
\end{lemma}
%
\begin{proof}
Given an instance $\langle A, \Sigma, k \rangle$ of BDFAI${}_R$, construct the 
following instance $\langle A', \Sigma', k' \rangle$ of BDFAI${}_R$:  Let $\Sigma' = 
\{0,1\}$ and assign each symbol in $\Sigma$ a binary codeword of fixed 
length $\ell = \lceil \log |\Sigma| \rceil$. For each DFA $a \in A$, create
a DFA $a' \in A'$ by adjusting $Q$ and $\delta$ such that each state 
$q$ and its outgoing transitions in $a$ is replaced with a ``decoding tree'' on
$2^{\ell} - 1$ states in $a'$ that uses $\ell$ bits to connect $q$ to the 
appropriate states. Finally, let $k' = k\ell$. Note that in the constructed 
instance of BDFAI${}_R$, $|A'| = |A|$ and $|\Sigma'| = 2$; moreover, as 
$(|Q| + 1)(|\Sigma| - 1) \leq |Q'|$ and $k \leq |Q|$, $k' = k\ell \leq |Q|\lceil
\log |\Sigma| \rceil \leq (|Q| + 1)(|\Sigma| - 1) \leq |Q'|$.
\qed \end{proof}

\begin{theorem}

\hspace*{0.1in}
\vspace*{-0.07in}
%
\begin{enumerate}
\item{
{\rm BDFAI${}_R$} is $NP$-hard when $|\Sigma| = 2$.
}
\item{
$\langle k,|\Sigma| \rangle$-{\rm BDFAI${}_R$} is in $FPT$.
}
\item{
$\langle |A|,|Q| \rangle$-{\rm BDFAI${}_R$} is in $FPT$.
}
\item{
$\langle |Q|,|\Sigma| \rangle$-{\rm BDFAI${}_R$} is in $FPT$.
}
\item{
$\langle |A|,k \rangle$-{\rm BDFAI${}_R$} is $W[1]$-hard.
}
\item{
$\langle k,|Q| \rangle$-{\rm BDFAI${}_R$} is $W[2]$-hard.
}
\item{
$\langle |A|,|\Sigma|_2 \rangle$-{\rm BDFAI${}_R$} is $W[t]$-hard for all $t \geq 1$.
}
\item{
$\langle |\Sigma| \rangle$-{\rm BDFAI${}_R$} $\not\in XP$ unless $P = NP$.
}
\end{enumerate}

\label{Thm_BDFAI_Prm}
%
\end{theorem}
\vspace*{-0.15in}
\noindent
{\em Proof of (1)}: Follows from the $NP$-hardness of LCS
\cite[Problem SR10]{GJ79}, the reduction in Lemma \ref{Lem_BDFAI_red_LCS}
from LCS to BDFAI${}_R$, and the reduction in Lemma \ref{Lem_BDFAI_red_BDFAI} 
from BDFAI${}_R$ to BDFAI${}_R$ in which $|\Sigma| = 2$.

\noindent
{\em Proof of (2)}: Follows from the algorithm that generates all
$|\Sigma|^k$ possible $k$-length strings over alphabet $\Sigma$ and 
checks each string in $O(|A|k)$ time to see whether that string is
accepted by each of the DFA in $A$.  The algorithm as a whole runs in
$O(|\Sigma|^kk|A|)$ time, which is fixed-parameter tractable relative
to $k$ and $|\Sigma|$.

\noindent
{\em Proof of (3)}: Follows from the algorithm that constructs the 
intersection DFA of all DFA in $A$ and the $k + 1$-state DFA that 
recognizes all strings in $\Sigma^k$, and then applies depth-first search to 
the transition diagram for this  intersection DFA to determine if any of
its final states are reachable from its start state. 
The intersection DFA can be created in $O(|Q|^{|A|+ 1}
(k + 1)|\Sigma|^2) = O(|Q|^{|A|+ 1}2k    |\Sigma|^2) = O(|Q|^{|A|+ 1}k
|\Sigma|^2)$ time. As the graph $G = (V,E)$ associated with the 
transition diagram of this DFA has $|V| \leq (k + 1)
|Q|^{|A|} \leq 2k|Q|^{|A|}$ states and $|A| \leq (k + 1)|Q|^{|A|}
|\Sigma| \leq 2k|Q|^{|A|}|\Sigma| $ arcs and 
depth-first search runs in $O(|V| + |A|)$ time, the algorithm as a whole
runs in $O(|Q|^{|A| + 1}k|\Sigma|^2)$ time, which is fixed-parameter 
tractable relative to $|A|$ and $|Q|$.

\noindent
{\em Proof of (4)}: This result follows from the observation that there are
at most $|Q|^{|\Sigma||Q|} \times 2^{|Q|} \leq |Q|^{2|\Sigma||Q|}$
$i/o$-deterministic FST for any choice of $|Q|$ and $|\Sigma|$. Hence, the 
number of different FST in any set $A$ is at most $|Q|^{2|\Sigma||Q| + 1}$. 
This suggests the algorithm that removes
all redundant FST in $A$ and then performs the algorithm given in part (3)
above. The first step involves checking the isomorphism of the transition
diagrams of all FST in $A$, where each transition diagram has at most
$|Q|$ vertices and at most $|Q|^2|\Sigma|$ edges, which can be done in
$O(((|A|(|A| - 1)/2)|Q|^{|Q|}|Q|^2|\Sigma|) = O((|A|^2|Q|^{|Q| + 2}|\Sigma|)$ 
time. Hence, the algorithm as a whole runs in 
$O(|Q|^{(|Q|^{2|\Sigma||Q|}) + 1}k|\Sigma^2||A|^2)$ time, which is 
fixed-parameter tractable relative to $|Q|$ and $|\Sigma|$.

\noindent
{\em Proof of (5)}: Follows from the $W[1]$-completeness of $\langle k,m 
\rangle$-LCS \cite{BDFW95}, the reduction in Lemma \ref{Lem_BDFAI_red_LCS} 
from LCS to BDFAI${}_R$ in which $|A'| = k$ and $k' = m$, and
Lemma \ref{Lem_PCT_red_dp}.

\noindent
{\em Proof of (6)}: Follows from the $W[2]$-completeness of $\langle k 
\rangle$-{\sc Dominating set} \cite{DF99}, the reduction in Lemma 
\ref{Lem_BDFAI_red_DS} from {\sc Dominating set} to BDFAI${}_R$ in which $k' 
= k$ and $|Q| = k + 1$, and Lemma \ref{Lem_PCT_red_dp}.

\noindent
{\em Proof of (7)}: Follows from the $W[t]$-hardness of $\langle k 
\rangle$-LCS for $t \geq 1$ \cite{BDFW95}, the \linebreak reduction in Lemma 
\ref{Lem_BDFAI_red_LCS} from LCS to BDFAI${}_R$ in which $|A'| = k$, the
reduction in Lemma \ref{Lem_BDFAI_red_BDFAI} from BDFAI${}_R$ to BDFAI${}_R$ in 
which $|A'| = |A|$ and $|\Sigma'| = 2$, and Lemma \ref{Lem_PCT_red_dp}.

\noindent
{\em Proof of (8)}: Follow from (1) and Lemma \ref{Lem_PCT_XP}.
%
\qed

\vspace*{0.07in}

\noindent
As BDFAI${}_R$ is a restriction of BDFAI, all hardness results above also
hold for BDFAI. However, as the value of $k$ is not necessarily bounded by a 
polynomial in the instance size in BDFAI, the algorithm for part (4) only works 
(and hence results (4) and (5) only hold) for BDFAI if $k$ is also
included in the parameter.


\subsection{$i/o$-deterministic FST Intersection}

\begin{lemma}
{\rm BDFAI${}_R$} $\leq_m$ {\sc FST-I}.
%
\label{Lem_KIMEnc_red}
\end{lemma}
%
\begin{proof}
Given an instance $\langle A,\Sigma,k \rangle$ of BDFAI${}_R$, construct the following
instance  $\langle A', \Sigma'_i, \Sigma'_o, u' \rangle$  of {\sc FST-I}:
Let $\Sigma'_i = \{\Delta\}$ for some symbol $\Delta \not\in \Sigma$, 
$\Sigma'_o = \Sigma$ and $u' = \Delta^k$. Given a DFA 
$a = \langle Q, \Sigma, \delta, s, F \rangle$, let $FST_u(a) = \langle Q, \Sigma'_i,
\Sigma, \delta_F, s, F \rangle$ be the FST such that $\delta_F = 
\{ (q, \Delta, x, q') ~ | ~ (q,x,q') \in \delta \}$ and let $A'$ be the set
consisting of all  FST $FST_u(a)$ corresponding to DFA $a \in A$. 
Note that in the constructed instance of {\sc FST-I}, $|A'| = 
|A|$, $|u'| = k$,  $|Q'| = |Q|$, $|\Sigma'_u| = 1$, and
$|\Sigma'_s| = |\Sigma|$.
\qed \end{proof}

\begin{theorem}

\hspace*{0.1in}
\vspace*{-0.07in}
%
\begin{enumerate}
\item{
{\sc FST-I} is $NP$-hard when $|\Sigma_i| = 1$ and $|\Sigma_o| = 2$ and
when $|Q| = 4$ and $|\Sigma_o| = 3$.
}
\item{
$\langle |u|,|\Sigma_o| \rangle$-{\sc FST-I},
$\langle |A|,|Q| \rangle$-{\sc FST-I}, and
$\langle |Q|,|\Sigma| \rangle$-{\sc FST-I} are in $FPT$.
}
\item{
$\langle |A|,|u|,|\Sigma_i|_1 \rangle$-{\sc FST-I} is $W[1]$-hard.
}
\item{
$\langle |u|,|Q|,|\Sigma_i|_1 \rangle$-{\sc FST-I} is $W[2]$-hard.
}
\item{
$\langle |A|,|\Sigma_i|_1,|\Sigma_o|_2 \rangle$-{\sc FST-I} is $W[t]$-hard
for all $t \geq 1$.
}
\item{
$\langle |\Sigma_o|,|\Sigma_i| \rangle$-{\sc FST-I} and
$\langle |Q|, |\Sigma_o| \rangle$-{\sc FST-I} 
are not in $XP$  unless $P = NP$.
}
\end{enumerate}
%
\label{Thm_KIMEnc_Prm}
%
\end{theorem}
% 
\vspace*{-0.25in}
\begin{proof}
({\em Sketch}) Almost all results follow by arguments similar to 
those in \linebreak Theorem \ref{Thm_BDFAI_Prm} relative to the reduction in Lemma 
\ref{Lem_KIMEnc_red} and the appropriate results in Theorem 
\ref{Thm_BDFAI_Prm}. The $NP$-hardness of {\sc FST-I} when 
$|Q| = 4$ and $|\Sigma_o| = 3$ follows from the reduction in
\cite[Section 5.5.3]{BBR87}. 
\qed \end{proof}


\subsection{$i/o$-deterministic FST Composition}

\noindent
The following reduction formalizes the observation (made independently by 
Karttunen \cite{Kar98}) that FSA intersection can be simulated by the 
composition of identity-relation FST.

\begin{lemma}
{\rm BDFAI${}_R$} $\leq_m$ {\sc FST-C}.
%
\label{Lem_FSTEnc_red}
\end{lemma}
%
\begin{proof}
Given an instance $\langle A,\Sigma,k \rangle$ of BDFAI${}_R$, construct the following
instance  $\langle A', O', \Sigma', u', \rangle$ of {\sc FST-C}:
Let $\Sigma' = \Sigma \cup \{\Delta\}$ for some symbol $\Delta \not\in 
\Sigma$, and $u' = \Delta^k$. Given a DFA 
$a = \langle Q, \Sigma, \delta, s, F \rangle$, let $FST_u(a) = \langle Q, \Sigma,
\Sigma, \delta_F, s, F \rangle$ be the FST such that $\delta_F = 
\{ (q, x, x, q') ~ | ~ (q,x,q') \in \delta \}$. Let $A'$ be the set
consisting of all  FST $FST_u(a)$ corresponding to DFA $a \in A$ plus the
special FST $FST_{init} = \langle \{ q_1 \}, \{ \Delta \}, \Sigma, \delta, q_1,
\{q_1\} \rangle$ for which $\delta =  \{ (q_1, \Delta, x, q') ~ | ~ x \in 
\Sigma \}$, and let $O'$ be an ordering on $A'$ such that $FST_{init}$ is the 
first FST in $O$ and the other FST appear in an arbitrary order.
Note that in the constructed instance of {\sc FST-C}, $|A'| = 
|A| + 1$, $|u'| = k$, $|Q'| = \max(|Q|,1) = |Q|$, and $|\Sigma'| = 
|\Sigma| + 1$.
\qed \end{proof}

\begin{theorem}

\hspace*{0.1in}
\vspace*{-0.07in}
%
\begin{enumerate}
\item{
{\sc FST-C} is $NP$-hard when $|\Sigma| = 3$.
}
\item{
$\langle |u|,|\Sigma| \rangle$-{\sc FST-C} and $\langle |A|,|Q| \rangle$-{\sc FST-C} 
are in $FPT$.
}
\item{
$\langle |A|,|u| \rangle$-{\sc FST-C} is $W[1]$-hard.
}
\item{
$\langle |u|,|Q| \rangle$-{\sc FST-C} is $W[2]$-hard.
}
\item{
$\langle |A|,|\Sigma|_3 \rangle$-{\sc FST-C} is $W[t]$-hard
for all $t \geq 1$.
}
\item{
$\langle |\Sigma| \rangle$-{\sc FST-C} is not in $XP$ unless $P = NP$.
}
\end{enumerate}
%
\label{Thm_FSTEnc_Prm}
%
\end{theorem}
%
\vspace*{-0.25in}
\begin{proof}
({\em Sketch}) Almost all results follow by arguments similar to 
those in \linebreak Theorem \ref{Thm_BDFAI_Prm} relative to the reduction in Lemma 
\ref{Lem_FSTEnc_red} and the appropriate results in Theorem 
\ref{Thm_BDFAI_Prm}. The fixed-parameter tractability of $\langle |u|,|\Sigma| 
\rangle$-{\sc FST-C} follows by a variant of an algorithm in 
\cite[Theorem 4.3.3, Part (3)]{War99} that uses an $|\Sigma|^{|u|}$-length 
bit-vector to store the intermediate sets of 
strings produced during the FST composition. 
\qed \end{proof}

\section{Discussion}

All parameterized complexity results for problems BDFAI, FST-I, 
and FST-C that are either stated or implicit in the previous section are shown 
in Tables \ref{Tab_FSTEncRes} and \ref{Tab_KIMEncRes}.  Recall
that results for problems FST-I and FST-C are stated relative to restricted FST;
hence, only hardness results necessarily hold for these problems relative to 
general FST, and given $FPT$ algorithms are at best outlines for possible 
$FPT$ algorithms for general FST (see \cite[Sections 4.3.3 and 4.4.3]{War99} for
further discussion). Future research should both look for algorithms that 
exploit the sets of aspects underlying the 
state Cartesian product ($|A|$, $|Q|$) and exhaustive string generation 
($|u|$, $|\Sigma|$) constructions) in new ways and consider
other aspects of finite-state automaton intersection and composition
problems, such as characterizations of
logic formulas describing the automata \cite{Str94}.

One such aspect of great interest is FST ambiguity (essentially, the
maximum number of strings associated with any input string by a FST). 
Problems FST-I and FST-C are solvable in low-order polynomial time when they
are restricted to operate on sequential FST, {\em i.e.}, FST that associate
at most one output string with any input string. The reduction
in Lemma \ref{Lem_FSTEnc_red} suggests that the presence of only one 
$i/o$-deterministic FST can make FST composition  $NP$-hard. 
What about more restricted classes
of FST? One candidate is the {\bf $p$-subsequential FST} \cite{Moh97}, which
are essentially sequential FST which are allowed to append any one of a fixed 
set of $p$ strings to their output. Such FST seem adequate for efficiently
representing the ambiguity present in many applications \cite{Moh97}. However, 
the following result suggests that this observed efficiency is not universal.

\begin{theorem}
{\sc 2-subsequential FST composition} is $NP$-hard.
\end{theorem}
%
\begin{proof}
({\em Sketch}) Given instances of BDFAI${}_R$ created
in Lemma \ref{Lem_BDFAI_red_BDFAI}, the reduction in Lemma \ref{Lem_FSTEnc_red}
can be modified by setting $u' = \Delta$ and replacing the $i/o$-deterministic 
FST $FST_{init}$ with a set of $|u|$ 2-sequential FST that echo their input and 
append a  0 or a 1 (that is, a set of 2-subsequential FST whose composition
generates all possible strings of length $|u|$ over the alphabet $\{0,1\}$).
\qed \end{proof}

\vspace*{0.2in}

\noindent
{\bf Acknowledgments}: The author would like to thank the CIAA referees for
various helpful suggestions, and for pointing out several errors in the 
original manuscript as well as solutions for some of these errors.

\vspace*{0.in}

\bibliographystyle{plain}

%\begin{thebibliography}{AAAA99A}
\begin{thebibliography}{99}

\bibitem{Bae91}
R.A.\ Baeza-Yates.
\newblock 1991.
\newblock Searching Subsequences.
\newblock {\em Theoretical Computer Science}, 78, 363--376.

\bibitem{BBR87}
G.E.\ Barton, R.C.\ Berwick, and E.S.\ Ristad.
\newblock 1987.
\newblock {\it Computational Complexity and Natural Language}. 
\newblock MIT Press, Cambridge, MA.

\bibitem{BDFW95}
H.L.\ Bodlaender, R.G.\ Downey, M.R.\ Fellows, and H.T.\ Wareham.
\newblock 1995.
\newblock \linebreak The Parameterized Complexity of Sequence Alignment and Consensus. 
\newblock \linebreak {\em Theoretical Computer Science}, 147(1--2), 31--54. 

\bibitem{DF99}
R.G.\ Downey and M.R.\ Fellows.
\newblock 1999.
\newblock {\em Parameterized Complexity}.
\newblock Springer-Verlag, Berlin.

\bibitem{GJ79}
M.R.\ Garey and D.S.\ Johnson. 
\newblock 1979.
\newblock {\it Computers and Intractability: A Guide to the Theory of 
	         $NP$-Completeness}.
\newblock W.\  H.\  Freeman and Company, San Francisco.

\bibitem{HU79}
J.E.\ Hopcroft and J.D.\ Ullman.
\newblock 1979.
\newblock {\em Introduction to Automata Theory, \linebreak Languages, and Computation}.
\newblock Addison-Wesley, Reading, MA.

\bibitem{KK94}
R.M.\ Kaplan and M.\ Kay.
\newblock 1994.
\newblock Regular Models of Phonological Rule Systems.
\newblock {\em Computational  Linguistics}, 20(3), 331--378.

\bibitem{Kar98}
L.\ Karttunen.
\newblock 1998.
\newblock The Proper Treatment of Optimality in Computational Phonology.
\newblock Technical Report ROA-258-0498, Rutgers Optimality Archive.

\bibitem{Koz77}
D.\ Kozen.
\newblock 1977.
\newblock Lower Bounds for Natural Proof Systems.
\newblock In {\em 18th IEEE \linebreak Symposium on Foundations
           of Computer Science}, pp.\ 254-266. IEEE Press.

\bibitem{Kur94}
R.P.\ Kurshan.
\newblock 1994.
\newblock {\em Computer-Aided Verification of Coordinating Processes:
                \linebreak The  Automata-Theoretic Approach.}
\newblock Princeton University Press.

\bibitem{Moh97}
M.\ Mohri.
\newblock 1997.
\newblock On the Use of Sequential Transducers in Natural Language
           Processing. 
\newblock In E.\ Roche and Y.\ Schabes, eds., {\em Finite-State
	   Language Processing}, pp.\ 355--382. MIT Press, Cambridge, 
	   MA.

\bibitem{Str94}
H.\ Straubing.
\newblock 1994.
\newblock {\em Finite Automata, Formal Logic, and Circuit Complexity}.
\newblock Birkh\"{a}user, Boston, MA.

\bibitem{War99}
H.T.\ Wareham.
\newblock 1999.
\newblock {\em Systematic Parameterized Complexity Analysis in Computational
                Phonology}. 
\newblock Ph.D.\ thesis, Department of Computer Science, University of Victoria.
          Technical Report  ROA-318-0599, Rutgers Optimality Archive.

\end{thebibliography}

\begin{table}[h]
%
\caption[The Parameterized Complexity of the {\sc Bounded DFA
          Intersection} and {\sc $i/o$-deterministic FST 
	  Composition} Problems]
        {The Parameterized Complexity of the {\sc Bounded DFA 
          Intersection} and {\sc $i/o$-deterministic FST Composition} 
          Problems.  (a) The {\sc Bounded DFA \linebreak
          Intersection} Problem.  
          (b) The {\sc $i/o$-deterministic FST Composition} Problem.
        }
%
\label{Tab_FSTEncRes}
%
\hspace*{1.25in} (a) \hspace*{2.3in} (b) \newline \newline
\mbox{
\begin{tabular}{| c || c | c |}
\hline 
	& \multicolumn{2}{c |}{Alphabet Size $|\Sigma|$} \\ 
\cline{2-3}
Parameter	& Unbounded	& Parameter	\\	
\hline \hline
--		& $NP$-hard	& $\not\in XP$  \\
		&               & unless $P = NP$ \\
\hline
$|A|$		& $W[t]$-hard	& $W[t]$-hard	\\
\hline
$k$         	& $W[2]$-hard	&  $FPT$	\\
\hline
$|Q|$		& $W[2]$-hard	&  ???		\\
\hline
$|A|$, $k$	& $W[1]$-hard	&  $FPT$	\\
\hline
$|A|$, $|Q|$	& ???  		&  ???  	\\
\hline
$k$, $|Q|$	& $W[2]$-hard	&  $FPT$	\\
\hline
$|A|$, $k$, $|Q|$ 
           	&  $FPT$	&  $FPT$ \\
\hline
\end{tabular}
}
\hspace*{0.25in}
\mbox{
\begin{tabular}{| c || c | c |}
\hline 
	& \multicolumn{2}{c |}{Alphabet Size $|\Sigma|$} \\ 
\cline{2-3}
Parameter	& Unbounded	& Parameter	\\	
\hline \hline
--		& $NP$-hard	& $\not\in XP$  \\
		&               & unless $P = NP$ \\
\hline
$|A|$		& $W[t]$-hard	& $W[t]$-hard	\\
\hline
$|u|$           & $W[2]$-hard	& $FPT$	\\
\hline
$|Q|$		& $W[2]$-hard	& ??? 	\\
\hline
$|A|$, $|u|$	& $W[1]$-hard	& $FPT$	\\
\hline
$|A|$, $|Q|$	& $FPT$		& $FPT$ \\
\hline
$|u|$, $|Q|$	& $W[2]$-hard	& $FPT$	\\
\hline
$|A|$, $|u|$ $|Q|$ 
           	& $FPT$		& $FPT$ \\
\hline
\end{tabular}
}
%
\end{table}

\begin{table}[h]
%
\caption[The Parameterized Complexity of the {\sc $i/o$-deterministic FST Intersection} Problem]
        {The Parameterized Complexity of the {\sc $i/o$-deterministic FST \linebreak Intersection} Problem.
        }
%
\label{Tab_KIMEncRes}
%
\vspace*{0.2in}
%
\centering
%
\begin{tabular}{| c || c | c | c | c |}
\hline 
	& \multicolumn{4}{c |}{Alphabet Sizes 
			       ($|\Sigma_i|$,$|\Sigma_o|$)} \\ 
\cline{2-5}
Parameter	& (Unb,Unb)	& (Unb,Prm)	& (Prm,Unb) 
		& (Prm,Prm) \\	
\hline \hline
--		& $NP$-hard	& $\not\in XP$  & $\not\in XP$ 
		& $\not\in XP$ \\
		&
		& unless $P = NP$ 
		& unless $P = NP$ 
		& unless $P = NP$ \\
\hline
$|A|$		& $W[t]$-hard	& $W[t]$-hard		& $W[t]$-hard
		& $W[t]$-hard \\
\hline
$|u|$		& $W[2]$-hard	& $FPT$ 		& $W[2]$-hard
		& $FPT$ \\
\hline
$|Q|$		& $W[2]$-hard   & $\not\in XP$		& $W[2]$-hard 
		& $FPT$ \\
		&
		& unless $P = NP$ 
		& 
		& \\
\hline
$|A|,|u|$	& $W[1]$-hard	& $FPT$ 		& $W[1]$-hard
		& $FPT$ \\
\hline
$|A|,|Q|$	& $FPT$ 	& $FPT$			& $FPT$
		& $FPT$ \\
\hline
$|u|,|Q|$	& $W[2]$-hard	& $FPT$ 		& $W[2]$-hard
		& $FPT$ \\
\hline
$|A|,|u|,|Q|$	& $FPT$		& $FPT$			& $FPT$
		& $FPT$ \\
\hline
\end{tabular}
%
\end{table}

\end{document}