text:
# Logic Programming with Ordered Disjunction

## 1 Introduction

In a recent paper  a propositional logic called Qualitative Choice Logic ($`\mathrm{𝑄𝐶𝐿}`$) was introduced. The logic contains a new connective $`\times `$ representing ordered disjunction. Intuitively, $`A\times B`$ stands for: if possible $`A`$, but if $`A`$ is impossible then (at least) $`B`$. This connective allows context dependent preferences to be represented in a simple and elegant fashion. As a simple example consider the preferences for booking a hotel for a conference. Assume the most preferred option is to be within walking distance from the conference site, the second best option is to have transportation provided by the hotel, the third best is public transportation. This can simply be represented as

$$walking\times hoteltransport\times publictransport$$

From a description of available hotels, a disjunction expressing that one of the hotels must be picked, and the above formula $`\mathrm{𝑄𝐶𝐿}`$ is able to derive the hotel which satisfies best the given preferences (if there is more than one such hotel a corresponding disjunction is concluded).

The semantics of the logic is based on degrees of satisfaction of a formula in a classical model. The degrees, intuitively, measure disappointment and induce a preference relation on models. Consequence is defined in terms of most preferred models. It is argued in that paper that there are numerous useful applications, e.g. in configuration and design.

In this paper we want to combine ideas underlying $`\mathrm{𝑄𝐶𝐿}`$ with logic programming. More precisely, we want to investigate logic programs based on rules with ordered disjunction in the heads. We call such programs logic programs with ordered disjunction ($`\mathrm{𝐿𝑃𝑂𝐷}`$s).

The semantical framework in which the investigation will be carried out is that of answer set semantics . Logic programs under answer set semantics have emerged as a new promising programming paradigm dubbed answer set programming. There are numerous interesting AI applications of answer set programming, for instance in planning  and configuration . One of the reasons for this success is the availability of highly efficient systems for computing answer sets like smodels  and dlv .

We think it is worthwhile to investigate simple representations of context dependent preferences in the answer set programming paradigm. Our combination of ideas from $`\mathrm{𝑄𝐶𝐿}`$ and answer set programming will lead to an approach which is less expressive than $`\mathrm{𝑄𝐶𝐿}`$ in one respect: the syntax of $`\mathrm{𝐿𝑃𝑂𝐷}`$s restricts the appearance of ordered disjunction to the head of rules. On the other hand, we inherit from answer set programming the nonmonotonic aspects which are due to default negation. This allows us to combine default knowledge with knowledge about preferences and desires in a simple and elegant way.

The basic intuition underlying our approach can be described as follows: we will use the ordered disjunctions in rule heads to select some of the answer sets of a program as the preferred ones. Consider a program containing the rule

$$A\times BC$$

If $`S_1`$ is an answer set containing $`C`$ and $`A`$ and $`S_2`$ is an answer set containing $`C`$ and $`B`$ but not $`A`$, then - ceteris paribus (other things being equal) - $`S_1`$ is preferred over $`S_2`$. Of course, we have to give precise meaning to the ceteris paribus phrase. Intuitively ceteris paribus is to be read as $`S_1`$ and $`S_2`$ satisfy the other rules in the program equally well.

We will show that under certain conditions reasoning from most preferred answer sets yields optimal problem solutions. In more general decision making settings the preference relation on answer sets provides a basis for best possible choices given a specific decision strategy.

We will restrict our discussion in this paper to propositional programs. However, as usual in answer set programming, we admit rule schemata containing variables bearing in mind that these schemata are just convenient representations for the set of their ground instances.

The rest of the paper is organized as follows. In the next section we introduce syntax and semantics of $`\mathrm{𝐿𝑃𝑂𝐷}`$s. We define the degree of satisfaction of a rule in an answer set and show how to use the degrees to determine a preference relation on answer sets. Conclusions are defined as the literals true in all preferred answer sets. The subsequent section discusses some simple examples and potential applications. We then investigate implementation issues. The following section shows how $`\mathrm{𝐿𝑃𝑂𝐷}`$s can serve as a basis for a qualitative decision making. The last section discusses related work and concludes.

## 2 Logic programs with ordered disjunction

Logic programming with ordered disjunction is an extension of logic programming with two kinds of negation (default and strong negation) . The new connective $`\times `$ representing ordered disjunction is allowed to appear in the head of rules only. A (propositional) $`\mathrm{𝐿𝑃𝑂𝐷}`$ thus consists of rules of the form

$$C_1\times \mathrm{}\times C_nA_1,\mathrm{},A_m,\mathrm{not}B_1,\mathrm{},\mathrm{not}B_k$$

where the $`C_i`$, $`A_j`$ and $`B_l`$ are ground literals.

The intuitive reading of the rule head is: if possible $`C_1`$, if $`C_1`$ is not possible then $`C_2`$, …, if all of $`C_1,\mathrm{},C_{n1}`$ are not possible then $`C_n`$. The literals $`C_i`$ are called choices of the rule. Extended logic programs with two negations are a special case where $`n=1`$ for all rules. As usual we omit $``$ whenever $`m=0`$ and $`k=0`$, that is, if the rule is a fact. Moreover, rules of the form $`body`$ (constraints) are used as abbreviations for $`pbody,\mathrm{not}p`$ for some $`p`$ not appearing in the rest of the program. The effect is that no answer sets containing $`body`$ exist.

Before defining the semantics of $`\mathrm{𝐿𝑃𝑂𝐷}`$s a few observations are in order. As already mentioned in the introduction we want to use the ranking of literals in the head of rules to select some of the answer sets of a program as the preferred ones. But what are the answer sets of a program among which to make this selection?

Since ordered disjunction is a particular prioritized form of disjunction it seems like a natural idea to base the semantics of $`\mathrm{𝐿𝑃𝑂𝐷}`$s on one of the standard semantics for disjunctive logic programs, for instance Gelfond and Lifschitz’s semantics .

Unfortunately, this doesn’t work. The problem is that most of the semantics for disjunctive logic programs have minimality built in. For instance, according to Gelfond and Lifschitz, $`S`$ is an answer set of a disjunctive logic program $`P`$ iff $`S`$ is a minimal set of literals which is logically closed, and closed under the $`S`$-reduct of $`P`$. The $`S`$-reduct of $`P`$ is obtained from $`P`$ by (1) deleting all rules $`r`$ from $`P`$ such that $`\mathrm{not}B_j`$ in the body of $`r`$ and $`B_jS`$, and (2) deleting all default negated literals from the remaining rules. A set of literals $`S`$ is closed under a rule $`r`$ if one of the literals in the head of $`r`$ is in $`S`$ whenever the body is true in $`S`$ (see  for the details).

In this approach answer sets are minimal: if $`S_1`$ and $`S_2`$ are answer sets of a disjunctive program $`P`$ and $`S_1S_2`$, then $`S_2S_1`$.

Minimality is not always wanted for $`\mathrm{𝐿𝑃𝑂𝐷}`$s. Consider the following two facts:

> 1) $`A\times B\times C`$
> 2) $`B\times D`$

The single best way of satisfying both ordered disjunctions is obviously to make $`A`$ and $`B`$ true, that is, we would expect $`\{A,B\}`$ to be the single preferred answer set of this simple $`\mathrm{𝐿𝑃𝑂𝐷}`$. However, since $`B`$ is sufficient to satisfy both disjunctions, the set $`\{A,B\}`$ is not even an answer set of the corresponding disjunctive logic program (where $`\times `$ is replaced by $``$) according to the semantics of : the built in minimality precludes sets containing both $`A`$ and $`B`$ from consideration.

We thus have to use a semantics which is not minimal. Indeed, there is such a semantics, the possible models semantics proposed by Sakama and Inoue . It is based on so-called split programs, that is, disjunction free programs which contain arbitrary subsets of single head rules obtained from disjunctive rules by deleting all but one alternatives in the head.

Unfortunately, also this semantics is inadequate, this time for opposite reasons: it admits too many literals in answer sets. Consider the disjunctive logic program

> 1) $`ABC`$

There are seven split programs corresponding to the nonempty subsets of the literals of the fact. The split program containing the facts $`A,B,C`$ generates the possible model where $`A,B,C`$ is true.

Let us replace disjunction by ordered disjunction in this formula. According to our intuitive discussion we want to read the rule as ”if possible $`A`$, if this is not possible then $`B`$, and if also $`B`$ is not possible then $`C`$”. Under this reading models containing more than one of the literals in the head do not seem justified on the basis of a single rule (they may be justified by different rules, though).

For this reason we will not allow cases where a single rule of the original program gives rise to more than one rule in the split program. There is a further complication: consider the program:

> 1) $`A\times B\times C`$
> 2) $`A`$

We do not want to obtain $`\{A,B\}`$ as an answer set from the split program consisting of these 2 atomic facts since again this does not correspond to the intuitive reading of the first rule ($`B`$ only if $`A`$ is not possible). We therefore have to use slightly more complicated rules in split programs.

###### Definition 1

Let $`r=C_1\times \mathrm{}\times C_nbody`$ be a rule. For $`kn`$ we define the $`k`$th option of $`r`$ as

$$r^k=C_kbody,\mathrm{not}C_1,\mathrm{},\mathrm{not}C_{k1}.$$

###### Definition 2

