# Dictionary Definition

circumscription n : the act of
circumscribing

# User Contributed Dictionary

## English

### Etymology

circumscriptio.### Noun

- the act of circumscribing or the quality of being circumscribed
- anything that circumscribes or a circumscribed area
- the definition of what does and does not belong to a given
taxon, from a particular
taxonomic viewpoint or
taxonomic
system.
- The circumscription in the APG system of the family Malvaceae includes the former families Bombacaceae, Sterculiaceae and Tiliaceae.

#### Translations

act of circumscribing; quality of being
circumscribed

- Italian: circoscrizione

anything that circumscribes or a circumscribed
area

- Italian: circoscrizione

taxonomy: definition of what belongs in a taxon

- Italian: circoscrizione

# Extensive Definition

distinguish circumscribe
Circumscription is a non-monotonic
logic created by
John McCarthy to formalize the common sense
assumption that things are as expected unless otherwise specified.
Circumscription was later used by McCarthy in an attempt to solve
the frame
problem. In its original first-order
logic formulation, circumscription minimizes the extension
of some predicates, where the extension of a predicate is the set
of tuples of values the predicate is true on. This minimization is
similar to the closed
world assumption that what is not known to be true is
false.

The original problem considered by McCarthy was
that of
missionaries and cannibals: there are three missionaries and
three cannibals on one bank of a river; they have to cross the
river using a boat that can only take two, with the additional
constraint that cannibals must never outnumber the missionaries on
either bank (as otherwise the missionaries would be killed and,
presumably, eaten). The problem considered by McCarthy was not that
of finding a sequence of steps to reach the goal (the article on
the
missionaries and cannibals problem contains one such solution),
but rather that of excluding conditions that are not explicitly
stated. For example, the solution “go half a mile south
and cross the river on the bridge” is intuitively not
valid because the statement of the problem does not mention such a
bridge. On the other hand, the existence of this bridge is not
excluded by the statement of the problem either. That the bridge
does not exist is a consequence of the implicit assumption that the
statement of the problem contains everything that is relevant to
its solution. Explicitly stating that a bridge does not exist is
not a solution to this problem, as there are many other exceptional
conditions that should be excluded (such as the presence of a rope
for fastening the cannibals, the presence of a larger boat nearby,
etc.)

Circumscription was later used by McCarthy to
formalize the implicit assumption of inertia: things do not change
unless otherwise specified. Circumscription seemed to be useful to
avoid specifying that conditions are not changed by all actions
except those explicitly known to change them; this is known as the
frame problem. However, the solution proposed by McCarthy was later
shown leading to wrong results in some cases, like in the Yale
shooting problem scenario. Other solutions to the frame problem
that correctly formalize the Yale shooting problem exist; some use
circumscription but in a different way (see frame
problem for details).

## The propositional case

While circumscription was initially defined in
the first-order logic case, the particularization to the
propositional case is easier to define. Given a propositional
formula T, its circumscription is the formula having only the
models of T with a minimal amount of variables assigned to
true.

Formally, propositional models can be represented
by set of propositional
variables; namely, each model is represented by the set of
propositional variables it assign to true. For example, the model
assigning true to a, false to b, and true to c is represented by
the set \, because a and c are exactly the variables that are
assigned to true by this model.

Given two models M and N represented this way,
the condition N \subseteq M is equivalent to M setting to true
every variable that N sets to true. In other words, \subseteq
models the relation of “setting to true less
variables”.

Circumscription is expressed by selecting only
the models that assign to true a minimal amount of variables. It
can therefore defined as follows:

- CIRC(T) = \

Alternatively, one can define CIRC(T) as a
formula having exactly the above set of models; furthermore, one
can also avoid giving a definition of CIRC and only define minimal
inference as T \models_M Q if and only if every model of the above
set is also a model of Q.

As an example, the formula T=a \wedge (b \vee c)
has three models:

- a, b, c are true;
- a and b are true, c is false;
- a and c are true, b is false.

