Anne-Lise Ducluzeau

Robert Van Lis

Simon Duval

Barbara Schoepp-Cothenet

Michael J Russell

Wolfgang Nitschke
email: nitschke@ibsm.cnrs-mrs.fr

Was nitric oxide the first deep electron sink?

Evolutionary histories of enzymes involved in chemiosmotic energy conversion indicate that a strongly oxidizing substrate was available to the last universal common ancestor before the divergence of Bacteria and Archaea. According to palaeogeochemical evidence, O 2 was not present beyond trace amounts on the early Earth. Based on recent phylogenetic, enzymatic and geochemical results, we propose that, in the earliest Archaean, nitric oxide (NO) and its derivatives nitrate and nitrite served as strongly oxidizing substrates driving the evolution of a bioenergetic pathway related to modern dissimilatory denitrification. Aerobic respiration emerged later from within this ancestral pathway via adaptation of the enzyme NO reductase to its new substrate, dioxygen.

Chemiosmosis in early life: the question of the terminal electron acceptor Mitchellian chemiosmotic energy conversion [START_REF] Mitchell | Vectorial chemiosmotic processes[END_REF], the process by which systems harvest the Gibbs free energy contained in the electrochemical disequilibrium between reducing and oxidizing substrates, is a common feature of Bacteria and Archaea. Therefore, it probably already operated in what is commonly referred to as the 'last universal common ancestor' (LUCA) of the two prokaryotic domains [START_REF] Martin | On the origin of cells: a hypothesis for the evolutionary transitions from abiotic geochemistry to chemoautotrophic prokaryotes, and from prokaryotes to nucleated cells[END_REF]. On modern Earth, strongly oxidizing substrates abound, whereas strongly reducing ones, such as molecular hydrogen (H 2 ) or reduced sulfur compounds, are confined to specific habitats. This predominant oxidizing environment results from oxygenic photosynthesis pumping O 2 into the biosphere for at least 2.5 billion years [START_REF] Xiong | Molecular evidence for the early evolution of photosynthesis[END_REF][START_REF] Nitschke | The FeS-type photosystems and the evolution of photosynthetic reaction centres[END_REF][START_REF] Baymann | Daddy, where did (PS)I come from?[END_REF][START_REF] Allen | Evolutionary biology: out of thin air[END_REF][START_REF] Tomitani | The evolutionary diversification of cyanobacteria: molecular-phylogenetic and paleontological perspectives[END_REF].

Before the onset of oxygenic photosynthesis the average redox state of the habitable environment must have been substantially lower with a likely predominance of H 2 , reduced sulfur and ferrous iron [START_REF] Russell | The emergence of life from iron nonsulphide bubbles at a submarine hydrothermal redox and pH front[END_REF][START_REF] Russell | The onset and early evolution of life[END_REF], whereas the anthropocentrically 'archetypal' substrate to chemiosmosis (Figure 1), O 2 , was almost certainly absent [10]. Recent hypotheses on the origin of chemiosmosis, therefore, invoke the relatively weak oxidant CO 2 as the most likely early electron acceptor from H 2 , yielding acetate or methane as reaction products [START_REF] Martin | On the origin of cells: a hypothesis for the evolutionary transitions from abiotic geochemistry to chemoautotrophic prokaryotes, and from prokaryotes to nucleated cells[END_REF][START_REF] Martin | On the origin of biochemistry at an alkaline hydrothermal vent[END_REF].

However, molecular phylogenies of several bioenergetic enzymes indicate the presence of bioenergetic electron sinks that are substantially more oxidizing than CO 2 in the early Archaean. Based on a re-evaluation of the phylogeny of the heme copper oxidase (HCO) superfamily and on recent insights in structure-function particularities of the major HCO subgroups, we argue that nitric oxide (NO) was the likely ancestral substrate to the HCO superfamily in the earliest Archaean. Contrary to the case of oxygen, a source for mass production of NO and its derivatives (NO 3 À and NO 2

À

) existed on the early Earth [START_REF] Navarro-Gonza ´lez | A possible nitrogen crisis for Archaean life due to reduced nitrogen fixation by lightning[END_REF]. Our scenario suggests an important role for the dissimilatory denitrification pathway or of its constituent segments in primordial energy conversion. Aerobic respiration would have originated from within the denitrification pathway through adaptation of NO reductase to its new substrate, O 2 .

Evolutionary histories of bioenergetic enzymes and the increasing environmental oxidation state

Enzyme phylogenies encompassing representatives from both prokaryotic domains, Bacteria and Archaea, serve to deduce whether a given enzyme existed before the Archaea-Bacteria split or appeared more recently. So far, only a few bioenergetic enzymes have been studied to this end. Phylogenies of Ni-Fe hydrogenase (i.e. the enzyme serving as the entry point for electrons from H 2 into energy-conserving chains) indicate that this redox complex evolved before the Archaea-Bacteria split [13,[START_REF] Baymann | The redox protein construction kit; pre-LUCA evolution of energy conserving enzymes[END_REF], in agreement with the abundance of H 2 in specific habitats on the early Earth and with the resulting likely crucial role of hydrogenase in primordial bioenergetics [START_REF] Martin | On the origin of biochemistry at an alkaline hydrothermal vent[END_REF]. An unexpected important role of arsenics as redox substrates in primordial habitats is becoming increasingly evident [START_REF] Kulp | As(III) fuels anoxygenic photosynthesis in hot spring biofilms from Mono Lake, California[END_REF]. In the early Archaean, the reduced form, arsenite, was most likely to be predominant and, correspondingly, the bioenergetic enzyme arsenite oxidase [Figure 2a(i)] seems to be pre-LUCA [START_REF] Lebrun | Arsenite oxidase, an ancient bioenergetic enzyme[END_REF].

In turn, phylogenies of several enzymes that reduce high redox-potential substrates bear distinctive signs of late, that is, post-LUCA origins followed by dissemination via horizontal gene transfer. Prominent examples are provided by the complexes involved in electron transfer towards oxidized sulfur compounds [START_REF] Stahl | Origins and diversification of sulfate-respiring microorganisms[END_REF] or in arsenate respiration [START_REF] Duval | Enzyme phylogenies as markers for the oxidation state of the environment: the case of the respiratory arsenate reductase and related enzymes[END_REF] [Figure 2a(i)], which uses the oxidized form of arsenics as the terminal electron acceptor. Indeed, arsenate reductase seems to have appeared long after the Archaea-Bacteria divergence, probably driven by rising arsenate levels induced by the increasing environmental oxidation state.

As logical as the dissimilar evolutionary histories of arsenite oxidases and arsenate reductases might seem, considering the gradual oxidation of substrates by photosynthesis, a nagging problem persists. Arsenite oxidase oxidizes a substrate with an electrochemical potential of approximately +60 mV at pH 7 (Figure 1). For this reaction to be productive in a bioenergetic chain there must be a terminal oxidant. This substance should be substantially more oxidizing than arsenate. According to its phylogeny, arsenite oxidase seems to have functioned before the Archaea-Bacteria split, that is, long before photosynthetic oxygen production [START_REF] Xiong | Molecular evidence for the early evolution of photosynthesis[END_REF][START_REF] Baymann | Daddy, where did (PS)I come from?[END_REF] set in; therefore, the nature of such a terminal oxidant remains enigmatic (Figure 1).

The substrate conundrum of the Rieske-cytb complexes

Another enzyme that strikingly violates the rule that high redox-potential substrates correlate with post-LUCA emergence is the Rieske-cytochrome b (cytb) complex. This enzyme is almost ubiquitous among prokaryotes and plays a pivotal part in energy conversion [START_REF] Kramer | The cytochrome bc 1 and related bc complexes, the Rieske/cytb complex as the functional core of a central electron/proton transfer complex[END_REF]. The family is widely known through two specific representatives, the cyt bc 1 complex (corresponding to mitochondrial complex III) and the cyt b 6 f complex operating in cyanobacteria and chloroplast oxygenic photosynthesis. The phylogenetic trees of both cytochrome b and the Rieske protein strongly resemble that of common 16S ribosomal (r)RNA trees and, in particular, show a pronounced cleavage into archaeal and bacterial subtrees [START_REF] Lebrun | The Rieske protein; a case study on the pitfalls of multiple sequence alignments and phylogenetic reconstruction[END_REF]. It is possible to root the tree because the Rieske protein is also an arsenite oxidase subunit. The composite phylogeny of Rieske-cytb complexes and arsenite oxidases [START_REF] Lebrun | Arsenite oxidase, an ancient bioenergetic enzyme[END_REF][START_REF] Lebrun | The Rieske protein; a case study on the pitfalls of multiple sequence alignments and phylogenetic reconstruction[END_REF] strongly indicates a pre-LUCA origin for both enzymes and, thus, corroborates the corresponding conclusion drawn for the catalytic molybdenum subunit of arsenite oxidases [Figure 2a(ii)].

The Rieske-cytb complexes transfer reducing equivalents from quinols to soluble electron-shuttle proteins such as cytochromes, copper proteins or high-potential iron sulfur proteins, which, in turn, reduce terminal oxidases. The midpoint potentials of these electron shuttles admittedly vary as a function of the chemical nature of the quinone molecule [START_REF] Schu ¨tz | Early evolution of cytochrome bc-complexes[END_REF] but always are in the positive range of potentials (Figure 1). To efficiently pull electrons ) and extend to 60 mV on both sides of the E m to indicate the range of ambient potentials in which these chemicals change their redox states (from $10% to 90% reduction; Eh, pH 7 stands for the ambient redox potential at pH 7). For simplicity, the differing 'steepness' of redox reactions of one-, two-or more-electron carriers was neglected. Blue or red boxes indicate that the corresponding redox couple is present predominantly in the reduced or oxidized state, respectively, whereas mixed colored boxes mean that the redox compound is oxidized or reduced according to the specific ambient conditions. The shaded ellipsoids mark the range ofE m values of redox cofactors harbored by the Rieske-cytb complexes. In the earliest Archaean environment, most modern electron acceptors are widely considered to have been fully reduced and, hence, are unavailable as electron acceptors (b). This would leave Archaean bioenergetics confined to electron transfer to CO 2 (i.e. acetogenesis and methanogenesis). However, as we argue here, several phylogenetic arguments point towards the presence of electron acceptors with E m values >100 mV, raising the question of the chemical nature of such high-potential acceptors (indicated by '?'). NO and its derivatives, nitrate and nitrite, produced by electrical discharge and follow-up reactions from CO 2 and N 2 (Box 1), are likely to have played the part of strong oxidants on the early Earth. Whether an enzyme related to nitrous oxide reductase might have closed the cycle towards atmospheric N 2 remains an open question.

