{'fraction_non_alphanumeric': 0.046477667556271716, 'fraction_numerical': 0.010473840576061232, 'mean_word_length': 4.106582669066598, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 1, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 12, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Surprise Minimization Revision Operators

Prominent approaches to belief revision prescribe the adoption of a new belief that is as close as possible to the prior belief, in a process that, even in the standard case, can be described as attempting to minimize surprise. Here we extend the existing model by proposing a measure of surprise, dubbed relative surprise, in which surprise is computed with respect not just to the prior belief, but also to the broader context provided by the new information, using a measure derived from familiar distance notions between truth-value assignments. We characterize the surprise minimization revision operator thus defined using a set of intuitive rationality postulates in the AGM mould, along the way obtaining representation results for other existing revision operators in the literature, such as the Dalal operator and a recently introduced distance-based min-max operator.


Introduction
Belief change models rational adjustments made to an agent's epistemic state upon acquiring new information (Peppas 2008;Hansson 2017;Fermé and Hansson 2018). When the new information is assumed to be reliable, the logic of changing one's prior beliefs to accommodate such new-found knowledge falls under the heading of revision. Belief revision is typically thought of by appeal to a set of intuitive normative principles, usually along the lines of the AGM framework (Alchourrón, Gärdenfors, and Makinson 1985), alongside more concrete revision representations and mechanisms (Grove 1988;Dalal 1988; Gärdenfors and Makinson 1988;Katsuno and Mendelzon 1992;Rott 1992).
A perspective underlying many of these representations, which we share here, is that belief revision is akin to a choice procedure guided by a plausibility relation over possible states of affairs: revising a belief, in this sense, amounts to choosing the most plausible states of affairs consistent with the new information. Plausibility over states of affairs, in turn, is judged according to some notion of dissimilarity, or distance between states of affairs: I judge a situation to be less likely the further away from my own belief it is. Among the various distance notions that can be used to make this intuition precise, the approach using Hamming distance to rank truth-value assignments is among the most prominent, used for the well-known Dalal revision operator (Dalal 1988), and the more recently introduced Hamming distance min-max operator (Haret and Woltran 2019).
Both the Dalal and the Hamming distance min-max operator are designed to respond to new information by minimizing departures from the prior belief, in what can be described, just as well, as an attempt to prevent major surprise: if I have a prior belief that all major carbon emitting countries will have halved their emissions by the end of 2049, and it turns out that neither of them has, then I am likely to be surprised-certainly more suprised than seeing my belief confirmed. Consequently, if I acquire information to the effect that these are the only two possible outcomes (i.e., either all countries cut emissions, or none of them does), then, on the assumption that this information stems from some noisy observation of the true state, I will use my prior belief and gravitate towards the outcome that occasions less surprise.
In this revision procedure, consistent with both the Dalal and the min-max operators, the measure of surprise is taken to depend only on the absolute difference between my prior belief and the states of affairs learned to be viable. However, we can readily imagine that the amount of anticipated surprise depends in equal measure on other factors, e.g., the context provided by the newly acquired information: if in 2049 it turns out that none of the countries has reduced emissions, then I am likely to be less surprised if I had been told in advance that at most one of them would than if I had been told that, possibly, any number of them could achieve the target. In other words, it is desirable to have a broader notion of surprise complementing the absolute one, to account for situations in which change in the epistemic state depends not just on the prior belief but also on the range of options provided by the new information. However, despite the fact that surprise minimization is a natural idea that has been gaining traction in Cognitive Science (Friston 2010;Hohwy 2016), there are not many belief revision policies that explicitly take it into account.
In this paper we put forward a notion of relative surprise that is richer in precisely this sense, and leverage it to define a new type of revision operator, called the Hamming surprise min-max operator, and which is calibrated to take into account contextual effects as described above. Though it deviates from some of the postulates in the AGM framework (notably, Vacuity, Superexpansion and Subexpansion (Fermé and Hansson 2018)), we show that the Hamming surprise min-max operator shares other desirable, though less obvious, features with the Dalal and the Hamming distance min-max operator. Significantly, we use these features to fully characterize the newly introduced surprise operator, in the process obtaining full chacterizations for the Dalal and Hamming distance min-max operators.

Contributions.
On a conceptual level, we argue that the notion of distance standardly used to define revision operators can be seen as quantifying a measure of surprise, with different distance-based operators providing different ways to minimize it. We then enrich this landscape by introducing a notion of relative surprise, which is then put to use in defining the Hamming surprise min-max operator. We compare this operator against the standard KM postulates for revision (Katsuno and Mendelzon 1992) and present new postulates that complement the KM ones, for a full characterization. The versatility of the ideas underlying these postulates is showcased by adapting them to the Dalal and Hamming distance min-max operators: in the case of the min-max operator our postulates complement the subset of KM postulates the operator is known to satisfy; in the case of the Dalal operator our postulates strengthen the KM postulates. In both cases, we obtain full characterizations.
Related work. Among belief revision operators that are insensitive to syntax, the Dalal operator has received a significant amount of attention, either from attempts to express it by encoding the Hamming distance between truth-value assignments at the syntactic level (del Val 1993;Pozos-Parra, Liu, and Perrussel 2013); as an instance of the more general class of parameterized difference operators (Peppas and Williams 2018;Aravanis, Peppas, and Williams 2021); or in relation to Parikh's relevance-sensitivity axiom (Peppas et al. 2015). However, to the best of our knowledge, the characterization we offer here is the first of its kind.
Strengthening the AGM framework to induce additional desired behavior from revision operators has been considered in relation to issues of iterated revision (Darwiche and Pearl 1997), or relevance sensitivity (Parikh 1999;Peppas and Williams 2016). In terms of choice rules, the closest analogue to the surprise minimization operator is the decision rule that minimizes maximum regret in decisions with ignorance (Milnor 1954;Lave and March 1993;Peterson 2017), with Hamming distances playing the role of utilities in our present setting. However, the logical setting and the fact that the distances depend on the states themselves means that decision theoretic results do not translate easily to our current framework.
Outline. Section 2 introduces the main notions related to propositional logic and belief revision that will be used in the rest of the paper, and argues for the surprise-based interpretations of distances, Section 3 defines the relative Hamming surprise measure and the Hamming surprise min-max operator. Sections 4 and 5 consist of a slight detour in which the Dalal and Hamming distance min-max operators are characterized, setting up the stage for the characterization of the surprise operator in Section 6. Section 7 offers conclusions.

Preliminaries
Propositional Logic. We assume a finite set A of propositional atoms, large enough that we can always reach into it and find additional, unused atoms, if any are needed. The set L of propositional formulas is generated from the atoms in A using the usual propositional connectives (∧, ∨, ¬, → and ↔), as well as the constants ⊥ and ⊤.
An interpretation w is a function mapping every atom in A to either true or false. Since an interpretation w is completely determined by the set of atoms in A it makes true, we will identify w with this set of atoms and, if there is no danger of ambiguity, display w as a word where the letters are the atoms assigned to true. The universe U is the set of all interpretations for formulas in L. If w 1 and w 2 are interpretations, the symmetric difference w 1 △w 2 of w 1 and w 2 is defined as w 1 △w 2 = (w 1 \ w 2 ) ∪ (w 2 \ w 1 ), i.e., as the set of atoms on which w 1 and w 2 differ. The Hamming distance d H : U × U → N is defined, for any interpretations w 1 and w 2 , as d H (w 1 , w 2 ) = |w 1 △w 2 |. Intuitively, the Hamming distance d H (w 1 , w 2 ) between w 1 and w 2 counts the number of atoms that w 1 and w 2 differ on, and is used to quantify the disagreement between two interpretations.
The models of a propositional formula ϕ are the interpretations that satisfy it, and we write [ϕ] for the set of models of ϕ. If ϕ 1 and ϕ 2 are propositional formulas, we say that ϕ 1 entails ϕ 2 , written ϕ 1 |= ϕ 2 , if [ϕ 1 ] ⊆ [ϕ 2 ], and that they are equivalent, written The models of ⊥ and ⊤ are [⊥] = ∅ and [⊤] = U. We will occasionally find it useful to explicitly represent the models of a formula, in which case we write ϕ v1,...,vn for a propositional formula such that [ϕ v1,...,vn ] = {v 1 , . . . , v n }. A propositional formula ϕ is complete if it has exactly one model, and we will typically denote a complete formula as ϕ v to draw attention to its unique model v. The null formula ε and the full formula α are defined as ε = p∈A ¬p and α = p∈A p, i.e., as the conjunction of the negated and non-negated atoms in A, respectively. Note that [ε] = {∅} and [α] = A.
The primary device for generating concrete revision operators we make recourse to here is the Hamming distance. Thus, the Hamming distance min-min operator • dH, min , or, as it is more commonly known, the Dalal operator (Dalal 1988), is defined, for any propositional formulas ϕ and µ, as a formula ϕ • dH, min µ such that: Intuitively, the shortest distance from w to any model of ϕ, i.e., min v∈[ϕ] d H (v, w), can be interpreted as a measure of distance between w and ϕ, and we will refer to it as the Hamming min-distance between ϕ and µ. The result ϕ • dH, min µ of revision, then, selects those models of µ that are closest to ϕ according to this measure.
Recently, an alternative revision operator has been analyzed (Haret and Woltran 2019): what we will call here the Hamming distance min-max operator • dH, max , defined, for any ϕ and µ, as a formula ϕ • dH, max µ such that: i.e., a formula whose models are exactly those models of [µ] that minimize the Hamming distance to max v∈[ϕ] d H (v, w), the Hamming max-distance between ϕ and µ.
Distance as surprise. Consistent with the idea that revision models the agent learning about the world around it, we can see the new information µ as a noisy observation of some underlying ground truth state w * : by acquiring µ, the agent learns of a set of outcomes (the models of µ), all of which stand a chance of being the true state w * . In that sense, the distance d(v, w) between any v ∈ [ϕ] and w ∈ [µ] stands for a quantity that can be aptly described as surprise: it is the difference between what the agent expects is the case (v) and what might turn out to actually be the case (w). Naturally, the agent will want to minimize the divergence between its predictions and reality, with existing revision operators providing different means to do so. Intuitively, we read this as saying that if an agent believes the true state to be either of the worlds in [ϕ] = {∅, abcd}, but finds out it is one among [µ] = {∅, abcd, abe}, then • dH, min selects the new belief to be {∅, abcd}, as this supplies the least amount of surprise in an optimistic, best best-case scenario: if the true state turns out to be either of ∅ or abcd, then the agent, believing this, will be able to say "I told you so!"; the abe case, which is surprising in both cases, is ignored. In a complementary approach, the • dH, max operator shifts the agent's belief to {abe}, as this provides, more cautiously, the best worst-case scenario: from the standpoint of both ∅ or abcd, abe seems the least risky of the other options.

e} of atoms, standing for countries that might meet their emission targets before 2049, and formulas
Example 1 serves as a springboard for some important observations. Firstly, it illustrates that • dH, min and • dH, max are distinct operators. Secondly, it is apparent from Example 1 that, given prior beliefs ϕ, interpretations can be ranked according to their Hamming min-or max-distance to ϕ. It is straightforward to see that (i) in both cases the resulting rankings depend only on the models of ϕ, are total and admit ties; (ii) the min-distance places models of ϕ at the bottom of this ranking, i.e., as the most plausible interpretations according to ϕ, in a pattern that goes under the name of a faithful ranking (Katsuno and Mendelzon 1992); and, perhaps, less conspicuously, that (iii) the max-distance places models of the so-called dual of ϕ (i.e., the formula obtained from ϕ by replacing all its atoms with their negations), at the very top, i.e., as the least plausible interpretations according to ϕ (Haret and Woltran 2019). The different flavors of rankings, faithful or otherwise, generated in this distance-based approach usually play a prominent role in representation results for revision, as they open up a level of abstraction between that of concrete numbers and general principles. In this work, however, we will bypass talk of rankings and work directly at the interface between distancebased measures and normative principles.
Finally, an observation that will prove useful is that we can (and will) think of the individual models v of ϕ as generating their own plausibility rankings over interpretations: these rankings correspond to the columns in Table 1 and are the rankings that would be generated if the prior belief were the complete formula [ϕ v ] = {v}, i.e., what the landscape of plausibility looks like if the agent puts the entire weight of its belief on ϕ v . Revision can then be seen as employing a function (min or max) to aggregate the individual rankings, and then choosing something out of the aggregated result: the Dalal operator • dH, min chooses, optimistically, the models that are the best of the best, while • dH, max chooses, pessimistically, the best of the worst models across the individual rankings. In keeping with this way of looking at things, we will often speak, loosely, of formulas and interpretations 'judging' and 'choosing' among possible outcomes.
What recommends the choice behavior of operators (such as Dalal's operator) as reasonable is adherence to a set of intuitive normative principles, or rationality postulates.
The most common set of such principles consists of the AGM postulates for revision (Alchourrón, Gärdenfors, and Makinson 1985), which we present here in the Katsuno-Mendelzon formulation (Katsuno and Mendelzon 1992). The postulates apply for any propositional formulas ϕ, µ, µ 1 and µ 2 : The primary assumption of revision (postulate R 1 ) is that new information originates with a trustworthy source; thus, revising ϕ by µ involves a commitment to accept the newly acquired information. Postulate R 2 , known as the Vacuity postulate, says that if the newly acquired information µ does not contradict the prior information ϕ, the result is just the conjunction of µ and ϕ. Postulate R 3 says that if the newly acquired information µ is consistent, then the revision result should also be consistent. Postulate R 4 says that the result depends only on the semantic content of the information involved. Postulates R 5 and R 6 , known as Subexpansion and Superexpansion, respectively, enforce a certain kind of coherence when the new information is presented sequentially, which is for present purposes best understood as akin to a form of independence of irrelevant alternatives familiar from rational choice (Sen 2017): the choice over two alternatives (here, interpretations w 1 and w 2 in [µ]) should not depend on the presence of other alternatives in the menu (here represented by new information µ).
The Dalal operator • dH, min satisfies postulates R 1 -R 6 (Katsuno and Mendelzon 1992), though these postulates do not uniquely characterize it. The Hamming distance maxoperator • dH, max satisfies postulates R 1 and R 3 -R 6 but not R 2 , though it does satisfy the following two postulates (Haret and Woltran 2019), where ϕ stands for the dual of ϕ, as defined above: In certain circumstances, ϕ can be thought of as the point of view opposite to that of ϕ, such that, taken together, postulates R 7 and R 8 inform the agent to believe states of affairs compatible with ϕ only if it has no other choice in the matter: the models of ϕ should be part of a viewpoint one is willing to accept only as a last resort.

Relative Hamming Surprise Minimization
In this section we introduce our novel surprise-based operator. We start by defining, for any interpretations v and w, the (relative) Hamming surprise s µ H (v, w) of v with respect to w relative to µ, as: , the distance between v and w normalized by the distance between v and µ. The new information µ, here, serves as the reference point, or context, relative to which surprise is calculated. The Hamming surprise min-max operator • s, max is defined as a formula ϕ • sH, max µ such that: i.e., as a formula whose models are exactly those models of µ that minimize maximum Hamming surprise with respect to ϕ, and relative to µ. We refer to max v∈[ϕ] s µ H (v, w), as the max-surprise of ϕ with w relative µ.
The lower surprise is, the more plausible w is considered to be, from the standpoint of v. The model minimizing overall surprise is emphasized in bold font.  Table 3. Note that in this case we obtain that [ϕ • sH, max ν] = {abcd}. Thus, in revision by µ, abe is chosen over abcd, whereas in revision by ν the choice is reversed. Intuitively, when ∅ stops being a viable option, abcd becomes more attractive than abe, as the amount of surprise it would inflict, from the standpoint of ∅, relative to abe, becomes smaller: considering the options, abcd is not as extreme as abe. In other words, for ∅ the two interpretations abcd and abe are sufficiently alike to be considered almost equally risky: the marginal surprise that abcd carries over abe is not big enough to be considered significant, so that the final decision ends up choosing abcd as carrying the least amount of risk. By contrast, when ∅ is present as an option (see Table 2) the situation is markedly different, as the relative surprise of actually ending up with abcd or abe becomes much more significant.
The type of scenario depicted in Example 2 is reminiscent of deviations from the principle of independence from irrelevant alternatives signaled in the rational choice literature (Sen 1993), and immediately points toward a salient feature of the relative surprise operator we have introduced: it is not guaranteed to satisfy postulates R 2 , R 5 and R 6 . Indeed, for ϕ and µ from Example 2 we have that [ϕ • sH, max µ] = {abe}, despite the fact that [ϕ ∧ µ] = {∅, abcd}, which speaks to postulate R 2 . Since ϕ • sH, max µ coincides, in this case, with ϕ• dH, max µ, and • dH, max is already known not to satisfy postulate R 2 , this is perhaps not surprising, but similar reasoning shows that ϕ • sH, max µ does not satisfy postulates R 7 and R 8 either. And [ϕ • sH, max (µ ∧ ν)] = {abcd}, despite the fact that [(ϕ • sH, max µ) ∧ ν] = {abe}, which speaks to postulates R 5 and R 6 . More to the point, the ranking on interpretations that is generated by the surprise measure s + H varies with µ, to the extent that narrowing down the new information, as in Example 2, can lead to inversions between the relative ranking of two interpretations. At the same time, the ranking plainly depends on nothing more than ϕ and µ, such that the result of revision is invariant to the syntax of the prior and new information. Additionally, • sH, max selects the result from the models of µ, and is guaranteed to output something as long as µ is consistent. We summarize these observations in the following proposition.
One detail worth mentioning is that when ϕ is complete all operators presented so far coincide.
Proof. For complete ϕ v it is only the relative ranking of interpretations with respect to v that matters, and this is the same for all three operators.
Proposition 1 shows that the • sH, max operator does not fit neatly into the standard revision framework. However, since, we have argued, • sH, max formalizes an appealing intuition, it will be useful to unearth the general rules underpinning it: our goal, now, is to find a set of normative principles strong enough to characterize • sH, max . A set of such principles is offered in Section 6, but, since • sH, max can be seen as a more involved min-max operator, we set the scene by first characterizing • dH, max . And to set the scene for • dH, max , we first characterize the Dalal operator.

Characterizing the Dalal Operator
In this section we present a set of postulates that characterize the Dalal operator • dH, min . Apart from being of independent interest, this section presents, in the familiar setting of a known operator, the main intuitions and techniques used in subsequent sections. We start by introducing some additional new notions.
A renaming r of A is a bijective function r : A → A. If ϕ is a propositional formula, the renaming r(ϕ) of ϕ is a formula r(ϕ) whose atoms are replaced according to r. On the semantic side, if w is an interpretation and r is a renaming of A, the renaming r(w) of w is an interpretation obtained by replacing every atom p in w with r(p). If W is a set of interpretations, the renaming r(W) of W is defined as r(W) = {r(w) | w ∈ W}, i.e., the set of interpretations whose elements are the renamed interpretations in W.
A flip function f : 2 A × L → L is a function that takes as input a set v ⊆ A of atoms (equivalently, v can be thought of as an interpretation) and a propositional formula ϕ, and returns a propositional formula f v (ϕ) that is just like ϕ except that all the atoms from v that appear in ϕ are flipped, i.e., replaced with their negations. Overloading notation, a flip function applied to interpretations v and w returns an interpretation f v (w) in which all the atoms from v that appear in w are flipped, i.e., f v (w) = {p ∈ A | p ∈ w and p / ∈ v, or p ∈ v and p / ∈ w}. It is straightforward to see that f v (w) = w△v. If W is a set of interpretations, then f v (W) = {f v (w) | w ∈ W}, i.e., the set of interpretations obtained by flipping every atom in v. In Example 3 it holds that: and we note here that all these equalities hold generally (for (ii) see, for instance, Exercise 2.28 in (Goldrei 2005)). Their relevance will become apparent shortly.
To characterize the Dalal operator • dH, min we introduce a set of new postulates, starting with Neutrality R N : Postulate R N states that revision is invariant under renaming atoms and hence neutral in that the specific labels for the atoms do not matter towards the final result. This postulate is inspired by similar ideas in social choice and has appeared before in belief change contexts (Herzig and Rifi 1999;Marquis and Schwind 2014;Haret and Woltran 2019).
The next postulate concerns the effect of flipping the same atoms in both ϕ and µ, and is called, appropriately, the Flipping postulate R F : An additional constraint, the Addition postulate R A , is obtained by considering the effect of adding new atoms that affect the standing of one interpretation, and is meant to apply to any formulas ϕ and µ and set x of new atoms, i.e., such that none of the atoms in x appears in either ϕ or µ: Postulate R A is best understood through a choice perspective: if w 1 is chosen by ϕ over w 2 when the choice is [µ w1,w2 ] = {w 1 , w 2 }, then adding extra new atoms x to w 2 , (and, thereby, increasing the distance to ϕ) ensures that w 2 ∪ x is not chosen when the choice is [µ w1,w2∪x ] = {w 1 , w 2 ∪ x}. In all of these postulates the prior belief ϕ is assumed to be complete: this is not essential for the characterization of the Dalal operator, but makes life easier in the characterization of the surprise minimization operator, in Section 6. The next postulate involves a mix of flips and we ease into it by introducing an intermediary notion. The best-of-best formula β ϕ,µ with respect to ϕ and µ is defined as: i.e., as the result of revising the null formula ε (recall that [ε] = {∅}) by a disjunction made up of multiple versions of µ, where each such version is obtained by flipping the atoms in a model v of ϕ. Intuitively, the intention is to recreate the table of Hamming distances (e.g., In other words, we are creating a scenario in which ε has to choose between interpretations obtained as the symmetric difference of the elements of [ϕ] and [µ]. The result we are working towards, yet to be proven, is that an element of [ v∈ [ϕ] f v (µ)] chosen by ε, i.e., an interpretation w i △v j ∈ [β ϕ,µ ], corresponds to an interpretation w i ∈ [µ] that minimizes the overall Hamming distance to ϕ, and is thus among the best of the best interpretations in this revision scenario. The role of the Best-of-Best postulate R BOB , then, is to recover the models of µ from the models of β ϕ,µ : Postulate R BOB stipulates that the result of revising ϕ by µ consists of those interpretations of µ that come out of flipping β ϕ,µ by each model of ϕ, in this way reversing the initial flips that delivered the revision formula posed to ε.
What is the significance of the null formula ε in β ϕ,µ ? We want to reduce arbitrary revision tasks to a common denominator, a base case in which the result of revision can be decided without explicit appeal to distances (i.e., numbers), and only by appeal to desirable normative principles, such as the postulates laid out above. The case when the prior belief is ε turns out to be well suited for this task, since, as we show next, postulates R 1 , R 3 -R 6 , R N and R A guarantee that ε always selects the interpretations with minimal cardinality.
Proof. ("⊆") Suppose, first, that w 1 ∈ [ε • µ] and there is w 2 ∈ [µ] such that |w 1 | > |w 2 |. Using postulate R 5 we obtain that w 1 ∈ [ϕ•µ w1,w2 ]. We now show that this leads to a contradiction, and we do this using the Neutrality postulate R N : however, we would like to apply R N to interpretations of equal size. Towards this, take a set x of new atoms (i.e., that do not occur in either ϕ or µ), with |x| = |w 1 | − |w 2 |, and add x to w 2 to form w ′ 2 = w 2 ∪ x. We have that |w ′ 2 | = |w 2 | + (|w 1 | − |w 2 |) = |w 1 |, i.e., w 1 and w ′ 2 are of the same size, which implies that |w 1 \ w ′ 2 | = |w ′ 2 \ w 1 |. Applying the addition postulate R A , we obtain that w ′ 2 / ∈ [ε • µ w1,w ′ 2 ]. Consider, now, a renaming r that swaps atoms in w 1 \ w ′ 2 with atoms in w ′ 2 \ w 1 , made possible by the fact that w 1 \ w ′ 2 and w ′ 2 \ w 1 are of the same size. This implies that r(w 1 ) = w ′ 2 and r(w ′ 2 ) = w 1 and thus r( . Applying the Neutrality postulate R N to ε • µ w1,w ′ 2 with the renaming r thus defined, and, keeping in mind that [r(ε)] = [ε], and thus that r(ε) ≡ ε, we obtain that: This implies that w 1 = w ′ 2 but, since w ′ 2 contains a nonnegative number of atoms that do not appear in w 1 , this is a contradiction.
("⊇") For the opposite direction, suppose that w 1 ∈ argmin w∈[µ] |w| but w 1 / ∈ [ε • µ]. Using postulates R 1 and R 3 we have that there is w 2 ∈ [ϕ • µ] and, with postulate R 6 we obtain that [ε • µ w1,w2 ] = {w 2 }. Since |w 1 | ≤ |w 2 | we add to w 1 a set x of new atoms, where |x| = |w 2 | − |w 1 |, and denote w ′ 1 = w 1 ∪ x. Applying R A we obtain that [ε • µ w ′ 1 ,w2 ] = {w 2 } and, using a renaming r defined, as in the previous direction, such that r(w 2 ) = w ′ 1 and r(w ′ 1 ) = w 2 , and applying R N to r and ε • µ w ′ 1 ,w2 , we obtain that [ε • µ w ′ 1 ,w2 ] = {w ′ 1 }, leading to a contradiction. Lemma 1 shows that, in the very particular case in which the prior belief is ε, we can ensure that the result of revision coincides with the result delivered by the Dalal operator. The next move consists in using the Flipping postulate R F to extend this fact to complete formulas. Lemma 2. If a revision operator • satisfies postulates R 1 , R 3 -R 6 , R N , R A and R F , then, for any formula µ and complete formula ϕ v , it holds that w△v∈[fv (µ)] |w△v| and, since d H (v, w) = |w△v|, we derive the conclusion.
Lemma 2 shows that it is not just the formula ε that makes choices consistent with the Dalal operator, but any complete formula ϕ v . The intuition driving Lemma 2 is that the situation where v chooses between w 1 and w 2 is equivalent, through the Flipping postulate R F , to a scenario where ∅ chooses between w 1 △v and w 2 △v: and we know that in this situation postulates R N and R A guide ∅ to choose the interpretation w i △v of minimal cardinality, which corresponds to w i being at minimal Hamming distance to v.
The next step involves pushing this intuition even further, to the case of any propositional formula ϕ. As anticipated, the Best-of-Best postulate R BOB is the postulate that facilitates this move, and the proof goes through the intermediary obervation that the best-of-best formula β ϕ,µ selects interpretations corresponding to the desired redult. Lemma 3. If • is a revision operator that satisfies postulates R 1 , R 3 -R 6 R 4 , R N , R A and R F then, for any formulas ϕ and µ and interpretations w and v, it holds that w△v ∈ [β ϕ,µ ] if and only if w ∈ argmin w∈[µ] min v∈[ϕ] d H (v, w).
Proof. By Lemma 1, [β ϕ,µ ] chooses exactly those interpretations w i △v j , for w i ∈ [µ] and v j ∈ [ϕ], that are of minimal cardinality. Since |w i △v j | = d H (w i , v j ), the conclusion follows immediately.
By Lemma 3, the result of the Dalal operator • dH, min applied to ϕ and µ consists of those interpretations w ∈ [µ] such that w△v ∈ [β ϕ,µ ], for some v ∈ [ϕ]. The Best-of-Best postulate R BOB instructs us that these are exactly the models of µ that should be chosen by an operator •, and provides the final piece in the sought after characterization. Theorem 1. A revision operator • satisfies postulates R 1 , Proof. For one direction, we take as known that the Dalal operator • dH, min satisfies postulates R 1 , R 3−6 (Katsuno and Mendelzon 1992) and R N (Haret and Woltran 2019).
For postulate R N , given Lemma 3, satisfaction of postulates R N , R A , R F and R BOB follows straightforwardly.
For the other direction, we have to show that if • satisfies all the stated postulates, then [ϕ • µ] = argmin w∈[µ] min v∈[ϕ] d H (v, w), for any formulas ϕ and µ. Lemma 3 already gives us that β ϕ,µ selects those inter- } of symmetric differences between models of ϕ and of µ. This means that i.e., if w i is selected by the Dalal operator then it shows up in [( v∈[ϕ] f v (β ϕ,µ )) ∧ µ]. Conversely, suppose there is an interpretation w i ∈ [( v∈[ϕ] f v (β ϕ,µ )) ∧ µ] that is not at minimal distance to ϕ. This means that w i = (w j △v k )△v l , where w j ∈ [µ] corresponds to a model of µ that is at minimal Hamming distance to ϕ and v k , v l ∈ [ϕ]. We infer from this that w i △v l = ((w j △v k )△v l )△v l = w j △v k , and thus |w i △v l | = |w j △v k |. But this contradicts the assumed minimality of w j △v k .
Note that postulate R 2 is not present in Theorem 1, even though the Dalal operator satisfies it, as it follows from the other postulates.
Theorem 1 can be read not just as a characterization of the Dalal operator, but also as a recipe, or a step-by-step argument, for constructing ϕ • µ from a set of simpler problems, in a srquence of steps guided by the transformations inherent in postulates R N , R A , R F and R BOB . The form such an argument could take is illustrated in the following example.    Figure 1: By flipping the atoms of v ∈ [ϕ] in a model w of µ we get an interpretation w△v whose size corresponds to the Hamming distance between v and w, i.e., |v△w| = dH(v, w) = dH(∅, v△w) = dH(∅, fv(w)). In this way, flipped models that get chosen by ε corresponds to models of µ that minimize overall Hamming distance to ϕ.

Characterizing the Hamming Distance Min-Max Operator
The postulates put forward in Section 4 for characterizing the Dalal operator prove their worth in an additional sense, as they can be put to use, with minimal modifications, in characterizing the Hamming distance min-max operator • dH, max . This is the topic of the current section. Of the newly proposed postulates, the Neutrality, Addition and Flipping postulates (R N , R A and R F , respectively) can be used as stated in Section 4, while the Best-of-Best postulate R BOB has to be modified. Intuitively, this makes sense: postulates R N , R A and R F are used in regulating what happens when the prior information is a complete formula ϕ v (alternatively, for what happens in the ranking that corresponds to the v-column in the table of distances, e.g., Table  1), in which case, as per Proposition 2, all operators presented here coincide, whereas postulate R BOB instructs us how to choose when the prior information consists of more than one model (alternatively, across different columns of the table of distances). Correspondingly, postulate R BOB encodes the constraint that revision should pick the best of the best models across all of the ϕ v 's, for v ∈ [ϕ], but this is not the rule that defines operator • dH, max . For • dH, max we need a principle that mandates picking the best of the worst models across the ϕ v 's. The key fact allowing us to do this relies on a certain duality specific to the Hamming distance that will guide us in designing an appropriate postulate for • dH, max , and which is summarized in the following result. Recall that A is the set of all atoms. Lemma 4. If v and w are interpretations and |A| = n, then Intuitively, Lemma 4 implies that the further away w is from v (in terms of Hamming distance), the closer w is to A \ v. In particular, we can infer that: Hence, w ∈ [µ] is among the models of µ at maximal Hamming distance to v if and only if f v (w) is, among the models of f v (µ), the closest to A, or, more intuitively, the worst model of µ according to v is the best model of f v (µ) according to α, where [α] = A. We can thus define the bestof-worst formula γ ϕ,µ with respect to ϕ and µ as: i.e., as the result of revising the null formula ε by a disjunction made up of the results obtained from a sequence of revisions of the full formula α. In this sequence α is revised, in turn, by f v (µ), for every model v ∈ [ϕ]. Thus, similarly as for β ϕ,µ from Section 4, γ ϕ,µ simulates the process of going through the table of Hamming distances (e.g., Table 1), except that in this case we are interested in (i) selecting the worst elements according to each ϕ v , for v ∈ [ϕ], an operation reflected by the revision α • f v (µ), and (ii) selecting the best among these worst elements, an operation reflected by submitting the results obtained previously to ε for an additional round of revision. A bespoke postulate, called the Best-of-Worst postulate R BOW , recovers the models of µ from the models of γ ϕ,µ : Postulate R BOW stipulates that the result of revising ϕ by µ consists of those models of µ that come out of flipping γ ϕ,µ by each model of ϕ, in this way reversing the initial flips that delivered the revision formula posed to ε. The proof that the postulates put forward actually characterize the • dH, max operator hinges on γ ϕ,µ selecting interpretations corresponding to models w of µ that minimize maximal Hamming distance to ϕ. Lemma 5. If • is a revision operator that satisfies postulates R 1 , R 3 -R 6 , R N , R A , R F and R BOW , then, for any formulas ϕ Proof. Using postulates R N , R A and R F we can prove that α selects the models of µ that minimize Hamming distance to A, in a way completely analogous to Lemmas 1 and Lemma 2. Thus, using Equality 1, α Then, using Lemma 1, we obtain that γ ϕ,µ selects interpretations w△v where w minimizes max-distance to ϕ.
With Lemma 5 the characterization of • dH, max follows immediately. Theorem 2. If • is a revision operator, then • satisfies postulates R 1 , R 3 -R 6 , R N , R A , R F and R BOW iff • ≡ • dH, max . The proof is similar, in its essentials, to the proof of Theorem 1 and is therefore omitted. The following example, however, illustrates how the mechanism works on a concrete case.  Figure  2 for an illustration). At this point, we have obtained the (flipped versions of) the models of µ at maximal Hamming distance to a and b, respectively. FOllowing this, we get that [γ ϕ,µ = [ε • (α • f a (µ)) ∨ (α • f b (µ)) ] = {bc}, where bc was obtained from abc by flipping a. Postulate BOW then be recovers abc through an extra flip of a.

Characterizing the Hamming Surprise
Min-Max Operator As expected, the R BOWS postulate delivers exactly those models of µ that minimize maximum surprise, and underpins the final characterization result.
Theorem 3. A revision operator • satisfies postulates R 1 , R 3 -R 4 , R c 5 -R c 6 , R N , R A , R F and R BOWS iff • ≡ • sH, max . The following example illustrates the way in which postulate R BOWS obtains the revision result.

Conclusion
We have introduced the Hamming surprise min-max operator • sH, max , a revision operator that minimizes surprise relative to the prior belief as well as the newly acquired information. We have shown that, even though • sH, max does not satisfy all standard KM revision postulates, it is underpinned, in its choice behavior, by principles similar to those guiding established revision operators, among them appealing symmetry notions such as invariance under renamings and flips. When unearthed and formulated as logical postulates, these principles (or slight variations thereof) turned out to be powerful enough to fully characterize not just the surprise operator, but also the existing Dalal and Hamming distance min-max operator.
One obvious direction for future work lies in taking the idea of context dependence further: what other aspects of the environment influence an agent's plausibility rankings? Things that come to mind are issues of trust, the 'strangeness' of the new information, or peer effects. An alternative is to exploit the bottom-up, DIY nature of some of the postulates presented here in order to construct a framework, similar to that employed in collective decision-making (Cailloux and Endriss 2016), for offering justifications for revision results, i.e., human-readable and at the same time rigorous step-by-step arguments for how to obtain a particular result, starting from a specific set of postulates. Finally, the assumptions embedded in the present treatment call for taking the epistemic stance seriously, and investigating the relative worth of the various revision operators with respect to recovering the ground truth.