The first model is not minimal in the set of
variables it assigns to true. Indeed, the second models makes the
same assignments but for c, which is assigns to false and not to
true. Therefore, the first model is not minimal. The second and
third models are incomparable: while the second assigns true to b,
the third assigns true to c instead. Therefore, the models
circumscribing T are the second and third models of the list. A
propositional formula having exactly these two models is the
following one:

- a \wedge (b \not\equiv c)

A feature of circumscription is that a variable
is assigned to false only if this is possible. For example, only
one between b or c can be assigned to false according to T, and
circumscription actually assigns exactly one of these variables to
false. The variable a cannot be set to false at all, and
circumscription does not set it to false in any model.

## Fixed and varying predicates

The extension of circumscription with fixed and
varying predicates is due to Vladimir
Lifschitz. The idea is that some conditions are not to be
minimized. In propositional logic terms, some variables are not to
be falsified if possible. In particular, two kind of variables can
be considered:

The difference is that the value of the varying
conditions are simply assumed not to matter. The fixed conditions
instead characterize a possible situation, so that comparing two
situations where these conditions have different value makes no
sense.

Formally, the extension of circumscription that
incorporate varying and fixed variables is as follows, where P is
the set of variables to minimize, Z the fixed variables, and the
varying variables are those not in P \cup Z:

- CIRC(T;P,Z) = \

In words, minimization of the variables assigned
to true is only done for the variables in P; moreover, models are
only compared if the assign the same values on the variables of Z.
All other variables are not taken into account while comparing
models.

The solution to the frame problem proposed by
McCarthy is based on circumscription with no fixed conditions. In
the propositional case, this solution can be described as follows:
in addition to the formulae directly encoding what is known, one
also define new variables representing changes in the values of the
conditions; these new variables are then minimized.

For example, of the domain in which there is a
door that is closed at time 0 and in which the action of opening
the door is executed at time 2, what is explicitly known is
represented by the two formulae:

- \neg open_0
- true \rightarrow open_2

The frame problem shows in this example as the
problem that \neg open_1 is not a consequence of the above
formulae, while the door is supposed to stay closed until the
action of opening it is performed. Circumscription can be used to
this aim by defining new variables change\_open_t to model changes
and then minimizing them:

- change\_open_0 \equiv (open_0 \not\equiv open_1)
- change\_open_1 \equiv (open_1 \not\equiv open_2)
- ...

As shown by the Yale
shooting problem, this kind of solution does not work. For
example, \neg open_1 is not yet entailed by the circumscription of
the formulae above: the model in which change\_open_0 is true and
change\_open_1 is false is incomparable with the model with the
opposite values. Therefore, the situation in which the door becomes
open at time 1 and then remains open as a consequence of the action
is not excluded by circumscription.

Several other formalizations of dynamical domains
not suffering from such problems have been developed (see frame
problem for an overview). Many use circumscription but in a
different way.

## Predicate circumscription

The original definition of circumscription
proposed by McCarthy is about first-order logic. The role of
variables in propositional logic (something that can be true or
false) is played in first-order logic by predicates. Namely, a
propositional formula can be expressed in first-order logic by
replacing each propositional variable with a predicate of zero
arity (i.e., a predicate with no arguments). Therefore,
minimization is done on predicates in the first-order logic version
of circumscription: the circumscription of a formula is obtained
forcing predicates to be false whenever possible.

Given a first-order logic formula T containing a
predicate
P, circumscribing this predicate amounts to select only the models
of T in which P is assigned to true on a minimal set of tuples of
values.

Formally, the extension of a predicate in a
first-order model is the set of tuples of values this predicate
assign to true in the model. First-order models indeed includes the
evaluation of each predicate symbol; such an evaluation tells
whether the predicate is true or false for any possible value of
its arguments. Since each argument of a predicate must be a term,
and each term evaluates to a value, the models tells whether
P(v_1,\ldots,v_n) is true for any possible tuple of values \langle
v_1,\ldots,v_n \rangle. The extension of P in a model is the set of
tuples of terms such that P(v_1,\ldots,v_n) is true in the
model.