through the chain, the terminal electron-accepting substrates are expected to be substantially more oxidizing with redox potentials no lower than +100 mV.

The apparent pre-divergence origin of the Rieske-cytb complexes, as for arsenite oxidase, implies the availability of a strong oxidant in the early Archaean. Guided by the layout of extant bioenergetic mechanisms [Figure 1(a)], molecular oxygen would be the straightforward candidate for such an oxidizing molecule. Although most paleogeochemical proxies indicate extremely little or no O 2 in the early Archaean [10], there are counter suggestions in favor of oxic intervals in this era [START_REF] Ohmoto | Sulphur isotope evidence for an oxic Archaean atmosphere[END_REF].

From the point of view of molecular evolution, it is tempting to tackle the question of molecular oxygen ancestry by analyzing the phylogeny of the enzymes that use O 2 as their (bioenergetic) substrate, that is, the respiratory O 2 reductases, historically called cytochrome (and quinol) oxidases.

HCO superfamily phylogeny: the controversy Three major groups of respiratory O 2 reductases have been identified [START_REF] Saraste | Evolution of cytochrome oxidase[END_REF] and are referred to as HCOs based on their cofactor composition comprising heme groups and copper atoms. A fourth group belonging to this enzyme superfamily was recognized in 1994 based on substantial similarities in sequence and cofactor composition [START_REF] Van Der Oost | The heme-copper oxidase family consists of three distinct types of terminal oxidases and is related to nitric oxide reductase[END_REF]. The members of this additional group reduce NO rather than oxygen and they deviate from the O 2 reductases owing to the presence of an iron atom, rather than a copper ion, in the catalytic site. In a series of articles some 15 years ago, Matti Saraste and colleagues concluded, from the prominent Archaea-Bacteria cleavage in phylogenetic trees of HCOs, that HCOs had their origin in the common ancestor of Bacteria and Archaea [25][START_REF] Castresana | Evolution of energetic metabolism: the respiration-early hypothesis[END_REF][START_REF] Castresana | New archaebacterial genes coding for redox proteins: implications for the evolution of aerobic metabolism[END_REF]. A possible descendence of O 2 reductases from NO reductases was considered based on the evident affiliation of the latter enzymes to the HCO superfamily [START_REF] Hendriks | From NO to OO: nitric oxide and dioxygen in bacterial respiration[END_REF]. These results thus favored the scenario of O 2 being present before the divergence of domains.

Whereas the early phylogenetic trees were reconstructed from only a handful of sequences, a more recent study analyzing a larger sample of dioxygen reductase sequences arrived at the opposite conclusion [START_REF] Pereira | A novel scenario for the evolution of haemcopper oxygen reductases[END_REF]. Pereira et al. [START_REF] Pereira | A novel scenario for the evolution of haemcopper oxygen reductases[END_REF] suggest that lateral gene transfer occurred among many early-diverging branches of the tree. One of the three groups, the cyt cbb 3 oxidases, were found to be devoid of archaeal representatives and seemed to contain only proteobacterial species leading to the proposal that this group diverged more recently from one of the other two O 2 reductase groups [START_REF] Pereira | A novel scenario for the evolution of haemcopper oxygen reductases[END_REF][START_REF] Myllykallio | Dual role for cytochrome cbb 3 oxidase in clinically relevant proteobacteria?[END_REF]. The ensemble of these observations was taken to indicate a post-divergence origin of dioxygen reductases followed by distribution over the entire prokaryotic world via lateral gene transfer.

HCO superfamily phylogeny: pre-and post-dualism

We have reanalyzed the phylogeny of the HCO superfamily (including the related heme-iron NO reductases) taking advantage of the recent explosion in the number of sequenced prokaryotic genomes. This tree [Figure 2a(iii)] features several well-defined clades. Two of these clades arise from quinol-and cytochrome-oxidizing NO reductases (qNOR and cNOR), respectively. The qNOR clade divides almost perfectly into archaeal and bacterial subtrees. The clade representing cbb 3 oxidases diverges close to NORs, as already noticed by Castresana and Saraste [START_REF] Castresana | Evolution of energetic metabolism: the respiration-early hypothesis[END_REF]. In our analysis, the cbb 3 clade was well separated from all other clades and encompassed nearly the full tree of the domain Bacteria, refuting the notion of a recent divergence of this enzyme from other types of HCO [START_REF] Ducluzeau | cbb 3 oxidases are an ancient innovation of the domain Bacteria[END_REF]. However, no archaeal cbb 3 family members were detected. The remaining clades of dioxygen reductases contain archaeal and bacterial representatives but, although well-separated archaeal and bacterial clusters are present, the roots do not fall in between Archaea and Bacteria [Figure 2a(iii)], in line with the results of Pereira et al. [START_REF] Pereira | A novel scenario for the evolution of haemcopper oxygen reductases[END_REF]. These phylogenies, thus, indicate early interdomain gene transfer (except for the cbb 3 oxidases) and subsequent vertical inheritance for the different groups of O 2 reductases rather than pre-divergence origins.

As much as this conclusion seems to be straightforward for each individual O 2 reductase clade, the structure of the whole tree leads to an entirely different conclusion. All HCO groups (including NOR) form well-defined clades separated by long rooting branches. This topology is difficult to rationalize assuming a single origin of a dioxygen reductase in either Archaea or Bacteria. Moreover, the assumption of a pre-divergence origin for qNOR, as indicated by the phylogenetic tree, implies that the common ancestors of the O 2 reductase clades, all being outgroups to NOR, already were present in the common ancestor. The structure we obtain for the phylogenetic tree of the HCO superfamily, therefore, gives contradictory messages, supporting at the same time a pre-and a post-divergence origin of HCOs. This tree, thus, remains incomprehensible in the absence of a radically new evolutionary paradigm.

From NO to O 2 reductases: the problem of the missing electron Despite the close phylogenetic relationship and the resulting structural similarities of the enzymes involved, the biochemical reactions of NO and O 2 reduction differ substantially [START_REF] Wikstro ¨m | Mechanism and energetics of proton translocation by the respiratory heme-copper oxidases[END_REF][START_REF] Zumft | Nitric oxide reductase of prokaryotes with emphasis on the respiratory, heme-copper oxidase type[END_REF]. Reduction of NO to nitrous oxide is a bimolecular reaction combining two NO molecules to N 2 O and water, whereas in dioxygen reduction a single O 2 molecule yields two water molecules:

NO þ NO þ 2e À þ 2H þ ! N 2 O þ H 2 O O 2 þ 4e À þ 4H þ ! H 2 O þ H 2 O
Furthermore, twice the number of reducing equivalents is required for O 2 compared with NO reduction.

In HCO-type O 2 and NO reductases, the catalytic step occurs in the binuclear center, which comprises a 5-coordinated heme moiety and a copper or an iron atom (Figure 2b). O 2 and the two NO molecules are assumed to bind between the two metal centers. The two reducing equivalents necessary for the conversion of two NO molecules into N 2 O are individually delivered by ferrous (Fe 2+ ) to ferric (Fe 3+ ) transitions of the heme and the non-heme irons in the binuclear center of NO reductases. In O 2 reductases, the heme shuttles between the ferrous (Fe 2+ ) and the ferryl (Fe 4+ ) states, thereby contributing two electrons to the catalytic step. The biologically accessible redox ) reductase, arsenite (As 3+ ) oxidase and other enzymes from this superfamily [START_REF] Duval | Enzyme phylogenies as markers for the oxidation state of the environment: the case of the respiratory arsenate reductase and related enzymes[END_REF], (ii) the Rieske subunit of arsenite oxidase and the Rieske-cytb complex [START_REF] Lebrun | The Rieske protein; a case study on the pitfalls of multiple sequence alignments and phylogenetic reconstruction[END_REF] and (iii) the catalytic subunit of representative members of the HCO superfamily. The topologies of the individual trees provide information on the evolutionary history of the respective families. Enzymes occurring in Archaea (A) are coded by orange branches, whereas those harbored by Bacteria (B) are marked in cyan (Firmicutes), dark green (Proteobacteria [Proteo]) and light green (all others). Eukaryotic (E) representatives are indicated in red. Trees featuring distinct Archaea-Bacteria cleavages at their roots indicate pre-divergence origins of the corresponding enzyme. This is, for example, the case for the Rieske-cytb complexes (ii) and arsenite (As 3+ ) oxidase (i and ii). By contrast, trees characterized by the absence of this cleavage and/or strong incongruence with 16S rRNA-based species trees (such as observed for the As 5+ reductase subtree) indicate late origins and dissemination via lateral gene transfer. The tree reconstructed on the HCOs (iii) is ambiguous with respect to these criteria and can, therefore, not be interpreted conventionally. In the HCO tree, qNOR and cNOR stand for quinol-and cytochrome-oxidizing NO reductases, respectively. The denomination of O 2 reductase clades (shaded) features both the nomenclature used by Saraste and colleagues [25] (i.e. SoxM, SoxB and FixN) and the more recent one introduced by Pereira et al. [START_REF] Pereira | A novel scenario for the evolution of haemcopper oxygen reductases[END_REF] (A-, B-and C-type). The phylogenetic tree has been reconstructed using the neighbor-joining method. Nodes supported by bootstrap values <50% are marked by circles. The topology of the tree at these nodes, therefore, is less reliable than in the rest of the tree. A detailed version of the tree featuring species names and its underlying alignment are available on request. (b) O 2 reductases distinguish themselves from NO reductases by the presence of a catalytically important tyrosine residue close to the active center. The catalytic binuclear center couple of the copper ion only enables the Cu + to Cu 2+ transition, adding a third electron to the reaction. This leaves the binuclear center short of one electron to proceed towards full reduction of O 2 . A multiple-step reduction of dioxygen (i.e. involving re-reduction of the heme in the binuclear center by secondary electron donors), however, presumably is evolutionarily strongly counter-selected against. Such a reaction scheme would produce reactive oxygen species (ROS) capable of diffusing out of the catalytic center and wreaking havoc in the parent cells. Indeed, in the well-characterized A (or SoxM)-type O 2 reductase (the enzyme functioning in our mitochondria) [Figure 2b(i)], the fourth electron is delivered (together with a proton in the form of a hydrogen atom) by the oxidation of a tyrosine residue [Figure 2b(i), labeled Tyr I ] present in the catalytic site [START_REF] Gennis | Multiple proton-conducting pathways in cytochrome c oxidase and a proposed role for the active-site tyrosine[END_REF][START_REF] Macmillan | Direct evidence for a tyrosine radical in the reaction of cytochrome c oxidase with hydrogen peroxide[END_REF][START_REF] Proshlyakov | Oxygen activation and reduction in respiration: involvement of redox-active tyrosine 244[END_REF].