Let $`P`$ be an $`\mathrm{𝐿𝑃𝑂𝐷}`$. $`P^{}`$ is a split program of $`P`$ if it is obtained from $`P`$ by replacing each rule in $`P`$ by one of its options.

Here is a simple example. Let $`P`$ consist of the rules

> 1) $`A\times B\mathrm{not}C`$
> 2) $`B\times C\mathrm{not}D`$

We obtain 4 split programs

| $`A\mathrm{not}C`$ | $`A\mathrm{not}C`$ |
| --- | --- |
| $`B\mathrm{not}D`$ | $`C\mathrm{not}D,\mathrm{not}B`$ |
|  |
| $`B\mathrm{not}C,\mathrm{not}A`$ | $`B\mathrm{not}C,\mathrm{not}A`$ |
| $`B\mathrm{not}D`$ | $`C\mathrm{not}D,\mathrm{not}B`$ |

Split programs do not contain ordered disjunction. We thus can define:

###### Definition 3

Let $`P`$ be an $`\mathrm{𝐿𝑃𝑂𝐷}`$. A set of literals $`A`$ is an answer set of $`P`$ if it is a consistent answer set of a split program $`P^{}`$ of $`P`$.

We exclude inconsistent answer sets from consideration since they do not represent possible problem solutions. In the example above we obtain 3 answer sets: $`\{A,B\},\{C\},\{B\}`$. Note that one of the answer sets is a proper subset of another answer set. On the other hand, none of the rules in the original $`\mathrm{𝐿𝑃𝑂𝐷}`$ sanctions more than one literal in any of the answer sets, as intended.

Not all of the answer sets satisfy our most intended options. Clearly, $`\{B,A\}`$ gives us the best options for both rules, whereas $`\{C\}`$ gives only the second best option for 2) and $`\{B\}`$ the second best option for 1). To distinguish between more and less intended answer sets we introduce the degree of satisfaction of a rule in an answer set:

###### Definition 4

Let $`S`$ be an answer set of an $`\mathrm{𝐿𝑃𝑂𝐷}`$ $`P`$. $`S`$ satisfies the rule

$$C_1\times \mathrm{}\times C_nA_1,\mathrm{},A_m,\mathrm{not}B_1,\mathrm{},\mathrm{not}B_k$$

* to degree 1 if $`A_jS`$, for some j, or $`B_iS`$, for some i,
* to degree j $`(1jn)`$ if all $`A_jS`$, no $`B_iS`$, and $`j=min\{r\text{ }|\text{ }C_rS\}`$.

###### Proposition 1

If $`A`$ is an answer set of $`P`$ then $`A`$ satisfies all rules of $`P`$ to some degree.111The other direction of the proposition does obviously not hold. For example, the set $`\{A\}`$ satisfies the rule $`B\mathrm{not}A`$, but is not an answer set for the program consisting of this single rule.

Proof:   Let $`r`$ be a rule of $`P`$. If $`S`$ is an answer set of $`P`$, then there is a split program $`P^{}`$ such that $`S`$ is an answer set of $`P^{}`$. Let $`r^i`$ be the rule in $`P^{}`$ generated from $`r`$. Since $`S`$ is an answer set of $`P^{}`$ either the body of $`r^i`$ is satisfied in $`S`$ and thus $`C_i`$ is contained in $`S`$, in which case $`r`$ is satisfied to degree $`i`$ or smaller, or the body of $`r^i`$ is not satisfied in $`S`$, in which case $`r`$ is satisfied to degree 1 in $`S`$, or there is a better choice than $`C_k`$, $`k<i`$, in $`S`$ and $`r`$ is satisfied to degree $`k`$. $`\mathrm{}`$ We use the degrees of satisfaction of a rule to define a preference relation on answer sets. There are different ways of doing this. For instance, we could simply add up the satisfaction degrees of all rules and prefer those answer sets where the total sum is minimal. Although this may be reasonable in certain applications, this approach makes quite strong assumptions about the commensurability of choices in different rule heads. In  a lexicographic ordering of models based on the number of premises satisfied to a particular degree was proposed. This lexicographic ordering has a highly syntactic flavour. Therefore, we will use here a somewhat more cautious preference relation (in the sense that fewer answer sets are considered better than others) based on set inclusion of the rules satisfied to certain degrees:

###### Definition 5

For a set of literals $`S`$, let $`S^i(P)`$ denote the set of rules in $`P`$ satisfied by $`S`$ to degree $`i`$. Let $`S_1`$ and $`S_2`$ be answer sets of an $`\mathrm{𝐿𝑃𝑂𝐷}`$ $`P`$. $`S_1`$ is preferred to $`S_2`$ ($`S_1>S_2`$) iff there is $`i`$ such that $`S_2^i(P)S_1^i(P)`$, and for all $`j<i`$, $`S_1^j(P)=S_2^j(P)`$.

###### Definition 6

A set of literals $`S`$ is a preferred answer set of an $`\mathrm{𝐿𝑃𝑂𝐷}`$ $`P`$ iff $`S`$ is an answer set of $`P`$ and there is no answer set $`S^{}`$ of $`P`$ such that $`S^{}>S`$.

###### Definition 7

A literal $`l`$ is a conclusion of an $`\mathrm{𝐿𝑃𝑂𝐷}`$ $`P`$ iff $`l`$ is contained in all preferred answer sets of $`P`$.

Consider again the program

> 1) $`A\times B\mathrm{not}C`$
> 2) $`B\times C\mathrm{not}D`$

As discussed before we obtain the 3 answer sets: $`S_1=\{A,B\}`$, $`S_2=\{C\}`$ and $`S_3=\{B\}`$. $`S_1`$ satisfies both rules with degree 1, $`\{C\}`$ satisfies 1) to degree 1 but 2) to degree 2. $`\{B\}`$ satisfies 1) to degree 2 and 2) to degree 1. The single preferred answer set is thus $`S_1`$, as intended, and $`A`$ and $`B`$ are the conclusions of the program.

## 3 Examples

$`\mathrm{𝐿𝑃𝑂𝐷}`$s allow us - like normal logic programs - to express incomplete and defeasible knowledge through the use of default negation. In addition, they provide means to represent preferences among intended properties of problem solutions. Moreover, these preferences may depend on the current context.

In this section we discuss several examples illustrating potential uses of $`\mathrm{𝐿𝑃𝑂𝐷}`$s. The first example is about how to spend a free afternoon. You like to go to the beach, but also to the cinema. Normally you prefer the cinema over the beach, unless it is hot (which is the exception in the area where you live, except during the summer). If it is hot the beach is preferred over the cinema. In summer it is normally hot, but there are exceptions. If it rains the beach is out of question. This information can be represented using the following rules:

> 1) $`cinema\times beach\mathrm{not}hot`$
> 2) $`beach\times cinemahot`$
> 3) $`hot\mathrm{not}\neg hot,summer`$
> 4) $`\neg beachrain`$

Without further information about the weather we obtain the single preferred answer set $`S_1=\{cinema\}`$. There is no information that it might be hot, so rule 1) will determine the preferences. $`S_1`$ satisfies all rules to degree 1.

Now assume the fact $`summer`$ is additionally given. In this case we obtain $`S_2=\{summer,hot,beach\}`$ as the single preferred answer set. Again this answer set satisfies all rules to degree 1.

Next assume that, in addition to $`summer`$ also the literal $`\neg hot`$ is given. The single preferred answer set now is $`S_3=\{summer,\neg hot,cinema\}`$. All rules are staisfied to degree 1.

Finally, assume the additional facts are $`summer`$ and $`rain`$. Now the single preferred answer set (and in fact the single answer set) is

$$S_4=\{summer,rain,hot,\neg beach,cinema\}.$$

Note that this time it is not possible to satisfy all rules to degree 1: rule 2) is satisfied to degree 2 only. As often in real life, there are situations where the best options simply do not work out.

We think that $`\mathrm{𝐿𝑃𝑂𝐷}`$s are very well suited for representing problems where a certain choice has to be made or, more generally, where a number of components have to be chosen for a certain configuration task. The general idea would be to have

* for each component a set of rules describing its properties,
* rules describing which components are needed for the configuration to be complete; this may depend on other components chosen,
* rules describing intended properties of the solution we want to generate. The involved preferences may be context dependent, and
* a description of the case at hand.

In each case default knowledge can be used to describe what is normally the case. Consider the problem of configuring a menu. The menu should consist of a $`starter`$, a $`main`$ course, a $`dessert`$ and a $`beverage`$. As a $`starter`$ you prefer $`soup`$ over $`salad`$. As $`main`$ course $`fish`$, $`beef`$ and $`lasagne`$ are possible (this is all you are able to cook) and your preferences are in this order. Of course, if the visitor is $`vegetarian`$ the first two (as well as the $`soup`$) are out of the question. In case of $`beef`$ you prefer $`red`$ wine over $`white`$ wine over mineral $`water`$, otherwise the order between wines is reversed. Only $`icecoffee`$ and $`tiramisu`$ is available as a $`dessert`$. If $`tiramisu`$ is chosen, then an extra $`coffee`$ is necessary. You prefer $`espresso`$ over $`cappucino`$.

