Notation

The predicates used in this paper are predicates on $\Sigma$. So, each predicate $\pi$ is a total function such that for each $\sigma\in\Sigma$, $\pi(\Sigma)$ is either true or false. If $\pi$ is the characteristic function of the set $S\subseteq \Sigma$, i.e., $S = \{\sigma\in \Sigma\vert\pi(\sigma)\}$, then in transition diagrams we often write S instead of $\pi$. As usual, if S is a set, then the complement of S is written $\overline{S}$. Moreover, if S is of the form {c}, i.e., a singleton set, then we abbreviate this predicate simply as c. As a special case, $\Sigma$ is written as ?. In transducers, a transition is associated both with an input predicate $\pi_d$ as well as with an output predicate $\pi_r$; such a pair of predicates is written as $\pi_d:\pi_r$.

Below, we will often refer to states in automata using p, q, and r. For examples of symbols we use characters from the beginning of the alphabet in typewriter font such as a, b, c; for sequences of symbols we use characters w, x, y, z. Typically, we use $\sigma$ as a variable that takes a symbol as its value. Examples of predicates are written in small caps, using characters from the beginning of the alphabet, like A, B, C. A variable that takes a predicate as its value is written $\pi$. A sequence of predicates is often written using Greek symbols $\phi, \psi$. Finally, note that the empty sequence is written $\epsilon$, for either the empty sequence of symbols or the empty sequence of predicates.