Has the 'tyrosine solution' to the missing-electron problem been found independently several times? In the past, the case of the cbb 3 oxidases frequently was used to argue against an indispensable role of the tyrosine in catalyzing HCO-mediated O 2 reduction. The tyrosine residue, which is fully conserved in SoxM-type oxidases, is indeed absent in cbb 3 oxidases. In 2005, however, a milestone article from Bob Gennis' group [START_REF] Hemp | Helix switching of a key active-site residue in the cytochrome cbb3 oxidases[END_REF] demonstrated that the tyrosine residue (Tyr II ) involved in cbb 3 oxidase catalysis is located in a different sequence position and even on a different helix [Figure 2b(ii)]. Despite it being distant on the primary sequence of the protein, molecular modeling indicated that Tyr II is located in close vicinity to the binuclear center [START_REF] Hemp | Helix switching of a key active-site residue in the cytochrome cbb3 oxidases[END_REF], occupying a position almost identical to that of Tyr I [Figure 2b(i)]. The functional equivalence of this residue to that of the previously studied classes of O 2 reductases was subsequently shown by several laboratories [START_REF] Hemp | Evolutionary migration of a post-translationally modified active-site residue in the proton-pumping heme-copper oxygen reductases[END_REF][START_REF] Rauhama ¨ki | Identification of a histidine-tyrosine cross-link in the active site of the cbb 3 -type cytochrome c oxidase from Rhodobacter sphaeroides[END_REF]. These publications referred to the differing position of the tyrosine residue as 'migration of a functionally important residue'. Mechanistically, a mutant strain having lost the tyrosine in one place would have inserted this residue in another sequence position to suppress the deleterious ROS production. Such double-site suppressor mutations have been demonstrated for many other enzyme systems [START_REF] Di Rago | Genetic analysis of the folded structure of yeast mitochondrial cytochrome b by selection of intergenic second-site revertants[END_REF].