The possible components thus are $`soup`$, $`salad`$, $`fish`$, $`beef`$, $`lasagne`$, $`icecoffee`$, $`tiramisu`$, $`espresso`$, $`cappucino`$, $`red`$, $`white`$ and $`water`$. The following properties of the components are relevant:

| $`\neg vegetarianbeef`$ | $`alcoholwhite`$ |
| --- | --- |
| $`\neg vegetarianfish`$ | $`alcoholred`$ |
| $`\neg vegetariansoup`$ |

The needed components are

| $`starter`$ | $`beverage`$ |
| --- | --- |
| $`main`$ | $`coffeetiramisu`$ |
| $`dessert`$ |

The preferences are as follows:

| $`soup\times saladstarter`$ |
| --- |
| $`fish\times beef\times lasagnemain`$ |
| $`red\times white\times waterbeverage,beef`$ |
| $`white\times red\times waterbeverage,\mathrm{not}beef`$ |
| $`espresso\times cappuccinocoffee`$ |
| $`icecoffee\mathrm{not}tiramisu,dessert`$ |
| $`tiramisu\mathrm{not}icecoffee,dessert`$ |

Now, given a description of the case at hand, e.g. whether the visitor is vegetarian or not, drinks alcohol or not, likes fish etc. the preferred answer sets will determine a menu which satisfies the preferences as much as possible. The last two rules are necessary to make sure that one of the desserts is picked. For the other courses this is implicit in the specified preferences. In the language of  these rules can be represented as the cardinality constraint rule $`1\{icecoffee,tiramisu\}1dessert`$. Combinations of $`\mathrm{𝐿𝑃𝑂𝐷}`$s and such constraints are a topic of further research.

## 4 Computation

The first question to ask is whether $`\mathrm{𝐿𝑃𝑂𝐷}`$s can simply be reduced to standard logic programs with two kinds of negation. In that case standard answer set programming techniques would be sufficient for computing consequences of $`\mathrm{𝐿𝑃𝑂𝐷}`$s. We will show that a seemingly natural translation does not yield the intended answer sets.

###### Definition 8

The pseudo-translation $`trans(r)`$ of a rule

$$r=C_1\times \mathrm{}\times C_nbody$$

is the collection of rules

| $`C_1`$ | $`body,\mathrm{not}C_1`$ |
| --- | --- |
| $`C_2`$ | $`body,\mathrm{not}C_2,C_1`$ |
| $`\mathrm{}`$ |
| $`C_{n1}`$ | $`body,\mathrm{not}C_{n1},C_1,\mathrm{},C_{n2}`$ |
| $`C_n`$ | $`body,C_1,\mathrm{},C_{n1}`$ |

where $`C`$ is the complement of $`C`$, that is $`\neg C`$ if $`C`$ is an atom and $`C^{}`$ if $`C=\neg C^{}`$. The pseudo-translation $`trans(P)`$ of an $`\mathrm{𝐿𝑃𝑂𝐷}`$ $`P`$ is

$$trans(P)=\underset{rP}{}trans(r)$$

The pseudo-translation creates for each option $`C_i`$ in the head of $`r`$ a rule with head $`C_i`$ which has the negation of the better options as additional body literals. In addition, the rule is made defeasible by adding the default negation of the complement of $`C_i`$ to the body. There is an exception: the rule generated for the last option is not made defeasible this way since at least one of the options must be true whenever the body of the original rule is true.

Although this translation seems natural it does not work. Consider the following example:

> 1) $`a\times b`$
> 2) $`p\mathrm{not}p,a`$

The single preferred answer set is $`\{b\}`$. The pseudo-translation is

> 1) $`a\mathrm{not}\neg a`$
> 2) $`b\neg a`$
> 3) $`p\mathrm{not}p,a`$

The resulting program has no answer set. In fact, we can prove the following proposition:

###### Proposition 2

There is no translation $`trans`$ from $`\mathrm{𝐿𝑃𝑂𝐷}`$s to extended logic programs (without ordered disjunction) such that for each program $`P`$ the preferred answer sets of $`P`$ and the answer sets of $`trans(P)`$ coincide.

Proof:   The proposition follows from the fact that preferred answer sets of $`\mathrm{𝐿𝑃𝑂𝐷}`$s are not necessarily subset minimal. Consider the program $`a\times b`$; $`c\times ba`$; $`\neg c`$. The preferred answer sets are $`S_1=\{b,\neg c\}`$ and $`S_2=\{a,b,\neg c\}`$. Clearly, $`S_1S_2`$. There is thus no extended logic program with these answer sets. $`\mathrm{}`$

Of course, this does not exclude the possibility of translations to programs containing some extra atoms. This is a topic of further study.

An implementation of $`\mathrm{𝐿𝑃𝑂𝐷}`$s on top of a standard answer set prover for non-disjunctive programs is described in . We compute preferred answer sets of an $`\mathrm{𝐿𝑃𝑂𝐷}`$ $`P`$ using two programs. A similar approach is used in  to compute stable models of disjunctive logic programs using *Smodels*. The two programs are:

* A *generator* $`G(P)`$ that creates all answer sets of $`P`$; and
* A *tester* $`T(P,M)`$ that checks whether a given answer set $`M`$ of $`P`$ is maximally preferred.

The two programs are run in an interleaved fashion. First, the generator constructs an arbitrary answer set $`M`$ of $`P`$. Next, the tester tries to find an answer set $`M^{}`$ that is strictly better than $`M`$. The tester possesses an answer set $`M^{}`$ iff $`M^{}`$ is an answer set of $`P`$ preferred to $`M`$. If there is no such $`M^{}`$, we thus know that $`M`$ is a preferred answer set. Otherwise, we use $`G(P)`$ to construct the next candidate. When we want to find only one preferred answer set we can save some effort by taking $`M^{}`$ directly as the new answer set candidate. We can thus iterate until a maximally preferred answer set is reached.

Since the tester is based on a declarative representation of the preference criterion it is easy to switch between different notions of preference, or to define new ones.

We have constructed a prototype implementation for $`\mathrm{𝐿𝑃𝑂𝐷}`$s based on *Smodels*, an efficient ASP solver developed at Helsinki University of Technology. The generator and tester programs use special rule types of the *Smodels* system, but they can be modified to work with any ASP solver. The prototype implementation is available at http://www.tcs.hut.fi/Software/smodels/priority. The mentioned paper contains also complexity results related to $`\mathrm{𝐿𝑃𝑂𝐷}`$s.

## 5 Decision Making using LPODs

In Section 3 we discussed several examples illustrating the notions underlying LPODs. The examples were chosen in such a way that the most preferred answer sets in each case provided the best solutions to the problem at hand. Later in this section we will analyze why this worked for the chosen examples.

In more general decision making settings it is not sufficient to consider the most preferred answer sets only since this amounts to an extremely optimistic view about how the world will behave (this view is sometimes called wishful thinking). As is well-known in decision theory, for realistic models of decision making it is necessary to clearly distinguish what is under the control of the agent (and thus may constitute the agent’s decision) from what is not. We will do this by distinguishing a subset of the literals in a program as decision literals.

In this section we describe a general methodology for qualitative decision making based on $`\mathrm{𝐿𝑃𝑂𝐷}`$s. The basic idea is to use $`\mathrm{𝐿𝑃𝑂𝐷}`$s to describe possible actions or decisions and their consequences, states of the world and desired outcomes. The representation of desires induces, through ordered disjunction, a preference ordering on answer sets representing their desirability. Based on this preference ordering an ordering on possible decisions can be defined based on some decision strategy.

Let us describe the necessary steps more precisely:

1. Among the literals in the logical language distinguish a set of decision literals $`C`$. $`C`$ is the set of literals the agent can decide upon. It’s the agent’s decision which makes them true. A decision is a consistent subset of $`C`$.
2. Represent the different alternative decisions which can be made by the agent. This can be done using standard answer set programming techniques. Note that certain options may lead to additional choices that need to be made.
3. Represent the different alternative states of the world. Again standard answer set programming techniques apply.
4. Represent relationships between and consequences of different alternatives.
5. Represent desired properties. This is where ordered disjunction comes into play. Of course, desires may be context-dependent.
6. Use the preference relation on answer sets derived form the satisfaction degrees of rules to induce a preference relation on possible decisions. Of course, there are different ways to do this corresponding to different attitudes of the agent towards risk.
7. Pick one of the most preferred decisions.

We will use Savage’s famous rotten egg example  to illustrate this methodology. An agent is preparing an omelette. 5 fresh eggs are already in the omelette. There is one more egg. It is uncertain whether this egg is fresh or rotten. The agent can

* add it to the omelette which means the whole omelette may be wasted, or
* throw it away, which means one egg may be wasted, or
* put it in a cup, check whether it is ok or not and put it to the omelette in the former case, throw it away in the latter. In any case, a cup has to be washed if this option is chosen.

In this example, the decision literals correspond to the three possible actions, that is $`C`$ is the set of literals built from $`\{inomelette,incup,throwaway\}`$. Here are the rules which generate the possible decisions and states of the world:

| $`inomelette\mathrm{not}incup,\mathrm{not}throwaway`$ |
| --- |
| $`incup\mathrm{not}inomelette,\mathrm{not}throwaway`$ |
| $`throwaway\mathrm{not}incup,\mathrm{not}inomelette`$ |
| $`rotten\mathrm{not}fresh`$ |
| $`fresh\mathrm{not}rotten`$ |