The circumscription of a predicate P in a formula
T is obtained by selecting only the models of T with a minimal
extension of P. For example, if a formula has only two models,
differing only because P(v_1,\ldots,v_n) is true in one and false
in the second, then only the second model is selected. This is
because \langle v_1,\ldots,v_n \rangle is in the extension of P in
the first model but not in the second.

The original definition by McCarthy was
syntactical rather than semantical. Given a formula T and a
predicate P, circumscribing P in T is the following second-order
formula:

- T(P) \wedge \forall p \neg (T(p) \wedge p

In this formula p is a predicate of the same
arity as P. This is a second-order formula because it contains a
quantification over a predicate. The subformula p is a shorthand
for:

- \forall x (p(x) \rightarrow P(x)) \wedge

In this formula, x is a n-tuple of terms, where n
is the arity of P. This formula states that extension minimization
has to be done: in order for a truth evaluation on P of a model
being considered, it must be the case that no other predicate p can
assign to false every tuple that P assigns to false and yet being
different from P.

This definition only allows circumscribing a
single predicate. While the extension to more than one predicate is
trivial, minimizing the extension of a single predicate has an
important application: capturing the idea that things are usually
as expected. This idea can be formalized by minimized a single
predicate expressing the abnormality of situations. In particular,
every known fact is expressed in logic with the addition of a
literal \neg Abnormal(...) stating that the fact holds only in
normal situations. Minimizing the extension of this predicate
allows for reasoning under the implicit assumption that things are
as expected (that is, they are not abnormal), and that this
assumption is made only if possible (abnormality can be assumed
false only if this is consistent with the facts.)

## Pointwise circumscription

Pointwise circumscription is a variant of
first-order circumscription that has been introduced by Vladimir
Lifschitz. In the propositional case, pointwise and predicate
circumscription coincide. The rationale of pointwise
circumscription it minimize the value of a predicate for each tuple
of values separately, rather than minimizing the extension of the
predicate. For example, there are two models of P(a) \equiv P(b)
with domain \, one setting P(a)=P(b)=false and the other setting
P(a)=P(b)=true. Since the extension of P in the first model is
\emptyset while the extension for the second is \, circumscription
only selects the first model.

In pointwise circumscription, each tuple of
values is considered separately. For example, in the formula P(a)
\equiv P(b) one would consider the value of P(a) separately from
P(b). A model is minimal only it is not possible to turn any such
value from true to false while still satisfying the formula. As a
result, the model in which P(a)=P(b)=true is selected by pointwise
circumscription because turning only P(a) into false does not
satisfy the formula, and the same happens for P(b).

## Domain and Formula Circumscription

An earlier formulation of circumscription by
McCarthy is based on minimizing the domain
of first-order models, rather than the extension of predicates.
Namely, a model is considered less than another if it has a smaller
domain, and the two models coincide on the evaluation of the common
tuples of values. This version of circumscription can be reduced to
predicate circumscription.

Formula circumscription was a later formalism
introduced by McCarthy. This is a generalization of circumscription
in which the extension of a formula is minimized, rather than the
extension of a predicate. In other words, a formula can be
specified so that the set of tuples of values of the domain that
satisfy the formula is made as small as possible.

## Theory curbing

Circumscription does not always correctly handle
disjunctive information. Ray Reiter
provided the following example: a coin is tossed over a checkboard,
and the result is that the coin is either on a black area, or on a
white area, or both. However, there are a large number of other
possible places where the coin is not supposed to be on; for
example, it is implicit that the coin is not on the floor, or on
the refrigerator, or on the moon surface. Circumscription can
therefore be used to minimize the extension of On predicate, so
that On(coin,moon) is false even if this is not explicitly
stated.

On the other hand, the minimization of the On
predicate leads to the wrong result that the coin is either on a
black area or on a white area, but not both. This is because the
models in which On is true only on (coin,white\_area) and only on
(coin,black\_area) have a minimal extension of On, while the model
in which the extension of On is composed of both pairs is not
minimal.

Theory curbing is a solution proposed by Thomas
Eiter, Georg Gottlob, and Yuri Gurevich. The idea is that the model
that circumscription fails to select, the one in which both
On(coin,white\_area) and On(coin,black\_area) are true, is a model
of the formula that is greater (w.r.t. the extension of On) than
both the two models that are selected. More specifically, among the
models of the formula, the excluded model is the least upper bound
of the two selected models. Theory curbing selects such least upper
bounds models in addition to the ones selected by circumscription.
This inclusion is done until the set of models is closed, in the
sense that includes all least upper bounds of all sets of models it
contains.

## See also

## References

- M. Cadoli (1992). The complexity of model checking for circumscriptive formulae. Information Processing Letters, 44:113-118.

- M. Cadoli and M. Lenzerini (1994). The complexity of propositional closed world reasoning and circumscription. Journal of Computer and System Sciences, 48:255-310.

- T. Eiter and G. Gottlob (1993). Propositional circumscription and extended closed world reasoning are \Pi^p_2-complete. Theoretical Computer Science, 114:231-245.

- T. Eiter, G. Gottlob, and Y. Gurevich (1993). CURB your theory! In Proceedings of the Thirteenth International Joint Conference on Artificial Intelligence (IJCAI'93), pages 634-639.

- V. Lifschitz (1985). Closed-world databases and circumscription. Artificial Intelligence, 27:229-235.

- V. Lifschitz (1986). Pointwise circumscription. In Proceedings of the Fifth National Conference on Artificial Intelligence (AAAI'86), pages 406-410.

- V. Lifschitz (1994). Circumscription. In Handbook of Logic in Artificial Intelligence and Logic Programming, Volume 3, pages 297-352. Oxford University Press.

- J. McCarthy (1980). Circumscription - A form of non-monotonic reasoning. Artificial Intelligence, 13:27-39.

- J. McCarthy (1986). Applications of circumscription to formalizing common-sense knowledge. Artificial Intelligence, 28:89-116.

## External links

circumscription in Chinese: 限制

# Synonyms, Antonyms and Related Words

abbreviation, allowance, astriction, astringency, ban, bar, barring, beleaguerment, besetment, blockade, blockading, border line,
bottleneck, bound, boundaries, boundary, boundary condition,
boundary line, bounds,
bourn, bourns, boycott, break boundary,
breakoff point, ceiling,
cervix, cession, circumference, coarctation, compactedness, compaction, compass, compression, compressure, concentration, concession, condensation, confine, confinement, confines, consolidation, constriction, constringency, contraction, contracture, coordinates, cordoning, cramp, cramping, curtailment, cutoff, cutoff point, deadline, debarment, debarring, decrease, delimitation, demarcation, determinant, diminuendo, division line,
edges, embargo, enclosure, end, envelopment, exception, exclusion, exemption, extenuating
circumstances, extremity, finish, floor, fringes, frontier, grain of salt,
grant, hedge, hedging, high-water mark,
hourglass, hourglass
figure, immurement,
imprisonment,
inadmissibility,
incarceration,
inclusion, injunction, interface, isthmus, knitting, limen, limit, limitation, limitations, limiting
factor, limits, line, line of demarcation, lockout, low-water mark, lower
limit, march, marches, mark, mental reservation, mete, metes, metes and bounds, modification, narrow place,
narrowing, neck, nonadmission, omission, outlines, outskirts, pale, parameters, perimeter, periphery, preclusion, prohibition, puckering, pursing, qualification, quarantine, reduction, rejection, relegation, repudiation, reservation, restraint, restriction, salvo, shortening, siege, skirts, solidification, special
case, special treatment, specialness, specification, start, starting line, starting
point, stint, stranglement, strangulation, striction, stricture, systole, taboo, target date, term, terminal date, terminus, threshold, time allotment,
upper limit, verges,
waiver, wasp waist,
wrinkling