The predicates used in this paper are predicates on . So, each
predicate is a total function such that for each
, is either * true* or *
false*. If is the * characteristic function* of the set
, i.e.,
,
then in transition diagrams we often write *S* instead of .
As usual, if *S* is a set, then the complement of *S* is written
.
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,
is written as ` ?`. In transducers, a transition
is associated both with an input predicate as well as with an
output predicate ; such a pair of predicates is written as
.

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 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 . A sequence of predicates is often written using
Greek symbols .
Finally, note that the empty sequence is written
, for either the empty sequence of symbols or the empty sequence
of predicates.