For our example it is not necessary to specify that the different actions and states of the egg are mutually exclusive. It is guaranteed by the rules that only one of the exclusive options is contained in an answer set.

We next define the effects of the different choices:

| $`5omelettethrowaway`$ |
| --- |
| $`6omelettefresh,inomelette`$ |
| $`0omeletterotten,inomelette`$ |
| $`6omelettefresh,incup`$ |
| $`5omeletterotten,incup`$ |
| $`\neg wash\mathrm{not}incup`$ |
| $`washincup`$ |

For the different omelettes we must state that they are mutually inconsistent. We omit the 6 rules necessary for representing this. They are of the form $`\neg xomeletteyomelette`$ with $`xy`$. We finally represent our desires:

| $`\neg wash\times wash`$ |
| --- |
| $`6omelette\times 5omelette\times 0omelette`$ |

This logic program has the following 6 answer sets

| $`S_1=\{6omelette,\neg wash,fresh,inomelette\}`$ |
| --- |
| $`S_2=\{0omelette,\neg wash,rotten,inomelette\}`$ |
| $`S_3=\{6omelette,wash,fresh,incup\}`$ |
| $`S_4=\{5omelette,wash,rotten,incup\}`$ |
| $`S_5=\{5omelette,\neg wash,fresh,throwaway\}`$ |
| $`S_6=\{5omelette,\neg wash,rotten,throwaway\}`$ |

The preference relation among answer sets is as follows: $`S_1`$ is the single maximally preferred answer set. $`S_5`$ and $`S_6`$ are preferred to $`S_2`$ and $`S_4`$ but incomparable to $`S_3`$. $`S_3`$ is preferred to $`S_4`$ but incomparable to $`S_5`$, $`S_6`$ and $`S_2`$. $`S_2`$ and $`S_4`$ are incomparable. Fig. 1 illustrates these relationships:

Fig.1: Preferences among answer sets

Reasoning from maximally preferred answer sets in the example would yield $`inomelette`$ as the alternative chosen by the agent. It is obvious that this amounts to an extremely optimistic attitude towards decision making which in the example amounts to assuming the egg will be fresh.

A pessimistic decision maker might choose the action whose worst outcome is most tolerable. In the example the answer sets containing $`throwaway`$, that is $`S_5`$ and $`S_6`$, are preferred to the least preferred answer set containing $`inomelette`$, $`S_2`$, and to the least preferred answer set containing $`incup`$, $`S_4`$. Thus, a pessimistic decision maker would choose $`throwaway`$.

An extremely cautious strategy would prefer a decision $`C_1`$ over a decision $`C_2`$ if the least preferred answer set(s) containing $`C_1`$ are preferred to the most preferred answer set(s) containing $`C_2`$. This is a very strong requirement and in the egg example no action is preferred to another one according to this strategy.

Finally, we can distinguish a set of state literals $`\mathrm{\Sigma }`$ and compare answer sets statewise (states are subsets of $`\mathrm{\Sigma }`$, the states in the example are $`fresh`$ and $`rotten`$). A decision $`C_1`$ is preferred over a decision $`C_2`$ if for each state $`T\mathrm{\Sigma }`$ the least preferred answer set(s) containing $`C_1T`$ are preferred to the most preferred answer set(s) containing $`C_2T`$.

Intuitively, $`S_2`$ in our example seems far less desirable than $`S_4`$ and both $`S_5`$ and $`S_6`$ less desirable than $`S_3`$. This is not reflected in our preference relation on answer sets. To express this it is necessary to represent preferences between sets of literals rather than single literals. Within our framework this can be done by introducing new atoms representing conjunctions of literals. However, it would probably be more elegant to apply orderd disjunction directly to sets of literals (read as the conjunction of these literals). Extending LPODs in such a way is straightforward.

Another natural idea would be to use numerical penalties. We can use integers for this and write, say:

| $`\neg washcup\times washcup(1)`$ |
| --- |
| $`6omelette\times 5omelette(5)\times 0omelette(50)`$ |

The overall penalty for an answer set $`S`$ is obtained by adding up the penalties for all rules, where the penalty of $`c_1\times c_2(n_2)\times \mathrm{}\times c_k(n_k)body`$ is 0 if $`body`$ is not satisfied in $`S`$ or $`c_1S`$, $`n_j`$ otherwise, where $`j`$ is the smallest integer such that $`c_jS`$. The preference relation among answer sets is obtained through their overall penalty. In the example we would obtain the following overall penalties:

| $`S_1:0`$ | $`S_3:1`$ | $`S_5:5`$ |
| --- | --- | --- |
| $`S_6:5`$ | $`S_4:6`$ | $`S_2:50`$ |

Choices could then be ordered on the basis of the average penalties of answer sets they contain. This strategy would thus choose $`incup`$.

Of course, many alternative strategies can be thought of. A further investigation is beyond the scope of this paper and left for future work.

Every approach to qualitative decision making has to combine preferences among outcomes of choices with a treatment of uncertainty. In our approach the preferences are described through ordered disjunction. But what about the uncertainty? Different possible states of the world are represented as different answer sets. As usual in nonmonotonic reasoning states of the world which are unnormal in some respect are totally disregarded (this is what McCarthy called jumping to conclusions). All states which have to be taken into account are considered plausible. Further distinctions between the generated answer sets are not possible. For instance, it is not possible to express, say, that $`fresh`$ is more probable than $`rotten`$ in the omelette example. If, however the possibility of $`rotten`$ is negligeable and $`fresh`$ is true by default we can make sure that only answer sets containing $`fresh`$ are generated by using adequate rules. Our general qualitative attitude towards uncertainty can thus be described as: states are either negligeable or plausible; in the latter case no assumption about the degree of plausibility is made.

We are now in a position to analyze why the examples in Sect. 3 which were based on reasoning from most preferred answer sets worked out properly. The reason is that in these examples only one answer set for the different possible choices (which were left implicit) is generated. This means that optimistic, pessimistic and other kinds of LPOD based decision making coincide. In general, this is possible whenever there is enough knowledge to guarantee a single plausible state for each case at hand (as in the cinema example), or whenever all relevant literals are under the control of the agent (as in the cooking example).

## 6 Conclusion

In this paper we introduced a new connective to logic programming. This connective - called ordered disjunction - can be used to represent context dependent preferences in a simple and elegant way. Logic programming with ordered disjunction has interesting applications, in particular in design and configuration, and it can serve as a basis for qualitative decision models.

There are numerous papers introducing preferences to logic programming. For an overview of some of these approaches see the discussion in  or the more recent . Only few of these proposals allow for context dependent preferences. Such preferences are discussed for instance in . The representation of the preferences in these papers is based on the introduction of names for rules, the explicit representation of the preference relation among rules in the logical language, and a sophisticated reformulation of the central semantic notion (answer set, extension, etc.) with a highly self-referential flavour. Alternative approaches  are based on compilation techniques and make heavy use of meta-predicates in the logical language. Nothing like this is necessary in our approach. All we have to do is use the degree of satisfaction of a rule to define a preference relation on answer sets directly.

Our approach is closely related to work in qualitative decision theory, for an overview see . Poole  aims at a combination of logic and decision theory. His approach incorporates quantitative utilities whereas our preferences are qualitative. Interestingly, Poole uses a logic without disjunction whereas we enhance disjunction. In  a graphical representation, somewhat reminiscent of Bayes nets, for conditional preferences among feature values under the ceteris paribus principle is proposed, together with corresponding algorithms. $`\mathrm{𝐿𝑃𝑂𝐷}`$s are more general and offer means to reason defeasibly. Several models of qualitative decision making based on possibility theory are described in . They are based on certainty and desirability rankings. Some of them make strong commensurability assumptions with respect to these rankings. In a series of papers , originally motivated by , the authors propose viewing conditional desires as constraints on utility functions. Intuitively, $`D(a|b)`$ stands for: the $`b`$-worlds with highest utility satisfy $`a`$. Our interpretation of ranked options is very different. Rather than being based on decision theory our approach can be viewed as giving a particular interpretation to the ceteris paribus principle.

In future work we plan to investigate application methodologies for logic programming with ordered disjunction. An answer set programming methodology for configuration tasks has been developed in a number of papers by Niemelä and colleagues at Helsinki University of Technology . We plan to study possibilities of combining this methodology with $`\mathrm{𝐿𝑃𝑂𝐷}`$s. Of course, the discussion of qualitative decision models in this paper was very preliminary. We plan to work this out in more detail in a separate paper.

## Acknowledgements

I would like to thank Salem Benferhat, Richard Booth, Tomi Janhunen, Ilkka Niemelä, Tommi Syrjänen and Leon van der Torre for helpful comments.


format: text

text:
# Thermal Emission as a Test for Hidden Nuclei in Nearby Radio Galaxies

## 1 Introduction

Now that the existence of supermassive black holes in AGN seems fairly secure, perhaps the next most fundamental questions are the sources of energy and the nature of the accretion flow in the various classes of objects. Historically (see Begelman, Blandford and Rees 1984 for an early review) it was thought that the optical/UV continuum (or “Big Blue Bump”) in quasars (hereafter: and broad line radio galaxies) represents thermal radiation from some sort of cool optically thick accretion flow. Radio galaxies didn’t show this component, so were posited to be “nonthermal AGN” with hot radiatively inefficient accretion, at a very low rate; in these cases the the jet power would derive from the hole rotation rather than release of gravitational potential energy from accretion.

