We study translations of dyadic first-order sentences into equalities between relationalexpressions. The proposed translation techniques (which work also in the conversedirection) exploit a graphical representation of formulae in a hybrid of the twoformalisms. A major enhancement relative to previous work is that we can cope with therelational complement construct and with the negation connective. Complementation ishandled by adopting a Smullyan-like uniform notation to classify and decompose relationalexpressions; negation is treated by means of a generalized graph-representation offormulae in ℒ+, and through a series of graph-transformation rules whichreflect the meaning of connectives and quantifiers.

We discuss how much space is sufficient to decide whether a unary given numbern is a prime. We show thatO(log log n) space is sufficient for a deterministicTuring machine, if it is equipped with an additional pebble movable along the input tape,and also for an alternating machine, if the space restriction applies only to itsaccepting computation subtrees. In other words, the language is a prime is inpebble–DSPACE(log log n) and also inaccept–ASPACE(log log n). Moreover, if the givenn is composite, such machines are able to find a divisor ofn. Since O(log log n) space is toosmall to write down a divisor, which might requireΩ(log n) bits, the witness divisor is indicated by theinput head position at the moment when the machine halts.