With locality as an additional condition on state-translation functions we could easily prove that conditional effects cannot be compiled away. Instead of doing so we will show, however, that it is possible to derive a weaker condition from the definition of compilation schemes that will be enough to prove the impossibility result. This weaker condition is *quasi-locality* of state-translation functions relative to a given set of symbols , which in turn is based on the notion of universal literals. A literal l is called a **universal literal** for given state-translation functions on iff one of the following conditions is satisfied:

$$t_{i}\quad p\quad,\quad p\quad,{\mathrm{or}}$$
$$1.{\mathrm{~for~all~}}p$$
1. for all p : l ti p ; p , or
$$2.{\mathrm{~for~all~}}p$$
$$t_{i}\quad p\ \ ,\quad\ p\quad,\ \mathrm{or}$$
2. for all p : l ti p ; f:p , or
$$3.{\mathrm{~for~all~}}p$$
$$t_{i}\quad p\ \ ,\,\emptyset\ ,\,{\mathrm{or}}$$
3. for all p : l ti p ; ; , or
$$4.{\mathrm{~for~all~}}p$$
$$t_{g}\quad p\ \ ,\ \ p\quad,\ \mathrm{or}$$
4. for all p : l tg p ; p , or
$$5.{\mathrm{~for~all~}}p$$
$$t_{g}\quad p\quad;\quad p\quad,\;\mathrm{or}$$
5. for all p : l tg p ; f:p , or
6. for all p : l tg p ; ; .

Let U denote the set of universal literals. Now we define **quasi-locality** of state-translation functions relative to a set of propositional atoms and the induced set of universal literals U as follows.

For each S  such that S 6j and for all pairs 1; 2  with 1 2 ;, we have

$$t_{i}\quad_{1},S\quad_{1}\quad t_{g}\quad_{2},S\quad_{2}^{--}\subseteq\mathbf{U}\,.$$

In words, the only *non-local* literals in quasi-local state-translation functions are the universal literals.

Lemma 10 *For a given compilation scheme* f hf ; fi; fg ; ti; tg i and natural number n, there exists a set of atoms   such that  n and ti and tg *are quasi-local on* . Proof. Let t  ! 2be a function that has as the result the union of all results for all possible translations of a literal returned by the state-translation functions, i.e.,

t p ti p ; p ti p ; f:p ti p ; ; tg p ; p tg p ; f:p tg p ; ; :
Set S  and U ;. Now we choose an infinite subset S of S such that either 1. for all p S , there are only finitely many other atoms q S such that t p t q))U 6 ;,
or if such an infinite subset of S does not exist,

2. S has a universal literal l 62 U and we set U U l .
Note that such an infinite subset S must exist. The reason is that some literal l 62 U must occur for infinitely many atoms in t over S because we could not find an infinite subset satisfying condition (1). Because for a single atom there are only six possible ways to generate l, there must exist an infinite subset such that this literal occurs in all of either tx p ; p , tx p ; f:p , or tx p ; ; (for x i; g) and in this subset l is a universal literal.