Definition 2.5 (Simple rational terms). Let $B$ be a finite alphabet. The simple rational terms with outputs in $B^*$ are the terms generated from the term $[] : 1 \to B^*$, which produces the empty string, by the following combinators:

• co-pairing: for $f_1 : A_1 \to B^*$ and $f_2 : A_2 \to B^*$, the term $\langle f_1, f_2 \rangle : A_1 + A_2 \to B^*$ that applies $f_1$ or $f_2$ depending on the summand;
• concatenation: for $f_1 : A_1 \to B^*$ and $f_2 : A_2 \to B^*$, the term $f_1 \odot f_2 : A_1 \times A_2 \to B^*$ that maps $(a_1, a_2)$ to $f_1(a_1)\,f_2(a_2)$;
• homomorphism: for $f : A \to B^*$, the term $\mathrm{hom}\, f : A^* \to B^*$ that maps $[a_1, \ldots, a_n]$ to $f(a_1) \cdots f(a_n)$;
• constants: for $f : A \to B^*$ and a string $w \in B^*$, the terms $w \cdot f$ and $f \cdot w$, which prepend or append $w$ to the output.

A function is represented by a simple rational term if it is the function that the term defines.