These arguments took a surprising turn when it was realized that many radio galaxies do have the quasar-like nuclei111We will use the terms ”thermal AGN” and ”hidden AGN” to refer to the optical/UV continuum and broad emission lines which characterize the spectra of quiescent quasars, broad line radio galaxies, and Seyfert galaxies in this spectral region. that are invisible from our line of sight. One Fanaroff-Riley II (edge-brightened, very luminous) radio galaxy, 3C234, was shown in 1982 to have quasar features (broad permitted emission lines and Big Blue Bump) in polarized light (Antonucci 1982, 1984; Antonucci 1993 for a review). Thus 3C234 does have the “thermal” optical/UV emission, which is only visible via scattering. Many other examples have been shown subsequently (e.g. Hines and Wills 1993; Young et al. 1996). Some invocations of the Unified Model postulated that this was generally true of the FR II (powerful, edge-brightened) class (e.g. Barthel 1989).

3C234 has powerful high-ionization narrow lines, consistent with its being a hidden quasar. However it is still contentious how those FR IIs with weak and/or low ionization narrow emission lines fit in (Singal 1993; Laing 1994; Gopal-Krishna et al. 1996; Antonucci 2001). The situation is even less clear for the FR I galaxies, almost all of which have undetectable or low-ionization emission lines.

For radio galaxies with no observable high-ionization narrow emission line region present, there is no a priori evidence for the presence of a quasar. These could still have a quasar nucleus, but any narrow line region would need to be mostly obscured as well. In fact there is some evidence that the high ionization narrow emission lines are partially obscured in many 3C radio galaxies (Hes et al. 1993). In NGC 4945 and many other ordinary looking galaxies, the only present evidence for a hidden AGN is in the hard X-ray (e.g. Madejski et al. 2002).

To summarize, many FR II radio galaxies fall into the apparently weak, low-ionization emission line category. Most of the FR I radio galaxies do as well. These spectra have been described as ”optically dull.” Quite recently, Chiaberge et al. (1999, 2000) have shown that among these optically dull sources of both FR types, a majority show optical point sources in HST images, and of course more might do so with better imaging data. Note that their result seems surprising at first: one might have guessed that those with stronger high-ionization spectra would have the point sources, but the opposite is true.

Chiaberge et al. argue that those with detectable optical point sources cannot in general have thick obscuring tori on. The reason is, if the point sources are truly nuclear, then we can see to the very center in most of these objects. These radio galaxies are effectively selected by an isotropic emission property - the radio lobe flux - so the source orientations should have an isotropic distribution. That is, the radio axes should be randomly oriented with respect to our line of sight. Since we can see optical point sources in most optically dull objects, most lines of sight to their nuclei must be unobscured in general. Recall that in the Chiaberge et al. picture, the HST optical point sources are the bases of the synchrotron jets which emit in the radio. As they point out, one caveat must be given with their line of argument. It is possible that obscuring tori exist below the HST resolution, and hide the nucleus and the very innermost region of the conical jet. For example, their optical point sources may really be jet emission on $`1`$ pc scales, and optical Big Blue Bump sources are much smaller. A torus might be large enough to obscure the latter while still allowing the pc scale jet emission to be seen over the top.

In the Chiaberge et al. scenario the optical point sources represent synchrotron emission from the bases of the jets. In support of this idea, those authors show that the optical fluxes correlate roughly with the core radio fluxes at 6 cm. It should be easy to check this: the relationship should tighten up substantially using millimeter fluxes instead of those at 6 cm.

It is very important to remember that some narrow line radio galaxies of both FR types do have strong high ionization emission lines, and in some cases definitive spectropolarimetric evidence for a hidden ”thermal” nucleus. In general such objects have no detectable optical point source. They behave instead like Seyfert 2 nuclei, with just spatially resolved scattered light and the extended narrow line region directly visible.

Our goal is to determine robustly which if any radio galaxies lack a hidden ”thermal” (optical/UV continuum) nucleus. This is crucial for AGN theory since it would prove the existence of an accretion mode different from that in quasars. In particular, current wisdom would posit a very low accretion rate and a very low radiative efficiency, that is, some variant of the advection dominated accretion flow for those radio galaxies. Then by default the enormous kinetic luminosity of the radio jets would be attributed to black hole rotational energy.

How can we tell whether or not a hidden nucleus is present? One method is via the hard X-rays. Many hidden AGN that are not Compton-thick have been discovered with X-ray observations. Some references to penetrating X-rays in optically dull sources are gathered in Antonucci 2001; NGC4945 is a spectacular example (e.g. Madejski et al. 2000).

Our approach here is to look instead for reradiation of the absorbed light from any hidden quasar-like nucleus by the dusty obscuring matter (torus). Modulo factors of order unity, the various models of the obscuring tori predict that the ”waste heat” from the obscuring matter will emerge in the mid-IR, and that this emission is roughly isotropic in all but the highest inclination cases. (Note that this assumption is the weakest point of our project, but that the various torus models predict it is true to within a factor of a few: Pier and Krolik 1992, 1993; Granato et al. 1997; Efstathiou and Rowan-Robinson 1995; a related model in Konigl and Kartje 1994 should also be consulted; Cen A is discussed specifically in Alexander et al 1999). We are making this test for hidden quasars using the Keck I telescope’s mid-IR instrument (the ”LWS”). This is the only way to isolate the nucleus well, and to achieve the required sensitivity. Here we show the power of the technique, and demonstrate the existence of at least one ”nonthermal” AGN222Preliminary reports of this work were published in Anotnucci 2001 and Whysong and Antonucci 2001 (astro-ph 0106381); shortly thereafter, Gemini mid-IR images were published and analyzed by Perlman et al. 2001. Their measurements and conclusions were similar to ours. Since their images were very deep, they were also able to detect extended jet emission..

## 2 Observations

### 2.1 3C 405 (Cygnus A)

in Figure 1 we present a diffraction limited mid-IR image of the nuclear source in 3C 405 (Cyg A), obtained with the Long Wavelength Spectrometer (LWS) instrument at the Keck I telescope333Instrument reference is available at: http://www2.keck.hawaii.edu:3636/realpublic/inst/lws/lws.html.. All data were taken with the 11.7$`\mu `$m filter, which has an $`1\mu `$m bandpass from 11.2 to 12.2 $`\mu `$m. The image was shown previously in Whysong and Antonucci (2001).

The nucleus of 3C 405 was imaged at 11.7$`\mu `$m with Keck I/LWS on 1999 September 30. The chop/nod throw was set to 10" in order to allow imaging of larger scale extended structure; this places the chop beam off the chip, which has a 10" field. We do not report on structures larger than the 10" chop distance. The images were dithered in a 5 position box pattern, 2" to a side, with 53.1 seconds on-source for the positive image per dither position. The entire 5-position exposure was repeated three times, for a total on-source time of 796.6 seconds.

Data were processed by subtracting all background chop/nod frames, shifting each dithered image to the correct position, and coadding all dither images. Morphology is extended, with structure to the east and southeast of the nucleus (Fig. 1). The standard star was alpha Ari444A table of photometric standards is available at: http://www2.keck.hawaii.edu:3636/realpublic/inst/lws/IRTF$`\mathrm{\_}`$Standards.html., with a FWHM of 0.27".

Our 11.7$`\mu `$m image and a partial spectral energy distribution are shown in Figs. 1 and 5. For comparison, the IRAS (large aperture) data for Cygnus A are listed in Table 3.

### 2.2 Cen A

The high resolution mid-IR data on Cen A also come from the Keck I telescope. Data were obtained on our behalf by Randy Campbell on 28 June 2002. Three filters were used: the 11.7 $`\mu `$m filter with 1 $`\mu `$m bandpass, a wider ”SiC” filter centered at 11.7 $`\mu `$m but with a 2.4 $`\mu `$m bandwidth, and the 17.75 $`\mu `$m filter with a $`1\mu `$m bandwidth. The standard star was Sigma Sco, a multiple star which was partially resolved so that it was necessary to increase the synthetic aperture to 2.24 arcsec in order to include all components. No photometric data are available for Sigma Sco at wavelengths longer than M, so we extrapolated to longer wavelengths using the Rayleigh-Jeans approximation.

The Cen A images show only an unresolved source in all filters. Photometric calibration results are F($`11.7\mu `$m)$`=1.6`$ Jy, F(SiC)$`=1.8`$ Jy with $`0.3`$ arcsec FWHM resolution, and F(17.75 $`\mu `$m)$`=2.3`$ Jy with $`0.5`$ arcsec FWHM resolution.

Since Cen A is so close, there are published data for relatively small physical apertures. A small physical aperture is key, because for both Cen A and M87, the large-aperture (e.g. IRAS, ISO) fluxes are much larger than that from the nucleus. But the much higher resolution Keck data isolate a nuclear point source with size $`5`$ pc at $`11.7\mu `$m and $`7.8`$ pc at $`17.75\mu `$m given a distance of 3.1 Mpc.

