2026-07-22T15:43:42Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:3233 2024-03-06T10:33:59Z ddc:004 open_access

Non-Definability Results for Randomised First-Order Logic Eickmeyer, Kord descriptive complexity randomised logics derandomisation 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]. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Kord Eickmeyer 2011 Is Part Of LIPIcs, Volume 12, Computer Science Logic (CSL'11) - 25th International Workshop/20th Annual Conference of the EACSL (2011) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CSL.2011.218 urn:nbn:de:0030-drops-32333 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2011.218 eng https://creativecommons.org/licenses/by-nd/3.0/legalcode