Finite State Transducers with a bounded Queue

We are now ready to define predicate-augmented finite state transducers with a bounded queue. A predicate-augmented finite state transducer with queue (qpfst) M is a tuple $(Q,\Sigma,\Pi,E,S,F)$ with Q a finite set of states, $\Sigma$ a set of symbols, $\Pi$ a set of predicates over $\Sigma$. As before, S and F are sets of start states and final states respectively. E is a finite set $Q\times ((\Pi\cup\{\epsilon\})\times\{0,1\}) \times ((\Pi\cup\{\lambda\})\times\{0,1\})^* \times Q$.

In a transition, each predicate is associated with a queue marker, which is one of {0,1}. On the input side, 1 will imply an enqueue operation of the symbol matching the predicate; on the output side 1 will imply a dequeue operation of the symbol matching the predicate. In the input part of the transition, $\epsilon$ can be used as well, in which case the queue marker must be 0 (input epsilons will be employed to represent outputs associated with initial and final states). In the output part of a transition we can have $\lambda$ instead of a predicate, in order to represent the explicit dequeue operations motivated earlier. We require that every $\lambda$ must have a corresponding queue marker which is 1.

The relation $O: ((\Pi\cup\{\lambda\})\times\{0,1\})^*\times\Sigma^*\times\Sigma^*\times\Sigma^*$ determines the effect of the output part of a transition. Its arguments represent respectively the output sequence of a transition, the (incoming and outgoing) queues, and the resulting output string. Note that queues are written from left to right in such a way that an element is enqueued to the left and dequeued from the right.

1. for all $x\in\Sigma^*$ we have $(\epsilon,x,x,\epsilon)\in O$

2. if $(\phi,x_0,x,z) \in O$ then for all $\sigma\in\Sigma$ we have $((\lambda,1)\phi,x_0\sigma,x,z)\in O$

3. if $(\phi,x_0,x,z) \in O$ then for all $\sigma\in\Sigma$ and $\pi\in\Pi$ such that $\pi(\sigma)$ we have $((\pi,1)\phi,x_0\sigma,x,\sigma z)\in O$

4. if $(\phi,x_0,x,z) \in O$ then for all $\sigma\in\Sigma$ and $\pi\in\Pi$ such that $\pi(\sigma)$ we have $((\pi,0)\phi,x_0,x,\sigma z)\in O$

The relation $\widehat{E} \subseteq Q \times \Sigma^*\times \Sigma^*\times Q\times \Sigma^*\times\Sigma^*$ is a relation between source states, sequences of input symbols, sequences of output symbols, target states, and source- and target queues. It is defined inductively.

1. for all $p\in Q$, $(p,\epsilon,\epsilon,p,\epsilon,\epsilon)\in\widehat{E}$.
2. for each transition $(p,(\epsilon,0),\phi,q)\in E$ such that $(\phi,x_0,x,w)\in O$, $(p,\epsilon,w,q,x_0,x)\in\widehat{E}$
3. for each transition $(p,(\pi,0),\phi,q)\in E$ such that $\pi(\sigma)$ and $(\phi,x_0,x,w)\in O$, $(p,\sigma,w,q,x_0,x)\in\widehat{E}$.
4. for each transition $(p,(\pi,1),\phi,q)\in E$ such that $\pi(\sigma)$ and $(\phi,\sigma x_0,x,w)\in O$, $(p,\sigma,w,q,x_0,x)\in\widehat{E}$.
5. if (q₀,x₁,y₁,q₁,x₀,x₁) and (q₁,x₂,y₂,q,x₁,x) are both in $\widehat{E}$ then $(q_0,x_1x_2,y_1y_2,q,x_0,x)\in\widehat{E}$

The relation R(M) accepted by a qpfst M is defined to be $\{(w_d,w_r)\vert q_s\in S, q_f\in F, (q_s,w_d,w_r,q_f,\epsilon,\epsilon)\in\widehat{E}\}$.

Such qpfst are generally very powerful. However, the qpfst which result from the generalized transducer determinization algorithm are all limited. Not only are these transducers deterministic by construction, but they are also limited in the way the queue is actually used: in each case the maximum size of the queue is some constant. And of course, since the input was a finite-state transducer, the resulting equivalent qpfst describes a finite-state transduction too. Another way to characterize this limited use of qpfst is to observe that in such cases every cyclic path through such a transducer will have identical input and output queue: the queue is only used in a strictly local sense.

The ordinary transducer determinization algorithm is guaranteed to terminate only if the input transducer can be determined, i.e., the transducer must be sub-sequential. A separate algorithm exists to check a given transducer for subsequentiality (section 5.2). The same termination property holds for the generalized transducer determinization algorithm. If the generalized transducer determinization algorithm terminates for a given pfst, then the result is an equivalent deterministic qpfst. The application of a determinized (potentially non-functional) qpfst T to a given string w is linear in the size of w, and independent of the size of T.