We will assume that this is mostly dust emission heated by the nucleus. This is consistent with the 10-20 micron nuclear spectrum taken by ISOCAM CVF in a $`4\mathrm{"}`$ aperture (Mirabel et al. 1999, reproduced here as Fig. 3). In fact, our 11.7 $`\mu `$m flux is in good agreement with that of the spectrum, suggesting that Fig. 3 is in fact the nuclear spectrum.

For comparison, the published, larger aperture mid-IR fluxes are much higher. The Cen A central region flux has been measured in the mid-IR by Grasdelen and Joyce (1976). Their 3.5” aperture has the same flux as the 5.2” aperture, so there is a compact source surrounded by a region of low or zero flux. The 3.5” aperture corresponds to 50 pc, and the enclosed flux is given as $`2.6`$ Jy at 11 microns, and 4.3 Jy at 12.6 microns. The IRAS 12.6$`\mu `$m flux measurement is even higher at 13.3 Jy.

### 2.3 M87

Here a new high-resolution Keck I image is also crucial. We obtained this data for M87 on 2000 January 18. The observation was made in chop-nod mode using a small 3.5" amplitude so as to keep both the object and chop beams on the CCD chip. The 11.7 $`\mu `$m filter was used, with a 1$`\mu `$m bandpass.

Integration time was 96 seconds per dither each for positive and negative (background). Unfortunately, due to a loss of guiding, the positive nucleus image was only fully imaged in one dither frame. However, we are still left with two independent images, both strong pointlike detections. Our measurement was taken from the better placed of the two.

Beta And and Mu UMa were used as standards for photometric calibration, yielding a flux scale of 0.0874 and 0.0931 mJy/(ADU/s) and FWHM of 0.33" and 0.31" respectively. This calibration for the unresolved nuclear component in M87 results in a flux of 13 +/- 2 mJy. The uncertainty is dominated by systematic errors in the background subtraction; we adopt a value of 13 mJy. A synthetic aperture of 0.96 arcsec was used, but the source is unresolved so the flux is insensitive to the aperture.

Again we note that the large aperture fluxes are much higher. In particular the IRAS fluxes (Moshir et al. 1990) are 231$`+/`$37 mJy at 12$`\mu `$m, $`<`$241 mJy at 25$`\mu `$m, and 393$`+/`$51 mJy at 60$`\mu `$m.

## 3 Discussion

### 3.1 Cen A

Fig 1 shows the SED for Cen A, combining all the $`1`$” measurements. For AGN which show the quasar-like optical nucleus in scattered light only, the mid-IR emission is typically two orders of magnitude greater than the (scattered) optical light. For Cen A the situation is similar, but with a slight modification (Bailey et al. 1996; Hough et al. 1987; Antonucci and Barvainis 1990; Alexander et al. 1999). The ratio is inflated by absorption of the pc scale scattered optical light by the kpc dust lane famous from photographs.

At 2u, a highly polarized point source indicates detection of a $``$ pc scale reflection region. The near-IR reflected light from pc scales penetrates the kpc scale dust lane which has only moderate optical depth. This situation was deduced for 3C323.1 and Cen A by Antonucci and Barvainis (1990). The pc scale dust screen can be consistently identified with the cold absorber seen in the X-ray spectrum, which has column density $`3\times 10^{23}`$ cm-2. Additional optical and near-IR scattered light on kpc scales has been mapped and disucssed by Capetti et al 2000 and Marconi et al 2000.

The case of Cen A shows that even radio galaxies with weak or low-ionization lines (the “optically dull” ones) can have hidden Type 1 nuclei. Others can be found in e.g. Ekers and Simkin 1983 and Sambruna et al. 2000.

To show the level of the reflected light in the nuclear region, we have plotted the value at 2 microns rather than that in the optical (which is highly absorbed). The K-band nuclear flux with starlight subtracted (Marconi et al. 2000) is F(K) $``$ 3 mJy, and $`\nu L_\nu 6\times 10^{39}`$ ergs/sec for a distance of 3 Mpc. The SED in Figure 2 shows that the mid-IR luminosity of the nucleus is much larger than the optical/near-IR value, as expeted. This is consistent with all other reflected-light objects.

The value of the mid-IR flux quoted above is $``$3.5 Jy at 11.7 microns, interpolated from measurements at two nearby wavelengths. The corresponding $`\nu L_\nu `$ is $`1.2\times 10^{42}`$ erg/sec. Assuming a normal quasar SED (e.g. Sanders et al 1989; Barvainis et al. 1990), that translates to a bolometric luminosity of $`2\times 10^{43}`$ ergs/sec for the hidden AGN.

The nature of the mid-IR emission is important. The SED has been fit to a synchrotron self-Compton model (Chiaberge et al. 2001) which would lead to a classification for Cen A as a “misaligned BL Lac”. However, the fit was to the mid-IR continuum slope instead of the different ISO bands because the latter were heavily affected by absorption and emission features (M. Chiaberge 2001, private communication). Small aperture mid-IR spectra show PAH and Si features (Figure 3), and the SED in $`4\mathrm{"}`$ apertures is consistent with predominantly dust rather than synchrotron (Alexander et al. 1999; note also that the ISOCAM CVF flux from the Mirabel et al. 1999 spectrum is consistent with our 11.7 $`\mu `$m measurement, suggesting that the spectrum is representative of our smaller aperture). These features indicate that most of the mid-IR flux is thermal emission as expected for the torus model.

### 3.2 M87

This radio galaxy is on the FR I-II borderline, both in morphology and in radio power (Owen et al. 2000). It is one of the majority of FR I radio galaxies with an optical/UV point source (Chiaberge et al. 1999, 2000). The optical point source is tentatively ascribed to synchrotron radiation associated with the radio core (see Ford & Tsvetanov 1999, as well as the Chiaberge et al. papers). However it’s not known whether this light is highly polarized, or whether broad emission lines are strong in either total or polarized optical/UV flux.

Our small $`0.3`$ arcsec FWHM beam isolates the innermost $`25`$pc in M87. The enclosed 11.7$`\mu `$m flux in an 0.6” synthetic aperture is 15 mJy; this aperture matches that used for Cen A in physical size. The flux measured in this way is much lower than the large aperture measurements in the literature. Published large-aperture data leave plenty of room for waste heat from a hidden AGN, but our data do not (Fig. 1). The mid-IR luminosity $`\nu L_\nu `$ is only of order that in the optical rather than much greater as for the hidden AGN sources. In fact, much or all of the mid-IR flux could simply be synchrotron radiation associated with the innermost part of the jet, so the measured flux is an upper limit to the dust luminosity. Note that this outcome for M87 is just what Chiaberge et al. implicitly predicted.

Unless the nuclear dust is too obscured to emit in the mid-IR, this rules out a powerful hidden nucleus. The observed 11.7$`\mu `$m flux corresponds to $`\nu L_\nu =1.0\times 10^{41}`$ erg/sec, for a distance of 15 Mpc. Suppose the mid-IR core is in fact all dust emission. For the SED for the PG quasar composite of Sanders et al. 1989, a bolometric luminosity of $`1.6\times 10^{42}`$ ergs/sec is expected. For comparison, a lower limit to the jet kinetic luminosity in M87 is $`5\times 10^{44}`$ erg/sec (Owen et al. 2000), so the jet is by far the dominant channel for energy release.666We can also make the empirical test of the ratio of the mid-IR flux to that of the radio lobes. We measured 15mJy at $`11.7\mu `$m, and NED shows $`220`$Jy at 1.4GHz. The ratio is $`6.8\times 10^5`$, much lower than the ratio for the objects with hidden AGN, such as Cen A. If correct, this suggests that M87 is the true “misaligned BL Lac.”

Published ADAF models (Reynolds et al. 1996) predict very low IR-optical-UV luminosities compared with those in the radio and X-ray. Our 11.7$`\mu `$m point is about equal to the optical value, but certainly our 11.7$`\mu `$m point may be partially or completely jet emission777It is unclear to us why the radio points, which fit the ADAF model, are taken as measurements while the (non-fitting) optical fluxes were not. Also, the Reynolds et al. figure apparently uses 3C273 as a “thermal” quasar-like template, but that object definitely has a large jet contribution in the radio and infrared (Robson et al. 1993)..

### 3.3 Cygnus A

This is a very powerful FR II radio galaxy at a redshift of 0.056. It has strong high-ionization narrow lines, suggestive of a hidden AGN. A broad Mg II 2800 emission line is detectable in total flux (Antonucci et al. 1994). That line may or may not be highly polarized, and thus scattered from a hidden nucleus. Several detailed papers report spectroscopic and spectropolarimatric data (Goodrich and Miller 1989; Tadhunter et al. 1994; Shaw and Tadhunter 1994; Vestergaard and Barthel 1993; Stockton et al. 1994; see also Tadhunter et al. 2000 and Thornton et al. 1999 - and there are several others), culminating in Ogle et al. 1997, which shows an extremely broad H-alpha line in polarized flux. It is virtually invisible in total flux because its great width makes it hard to distinguish from continuum emission.

A nuclear point source in the near-IR was noted by Djorgovski et al. (1991), but they don’t seem to have considered hot dust emission for this excess over the extrapolation from the optical light, as we believe.

