摘要：We investigate the expressive power of randomised first-order logic (BPFO) on restricted classes of structures. While BPFO is stronger than FO in general, even on structures with a built-in addition relation, we show that BPFO is not stronger than FO on structures with a unary vocabulary, nor on the class of equivalence relations. The same techniques can be applied to show that evenness of a linear order, and therefore graph connectivity, can not be defined in BPFO. Finally, we show that there is an FO[<]-definable query on word structures which can not be defined in BPFO[+1].