However, in the light of the ensemble of observations and conundrums outlined earlier, another scenario seems much more likely to us because it solves in one sweep most of the riddles of the evolutionary history of HCO. We propose that, rather than resulting from migration, the differing positions of the tyrosine in the HCO oxidases, in fact, betray the independent origins of these O 2 reductases from separate, now extinct, NO reductase subgroups. In this scenario, NO reductases would have diversified into several distinct groups before the Archaea-Bacteria divergence, much as it seems to be the case for the Ni-Fe hydrogenases [13,[START_REF] Baymann | The redox protein construction kit; pre-LUCA evolution of energy conserving enzymes[END_REF]. With increasing O 2 concentrations in the environment, dioxygen became a potent terminal acceptor for bioenergetic chains and some of these NO reductases evolved into dioxygen reducing enzymes 'simply' by inserting an electron-donating amino acid residue in close vicinity of the catalytic site.

One specific circumstantial observation resulting from our study of the HCO phylogeny lends support to this evolutionary scenario. In these phylogenies [Figure 2a(iii)], two clades lack a tyrosine residue in both the Tyr I and the Tyr II sequence positions. Screening the sequence stretches that structurally come close to the catalytic center, we found tyrosines, conserved within each clade, denoted Tyr III and Tyr IV , respectively, at two further sequence positions. Molecular modeling of these enzymes yields three-dimensional (3D) positions for Tyr III and Tyr IV with distances to the binuclear center that are perfectly comparable with those of the two characterized cases (Figure 2b). None of these enzymes, lacking both of the 'traditional' tyrosines, has been studied and we, therefore, cannot be sure whether they correspond to O 2 reductases rather than to 'reverted' NO reductases such as the enzyme in Bacillus azotoformans [START_REF] Suharti | NO reductase from Bacillus azotoformans is a bifunctional enzyme accepting electrons from menaquinol and a specific endogenous membrane-bound cytochrome c 551[END_REF]. A thorough analysis of selected members of these groups will help to elaborate our scenario in more detailor possibly weaken its likelihood.

Accepting the idea of several independent origins for the ability to reduce dioxygen rationalizes the topology of the HCO tree in an intriguingly simple manner. This evolutionary scenario, based on phylogenetic and biochemical evidence, predicts that NO was the primordial substrate of HCOs. It is noteworthy that the NO-N 2 O couple is even more oxidizing than is the O 2 -H 2 O couple (Figure 1). However, we then must ask where the NO might have originated on the early Earth.

Large-scale production of NO and its derivatives in the primordial atmosphere Several processes as diverse as lightning, volcanism and meteorite impacts would have produced up to 3 Â 10 12 g/yr of NO in the Archaean (Box 1). Part of this NO would subsequently have been photochemically converted (via HNO) to nitrate and nitrite and rained out into the primordial ocean (Box 1). The main substrates of the 'modern' dissimilatory denitrification pathway were, thus, present in the Archaean biosphere and probably provided the evolutionary driving force for the appearance of the denitrifying chain of enzymes or segments thereof. The NOR of O 2 reductases is made up by a heme group (yellow), a copper ion Cu B (blue) with its three histidine ligands and the redox-active tyrosine (red). Stretches of three nearby transmembrane (TM) helices (TM6 to TM8) are also shown in this figure. Four types of catalytic sites are grouped around the phylogenetic tree of O 2 reductases [reproduced in a thumbnail version from panel (a)]. (i) This structure is based on the crystallographic 3D structure of a SoxM-type O 2 reductase (PDB ID code 1V54; www.rcsb.org/pdb) and served as a template for the three remaining structures for which no 3D information is yet available. Although positioned on TM7 rather than TM6 (i.e. the canonical position in all SoxM-type O 2 reductases), the catalytic tyrosine of cbb 3 -type enzymes (ii) comes structurally as close to the heme-copper diade as does the tyrosine residue in (i) [START_REF] Hemp | Helix switching of a key active-site residue in the cytochrome cbb3 oxidases[END_REF]. The two different sequence positions for this tyrosine residue observed in SoxM-and cbb 3 -type O 2 reductases [START_REF] Hemp | Helix switching of a key active-site residue in the cytochrome cbb3 oxidases[END_REF] are denoted Tyr I and Tyr II , respectively. In the HCO tree [see part (a) of this figure], we observe two clades that contain neither Tyr I nor Tyr II but instead feature tyrosines in two new sequence locations (Tyr III and Tyr IV ). The structural models (iii and iv) of the catalytic site of enzymes possessing Tyr III and Tyr IV indicate that these tyrosines are again spatially close to the catalytic center and might, therefore, have a functional role similar to that of Tyr I and Tyr II . Because no representatives of the Tyr III and Tyr IV groups have been studied so far, these putatively important tyrosines are labeled with a '?'. The differing positions of the catalytic tyrosines can be rationalized assuming independent origins of the various O 2 reductase clades from ancestral NO reductases, which in turn abolishes the phylogenetic ambiguity of the HCO tree. The schematic representation of the transmembrane helices TM6 to TM8 beneath each structure indicates the corresponding positions of the respective tyrosine residues (red bar) and the three conserved histidine ligands to Cu B (black bars). The numbers of residues between each of these tyrosines and the closest histidine residue are shown. substrate would, thus, have been provided by the earlier steps of the denitrification cascade and possibly also by locally high NO concentrations directly produced in the electrical-discharge events.

Conclusion

Our hypothesis stipulates that, contrary to the widely accepted dogma, a strong oxidant was present during the earliest Archaean. This oxidant was not O 2 but NO and its derivatives nitrate and nitrite, produced geochemically in substantial amounts. Navarro-Gonza ´lez et al. [START_REF] Navarro-Gonza ´lez | A possible nitrogen crisis for Archaean life due to reduced nitrogen fixation by lightning[END_REF] estimated that decreasing CO 2 concentrations in the late Archaean prompted dwindling NO production. This might have induced a 'nitrogen crisis for Archaean life' possibly triggering the appearance of biological nitrogen fixation mechanisms [START_REF] Navarro-Gonza ´lez | A possible nitrogen crisis for Archaean life due to reduced nitrogen fixation by lightning[END_REF]. In the framework of our hypothesis, a reduced availability of nitrate, nitrite and NO would, in addition, have entailed an energy crisis, providing a further evolutionary driving force for the NO reductases of the denitrifying pathway to use the emerging O 2 as a new substrate.

Aerobic respiration, the quintessential bioenergetic mechanism of all (non-photosynthetic) complex life on this planet would, therefore, have its roots in an ancient energyconserving mechanism closely related to modern dissimilatory denitrification. Using the geochemically produced, strongly oxidizing nitrogen oxides as electron acceptors enabled this mechanism to operate on weak reductants (e.g. the heterotrophic substrates [Figure 1] pyruvate or lactate) as electron donors, an option previously considered inaccessible to life before the advent of O 2 . As a corollary to this fact, heterotrophic metabolism might also be much older than anticipated. Phylogenetic analyses of additional enzymes involved in these types of metabolism (see, for example, Ref. [START_REF] Jones | Phylogenetic analysis of nitrite, nitric oxide, and nitrous oxide respiratory enzymes reveal a complex evolutionary history for denitrification[END_REF]) will provide insights into the details of Archaean bioenergetic mechanisms.

We would like to emphasize that the conceptual framework of the 'enzymatic' portion of our hypothesis was provided initially in 1998 by Matti Saraste and colleagues [START_REF] Hendriks | From NO to OO: nitric oxide and dioxygen in bacterial respiration[END_REF] who recognized the likely evolutionary ancestry of NO reductase over O 2 reductases. However, they proposed that both NO and O 2 reductases were pre-divergence enzymes. Ten years earlier, Mancinelli and McKay had, based on palaeogeochemical arguments, arrived at the conclusion that dissimilatory denitrification probably operated in the Archaean, whereas aerobic respiration must have appeared only much later [START_REF] Mancinelli | The evolution of nitrogen cycling[END_REF].

The scenario that we present here and that is based on the recent advances in the understanding of O 2 reductases merges these two visionary proposals while correcting a few details. Pre-divergence denitrification, indeed, seems to pre-date O 2 -dependent aerobic respiration. This latter mechanism, however, directly arose from the evolutionary switch of the substrate for NO reductases: from NO to OO.

Box 1. Nitrogen oxides from CO 2 ,N 2 and energy As shown experimentally [START_REF] Navarro-Gonza ´lez | A possible nitrogen crisis for Archaean life due to reduced nitrogen fixation by lightning[END_REF], electrical-discharge events in an atmosphere containing CO 2 and N 2 produce NO via the following chain of reactions:

CO 2 ! O þ CO N 2 þ O ! NO þ N N þ CO 2 ! NO þ CO
Several sources for high-voltage electrical discharge existed in the Archaean and would have added up to create NO in the atmosphere. (a) Volcanically induced lightning would have produced $6 Â 10 11 g/yr [START_REF] Navarro-Gonza ´lez | Nitrogen fixation by volcanic lightning in the early Earth[END_REF]. (b) Meteorite impact plumes are estimated to have generated $10 12 g/yr [START_REF] Kasting | Bolide impacts and the oxidation state of carbon in the earth's early atmosphere[END_REF]. (c) Thunderstorm lightning would have yielded another $3 Â 10 11 g/yr [START_REF] Navarro-Gonza ´lez | A possible nitrogen crisis for Archaean life due to reduced nitrogen fixation by lightning[END_REF]. (d) Martin et al. [START_REF] Martin | Volcanic emissions and the early Earth atmosphere[END_REF] have, furthermore, argued that high temperature alone in volcanic gasses would have created $1.5 Â 10 12 g/yr. (a) to (d) add up to a total of $3 Â 10 12 g/yr. A small part of this atmospheric NO partitions directly into the ocean, whereas the bulk of this NO reacts, in the presence of water vapor, UVphotochemically to HNO according to the following reactions [START_REF] Mancinelli | The evolution of nitrogen cycling[END_REF][START_REF] Summers | Nitrogen fixation on early Mars and other terrestrial planets: experimental demonstration of abiotic fixation reactions to nitrite and nitrate[END_REF].

H 2 O þ hnð < 190 nmÞ!H þ OH CO þ H ! HCO HCO þ NO ! HNO þ CO
HNO rains out into the Hadean Ocean where it yields nitrate, nitrite and nitrous oxide [START_REF] Summers | Nitrogen fixation on early Mars and other terrestrial planets: experimental demonstration of abiotic fixation reactions to nitrite and nitrate[END_REF] and where NO 3 À and NO 2 À (produced in a 4:1 ratio) [START_REF] Summers | Nitrogen fixation on early Mars and other terrestrial planets: experimental demonstration of abiotic fixation reactions to nitrite and nitrate[END_REF] accumulate in the ocean and N 2 O escapes back to the atmosphere.

HNO ! H þ þ NO À NO À þ NO ! N 2 O 2 À N 2 O 2 À þ NO ! N 3 O 3 À N x O x À ! NO 2 À þ NO 3 À þ N 2 O
The mass of the modern ocean amounts to 1.410 24 g [START_REF] Bounama | The fate of the Earth's ocean[END_REF].T h e H a d e a nO c e a nm i g h th a v eh a du pt ot w i c et h a tm a s s [START_REF] Bounama | The fate of the Earth's ocean[END_REF] and for the following we, therefore, assume a total of 3 Â 10 24 gf o rt h e surface water on the early Earth. Because hydrological cycling between atmosphere and ocean is, and was, at least an order of magnitude more rapid than hydrothermal cycling between crust and ocean (which results in loss via reduction of the nitrogen oxides) [START_REF] Elderfield | Mid-ocean ridge hydrothermal fluxes and the chemical composition of the ocean[END_REF] (http://oceanworld.tamu.edu/resources/ oceanography-book/hydrocycle.html), accumulation of these nitrogen oxides to micromolar concentrations on average (and probably locally to even higher concentrations) would have taken approximately 1 million years, a mere blink of the eye on a geological timescale.

Figure 1 .

 1 Figure 1. Energy-conserving redox reactions on the modern and the primordial Earth. Today, owing to the almost ubiquitous O 2 , the ambient oxidation state of the environment is high and a plethora of different bioenergetic electron-transfer chains operate in living organisms. Only a few examples pertinent in the context of our scenario are depicted in part (a). The vertical bars are centered at the standard midpoint potentials (E m ) of the bioenergetic substrates (versus the standard hydrogen electrode [SHE]) and extend to 60 mV on both sides of the E m to indicate the range of ambient potentials in which these chemicals change their redox states (from $10% to 90% reduction; Eh, pH 7 stands for the ambient redox potential at pH 7). For simplicity, the differing 'steepness' of redox reactions of one-, two-or more-electron carriers was neglected. Blue or red boxes indicate that the corresponding redox couple is present predominantly in the reduced or oxidized state, respectively, whereas mixed colored boxes mean that the redox compound is oxidized or reduced according to the specific ambient conditions. The shaded ellipsoids mark the range ofE m values of redox cofactors harbored by the Rieske-cytb complexes. In the earliest Archaean environment, most modern electron acceptors are widely considered to have been fully reduced and, hence, are unavailable as electron acceptors (b). This would leave Archaean bioenergetics confined to electron transfer to CO 2 (i.e. acetogenesis and methanogenesis). However, as we argue here, several phylogenetic arguments point towards the presence of electron acceptors with E m values >100 mV, raising the question of the chemical nature of such high-potential acceptors (indicated by '?'). NO and its derivatives, nitrate and nitrite, produced by electrical discharge and follow-up reactions from CO 2 and N 2 (Box 1), are likely to have played the part of strong oxidants on the early Earth. Whether an enzyme related to nitrous oxide reductase might have closed the cycle towards atmospheric N 2 remains an open question.

Figure 2 .

 2 Figure 2. Molecular phylogenies of selected bioenergetic enzymes together with structural idiosyncrasies of different HCO clades indicate independent origins of O 2 reductases from NOR. (a) Shown are molecular phylogenies reconstructed on (i) the molybdopterin catalytic subunit of arsenate (As 5+) reductase, arsenite (As 3+ ) oxidase and other enzymes from this superfamily[START_REF] Duval | Enzyme phylogenies as markers for the oxidation state of the environment: the case of the respiratory arsenate reductase and related enzymes[END_REF], (ii) the Rieske subunit of arsenite oxidase and the Rieske-cytb complex[START_REF] Lebrun | The Rieske protein; a case study on the pitfalls of multiple sequence alignments and phylogenetic reconstruction[END_REF] and (iii) the catalytic subunit of representative members of the HCO superfamily. The topologies of the individual trees provide information on the evolutionary history of the respective families. Enzymes occurring in Archaea (A) are coded by orange branches, whereas those harbored by Bacteria (B) are marked in cyan (Firmicutes), dark green (Proteobacteria [Proteo]) and light green (all others). Eukaryotic (E) representatives are indicated in red. Trees featuring distinct Archaea-Bacteria cleavages at their roots indicate pre-divergence origins of the corresponding enzyme. This is, for example, the case for the Rieske-cytb complexes (ii) and arsenite (As 3+ ) oxidase (i and ii). By contrast, trees characterized by the absence of this cleavage and/or strong incongruence with 16S rRNA-based species trees (such as observed for the As 5+ reductase subtree) indicate late origins and dissemination via lateral gene transfer. The tree reconstructed on the HCOs (iii) is ambiguous with respect to these criteria and can, therefore, not be interpreted conventionally. In the HCO tree, qNOR and cNOR stand for quinol-and cytochrome-oxidizing NO reductases, respectively. The denomination of O 2 reductase clades (shaded) features both the nomenclature used by Saraste and colleagues [25] (i.e. SoxM, SoxB and FixN) and the more recent one introduced by Pereira et al.[START_REF] Pereira | A novel scenario for the evolution of haemcopper oxygen reductases[END_REF] (A-, B-and C-type). The phylogenetic tree has been reconstructed using the neighbor-joining method. Nodes supported by bootstrap values <50% are marked by circles. The topology of the tree at these nodes, therefore, is less reliable than in the rest of the tree. A detailed version of the tree featuring species names and its underlying alignment are available on request. (b) O 2 reductases distinguish themselves from NO reductases by the presence of a catalytically important tyrosine residue close to the active center. The catalytic binuclear center

Acknowledgements

We thank Christophe Le ´ger (Marseille) and Chris Boxe (Jet Propulsion Laboratory) for stimulating discussions. Our work was financially supported by the French Agence Nationale pour la Recherche (ANR-06-BLAN-0384 and ERRMoE; www.agence-nationale-recherche.fr). M.J.R.'s research described here was carried out at the Jet Propulsion Laboratory, California Institute of Technology (www.jpl.nasa.gov) under a contract with the National Aeronautics and Space Administration (www.nasa.gov).


Sergej Scheck
email: sergej.scheck@unicaen.fr

Alexandre Niveau
email: alexandre.niveau@unicaen.fr

Bruno Zanuttini
email: bruno.zanuttini@unicaen.fr

Explicit Representations of Persistency for Propositional Action Theories

Keywords: Planification, compilation de connaissances, théories d'actions, persistance, problème du cadre, circonscription Planning, knowledge compilation, action theories, persistency, frame problem, circumscription

Nous envisageons d'enrichir la représentation des actions en logique propositionnelle par des opérateurs syntaxiques pour représenter la persistance des variables. Ceci est motivé par le fait que le problème du cadre n'est pas résolu de manière satisfaisante par les langages propositionnels, tels que les diagrammes de décision binaires ou DNF. Nous introduisons deux de ces opérateurs, permettant de représenter différents types de persistance, et considérons les langages obtenus à partir de la logique propositionnelle en les ajoutant à n'importe quel niveau d'imbrication. Nous étudions les langages résultantes du point de vue de leur concision relative et de la complexité de la décision de successeur. Nous montrons une image intéressante de divers résultats de complexité.

Introduction

In automated planning, a central aspect of the description of problems is the formal representation of actions. Such representations are needed for specifying the available actions, and for the planners to operate on them while computing a plan. PDDL [START_REF] Mcdermott | PDDL-the planning domain definition language[END_REF] is a standard language for this.

More generally, the formal representation of actions is central to reasoning about actions, programs, and change using logic. Frameworks for this include proposals as diverse as the Situation Calculus [START_REF] Reiter | The frame problem in the situation calculus: A simple solution (sometimes) and a completeness result for goal regression[END_REF], the Event Calculus [START_REF] Kowalski | A logicbased calculus of events[END_REF], PDL [START_REF] Michael | Propositional dynamic logic of regular programs[END_REF], DL-PA [START_REF] Balbiani | Dynamic logic of propositional assignments: A well-behaved variant of pdl[END_REF], and many others. We view such languages as either imperative or declarative. Declarative languages allow one to specify the properties of situations, actions, events, while imperative languages concentrate on how the effects are brought about. In this view, the Situation and Event Calculi are declarative, as well as PDL, while PDDL and DL-PA are imperative. On the other hand, a well-known question when representing action and change is how to succinctly specify the noneffects of actions, that is, to ensure that the specification precludes fluents to change value while this is not intended. This is known as the frame problem. While imperative languages naturally come with a solution to the frame problem, because operational semantics literally transform a situation into another one, the frame problem is crucial in declarative languages, and it has been thoroughly studied, in particular for the Situation Calculus [START_REF] Reiter | The frame problem in the situation calculus: A simple solution (sometimes) and a completeness result for goal regression[END_REF]. We are interested here in the frame problem for actions specified in the simple language of propositional action theories, that is, as Boolean formulas describing the possible combinations of values for fluents before and after the action is taken. Though this language is very simple, it is indeed used in automated planning, because it makes operations on sets of states (aka belief states) conceptually simple [START_REF] Cimatti | Conformant planning via symbolic model checking[END_REF][START_REF] Bryce | Planning graph heuristics for belief space search[END_REF][START_REF] Son | A generic approach to planning in the presence of incomplete information: Theory and implementation[END_REF]. We consider action theories represented in Negation Normal Form (NNF), which encompasses representations usually used like ordered binary decision diagrams or formulas in disjunctive normal form. Such theories are adequate for representing (purely) nondeterministic actions, which lie at the core of fully observable nondeterministic planning and conformant planning [START_REF] Rintanen | Complexity of planning with partial observability[END_REF][START_REF] Albore | Compiling uncertainty away in nondeterministic conformant planning[END_REF][START_REF] Geffner | A Concise Introduction to Models and Methods for Automated Planning[END_REF][START_REF] Muise | Non-deterministic planning with conditional effects[END_REF][START_REF] Son | A generic approach to planning in the presence of incomplete information: Theory and implementation[END_REF][START_REF] Geffner | Compact policies for fully observable non-deterministic planning as SAT[END_REF]. Our contribution is to propose two different operators for representing the persistency of fluents, and to consider the language of NNF actions theories as enriched by one or the other. The originality of this contribution lies in the facts that (i) the language is enriched with an operator, which, we argue, allows one to specify the persistency of variables more naturally and succinctly than expressions in the plain underly-ing logic (like successor-state axioms for the Situation Calculus), and (ii) we allow the operators to occur anywhere in the formula, including nested occurrences, which again facilitates the description of actions. Our operators are one whose interpretation is dependent on the syntax of the action in its scope, and one whose interpretation depends only on its semantics (as a relation between the states before and after the action). The "semantic" one corresponds to interpreting the action in its scope under circumscription [START_REF] Mccarthy | Circumscription-a form of nonmonotonic reasoning[END_REF], here used as a semantics of minimal change through the action. We consider the resulting extensions of the language of NNF action theories in the formal framework of the knowledge compilation map [START_REF] Darwiche | A knowledge compilation map[END_REF]. This framework deals with the study of formal languages under the point of view of queries (how efficient is it to answer various queries depending on the language?), transformations (how efficient is it to transform or combine different representations in a given language?), and succinctness (how concise is it to represent knowledge in each language?). We focus on queries related to automated planning (deciding whether the action can lead from a state to another one, whether it is applicable at some state) and on succinctness issues. Naturally, there is a tradeoff between tractability of queries and succinctness of the languages. We give a complete picture for the languages which we consider. Precisely, we show that the syntactic operator can be added to NNF action theories without changing complexity of queries nor succinctness, since it can be compiled away in polynomial time; this shows that actions can be specified in the richer language without harming further calculations. On the other hand, we show that the semantic operator yields a more succinct language when allowed only at the root of expressions, and even more succinct when allowed everywhere, but that the complexity of answering queries increases accordingly.

Preliminaries

We consider a countable set of propositional state variables P = {p i | i ∈ N}. Let P ⊂ P be a finite set of state variables; a subset of P is called a P -state, or simply a state. The intended interpretation of a state s ∈ 2 P is the assignment to P in which all variables in s are true, and all variables in P \ s are false. For instance, for P = {p 1 , p 2 , p 3 }, s = {p 1 , p 3 } denotes the state in which p 1 , p 3 are true and p 2 is false. We write V(ϕ) for the set of variables occuring in an expression ϕ; note that expressions may involve both variables in P and variables not in P, so in general we do not have V(ϕ) ⊆ P.

Actions We consider (purely) nondeterministic actions, i.e., actions with which a single state may have several successors.

Definition 1. Let P ⊂ P be a finite set of variables. A P -action is a mapping a from 2 P to 2 (2 P ) . The states in a(s) are called a-successors of s.

Note that a(s) is defined for all states s. We will consider a to be applicable in s if and only if a(s) = ∅ holds. Definition 2. An action language is an ordered pair L, I , where L is a set of expressions and I is a partial function on L × 2 P such that, when defined on α ∈ L and P ⊂ P, I(α, P ) is a P -action.

We call the expressions in L action descriptions, and call I the interpretation function of the language. Observe that those sets P 's such that I(α, P ) is defined are a priori not related to V(α); α may involve auxiliary variables (not in P) which are not part of the state descriptions, and dually, a state may assign variables of P which do not occur in α. If L, I, P are fixed or clear from the context, then we write α(s) instead of I(α, P )(s) for the set of all α-successors of s. In this case we call P the scope of α. In this article we will consider action descriptions α which are intendedly constructed to ensure that I(α, P ) is defined. Definition 3. A translation from an action language L 1 , I 1 to another language L 2 , I 2 is a function f : L 1 × 2 P → L 2 satisfying I 1 (α, P ) = I 2 (f (α, P ), P ) for all α ∈ L 1 and P ⊂ P such that I 1 (α, P ) is defined.

In words, this means that the L 1 -expression α and the L 2expression f (α, P ) describe the same P -action. Again, when P is clear from the context, we write f (α) for f (α, P ). The translation f is said to be polynomial-time if it can be computed in time polynomial in the size of α and P , and polynomial-size if the size of f (α, P ) is bounded by a fixed polynomial in the size of α and P . Clearly, a polynomial-time translation is necessarily also a polynomial-size one, but the converse is not true in general.

Logic A Boolean formula ϕ over a set Q of variables is in negation normal form (NNF) if it is built up from literals using conjunctions and disjunctions, i.e., if it is generated by the grammar ϕ ::= q | ¬q | ϕ∧ϕ | ϕ∨ϕ, where q ranges over Q. Similarly to other expressions, Q may involve state variables (in P) and other variables (not in P). It is important to note that a formula ϕ with V(ϕ) ⊆ Q for some set of variables Q can be viewed as a formula over Q (and the truth value of the corresponding Boolean function does not depend on the variables in Q \ V(ϕ)). For a Boolean formula ϕ over Q and an assignment t to the variables in Q, we write t |= ϕ if ϕ evaluates to true under the assignment t. For readability, we sometimes use the symbols ↔ and → in Boolean formulas and still call them NNF formulas. Indeed, it will always be the case that there are equivalent NNF formula of the same size, up to a polynomial. We always use notation s, t, . . . for states, α, β, . . . for action descriptions, and ϕ, ψ, . . . for logical formulas.

Action theories

We define the action language of (NNF) action theories, whose extensions we are going to study. To prepare the definition we associate an auxiliary variable p / ∈ P to each variable p ∈ P; p denotes the value of p after the action took place, while p denotes the value before. Definition 4. An NNFAT action description is a Boolean formula α in NNF over P α ∪ {p | p ∈ P α } for some set of state propositions P α ⊂ P. The interpretation of an NNFAT action description α is defined for all P ⊆ P such that P ⊇ V(α)∩P (that is, when all state propositions have a value) by

∀s ⊆ P : I(α, P )(s) = {s | (s, s ) |= α}
where (s, s ) := s ∪ {p | p ∈ s } is the assignment to P ∪ {p | p ∈ P α } induced by s, s . For P ⊇ V(α) ∩ P, I(α, P ) is not defined. In words, an NNFAT expression represents the set of all ordered pairs s, s such that s is a successor of s, as a Boolean formula over variables in P ∪ {p | p ∈ P}. Importantly, NNFAT does not assume persistency of values, so that if, for example, a variable does not appear at all in an NNFAT expression, then this means that its value after the execution of the action can be arbitrary.

Example 5. Let P = {p 1 , p 2 , p 3 }, s 1 = ∅, s 2 = {p 1 }, and α := p 1 ∨ (p 1 ∧ p 2
), which can be read "when p 1 is false before the action is taken, both p 1 and p 2 become true after the action, and when p 1 is true anything can occur". Then α(s 1 ) = {{p 1 , p 2 }, {p 1 , p 2 , p 3 }}, and α(s 2 ) = 2 P .

Circuit representation Since we study the succinctness of languages, it is crucial to define the size of action descriptions. For this we use the same setting as typically used in knowledge compilation studies about propositional logic [START_REF] Darwiche | A knowledge compilation map[END_REF], and assume that all action descriptions α are represented by the directed acyclic graph, or circuit, obtained from the syntactic tree of α by iteratively identifying the roots of two isomorphic subexpressions to each other, until no more reduction is possible (like for binary decision diagrams [START_REF] Bryant | Symbolic boolean manipulation with ordered binary-decision diagrams[END_REF]). Clearly, for all expressions α, the circuit associated to α in this manner is unique, and it can be computed in polynomial time from the plain expression or from a nonreduced circuit.

Frame operators

Our proposal is to enrich NNFAT with operators for expressing persistency of variable values. Operators in action languages are used to construct new action descriptions from existing ones, and they can be roughly divided into two types: the interpretation of a syntactic operator depends on its argument action descriptions, while that of a semantic operator depends on the actions but not on their description. It is important to recall that NNF is a complete language for propositional logic and hence, that NNFAT is able to express any action. As a consequence, by enriching NNFAT we mean providing languages in which it is more convenient to express actions, as we will illustrate, but there is no action which those enriched languages can encode, that NNFAT cannot encode itself.

Semantic frame operator

The semantic frame operator which we study builds on circumscription [START_REF] Mccarthy | Circumscription-a form of nonmonotonic reasoning[END_REF], which is a nonmonotonic semantics for formulas enforcing a form of closed-world assumption, and especially by propositional circumscription [START_REF] Eiter | Propositional circumscription and extended closed-world reasoning are πp2-complete[END_REF][START_REF] Nordh | A trichotomy in the complexity of propositional circumscription[END_REF]. However, by introducing an operator for this interpretation, we allow circumscription to be enforced only on some parts of an expression. Let α be an action description and s be a P -state. For all partitions {X, V, F } of P , we introduce the operator C X,V,F so that C X,V,F (α)(s) chooses those α-successors of s which change variables from X minimally among all states with the same values over F . Precisely, we define a state s to be preferred to a state s with respect to a state s and to X, V, F , which we write s ≺ s X,V,F s , if s ∩ F = s ∩ F and (s ∆s) ∩ X ⊂ (s ∆s) ∩ X hold, where ∆ denotes symmetric difference for sets. 1Definition 6. The action language NNFAT C is the language L C , I C , where the expressions with scope P in L C are defined by the grammar

α ::= p | p | ¬p | ¬p | α ∧ α | α ∨ α | C X,V,F (α),
where p ranges over P and X, V, F over partitions of P , and I C is defined as for NNFAT, extended with It can be seen that the C X,V,F operator is convenient in particular for expressing actions which involve external causes (to be put in the set F ) of changes of values for variables of interest (set X), in the presence of ramifications (set V ).

I(C X,V,F (α), P )(s) = {s ∈ I(α, P )(s) | s ∈ I(α, P )(s) : s ≺ s X,V,F s }
Example 8. Consider encoding the action of driving from work to home. A particularly succinct description is

C {home},{at_work},{flat_tire,engine_ok} (engine_ok ∧ ¬flat_tire ) → home ) ∧ (home ↔ ¬at_work )
Consider s = {engine_ok, at_work}. Minimization of change over {home} entails that when the causes are not met (for instance, when engine_ok is false), among the possible successors of s only the ones with ¬home are retained, ignoring the ramification at_work ; successors with home are not retained, reflecting the fact that there is no "proof" provided by the action that home should change value. On the other hand, due to their presence in the set F , all combinations of causes will be retained. Precisely, the successors of s are {engine_ok, at_work, flat_tire}, {at_work}, {at_work, flat_tire}, and {engine_ok, home}.

Syntactic frame operator

We now define a syntactic operator, for representing the notion of persistency of languages like PDDL, where a variable does not change value if there is no explicit reason for this. Concretely, we want an operator F such that {p} is an F(p ∨¬p )-successor of s = ∅, but not an F(q ∨ ¬q )-successor for q = p, although p ∨¬p describes the same action as q ∨¬q . Therefore we need to formalize the intuition that some change is "explicitly mentioned" in an action description.

For this, we refine the notion of successor by considering the effects which apply in a state, themselves decomposed into explicit and implicit effects.

Definition 9. An effect (over P ⊆ P) is a quadruple e + , e -, i + , i -such that e + , e -, i + , i -are pairwise disjoint subsets of P . The explicit (resp. implicit) part of such an effect is the pair e + , e -(resp. i + , i -).

The positive (e + ∪ e -) and negative (e -∪ i -) are similar to add-and del-lists in STRIPS: e + , e -, i + , i -provokes a transition from a state s to s = (s ∪e + ∪i + )\(e -∪i -). We now define effects for NNFAT action descriptions. For combinations of effects via ∧, let

ε 1 = e + 1 , e - 1 , i + 1 , i - 1 and ε 2 = e + 2 , e - 2 , i + 2 , i - 2 . If e + 1 ∪ i + 1 = e + 2 ∪ i + 2 holds then we write ε 1 ≈ ε 2 and set ε 1 + ε 2 := e + 1 ∪ e + 2 , e - 1 ∪ e - 2 , i + 1 ∩ i - 1 , i + 2 ∩ i - 2 .
Intuitively, ε 1 ≈ ε 2 means that they provoke exactly the same transitions, but possibly with different explicit/implicit changes, and ε 1 + ε 2 is the effect which makes explicit any change which is explicit in one of them. Definition 10. Let α be an NNFAT action description and s be a state. Then the set of effects of α in s, written E(α, s), is defined inductively by

E(p, s) = { ∅, ∅, A, B | A, B ⊆ P } for s |= p, E(p, s) = ∅ for s |= p;
and dually for E(¬p, s)

E(p , s) = { ∅, ∅, A, B | A, B ⊆ P \ {p}} ∪{ {p}, ∅, A, B | A, B ⊆ P \ {p}} for s |= p, E(p , s) = { {p}, ∅, A, B | A, B ⊆ P \ {p}} for s |= p;
and dually for E(¬p , s)

E(α 1 ∧ α 2 , s) = {ε 1 + ε 2 | ε 1 ∈ E(α 1 , s), ε 2 ∈ E(α 2 , s), ε 1 ≈ ε 2 }; E(α 1 ∨ α 2 , s) = E(α 1 , s) ∪ E(α 2 , s) ∪ E(α 1 ∧ α 2 , s).
where A, B are always disjoint from each other.

Intuitively, the first case says that the action p is not applicable if s does not satisfy p (second line), and otherwise imposes no constraint on the successor state, but moreover does not set any value explicitly: a transition may occur from, say, {p, q} to {r}, but then the positive effects A = {r} and negative effects B = {p, q} are considered to be implicit.

For atomic actions of the form p , we distinguish two cases. When s does not already satisfy p, then all effects of p explicitly set p. Constrastingly, when s already satisfies p, then the action p leaves the value unchanged, and we include both effects with an explicit setting of p (to the same value) and effects with no setting of p at all (neither implicit nor explicit). Of course, for fixed A, B, those two effects provoke a transition from s to the same successor s . Nevertheless, including the effects which do not set p at all turns out to be necessary for ∧ to behave as expected in the extension of NNFAT with the F operator (to be defined soon). Finally, it is worth noting that we include the effects of

α 1 ∧ α 2 in those of α 1 ∨ α 2 .
Of course, the transitions of α 1 ∧ α 2 are already included in those of α 1 and in those of α 2 , but not necessarily with the same explicit parts. For instance, for α 1 = p , α 2 = q , and s = ∅, s = {p, q} is both an α 1 -and an α 2 -successor of s, but the "fully" explicit effect {p, q}, ∅, ∅, ∅ is only one of

α 1 ∧ α 2 .
With this in hand, we can define the framing operator F X . Intuitively, F X (α) retains only those effects of α which include no implicit effect on variables of X. As can be seen, this is equivalent to removing variables of X from the implicit part of all effects. So we define E(F X (α), s) to be { e + , e -, i + \ X, i -\ X | e + , e -, i + , i -∈ E(α, s)} Definition 11. The action language NNFAT F is the language L F , I F , where the expressions with scope P in L F are defined by the grammar

α ::= p | p | ¬p | ¬p | α ∧ α | α ∨ α | F X (α),
where p ranges over P and X over subsets of P , and I F is defined for all α, s, I F (α, P )(s) is defined to be

{(s ∪ e + ∪ i+) \ (e -∪ i -) | e + , e -, i + , i -∈ E(α, s)} Example 12.
Consider the action of leaving one's bike in a garage for them to repair exactly one wheel, but not knowing which one in advance. 2 The action may have two effects: making the front wheel or the back wheel ok (in both cases not affecting the other). However, in the process of repairing the back wheel, it might occur that the gear is changed. Additionally, in no case would the brakes be affected. Such an action could be encoded by

F brakes F f_wheel_ok (b_wheel_ok )∨F b_wheel_ok,gear (f_wheel_ok )
Importantly, in general, pushing all occurrences of F to the root of the expression changes its interpretation. For instance, in Example 12, this would yield the expression F brakes,f_wheel_ok,b_wheel_ok,gear b_wheel_ok ∨f_wheel_ok according to which the gear can never change value. Another important observation is that F X is not a special case of C X,V,F . It might seem that F X is nothing more than C X,∅,P \X . However, taking P = {p}, α = p ∨ ¬p , and s = ∅, it can be seen that both ∅ and {p} are F X (α)-successors of s, while only ∅ is a C X,∅,P \X (α)successor. Indeed, F X (α) takes into account the fact that both alternatives are explicitly mentioned in the formula, while C X,∅,P \X (α) considers only the semantics of α and hence, is equivalent to C X,∅,P \X ( ).

Restriction on circuits In addition to NNFAT C and NNFAT F , we will also study their natural restrictions where the operator C X,V,F or F X , respectively, occurs only at the root of expressions. Namely, NNFAT C is NNFAT augmented only with expressions of the form C X,V,F (α), where α is an NNFAT action description. We denote by NNFAT rC the resulting language. Similarly, we define the restricted language NNFAT rF . Observe that PDDL, for instance, can be seen as a language without framing, together with an (implicit) operator F P at the root of all expressions.

Compiling the Syntactic Operator Away

In this section, we show that the syntactic operator F X can be eliminated from an NNFAT F expression to yield an expression in NNFAT which has the same interpretation and size (up to a polynomial). Moreover, the elimination can be done in polynomial time. This means that NNFAT F can be used as a convenient language for describing actions, still the algorithms which manipulate those descriptions (e.g. planners) need not be extended to cope with F, since all its occurrences can simply be eliminated in polynomial time and space. Let us mention that the equivalent result is rather obvious for plain (tree-like) representations of formulas, but that we consider here circuit representations, in which a single subcircuit may occur in an exponential number of paths.

Our procedure essentially amounts to replacing all occurrences of F with subformulas similar to successor-state axioms. Before we show the result, we need two lemmas (the proofs are by induction on the structure of α).

The first lemma defines an expression Expl(α, p), and shows that this expression states that if p changes its value via α, then there is at least one effect which does it explicitly. For states s, s and action description α, write E(α, s, s ) for the set of effects which lead from s to s : E(α, s, s ) := { e + , e -, i

+ , i -∈ E(α, s) | s = (s ∪ e + ∪ i + ) \ (e -∪ i -)}.
Lemma 13. Let α be a NNFAT F action description with scope P , s, s ⊆ P be two states and p ∈ s∆s . Then there is an effect e + , e -, i + , i -∈ E(α, s, s ) with p ∈ e + e ∪ e - e if and only if (s, s ) |= Expl(α, s), where the NNFAT expression Expl(α, s) is defined to be

• α for α = p or α = ¬p ,
• ⊥ for α = q or α = ¬q with q = p,

• ⊥ for α = q or α = ¬q, for all variables q,

• (Expl(β, p) ∧ γ) ∨ (β ∧ Expl(γ, p)) for α = β ∧ γ, • Expl(β, p) ∨ Expl(γ, p) for α = β ∨ γ, • x∈X∪{p} (x ↔ x ) ∨ Expl(β, x) for α = F X (β).
The second lemma states properties of sets of effects.

Lemma 14. Let α be an NNFAT F action description with scope P ⊇ s and ε 1 , ε 2 ∈ E(α, s, s ). Then it holds:

1. If ε 1 ≈ ε 2 then ε 1 + ε 2 ∈ E(α, s) 2.
There is at least one e + , e -, i

+ , i -∈ E(α, s, s ) such that e + ∪ i + = s \ s and e -∪ i -= s \ s Proposition 15. NNFAT F is translatable into NNFAT in polynomial time.
Proof. Let α be a NNFAT F action description with scope P . The translation f (α) is obtained by replacing each node F X (β) (with X ⊆ P ) of the circuit of α by β ∧ p∈X (p ↔ p ) ∨ Expl(β, p) and keeping the other nodes.

The circuit of Expl(β, p) can be computed in polynomial time (in each step we create a bounded amount of edges and nodes). Thus f (α) can be computed in polynomial time, too. Now we show that f (α) describes the same action as α.

Suppose that f (β) ≡ β and (s, s and(s, s ) |= Expl(β, p) for all p ∈ X. Then by lemmas 13 and 14 for every p ∈ (s ∆s) ∩ X there exists an effect e + β,p , e - β,p , i + β,p , i - β,p with p ∈ e + β,p ∪ e - β,p which mentions only variables from s∆s and by lemma 14 the sum e + , e -, i + , i -of these effects is as well in E(β, s, s ) and (s∆s ) ∩ X ⊆ e + ∪ e -and thus e + , e -, i + , i -∈ E(α, s). This implies s ∈ (F X (β))(s). Conversely, if s ∈ (F X (β))(s) then there exists an effect e + , e -, i + , i -of β in s witnessing this with (s∆s )∩X ⊆ e + ∪e -. Therefore, by Lemma 13 all Expl(β, p) with p ∈ (s∆s )∩X from the definition of f (α) are satisfied by (s, s ), and for the rest the expression p ↔ p is satisfied. And β is satisfied by the inductive assumption. For α = α 1 ∧ α 2 or α = α 1 ∨ α 2 we trivially have that f (α) describes the same action as α if the claim was proven for α 1 and α 2 .

) |= f (α) = β ∧ p∈X (p ↔ p ) ∨ Expl(β, p) . Then s ∈ β(s),
We now turn to studying the complexity of queries to expressions. We concentrate on two natural queries for planning: checking the existence of a transition, and deciding applicability of an action in a state. These queries arguably are at the basis of most other reasonable queries. Let L, I be a fixed action language, and let α denote an expression in L, P ⊆ P denote a set of variables such that I(α, P ) is defined, and s, s denote two P -states.

Definition 16. The decision problem SUCC takes as input α, P, s, s , and asks whether s ∈ α(s).

Definition 17. The decision problem APPLIC takes as input α, P, s, and asks whether α(s) = ∅.

SUCC for NNFAT amounts to model-checking of an NNF formula, and for NNFAT F the complexity follows from Proposition 15.

Proposition 18. SUCC is in P for NNFAT and NNFAT F .

To prepare further results we introduce a notation. Notation 19. Let n ∈ N and X n = {x 1 , . . . , x n } be a set of variables. Observe that there are a cubic number N n of clauses of length 3 over X n . We fix an arbitrary enumeration γ 1 , γ 2 , . . . , γ Nn of all these clauses, and we define P n ⊂ P to be the set of state variables {p 1 , p 2 , . . . , p Nn }.

Write

∈ γ i if the literal occurs in the clause γ i . Then to any 3-CNF formula ϕ we associate the P n -state s(ϕ) = {p i | i ∈ {1, . . . , N n }, γ i ∈ ϕ}, and dually, to any P n -state s, we associate the 3-CNF formula over X n , written ϕ(s), which contains exactly those clauses γ i for which p i ∈ s holds.We set ψ n := Nn i=1 (¬p i ∨ ∈γi ). In words, ψ n is satisfied by an assignment t to P n ∪ {x 1 , . . . , x n } if and only if the 3-CNF over {x 1 , . . . , x n } encoded by t ∩ P n , is satisfied by the assignment to {x 1 , . . . , x n } encoded by t ∩ {x 1 , . . . , x n }.

Example 20. Consider an enumeration of all clauses over X 2 = {x 1 , x 2 } which starts with γ

1 = (x 1 ∨x 1 ∨x 2 ), γ 2 = (x 1 ∨x 1 ∨¬x 2 ), γ 3 = (x 1 ∨¬x 1 ∨x 2 ), . . . Then ϕ = (x 1 ∨ x 1 ∨ x 2 ) ∧ (x 1 ∨ ¬x 1 ∨ x 2 ) is encoded by s(ϕ) = {p 1 , p 3 }. Proposition 21. SUCC is coNP-complete for NNFAT rC .
Proof. For a formula ψ over the variables {q i | j ∈ J}, write ψ for the formula obtained by replacing all variables q j by q j . Consider the (polynomial-sized) NNFAT rC action description with scope P n := X n ∪ {p 1 , . . . , p Nn } as in Notation 19:

α n := C Pn,∅,∅ ψ n ∨ 1≤i≤Nn p i
Let ϕ be a 3-CNF over X n which is not satisfied by the assignment "∀i : x i = ". We claim that ϕ is unsatisfiable if and only if s(ϕ)∪X n is an α n -successor of s(ϕ). Indeed, if ϕ is satisfiable then by assumption a satisfying assignment (t X n ) contains at least one variable set to ⊥. Then by definition of C Pn,∅,∅ the state s(ϕ) ∪ X n can't be a successor of s(ϕ) because s(ϕ) ∪ t changes fewer variables from P n . Conversely, if s(ϕ) ∪ X n is an α n -successor of s(ϕ) then the only subset t ⊆ X n with t ∪ s(ϕ) ∈ α n (s(ϕ)) is t = X n , which is by a assumption not a satisfying assignment. Therefore SUCC is coNP-hard. For membership: s / ∈ C X,V,F (α)(s) can be justified in polynomial time by either showing that s / ∈ α(s) or that there exists s ∈ α(s) with (s ∆s) ∩ X (s ∆s) ∩ X and s ∩ F = s ∩ F (both justifications can be checked in polynomial time since α is in NNFAT).

Proposition 22. SUCC is PSPACE-complete for NNFAT C .

Proof. We modify Notation 19 by introducing for every variable x j two variables q j , r j and write q j ∈ γ i if x j ∈ γ i , and r j ∈ γ i if ¬x j ∈ γ i . We set Q n := {q j , r j | 1 ≤ j ≤ n}. S n := Q n ∪ {p 1 , . . . , p Nn }. We obtain β n n+1 by replacing all x j in ψ n by q j and all ¬x j by r j and then define recursively

β n i := C {qi,ri},∅,Sn\{qi,ri} (q i ∧r i )∨(q i ∧β n i+1 )∨(r i ∧β n i+1
) Let Φ := ∀x 1 : ∃x 2 : . . . : ∀x n : ϕ, which is equivalent to ∀x 1 : ¬(∀x 2 : ¬(. . . ¬(∀x n : ϕ) . . .), be a quantified Boolean formula with a 3-CNF ϕ. Deciding the validity of such formulas is obviously PSPACE-complete. We claim that Φ is true if and only if s(ϕ) ∪ Q n ∈ β n 1 (s(ϕ)). Indeed, first observe that for all i and all states s ⊆ S n \ {q i , r i }, t ⊆ {p 1 , . . . , p Nn }: s ∪ {q i , r i } ∈ β n i (t) ⇔ s ∪ {q i }, s∪{r i } / ∈ β n i+1 (t). We set V i := {q j , r j | i ≤ j ≤ n} and W i := {q i , r i } and it follows with t := s(ϕ)

s(ϕ) ∪ Q n ∈ β n 1 (s(ϕ)) ⇔s(ϕ) ∪ V 2 ∪ {q 1 }, s(ϕ) ∪ V 2 ∪ {r 1 } / ∈ β n 2 (s(ϕ)) ⇔∀z 1 ∈ W 1 : ¬(s(ϕ) ∪ V 2 ∪ {z 1 } ∈ β n 2 (s(ϕ))) . . . ⇔∀z 1 ∈ W 1 : ¬ ∀z 2 ∈ W 2 : ¬(∀z 3 ∈ W 3 : ¬ . . . (s(ϕ) ∪ {z 1 , . . . , z n } ∈ β n n+1 (s(ϕ)))) s(ϕ) ∪ {z 1 , . . . , z n } ∈ β n n+1 (s(ϕ))
in the last line is equivalent to ϕ being true under the assignment defined by x i := (z i = q i ). We have proven the claim and thus PSPACEhardness of SUCC. For membership: SUCC can be reduced to deciding the truth of a fully quantified boolean formula

(because s ∈ C X,V,F (α)(s) ⇔ ∀s : ((s ∆s) ∩ X (s ∆s) ∩ X ∧ s ∩ F = s ∩ F ⇒ s / ∈ α(s))).
Proposition 23. APPLIC is NP-complete for NNFAT, Σ p 2 -complete for NNFAT rC and PSPACE-complete for NNFAT C .

Proof. Satisfiability of a 3-CNF ϕ can be reduced to applicability in NNFAT by replacing each x by x and checking whether the obtained action description describes an action which is applicable in s = ∅.

For Σ p 2 -hardness in NNFAT rC : let x = (x 1 , . . . , x n ), ȳ = (y 1 , . . . , y m ), X n = {x 1 , . . . , x n }, Y m = {y 1 , . . . , y m }. A quantified boolean formula ∃ȳ∀xϕ(x, ȳ) is true if and only if the S := {q} ∪ X n ∪ Y m action C Xn∪{q},∅,Ym ((¬q ∧ ¬ϕ(x , ȳ )) ∨ q ) ∧ q is applicable in ∅, because it is applicable only if q can be set to true meaning that ¬ϕ(x , ȳ ) is unsatisfiable by any assignment to x . For membership: if we have an oracle for SUCC then we can justify applicability in polynomial time by giving a successor and checking successorship with the oracle. For PSPACE-hardness in NNFAT C : s ∈ α(s) if and only if α ∧ p∈s p ∧ p / ∈s ¬p is applicable in s. For membership: to check for applicability of α in s we need to check for all s whether s ∈ α(s).

Succinctness

Recall that all languages are fully expressive, so we use the following definition [START_REF] Darwiche | A knowledge compilation map[END_REF].

Definition 24. A language L 1 is at least as succinct as L 2 if there exists a polynomial-size translation from L 2 into L 1 .

Our separation results rely on yet unproven assumptions on nonuniform complexity classes. Recall that P/poly (resp. coNP/poly) is the class of all decision problems such that for all n ∈ N, there is a polytime algorithm (resp. a nondeterministic polytime algorithm for the complement) which decides the problem for all inputs of size n [START_REF] Arora | Computational complexity: a modern approach[END_REF]. The assumptions coNP ⊆ P/poly and PSPACE ⊆ coNP/poly which we use are standard ones; in particular, coNP ⊆ P/poly would imply a collapse of the polynomial hierarchy at the second level (Karp-Lipton theorem), and PSPACE ⊆ coNP/poly would imply a collapse at the third level [START_REF] Chee | Some consequences of non-uniform conditions on uniform classes[END_REF]. We first observe that since NNFAT is translatable into NNFAT F via the identity function, and NNFAT F is a superlanguage of NNFAT, so they are equally succinct.

Proposition 25. If coNP ⊆ P/poly then NNFAT rC is strictly more succinct than NNFAT.

Proof. Recall from the proof of proposition 21 that s(ϕ) ∪ X n is an α n -successor of s(ϕ) if and only if ϕ (assumed not to be satisfied by assigning to all variables) is unsatisfiable, and that α n depends only on the number n of variables in ϕ (not on ϕ itself). Now suppose that there exists a poly-size translation f from NNFAT rC into NNFAT. Then we can check whether ϕ is unsatisfiable by checking if it is not satisfied by the all-assignment, and whether s(ϕ) ∪ X n is an f (α n )-successor of s(ϕ). This gives a nonuniform polytime algorithm (Proposition 18) for nonsatisfiability, which is a coNP-complete problem.

The next proposition says that nesting of C X,V,F operators contributes to succinctness. We omit the proof since it is very similar to that of Proposition 25 (using Proposition 22).

Proposition 26. If PSPACE ⊆ coNP/poly then NNFAT rC is strictly less succinct than NNFAT C .

Conclusion

We studied extensions of NNF action theories with operators expressing two different types of persistency of variables, with the goal of enriching the language. We gave a picture of the resulting languages à la knowledge compilation map. It turns out that using a frame operator resembling that of PDDL at any level of nesting does not change time nor space complexity; hence this operator can be used when specifying actions, then compiled away efficiently so as to use algorithms designed for (standard) NNF action theories. The languages resulting for our second operator (related to the interpretation of formulas under circumscription) are more succinct but also have a greater complexity for basic queries. Our results raise new open knowledge compilation-related questions. For example, we are interested in comparing these new languages to already well-known languages like variants of PDDL or DL-PPA [START_REF] Herzig | Dynamic logic of parallel propositional assignments and its applications to planning[END_REF] in terms of succinctness. We are also interested in the complexity of queries other than studied here, e.g. whether all successors of a state via a given sequential plan satisfy some property. Our long-term goal is to study action description languages as defined by allowed operators or constructs, so as to get a complete picture.

Example 7 .

 7 Let P = {p 1 , . . . , p 5 }, X = {p 1 , p 2 }, V = {p 3 }, and F = {p 4 , p 5 }. Let α = (p 1 ∨p 3 )∧(p 2 ∨p 4 )∧(p 5 ) and s = ∅. Then {p 1 , p 2 , p 5 } is an α-successor, but not a C X,V,F (α)-successor, of s, because s = {p 2 , p 3 , p 5 } is also an α-successor of s with s ∩ F = {p 5 } = s ∩ F and (s ∆s) ∩ X = {p 2 } ⊂ {p 1 , p 2 } = (s ∆s) ∩ X. On the other hand, s is a C X,V,F (α)-successor of s even though s = {p 3 , p 4 , p 5 } changes fewer values over X, since s and s differ over F and hence are incomparable with each other.

As mnemonics, variables in V may vary; those in F are fixed.

E.g., knowing only that they are not aligned which each other.

Acknowledgements

This work has been supported by the French National Research Agency (ANR) through project PING/ACK (ANR-18-CE40-0011).