A powerful hidden nucleus should manifest a mid-IR dust luminosity much larger than the observed optical luminosity. However for this object and M87 (and virtually all others!) the only IR data available were taken with very large beam sizes. We (and Radomski et al. 2002)888Our Keck I image appeared publicly before that of Radomski et al. 2002, but we did relatively little analysis. isolate the core much better with the $`0.3\mathrm{arcsec}`$ ($`1.1`$ kpc) resolution provided by the Keck I telescope, and find a nuclear flux of $`60`$mJy. An uncertainty here derives from the extended emission, but flux as a function of aperture size does flatten out for apertures larger than the seeing disk, so the 0.96" measurement should be approximately correct (see Table 2). However, we can’t be sure from this observation alone that the emission is on pc scales. Since the emission is powerful and at the relatively short wavelength of 11.7$`\mu `$m, it is very likely that this comes from nuclear dust rather than a starburst.

It is entirely possible that the extended emission is thermal dust even at radii up to 1 kpc. The temperature of nuclear-heated dust can be estimated according to Barvainis 1988. Adopting a Hubble constant of 75 km/s Mpc, the $`\nu L_\nu `$ luminosity at 11.7$`\mu `$m is $`9.2\times 10^{43}`$ erg/sec. If the intrinsic SED is similar to those of PG quasars (Sanders et al. 1989), the 11.7$`\mu `$m value implies a bolometric luminosity of 16.5 $`\nu L_\nu `$ (11.7$`\mu `$m) $`1.5\times 10^{45}`$ erg/sec. An optical luminosity of $`10^{45}`$ erg/s produces a dust temperature of $`120`$K at a 500pc radius. A similar calculation of the dust temperature was done by (Radomski et al. 2002), yielding a slightly higher results (150 K) due to a higher estimate of the optical luminosity. Among the uncertainties are the nuclear UV luminosity and the possiblility of single photon heating.

The IRAS (large aperture, see Table 3) dust spectrum is quite cool, suggesting a large starburst contribution. Extended emission is seen in our image at 11.7$`\mu `$m. The core can’t be exactly separated from the extensions (see Table 2), but we can estimate around 60 mJy for the nuclear dust. Fig. 1 shows the Cyg A 11.7$`\mu `$m image, and Fig. 5 shows a partial spectral energy distribution. The nuclear luminosity $`\nu L_\nu `$ at 11.7$`\mu `$m is 10 times higher than that at 0.5$`\mu m`$. The latter wavelength needs two roughly canceling corrections: subtraction of optical light from the host galaxy, and dereddening (Ogle et al. 1997). The starbust contribution to the nuclear 11.7$`\mu `$m emission is expected to be small, but this should be checked with a spectral slope measurement.

The conclusion is simple and expected from prior evidence: Cyg A has a moderately powerful hidden nucleus.

As noted above, the estimated bolometric luminosity is $`1.5\times 10^{45}`$ erg/s. For comparison the jet power is estimated several different ways (Carilli and Barthel 1996; Sikora 2001; Punsly 2001). The values are rough, but generally lie in the $`>10^{45}`$ ergs/sec range. This is consistent with the finding that jet power and optical/UV luminosity are often comparable in double radio quasars (e.g., Falcke 1995).

Thus this is a moderate luminosity broad line radio galaxy with a very high luminosity radio source. It has in fact been inferred already that Cygnus A is an over-achiever in the radio (Carilli and Barthel 1996; Barthel and Arnaud 1996). This is well explained qualitatively by the fact that it is the only known FR II radio source in a rich X-ray-emitting cluster.

### 3.4 Blazars

A goal of this paper is to detect thermal IR bumps, often in the presence of a synchrotron continuum. In general the SED sampling is limited for our targets. Even in cases with convincing dust emission, the dust component is not very well isolated in the infrared SED. Thus we thought it would be helpful to show a well observed object which clearly isolates a nonthermal infrared bump from a broadband nonthermal component.

Blazar radio sources are typically dominated over most of their SED by variable synchrotron emission (and/or inverse Compton bump in the X-ray - $`\gamma `$-ray region). This means that in powerful cases, relatively few continuum components of emission are important for the SED. For example, starlight and dust warmed to tens of K by stars are relatively weak. Thus the infrared consists almost entirely of the broadband nonthermal and the (relatively) narrow band thermal components. The SED, shown in Fig. 4, is that of 3C 273 (data from Robson et al. 1993). It can be referred to while assessing the other SEDs in this paper.

## 4 Relation to other Radio Galaxies and Conclusion

Radio lobe emission is fairly isotropic, so it’s easy to make lists of double radio sources that are nearly unbiased with respect to orientation. The visibility of optical point sources in most of the optically dull (weak or low ionization emission line) galaxies show that there are no $`>`$ parsec scale tori present which are able to obscure the unresolved optical sources in those cases (Chiaberge et al. 1999, 2000). Whatever the nature of the M87 optical point source, we know it’s small from the variability on year timescales. The same would apply to the other optically dull nuclei if they vary as M87 does. This would strengthen the Chiaberge et al. argument that we have unobscured sightlines nearly all the way to the central engines.

Since the M87 optical/UV flux is quite variable (e.g., Tsvetanov et al. 1998) jet synchrotron emission is a possibility. By correlating the radio synchrotron core fluxes and the optical point source fluxes in FR I radio galaxies generally, Chiaberge et al. (1999) infer that the latter are in fact likely to be beamed synchrotron sources. Crucial tests of the nature of the optical point sources can be made with spectroscopy and polarimetry. We hope to do this with adaptive optics, excluding most of the starlight that dominates in arcsec apertures.

However, a large minority of low ionization FR I and FR II radio galaxies show no point source, and are similar in this way to AGN with hidden nuclei. In fact the closest FR I, Cen A, does have a big molecular torus (see Fig. 2 of Rydbeck et al. 1993!), and substantial evidence for a hidden nucleus as well (see references cited earlier). As a working hypothesis we might suppose that the same is true for all those without detectable optical pointlike nuclei. (Of course sensitivity of the optical/UV observations also enters in.)

Thus the FR I family is heterogeneous: some contain hidden optical/UV nuclei and some do not. It’s been difficult to find FR I objects with strong evidence for hidden AGN, but in fact at least a few are known to be quasar-like from direct spectroscopy (3C120 is well known; see also Lara et al. 1999 and Sarazin et al. 1999). The infrared peaks in some blazars such as 3C 66A are clearly distinct from the radio synchrotron, providing further evidence for FR I objects with hidden thermal emission. Therefore the “nonthermal” model does not apply to all optically dull or low ionization radio galaxies, or to all FR I galaxies. The FR class has no apparent direct relation to the mode of energy production, consistent with much recent evidence that FR Is behave very much like FR IIs at VLBI scales. We will understand this better after the completion of our mid-IR program.

Finally we reiterate an assumption in our program: we assume that any mid-IR dust emission is isotropic to within a factor of a few.

## 5 Acknowledgements

We wish to thank M. Chiaberge, P. Ogle, B. Wills, and R. Barvainis for good advice. A thousand huzzas to Randy Campbell at Keck for obtaining the Cen A data.

| Table 1: Flux Ratios | | | |
| --- | --- | --- | --- |
| Mid-IR results are from our Keck I survey. | | | |
| Name | 11.7$`\mu `$m (mJy) | 1.4 GHz (mJy) | Ratio |
| 3C 47 | 10 | 3800 | 2.6E-3 |
| 3C 216 | 9.7 | 4000 | 2.4E-3 |
| 3C 219 | 7.0 | 8000 | 8.8E-4 |
| 3C 234 | 186 | 5400 | 3.4E-2 |
| 3C 382 | 27.5 | 5100 | 5.4E-3 |
| 3C 452 | 22 | 10600 | 2.1E-3 |

| Table 2: LWS photometry results for Cygnus A: | |
| --- | --- |
| aperture diameter | flux (mJy) |
| (arcsec) |  |
| 0.64 | 44 |
| 0.96 | 71 |
| 1.28 | 93 |
| 1.60 | 111 |
| 1.92 | 122 |
| 2.56 | 139 |
| 3.20 | 152 |

| Table 3: IRAS photometry for Cygnus A (Impey and Neugebauer 1988): | |
| --- | --- |
| 12 $`\mu `$m | S = 144 +/- 5 mJy |
| 25 $`\mu `$m | S = 870 +/- 5 mJy |
| 60 $`\mu `$m | S = 2908 +/- 13 mJy |


text:
# Effective temperature and compactivity of a lattice-gas under gravity

\[

## Abstract

The notion of longitudinal effective temperature and its relation with the Edwards compactivity are investigated in an abstract lattice gas model of granular material compacting under gravity and weak thermal vibration.

\]

A distinctive feature of mean-field glassy dynamics is a peculiar violation of fluctuation-dissipation relations which leads to the definition of a time-scale dependent “effective temperature” , and the possibility of constructing a non-equilibrium thermodynamics of glasses and dense granular media . Effective temperature also appears in athermal systems, where the high packing density regime is attained by compression or by using a confining potential. A particularly interesting situation, which is relevant to the study of granular materials, occurs when the confining force is gravity. In this case a non stationary inhomogeneous density profile generally arises and the notion of effective temperature may be then not well defined unless suitable conditions are verified. In this note we explore the possibility of defining a global effective temperature in an abstract model of granular material under gravity and weak thermal vibration, and its relation with the Edwards compactivity.

The model consists of a gas of $`N`$ particles on a body centred cubic (bcc) lattice where there can be at most one particle per site. There is no cohesion energy among particles and the Hamiltonian is

$`_0`$ $`=`$ $`mg{\displaystyle \underset{i=1}{\overset{N}{}}}h_i,`$ (1)
where $`g`$ is the gravity constant, $`h_i`$ is the height of the particle $`i`$, and $`m`$ its mass. At each time step a particle can move with probability $`p`$ to a neighboring empty site if the particle has less than $`\nu `$ nearest neighbors before and after it has moved . Here $`p=\mathrm{min}[1,x^{\mathrm{\Delta }h}]`$ where $`\mathrm{\Delta }h=\pm 1`$ is the vertical displacement in the attempted elementary move , and $`x=\mathrm{exp}(mg/k_\mathrm{B}T)`$. We set $`mg/k_\mathrm{B}=1`$ and $`\nu =4`$ throughout. At high enough packing density, dynamical models of this kind possess an extensive entropy of blocked states (defined as configurations in which any particle is unable to move) whose derivative is the so-called Edwards compactivity. For this reason such models exhibit a slow compaction dynamics reminiscent of dense granular matter . It was found in particular that during compaction a generalized fluctuation-dissipation relationship is obeyed , giving a first evidence of an effective temperature in this regime. In Ref.  the drift contribution to the longitudinal mean-square displacement was ignored , leading to claim that “all measures of vertical correlation and response lead to the impossibility of defining effective temperature” and that “the vertical drift due to compaction leads to contradictory results” . Here we show that there are no such contradictory results: in the slow compaction regime the drift brings no qualitative change in the generalized fluctuation-dissipation relation found in Ref. , and its effect is substantially negligible at high packing density.

The fluctuation-dissipation properties can be characterized by applying a random perturbation to the system at times $`tt_\mathrm{w}`$:

$`_ϵ`$ $`=`$ $`_0+ϵ\mathrm{\Theta }(tt_\mathrm{w}){\displaystyle \underset{i=1}{\overset{N}{}}}f_ih_i,`$ (2)
where $`f_i=\pm 1`$ independently for each particle, $`ϵ`$ is small enough to probe the linear response regime, and $`\mathrm{\Theta }`$ is the step function. The integrated response function is then defined as:

$`\chi (t,t_\mathrm{w})`$ $`=`$ $`{\displaystyle \frac{1}{N}}{\displaystyle \underset{i=1}{\overset{N}{}}}\overline{f_i\mathrm{\Delta }h_i(t)},`$ (3)
where $`\mathrm{\Delta }h_i(t)`$ is the height difference between the perturbed and unperturbed $`i`$ particle at time $`t`$. The angular brackets denote the average over the thermal noise while the overline denotes the average over the random force. The ‘mean-square displacement’ between two configurations at time $`t_\mathrm{w}`$ and $`t>t_\mathrm{w}`$ is:

$`B(t,t_\mathrm{w})={\displaystyle \frac{1}{N}}{\displaystyle \underset{i=1}{\overset{N}{}}}\left[h_i(t)h_i(t_\mathrm{w})+\stackrel{~}{h}(t_\mathrm{w})\stackrel{~}{h}(t)\right]^2,`$ (4)
where the drift motion is taken into account by the average height:

$`\stackrel{~}{h}(t)={\displaystyle \frac{1}{N}}{\displaystyle \underset{i=1}{\overset{N}{}}}h_i(t).`$ (5)
Fig. 1 reports a parametric plot of mean-square displacement vs. response function at waiting time $`t_\mathrm{w}=2^{13}`$: it clearly shows that the presence of a slow longitudinal drift does not prevent the existence of generalized fluctuation-dissipation relation. In particular, no qualitative change occurs in the characteristic broken-line pattern when the drift term $`\stackrel{~}{h}(t_\mathrm{w})\stackrel{~}{h}(t)`$ in Eq. (4) is neglected, while appreciable quantitative deviations between the two sets of data (with and without the drift term) only appear when the measurement time is quite long. Similar results were also found in the so-called FILG model under gravity .

The second result of the numerical compaction experiment is reported in Fig. 2: it shows that the generalized fluctuation-dissipation relation is obeyed at different waiting times. From the parametric plot of $`\chi (t,t_\mathrm{w})`$ vs. $`B(t,t_\mathrm{w})`$ one can define a time scale dependent effective temperature by means of the relation:

$`T_{\mathrm{dyn}}(t,t_\mathrm{w})`$ $`=`$ $`{\displaystyle \frac{ϵ}{2}}{\displaystyle \frac{B(t,t_\mathrm{w})}{\chi (t,t_\mathrm{w})}},`$ (6)
provided $`T_{\mathrm{dyn}}`$ is constant on that time scale, and where now it is understood a possible dependence of $`T_{\mathrm{dyn}}`$ on the density profile. Indeed, during compaction the system develops inhomogeneous density profiles , as it also happens after a sudden compression in zero gravity , and one may wonder about their influence on the effective temperature. In Ref.  the stationary density profile was interpreted as formed by two parts: a lower flat part at critical density $`\rho _\mathrm{c}0.84`$, and an upper equilibrium part in which kinetic constraints play no role. Fig. 3 shows the temporal evolution of the density profile corresponding to the above compaction experiment: one observes that the upper part of the bulk density profile increases faster than the lower one (even when the former become denser than the latter), and that the bulk profile is far from being flat (see inset of Fig. 3). At late time the contribution of the top free interface is small for weak vibration, and - if sizeable - it would make higher the slope $`T/T_{\mathrm{dyn}}`$, of the fluctuation-dissipation plot (i.e. smaller the effective temperature). While the contribution of particles at the bottom is negligible as they do not evolve at all.

That the generalized fluctuation-dissipation relation is not affected qualitatively by an inhomogeneous density profile can be understood in terms of the mean-field dynamical model introduced in , and further generalized to nonzero gravity in . In both cases the long-time relaxation of the local density factorizes: $`\rho _\mathrm{c}\rho (z,t)=f(z)g(t)`$. Since the mean square displacement can be written as $`B(z,t,t_\mathrm{w})=F(z)G(t,t_\mathrm{w})`$ on long enough time interval $`tt_\mathrm{w}`$, the violation factor entails two independent contributions: a purely geometric factor and a purely dynamic one. The latter contribution is only responsible for the intrinsic violation of the fluctuation-dissipation relation. The notion of effective temperature therefore seems to be still reliable provided a geometric factor is taken into account (in this specific case the global geometric factor entering Eq. (6) would be $`=f(z)dz/F(z)dz`$). Notice that for a purely flat density profile there is no difference between ‘horizontal’ and ‘vertical’ observables, (and $`=1`$).

The question that naturally arises is whether the longitudinal effective temperature can be interpreted in terms of the Edwards measure, which should now be obtained by fixing the density profile of the experimental situation one wishes to reproduce . The numerical implementation of this strategy is however not straightforward. A more pragmatic approach consists in fixing a few feature of the profile (as suggested in this case by the expression of $``$), such as average density, average slope and so on. This is quite similar in spirit to the construction of restricted Edwards measure which has been recently exploited in Ref. , and generally improves the comparison with numerical experiments.

As a preliminary attempt to relate the effective temperature $`T_{\mathrm{dyn}}`$, to the inverse compactivity $`T_{\mathrm{Edw}}`$, we have computed the Edwards entropy $`s_{\mathrm{Edw}}(\rho )`$ to the lowest approximation, i.e. just by fixing a homogeneous density. In passing, the definition of blocked configuration in presence of gravity requires here some care: if one assumes a flat profile, it is not clear why blocked configurations should depend upon gravity, like in the definition adopted in Ref. . We have therefore explicitly checked that there is no dependence upon gravity for the bcc lattice. This is not however the most general case: interestingly, we found that for the simple cubic lattice, the anisotropy due to gravity, (say along the direction 001), suppresses the first order character of the phase transition present in the Edwards measure at density below $`0.7`$. We have then estimated $`T_{\mathrm{Edw}}(\rho )`$ from the relation:

$`T_{\mathrm{Edw}}{\displaystyle \frac{\mathrm{d}s_{\mathrm{Edw}}}{\mathrm{d}\rho }}`$ $`=`$ $`T{\displaystyle \frac{\mathrm{d}s}{\mathrm{d}\rho }},`$ (7)
where $`s(\rho )=\rho \mathrm{log}\rho (1\rho )\mathrm{log}(1\rho )`$ is the equilibrium entropy . The two effective temperatures, $`T_{\mathrm{Edw}}`$ and $`T_{\mathrm{dyn}}`$, are shown in Fig. 4 at several densities corresponding to the average bulk density profiles of the compaction experiment. It is clear that a ponderable comparison is possible only when other features of the density profile (e.g. the average slope) are fixed, but much work is needed to test this point.

In conclusion, we confirm the existence of a generalized fluctuation-dissipation relation in an abstract model of dense granular matter which exhibits non-stationary inhomogeneous density profiles. The occurrence of a longitudinal effective temperature in the slow compaction regime has been justified by a mean-field dynamical model and its relation with the Edwards compactivity has been discussed.

J.J. Arenzon, A. Barrat and S. Franz are acknowledged for discussions and comments.