SDAMS: SPOrt Data Archiving and Management System

SDAMS is the ensemble of database + software packages aimed to the archiving, quick-look analysis, off-line analysis, network accessibility and plotting of the SPOrt produced data. Many of the aspects related to data archiving, analysis and distribution are common to almost all the astronomical experiments. SDAMS ambition is to face and solve problems like accessibility and portability of the data on any hardware/software platform in a way as simpler as possible, though effective. The system is conceived in a way to be used either by the scientific community interested in background radiation studies or by a wider public with low or null knowledge of the subject. The user authentication system allows us to apply different levels of access, analysis and data retrieving. SDAMS will be accessible through any Web browser though the most efficient way to use it is by writing simple programs. Graphics and images useful for outreach purposes will be produced and put on the Web on a regular basis.

INTRODUCTION
SPOrt ( [1]) on ISS is an experiment which will produce a limited amount of data with respect to other space experiments. The foreseen total (i.e. housekeepings and scientific data) bit rate is ∼ 2.5 kbit s −1 . This means that in 3 years of operation time it will collect ∼ 30 Gbytes of data. In addition SPOrt has not pointing capabilities and it is expected to work in a stable and semi-automatic way. As a consequence the output data stream will be simply identified by time and orbital parameters of the Space Station. The data management system (i.e. quick look, archive and scientific analysis) can be build to be both simple and highly automatic.
The SDAMS system has two fundamental parts: database server and application server. The former performs the data storing and allows a simple (low level) fast access to them. To this aim we chose MySQL TM , a very easy to use data management system capable to deal with a relatively large amount of data. On the Web there are several examples of intensive usage of MySQL with application tools and there are extensions to use it within several programming languages (e.g. PHP). It has also the advantage to be an Open Source package, that means one can modify the source code to match any particular need and no license is required to use it. This is crucial to allow a standard (system) to be developed.
The SDAMS application server is a multithreaded server which uses a simple C-written communication protocol to interact with its clients. A task-oriented module library allows us to easily add further capabilities to those so far foreseen. The fundamental task of this component is to accept client connections (through socket) and invoke the appropriate modules to perform the required tasks.

HOW TO USE IT
There are several ways to use SDAMS, the simplest being through a Web interface. Such kind of interface allows users to setup a simple query in order to request data retrieval and visualization. This is done, for example, selecting a time or sky coordinates range. It will also be possible to view the sky portion seen by SPOrt (pointing at the zenith of the ISS) in any given time interval. In addition to Sun, Moon and some Planets, also "interesting" strong radio sources will be highlighted in the sky maps. Access to the data will be granted only to registered users. However, this is the less flexible way to use SDAMS as it only offers a limited set of choices; it will be likely used to perform data "quick-look" or by users not directly involved in the SPOrt project or by the general public. The communication protocol is so easy that it is possible to connect to SDAMS through a telnet session and typing in the commands. The output will be ASCII formatted. The most flexible way to access SDAMS is instead through a dedicated, user written (in any language) program. The only requirements are • capability to open TCP/IP sockets, • capability to read ASCII and binary files.
In this case the output can be formatted as a FITS binary (or ASCII) table. For these "high-level" users, a reference manual will be available reporting characteristics of the protocol and a full description of commands and message codes. Once again we note how SDAMS does not put any restriction to the hardware/software platform of the client. Figures 1 and 2 show how SDAMS works: for each client successfully connected to the socket a new thread is created; it is a sort of sub-process running on the server. It waits for queries from the client and executes them independently of what the other clients are doing. To each query, written by using high level commands, corresponds a spawned process which passes a reformatted low-level query to the database server. The output data are processed either by C or IDL TM routines (depending on the request) and then sent to the client in the requested format. This process is repeated until a "disconnect" request is received. The "language" used by the client to put its query is very simple, being an ASCII string containing the name of the procedure to use and its parameters. For example, to select the data for the Stokes parameter Q in the time interval (MJD) 52810-52813, in the 32 GHz frequency channel, averaged over 30 s, and perform a polynomial fit (third order) with automatic graphical output, the command is: sel, par='q', dt=[52810.0,52813.0], fr=32, av=30, fit='poly 3'

HOW IT WORKS
By default the graphics goes into a PostScript file, but other formats can be chosen.
It is worth to note how, in spite the application server talks to the database server using the SQL (Structured Query Language) syntax, it is not necessary to write the queries using this low-level format (but can be done starting the query with SQL). A dedicated module, the SQL wrapper, takes care of translating the input command string (after a validity check). When the client queries require complex operations (e.g. correlation analysis or sky-map production), the application server first extracts the data into a local directory then the appropriate (IDL) routine (one or more) is invoked for the analysis and finally the output is sent to the client (e.g. in FITS format). The clients do not need an IDL license as the application software only runs on the server. Figure 3 shows an example of sky coverage map extracted using the command "map, /coverage". It assumes only about 20 days are elapsed since the start of the mission. Adding a new feature to the system is extremely easy: it is enough to add the IDL routine (accessing the data using the SDAMS standards) to the library and adding its name to the list of allowed commands.


extfieldsofstudy: Physics Medicine

text:
Exact results for the reactivity of a single-file system

We derive analytical expressions for the reactivity of a Single-File System with fast diffusion and adsorption and desorption at one end. If the conversion reaction is fast, then the reactivity depends only very weakly on the system size, and the conversion is about 100%. If the reaction is slow, then the reactivity becomes proportional to the system size, the loading, and the reaction rate constant. If the system size increases the reactivity goes to the geometric mean of the reaction rate constant and the rate of adsorption and desorption. For large systems the number of nonconverted particles decreases exponentially with distance from the adsorption/desorption end.

We derive analytical expressions for the reactivity of a Single-File System with fast diffusion and adsorption and desorption at one end. If the conversion reaction is fast, then the reactivity depends only very weakly on the system size, and the conversion is about 100%. If the reaction is slow, then the reactivity becomes proportional to the system size, the loading, and the reaction rate constant. If the system size increases the reactivity goes to the geometric mean of the reaction rate constant and the rate of adsorption and desorption. For large systems the number of nonconverted particles decreases exponentially with distance from the adsorption/desorption end.  [1] They have one-dimensional pores through which molecules can diffuse, but with cross sections that are too small to allow passing. As for many other 1D systems, this leads to very interesting kinetic effects. [2] Research on SFS zeolites has focussed on the diffusion, because the mean-square displacement in a SFS is proportional to the square root of time, and not proportional to time. [3,4,5] Molecular Dynamics, [3,6,7] Dynamic Monte Carlo (DMC), [8,9,10] and reaction-diffusion equations [11] have mainly been used. Few studies have included reactions. [10,12,13] We have argued that this is unfortunate, because if diffusion is fast the temporal dependence of the mean-square displacement is not very relevant, but there are still effects from the non-passing of the particles in the pores.
In a previous paper we have investigated steady-state properties of a SFS for different assumptions of the reactive site distribution using DMC as well as analytical techniques. [10] In the current paper we derive exact results for the case that the entire pore is reactive. These results give detailed insight in the relationships of the various system parameters and the reactivity.
Our model consists of S sites forming a onedimensional finite chain. Each site is numbered consecutively from 1 for the site on one end, to S for the site on the other end. Each site is vacant or is occupied by a particle. We have two types of particles: A and B. An A can be converted into a B on any site. Adsorption and desorption of particles can only occur on site 1. Only A's are adsorbed, but both A's and B's desorb. Both types of particle diffuse by making random hops to neighboring sites if vacant.
The evolution of the system is described by a master equation [14,15] where α and β refer to the configuration of the adlayer (a particular distribution of particle over the sites), the P 's are the probabilities of the configurations, t is real time, and the W 's are constants that give the rates with which reactions change the occupations of the sites. W αβ corresponds to the reaction that changes β into α. The rate constants in our model are W ads for adsorption of an A onto site 1 if vacant, W des for desorption of a particle from site 1, W rx for the conversion of an A into a B on any site, and W diff for a hop of a particle to a vacant neighboring site. If the diffusion is infinitely fast, we can derive a simpler master equation for the number of particles in the system.
where P N is the probability that there are N particles in the system. This is a master equation of a one-step Markov process. [15] We are interested in the probability distribution f MK (t) that if at time t = 0 the number of particles is K, this number becomes M for the first time at time t with M < K. If there are N particles in the system and at time t = 0 a particle adsorbs, then f N,N +1 is the probability distribution for the time that this particle desorbs. This is based on the property of a SFS that particles can not pass each other. So f N,N +1 is the probability distribution for the residence time of a particle that adsorbs in a system with N particles.
Let P N K be the solution of Eq. (2) with N the number of particles and the initial condition P N K (0) = δ N K . Let Q N K also be a solution with Q N K (0) = δ N K , but now for the master equation with an adsorbing boundary at M : i.e., we remove the term in Eq. (2) that corresponds to an adsorption then there are M particles in the system. With N ≥ M we have This equation is called the renewal equation. [15] If we take N = M in the renewal equation, then we have Q MK (t) = 0 by definition. So we get the integral equation for f MK . A particle that adsorbs, stays in the system for a period t, and then desorbs, has a probability exp(−W rx t) that it is not converted during the time it was in the system. Because the probability distribution for the time that it stayed in the system is given by f N,N +1 (t), the probability that the particle desorbs without being converted is The reason for using this Laplace transform is that is that it is related to the Laplace transform of the solution of the master equation through the renewal equation. Laplace transforming Eq. (4) yieldŝ If we write the master equation (2) in matrix-vector notation asṖ = WP , and Laplace transform it we get With the initial condition for P MK this yieldŝ so thatf We define the reactivity B prod as the number of particles that is being converted per unit time. To get B prod we have to multiply the probability that a particle is converted by the rate of adsorption and make a weighted average over the number of particles in the system. The probability that a particle is converted equals 1−f N,N +1 (W rx ), and the rate of adsorption equals W ads (1 − N/S). At steady state the number of particles in the system is given by [10] Combining this results in  Figure 1 shows this reactivity for two finite system sizes and three loadings. The loading θ is defined as the probability that a site is occupied at steady state. It's equal to [10] The reactivity is compared to the (average) rate of adsorption and desorption λ, which at steady state is given by If the rates of adsorption and desorption are small compared to the reaction rate constant W rx , then B prod → λ. This means that almost every particle that enters the system is converted. If the rates of adsorption and desorption are much larger, then for λ/W rx → ∞ and S not too large. Figure 1 shows the θ dependence for small S and the S dependence for small θ. It does not show this S and θ dependence for S and θ both large. λ needs to be much larger than the values in the figure for that. For S = 100 we see that the reactivity may be proportional to θ for θ ≤ 0.5, but not around θ = 0.9. For the latter value the reactivity is even smaller than for θ = 0.5. In practice only W ads can usually be varied independently, either through the pressure or the concentration of A's outside the system. The limit W ads → ∞ corresponds to θ = 1 and λ = W des . So we see that there generally is an upper bound on λ.
Comparing S = 5 and S = 100 in Fig. 1 for some finite λ shows that B prod varies less with θ for larger S. We can show that in the limit S → ∞ the reactivity depends only on λ and W rx . If the system becomes infinitely large, then the fluctuations become small with respect to the number of sites. If the system is then at steady state we can write the master equation as Formally we can let the number of particles N run from −∞ to +∞. The matrix s − W can easily be diagonalized. The eigenvalues are s + 2λ(1 − cos k) with −π < k ≤ π, and the corresponding eigenvector has components exp [ikN ]. We can use this to calculate elements of the inverse of the matrix s − W. with This then yields for the probability that a particle adsorbs and desorbs at a later time without being converted the expressionf (Here and in the rest of the paper we set s = W rx in the definition of y.) For the reactivity B prod we have We see that the reactivity no longer depends on the loading θ if the system becomes large, but only on the reaction rate and on λ. For small rates of adsorption and desorption we again find B prod → λ. If the rates of adsorption and desorption are large, then for λ/W rx → ∞. The approach to the limit S → ∞ becomes very slow when λ is large as can be seen in Fig. 1.
The procedure for the first-passage problem above can also be used to derive the A and B profiles: i.e., the distribution of the A's and B's in the chain. We will first deal with the question what the probability is that the nth particle, counting from site 1, is an A. Then we will answer the question that site m is occupied by an A. The answers to the same questions about B's follow trivially from the ones for the A's.
We are only interested in the steady state. In this case we have detailed balance: i.e., the number of transitions per unit time from N to N + 1 particles is equal to those of N + 1 to N . This means that for each sequence in the number of particles where after a time lapse ∆t i the number of particles changes from N i to N i+1 , there is another sequence The second sequence is the time reversed of the first one. Moreover, both sequences are equally likely because of the detailed balance. Consequently, the probability distribution that the number of particles in the system is K at time t = 0 and M with M < K at time −t for the last time equals f MK (t). This means that if there are N particles in the system the probability distribution that particle n is in the system for a time t equals f N −n,N (t). The probability that that particle has not been converted is thenf N −n,N (W rx ) following the reasoning after Eq. (5). This probability can be calculated using Eq. (9). For the profile we need the probability that site m is occupied by particle n. This probability is given by The probability A m that site m is occupied by a particle that has not been converted is then given by where the first summation averages over the number of particles in the system and P for the probability that particle n has not been converted. We see that this probability decreases exponentially.
The probability P occ (n, N ; m, S) becomes P occ (n, m; θ) with θ = N/S for S → ∞. This limit of the combinatorial factors yields The probabilities An that a site is occupied by a non-converted particle as a function of site index n for rate of adsorption and desorption λ = 16, loading θ = 0.2, and various system sizes S.

Substituting this expression and (25) in (24) yields
Again we find an exponential decrease but now with a characteristic length of ∆ = 1/[ln(y + 1) − ln(y + 1 − 2θ)]. For high loadings (θ → 1) we find ∆ ≈ y/2. For low loading (θ → 0) we get ∆ ≈ (y + 1)/(2θ). So the characteristic length is larger for low loadings and higher rate of adsorption and desorption. Figure 2 shows some typical profiles. The straight line corresponds to the exponential decrease of Eq. (27). The result for finite system sizes can be understood from the fact that smaller systems are less reactive because there are fewer sites at which conversion can take place. As the reactivity must be equal to the number of desorbing converted particles, W des B 1 must be smaller for smaller S, and because B 1 = θ − A 1 the curves in Fig. 2 must start out at larger values of A 1 . The reactivity also equals W rx S n=1 A n . This means that S n=1 A n must be smaller for smaller S. Because A 1 is larger for smaller S, A n must decrease faster. Figure 2 confirms the slow convergence of the system to the limit S → ∞. At S = 100 the values of A n drop down to 2 · 10 −5 . At such low value one would not expect an influence of these sites on the kinetics, but one clearly sees differences between S = 100 and S → ∞ for all sites.
We would finally like to comment on three extensions of our model: adsorption and desorption at both ends, finite diffusion, and other reactions. A system with 2S sites and adsorption and desorption at both ends has a reactivity that is twice the one of a system with S sites and adsorption and desorption at just one end provided that S ≫ ∆. DMC simulation show that if S is near or smaller than ∆, then the system open at both ends is relatively more reactive.
Finite diffusion is expected to be equivalent to infinite diffusion as long as it is much faster than the other reactions. If this is not the case, then it may become a rate determining step. The system then becomes transport limited. As a consequence the reactivity can only go down. We have seen that in our simulations. [10] We expect that our results will change only little when we change the details of the reaction or when interaction between the particles are included. [16] Our results are a consequence of the non-passing of the particles and of the fact that particles that stay longer in the system have a higher probability of being converted. We therefore also do not expect our results to change when we change our model of discrete sites to some continuous model.


extfieldsofstudy: Physics Biology Mathematics Medicine

s2fieldsofstudy:
Computer Science
Mathematics

text:
Correlated random networks

We develop a statistical theory of networks. A network is a set of vertices and links given by its adjacency matrix $\c$, and the relevant statistical ensembles are defined in terms of a partition function $Z=\sum_{\c} \exp {[}-\beta \H(\c) {]}$. The simplest cases are uncorrelated random networks such as the well-known Erd\"os-R\'eny graphs. Here we study more general interactions $\H(\c)$ which lead to {\em correlations}, for example, between the connectivities of adjacent vertices. In particular, such correlations occur in {\em optimized} networks described by partition functions in the limit $\beta \to \infty$. They are argued to be a crucial signature of evolutionary design in biological networks.

Networks describe structures as diverse as the interaction links between proteins in a cell, the wiring of the brain, or the connections of the internet. Recent theoretical work [1,2] has focused on communication networks, and a wealth of quantitative data is now becoming available on networks in molecular biology. Examples include control networks in gene transcription [3], the interaction map of proteins [4], and the pathways of cell metabolism [5]. All these systems consist of many different kinds of molecules linked by complex interactions. Network models are a simplified description, which neglects quantitative aspects of these interactions and focuses solely on their pathways.
A network is a set of vertices i = 1, . . . , N connected by links. It is uniquely defined by the adjacency matrix c, whose entries are c ij = 1 if there is a link from i to j and c ij = 0 otherwise. We consider here networks with undirected links, where c is symmetric. The connectivity or degree of a vertex is then defined as the total number of links connected to it, k i ≡ j c ij . The distance d ij between two vertices i and j is the number of links along the shortest path connecting them [6]. We assume the vertices are labeled (for example, by their biochemical identity), so that the correspondence between adjacency matrix c and its graph is one-to-one [7].
Networks with an irregular wiring naturally lend themselves to a statistical description [6]. We discuss here the equilibrium statistics of networks. The partition function Z can be defined as a sum over all graphs with a fixed number N of vertices and a fixed number Averages over this ensemble are denoted by . . . . Alternatively one can define Z with an arbitrary number of links adjusted by a suitable chemical potential. The ensembles of relevance here have a finite average connectivity κ ≡ 2M/N . For fixed κ, the distribution of connectivities, becomes asymptotically independent of N , implying that typical adjacency matrices c become sparse for large N . This is the case of interest for applications. A satisfactory mathematical theory exists to date only for what we call uncorrelated random networks [8,9]. In this case, the Hamiltonian depends only on single-point connectivities, leading to p(k) ∼ exp[−βf (k)−µk]/k! where the constant of proportionality is fixed by normalization and µ is adjusted to give the correct average connectivity. Since all graphs with the same connectivities k 1 , . . . , k N have the same statistical weight, this ensemble ensures the maximally random wiring compatible with the distribution p(k). The simplest example is the well-known Erdös-Rény graphs, where βH = 0 and p(k) is a Poissonian. Many natural networks are, however, not of this type. The simplest kind of correlations occur if the joint distribution of connectivities for neighboring vertices, differs from its form for uncorrelated random networks, q 0 (k, k ′ ) = (kk ′ /κ 2 )p(k)p(k ′ ). Higher correlations can be defined in a similar way [10]. Connectivity correlations have been found in growth models of communication networks [11,12] as well as in data of genetic and protein networks [13,14].
These observations call for a statistical theory of more general ensembles called correlated random networks, which is the subject of this Letter. The ensembles of interest are characterized by finite distributions p(k) and q(k, k ′ ) in the limit of large N . One then expects a universal logarithmic scaling of the average distance d ij between vertices, i,j d ij /N 2 Ω ∼ log N Ω , in any connected component Ω with N Ω nodes [15]. This is consistent with our numerical findings. Hence, correlated random networks maintain a sparse connectivity matrix and are locally tree-like. The 'inverse temperature' β in (1) measures the deviation from Erdös-Rény graphs. Quite remarkably, these structural properties are preserved in the limit β → ∞, where we obtain nontrivial optimized networks. Ensembles of this kind generically have strong correlations.
The simplest type of Hamiltonian producing correlations has nearest-neighbor connectivity interactions, where g(k, k ′ ) is some function of the connectivities. The resulting class of graph ensembles can be seen as a showcase for correlated random networks where analytic expressions can be derived. Higher order correlations are generated by Hamiltonians with next-nearest neighbor interactions etc. We also study a Hamiltonian often called the diameter of the graph. For λ > 0 and a suitable scaling λ ∼ 1/(N log N ), this Hamiltonian is found to generate compactified networks with finite p(k) and q(k, k ′ ), provided the extra term H 1 stabilizes the network against collapse to a star. Compactified networks occur in communication and transport [16], and may play a role in biology [17,18]. For example, distance-optimized networks obtained from (6) show an abundance of high-connectivity vertices (hubs) which are preferentially connected to peripheral vertices of low connectivity. A very similar structure (with even more pronounced hubs) can also be obtained from local interactions of the form (5). Typical graphs are shown in Fig 1. To establish these results, we first discuss the analytical treatment of local interactions, choosing a generic Hamiltonian of the form H = H 1 + H 2 given by (3) and (5). From the partition function (1), the free energy is derived by using an integral representation for the constraints due to the connectivity k i at each vertex and making a Hubbard-Stratonovich transformation. The resulting integral can be evaluated in a saddle-point approximation, yielding the reduced free energy per vertex in the thermodynamic limit, The 'order parameters' Q k and the chemical potential µ have to be determined self-consistently from the saddlepoint condition. This form is closely related to a fieldtheoretic approach [9,19,20], where networks appear as the Feynman diagrams of a Gaussian integral with a propagator matrix G kk ′ = exp[−βg(k, k ′ )] − 1 and interactions as specified by the last term in (7). Notice the super-extensive scaling of the entropy, (κ/2) log N , which reflects that unlike in a regular lattice, each vertex can be connected to all N − 1 other vertices. The last term in (7) is directly related to the degree distribution, where C is a normalization constant. For example, a power-law tail in p(k) may be generated by a suitable choice of the weights f (k) but it is not generic. A more detailed account of networks with generic local interactions will be published elsewhere [21]. Here we turn to the simplest Hamiltonian with local interactions producing nontrivial optimized networks, see Fig. 1. It has the form H L = H 1 + H 2 with H 1 (c) = −(1/2) i k 2 i + η i k 3 i and H 2 (c) = ζ i<j δ ki,1 c ij δ kj ,1 . The first term (1/2) i k 2 i = (1/2) ijk c ik c kj gives the number of paths of length two on the graph. It rewards the formation of hubs, i.e. highly connected vertices, which in turn lead to short distances. In fact this term has the maximally compact, starlike configuration as its ground state. The collapse to a star, where the connectivity of the central vertex scales with the size of the graph, however, is prevented by the regularization term η i k 3 i . The correlation term H 2 with ζ → ∞ suppresses single, isolated links connecting two vertices of connectivity 1. Without this term an extensive number of isolated links remains even in the limit β → ∞ leading to graphs with a large number of disconnected parts. A minimal connectivity of 1 of each vertex is enforced. For this Hamiltonian, the free energy (7) contains only one non-zero order parameter Q 1 given by p(1) = κ Q1 Q1−e −µ . The chemical potential µ is determined by k kp(k) = κ. Remarkably, the connectivity correlation can be obtained from H 2 and single-vertex quantities, The constant of proportionality is fixed by normalization and the t k are determined by the marginal distribution k ′ q(k, k ′ ) = kp(k)/κ, giving t 1 = κ/(T (κ − p(1))) and The properties of optimized networks resulting from the Hamiltonian H L are readily inferred from Eqs. (8) and (9). At finite values β one finds that the degree distribution (8) has an exponentially decaying tail. In order to analyze the limit β → ∞, we replace the sum over k in (7) by an integral. One finds that the vertices arrange themselves into hubs of connectivity (10) and peripheral vertices of connectivity 1. The peripheral vertices are connected only to hubs, while the hubs form an uncorrelated random network. A remarkably similar structure is found for compactified networks generated by the Hamiltonian with nonlocal interactions H = H 1 + λH d with H d given by (6) and H 1 = η i k 3 i . For λ > 0, the nonlocal part H d favors networks with short distances, while H 1 prevents the collapse to a star as before. Hence, by choosing λ = 2/(N log N ), one obtains a well-defined thermodynamic limit with the average distance between vertices scaling as log N . We have studied this ensemble, as well as the case of local interactions H L , by a Monte-Carlo link dynamics. Starting, for example, from an Erdös-Reny graph, randomly chosen links are moved to previously unlinked vertex pairs with probability p = min(1, exp[−β∆H]) where ∆H denotes the corresponding change in the Hamiltonian. The minimum degree of 1 is enforced throughout, self-links are excluded [7]. No dependence on the initial conditions has been found. For the local Hamiltonian we use a network with N = 200, κ = 2.4, η = 0.03, for the nonlocal Hamiltonian we use N = 100, κ = 2.4, η = 0.001. We averaged over 100 samples. Fig. 2 juxtaposes analytical and numerical results for local interactions on the left with numerical results for nonlocal interactions on the right. The connectivity distribution p(k) shows the formation of high-connectivity hubs in both cases. For local interactions the hub connectivity is given by (10), for non-local interaction the distribution remains broad even in the limit β → ∞ (Fig. 2(a)) [22]. Lowconnectivity vertices are preferentially attached to hubs as indicated by the peaks at q(1, k * ) for local interactions and the corresponding peaks of q(k, k ′ ) for nonlocal interactions (Fig. 2(b)). The deviation from uncorrelated random networks is measured by the relative entropy S(q|q 0 ) = k,k ′ q(k, k ′ ) log q(k,k ′ ) q0(k,k ′ ) . In a single network of size N , we obtain the estimate S(q|q 0 ) from the observed frequenciesq(k, k ′ ) andp(k), withq 0 (k, k ′ ) = (kk ′ /κ 2 )p(k)p(k ′ ). We then generate a sufficient number of uncorrelated random networks [24] with frequenciesq α (k, k ′ ) and sampling entropies S(q α |q 0 ); their average and standard deviation are denoted by S 0 (q 0 ) and ∆S 0 (q 0 ) respectively. Connectivity correlations in the original network are significant if S(q|q 0 ) − S 0 (q 0 ) ∆S 0 (q 0 ). This is typically the case above a certain optimization degree β on, as shown by the ensemble averages over 10 samples S(q|q 0 ) , S 0 (q 0 ) , and ∆S 0 (q 0 ) shown in figure 2c).
Both kinds of networks become more compactified with increasing β, as shown by the average inverse distance K ≡ (2/N (N − 1)) i<j d −1 ij (Fig. 2(d)) [23]. We also plot K for the equivalent uncorrelated random networks; no such compactification is seen. Hence, the one-point distribution p(k) may miss important functional properties. On the other hand, the nonlocally interacting networks and their equivalent locally interacting counterparts (constructed to have the same p(k) and q(k, k ′ )) have a very similar degree of compactification [24]. This illustrates how optimization induces correlations.
In summary, we have shown how interactions shape the structure of a network. Hamiltonians beyond the 'single-vertex' form (3) generate correlations such as a neighbor connectivity distribution q(k, k ′ ) which differs from that in uncorrelated networks. Higher correlations can be defined in a similar way [10]. These correlations provide a more detailed fingerprint of the interactions present than the single-point connectivity distribution p(k). This observation should carry over to the dynamical rules for non-equilibrium ensembles such as the wellknown growth models [1,11].
In transcription control networks, structural motifs have been identified that can be expressed in terms of connectivity correlations [13]. Such correlations have also been observed in protein networks [14]. In view of our findings for optimized networks, they appear to be a natural consequence of the underlying dynamics and functional optimization. We expect the data to give important information on the underlying design principles of networks and on the selective forces governing their evolution. Reverse engineering seems feasible, with the aim of inferring the relevant dynamics from the data. The nonequilibrium theory of correlated random networks will thus be an important avenue for future research.
k, l at random with uniform probability and rewire them as i, k and j, l. Repeating this procedure sufficiently many times leaves p(k) invariant but destroys all higher correlations. It has been used in ref. [14] for protein networks. Similarly, the equivalent locally correlated network is obtained by swapping only links with ki = k l and kj = k l , which leaves p(k) and q(k, k ′ ) invariant but destroys all higher correlations.


extfieldsofstudy:
Mathematics
Computer Science

text:
Approximate Data Structures with Applications

This paper explores the notion of approximate data structures, which return approximately correct answers to queries, but run faster than their exact counterparts. The paper describes approximate variants of the van Emde Boas data structure, which support the same dynamic operations as the standard van Emde Boas data structure (min, max, successor, predecessor, and existence queries, as well as insertion and deletion), except that answers to queries are approximate. The variants support all operations in constant time provided the performance guarantee is 1+1/polylog(n), and in O(loglogn) time provided the performance guarantee is 1+1/polynomial(n), for n elements in the data structure. Applications described include Prim's minimum-spanning-tree algorithm, Dijkstra's single-source shortest paths algorithm, and an on-line variant of Graham's convex hull algorithm. To obtain output which approximates the desired output with the performance guarantee tending to 1, Prim's algorithm requires only linear time, Dijkstra's algorithm requires O(mloglogn) time, and the on-line variant of Graham's algorithm requires constant amortized time per operation.

Introduction
The van Emde Boas data structure (veb) [28,20] represents an ordered multiset of integers. The data * AT&T Bell Laboratories, 600 Mountain Avenue, Murray Hill, NJ 07974. Email: matias@research.att.com. † Department of Computer Science, Duke University, Box 90129, Durham, N.C. 27708-0129. Part of this research was done while the author was at Brown University. This research was supported in part by National Science Foundation grant CCR-9007851 and by Army Research Office grant DAAL03-91-G-0035. Email: jsv@cs.duke.edu. ‡ Computer Science Department, Princeton University. Part of this research was done while the author was at UMIACS, University of Maryland, College Park, MD 20742 and was partially supported by NSF grants CCR-8906949 and CCR-9111348. Email: ney@cs.princeton.edu. structure supports query operations for the current minimum and maximum element, the predecessor and successor of a given element, and the element closest to a given number, as well as the operations of insertion and deletion. Each operation requires O(log log U ) time, where the elements are taken from a universe {0, ..., U }.
We give variants of the veb data structure that are faster than the original veb, but only guarantee approximately correct answers. The notion of approximation is the following: the operations are guaranteed to be consistent with the behavior of the corresponding exact data structure that operates on the elements after they are mapped by a fixed function f . For the multiplicatively approximate variant, the function f preserves the order of any two elements differing by at least a factor of some 1 + ǫ. For the additively approximate variant, the function f preserves the order of any two elements differing additively by at least some ∆.
Let the elements be taken from a universe [1, U ]. On an arithmetic ram with b-bit words, the times required per operation in our approximate data structures are as follows: Under the standard assumption that b = Ω(log U + log n), where n is the measure of input size, the time required is as follows: ǫ, ∆/U 1/ polylog(nU ) 1/ exp( polylog(n)) The space requirements of our data structures are O(log(U )/ǫ) and O(U/∆), respectively. The space can be reduced to close to linear in the number of elements by using dynamic hashing. Specifically, the space needed is O(|S| + |f (S)| · t), where S is the set of elements, f is the fixed function mapping the elements of S (hence, |f (S)| is the number of distinct elements under the mapping), and t is the time required per operation. The overhead incurred by using dynamic hashing is constant per memory access with high probability [6,5]. Thus, if the data structures are implemented to use nearly linear space, the times given per operation hold only with high probability.
1.1 Description of the data structure. The approach is simple to explain, and we illustrate it for the multiplicative variant with ǫ = 1 and b = 1 + ⌊log U ⌋. Let f (i) = ⌊log 2 i⌋ (the index of i's most significant bit). The mapping preserves the order of any two elements differing by more than a factor of two and effectively reduces the universe size to U ′ = 1 + ⌊log U ⌋. On an arithmetic ram with b-size words, a bit-vector for the mapped elements fits in a single word, so that successor and predecessor queries can be computed with a few bitwise and arithmetic operations. The only additional structures are a linked list of the elements and a dictionary mapping bit indices to list elements.
In general, each of the approximate problems with universe size U reduces to the exact problem with a smaller universe size U ′ : For the case of multiplicative approximation we have size and for the case of additive approximation Each reduction is effectively reversible, yielding an equivalence between each approximate problem and the exact problem with a smaller universe. The equivalence holds generally for any numeric data type whose semantics depend only on the ordering of the elements. The equivalence has an alternate interpretation: each approximate problem is equivalent to the exact problem on a machine with larger words. Thus, it precludes faster approximate variants that don't take advantage of fast operations on words.
For universe sizes bigger than the number of bits in a word, we apply the recursive divide-and-conquer approach from the original veb data structure. Each operation on a universe of size U ′ reduces to a single operation on a universe of size √ U ′ plus a few constant time operations. When the universe size is b, only a small constant number of arithmetic and bitwise operations are required. This gives a running time of O(log log b U ′ ), where U ′ is the effective universe size after applying the universe reduction from the approximate to the exact problem.
1.2 Outline. In the next section we motivate our development of approximate veb data structures by demonstrating how they can be used in three wellknown algorithms: Prim's algorithm for minimum spanning trees, Dijkstra's shortest paths algorithm, and an on-line version of the Graham scan for finding convex hulls. Related work is discussed in Section 3. Our model of computation is defined in Section 4. In Section 5, we show how to construct our approximate veb data structures and we analyze their characteristics. We make concluding remarks in Section 6.

Applications
We consider three prototypical applications: to minimum spanning trees, to single-source shortest paths, and to semi-dynamic on-line convex hulls. Our approximate minimum spanning tree algorithm runs in linear time and is arguably simpler and more practical than the two known linear-time MST algorithms. Our approximate single-source shortest paths algorithm is faster than any known algorithm on sparse graphs. Our on-line convex hull algorithm is also the fastest known in its class; previously known techniques require preprocessing and thus are not suitable for on-line or dynamic problems. The first two applications are obtained by substituting our data structures into standard, wellknown algorithms. The third is obtained by a straightforward adaptation of an existing algorithm to the online case. These examples are considered mainly as prototypical applications. In general, approximate data structures can be used in place of any exact counterpart.
Our results below assume a ram with a logarithmic word size as our model of computation, described in more detail in Section 4. The proofs are simple and are given in the full paper.

Minimum spanning trees.
For the minimum spanning tree problem, we show the following result about the performance of Prim's algorithm [16,25,7] when our approximate veb data structure is used to implement the priority queue: Theorem 2.1. Given a graph with edge weights in {0, .., U }, Prim's algorithm, when implemented with our approximate veb with multiplicative error (1 + ǫ), finds a (1 + ǫ)-approximate minimum spanning tree in an n-node, m-edge graph in O((n + m) log(1 + (log 1 ǫ )/ log log nU )) time.
For 1/ǫ ≤ polylog(nU ), Theorem 2.1 gives a lineartime algorithm. This algorithm is arguably simpler and more practical than the two known linear-time MST algorithms. This application is a prototypical example for which the use of an approximate data structure is equivalent to slightly perturbing the input. Approximate data structures can be "plugged in" to such algorithms without modifying the algorithm.
If log(1/ǫ) ≤ polylog(n) log log U , the algorithm runs in O((n + m) log log n) time -faster than any known algorithm on sparse graphs -and is simpler than theoretically competitive algorithms. This is a prototypical example of an algorithm for which the error increases by the multiplicative factor at each step. If such an algorithm runs in polynomial time, then O(log log n) time per veb operation can be obtained with insignificant net error. Again, this speed-up can be obtained with no adaptation of the original algorithm.
Analysis. The proof of Theorem 2.2 follows the proof of the exact shortest paths algorithm (see, e.g., [27,Thm 7.6]). The crux of the proof is an inductive claim, saying that any vertex w that becomes labeled during or after the scanning of a vertex v also satisfies dist(w) ≥ dist(v), where dist(w) is a so-called tentative distance from the source to w. When using a (1+ǫ)-approximate veb data structure to implement the priority queue, the inductive claim is replaced by where vertex v is the ith vertex to be scanned. Thus, the accumulated multiplicative error is bounded by We leave the details to the full paper, and only note that it is not difficult to devise an example where the error is actually accumulated exponentially at each iteration.
2.3 On-line convex hull. Finally, we consider the semi-dynamic on-line convex hull problem. In this problem, a set of planar points is processed in sequence.
After each point is processed, the convex hull of the points given so far must be computed. Queries of the form "is x in the current hull?" can also be given at any time. For the approximate version, the hull computed and the answers given must be consistent with a (1+∆)approximate hull, which is contained within the true convex hull such that the distance of any point on the true hull to the approximate hull is O(∆) times the diameter.
We show the following result about the Graham scan algorithm [12] when run using our approximate veb data structure: This represents the first constant-amortized-timeper-query approximation algorithm for the on-line problem. This example demonstrates the usefulness of approximate data structures for dynamic/on-line problems. Related approximate sorting techniques require preprocessing, which precludes their use for on-line problems.
Analysis. Graham's scan algorithm is based on scanning the points according to an order determined by their polar representation, relative to a point that is in the convex hull, and maintaining the convex hull via local corrections. We adapt Graham's scan to obtain our on-line algorithm, as sketched below. As an invariant, we have a set of points that are in the intermediate convex hull, stored in an approximate veb according to their angular coordinates. The universe is [0, 2π] with a ∆ additive error, which can be interpreted as the perturbation error of points in their angular coordinate, without changing their values in the distance coordinates. This results in point displacements of at most (1 + ∆) times the diameter of the convex hull.
Given a new point, its successor and predecessor in the veb are found, and the operations required to check the convex hull and, if necessary, to correct it are carried on, as in Graham's algorithm [12]. These operations may include the insertion of the new point into the veb (if the point is on the convex hull) and the possible deletion of other points. Since each point can only be deleted once from the convex hull, the amortized number of veb operations per point is constant.
3 Related work Our work was inspired by and improves upon data structures developed for use in dynamic random variate generation by Matias, Vitter, and Ni [19].
Approximation techniques such as rounding and bucketing have been widely used in algorithm design. This is the first work we know of that gives a generalpurpose approximate data structure.
Finite precision arithmetic.
The sensitivity of algorithms to approximate data structures is related in spirit to the challenging problems that arise from various types of error in numeric computations. Such errors has been studied, for example, in the context of computational geometry [8,9,13,14,21,22,23]. We discuss this further in Section 6.
Approximate sorting. Bern, Karloff, Raghavan, and Schieber [3] introduced approximate sorting and applied it to several geometric problems. Their results include an O((n log log n)/ǫ)-time algorithm that finds a (1 +ǫ)approximate Euclidean minimum spanning tree. They also gave an O(n)-time algorithm that finds a (1 + ∆)approximate convex hull for any ∆ ≥ 1/polynomial.
In a loose sense, approximate veb data structures generalize approximate sorting. The advantages of an approximate veb are the following. An approximate veb bounds the error for each element individually. Thus, an approximate veb is applicable for problems such as the general minimum spanning tree problem, for which the answer depends on only a subset of the elements. The approximate sort of Bern et al. bounds the net error, which is not sufficient for such problems. More importantly, a veb is dynamic, so is applicable to dynamic problems such as on-line convex hull and in algorithms such as Dijkstra's algorithm in which the elements to be ordered are not known in advance. Sorting requires precomputation, so is not applicable to such problems.
Convex hull algorithms. There are several relevant works for the on-line convex hull problem. Shamos (see, e.g., [26]) gave an on-line algorithm for (exact) convex hull that takes O(log n) amortized time per update step. Preparata [24] gave a real-time on-line (exact) convex hull algorithm with O(log n)-time worst-case time per update step. Bentley, Faust, and Preparata [2] give an O(n + 1/∆)-time algorithm that finds a (1 + ∆)approximate convex hull. Their result was superseded by the result of Bern et al. mentioned above. Janardan [15] gave an algorithm maintaining a fully dynamic (1 + ∆)-approximate convex hull (allowing deletion of points) in O(log(n)/∆) time per request. Our on-line approximation algorithm is based on Graham's scan algorithm [12] and can be viewed as a combination of the algorithms by Shamos and by Bentley et al., with the replacement of an exact veb data structure by an approximate variant.
Computation with large words. Kirkpatrick and Reich [17] considered exact sorting with large words, giving upper and lower bounds. Their interest was theoretical, but Lemma 5.1, which in some sense says that maintaining an approximate veb data structure is equivalent to maintaining an exact counterpart using larger words, suggests that lower bounds on computations with large words are relevant to approximate sorting and data structures.
Exploiting the power of RAM. Fredman and Willard have considered a number of data structures taking advantage of arithmetic and bitwise operations on words of size O(log U ). In [10], they presented the fusion tree data structure. Briefly, fusion trees implement the veb data type in time O(log n/ log log n). They also presented an atomic heap data structure [11] based on their fusion tree and used it to obtain a lineartime minimum spanning tree algorithm and an O(m + n log n/ log log n)-time single-source shortest paths algorithm. Willard [29] also considered similar applications to related geometric and searching problems. Generally, these works assume a machine model similar to ours and demonstrate remarkable theoretical consequences of the model. On the other hand, they are more complicated and involve larger constants. Subsequent to our work Klein and Tarjan recently announced a randomized minimum spanning tree algorithm that requires only expected linear time [18]. Arguably, our algorithm is simpler and more practical.

Model of computation
The model of computation assumed in this paper is a modernized version of the random access machine (ram). Many ram models of a similar nature have been defined in the literature, dating back to the early 1960s [1]. Our ram model is a realistic variant of the logarithmic-cost ram [1]: the model assumes constant-time exact binary integer arithmetic (+, −, ×, div), bitwise operations (left-shift, right-shift, bitwise-xor, bitwise-and), and addressing operations on words of size b. Put another way, the word size of the ram is b. We assume that numbers are of the form i + j/2 b , where i and j are integers with 0 ≤ i, j < 2 b , and that the numbers are represented with two words, the first holding i and the second holding j. For simplicity of exposition, we use the "mostsignificant-bit" function MSB(x) = ⌊log 2 x⌋; it can be implemented in small constant time via the previously mentioned operations and has lower circuit complexity than, e.g., division.

Fast approximate data structures
This section gives the details of our approximate veb data structure. First we give the relevant semantics and notations. The operations supported are: The Insert operation and the query operations return the name N of the element in question. The name is just a pointer into the data structure allowing constanttime access to the element. Subsequent operations on the element are passed this pointer so they can access the element in constant time. Insert takes an additional parameter d, an arbitrary auxiliary data item. Search(x), where x is a real number (but not necessarily an element), returns the name of the largest element less than or equal to x. For the approximate variants, the query operations are approximate in that the element returned by the query is within a (1 + ǫ) relative factor or a ∆ absolute amount of the correct value. Operations Element(N ) and Data(N ), given an element's name N , return the element and its data item, respectively.
The universe (specified by U ) and, for the approximate variants, the error of approximation (ǫ or ∆) are specified when the data structure is instantiated.

Equivalence of various approximations.
The lemma below assumes a logarithmic word-size ram. The notion of equivalence between data structures is that, given one of the data structures, the other can be simulated with constant-time overhead per operation. Proof. Assume we have a data structure for the exact data type on the specified universe. To simulate the multiplicatively approximate data structure, the natural mapping to apply to the elements (as discussed previously) is x → ⌊log 1+ǫ x⌋. Instead, we map x to approximately 1 ln 2 (log 1+ǫ x) ≈ (log 2 x)/ǫ and we use a mapping that is faster to compute: Let k = ⌈log 2 1 ǫ ⌉, let x = i + j/2 b , and let ℓ = MSB(i). We use the mapping f that maps x to If ℓ < k, then to right-shift by (ℓ − k) means to left-shift by (k − ℓ). Note that in this case the fractional part of x is shifted in.
This mapping effectively maps x to the lexicographically ordered pair MSB(x), y , where y represents the bits with indices (ℓ − 1) though (ℓ − k) in x. The first part of the tuple distinguishes between any two x values that differ in their most significant bit. If two x values have MSB(x) = ℓ, then it suffices to distinguish them if they differ additively by 2 ℓ−k . The second part of the tuple suffices for this.
Note that f (1) = 0 and f (U ) < 2 k+1 log 2 U = O(log 1+ǫ U ). This shows one direction of the first part. The other direction of the first part is easily shown by essentially inverting the above mapping, so that distinct elements map to elements that differ by at least a factor of 1 + ǫ. Finally, the second part follows by taking the mapping (x → x div ∆) and its inverse.
5.2 Implementations. Lemma 5.1 reduces the approximate problems to the exact problem with smaller universe size. This section gives an appropriate solution to the exact problem. If an approximate variant is to be implemented, we assume the elements have already been mapped by the constant-time function f in Lemma 5.1. The model of computation is a ram with b-bit words.
A dictionary data structure supports update operations Set(key, value) and Unset(key) and query operation Look-Up(key) (returning the value, if any, associated with the key). It is well known how to implement a dictionary by hashing in space proportional to the number of elements in the dictionary or in an array of size proportional to the key space. In either case, all dictionary operations require only constant time. In the former case, the time is constant with high probability [6,5]; in the latter case, a well-known trick is required to instantiate the dictionary in constant time.
Each instance of our data structure will have a doubly-linked list of element/datum pairs. The list is ordered by the ordering induced by the elements. The name of each element is a pointer to its record in this list.
If the set to be stored is a multiset, as will generally be the case in simulating an approximate variant, then the elements will be replaced by buckets, which are doubly-linked lists holding the multiple occurrences of an element. Each occurrence holds a pointer to its bucket. In this case the name of each element is a pointer to its record within its bucket.
Each instance will also have a dictionary mapping each element in the set to its name. If the set is a multiset, it will map each element to its bucket. In general, the universe, determined when the data structure is instantiated, is of the form {L, ..., U }. Each instance records the appropriate L and U values and subtracts L from each element, so that the effective universe is {0, ..., U − L}.
The ordered list and the dictionary suffice to support constant-time Predecessor, Successor, Minimum, and Maximum operations. The other operations use the list and dictionary as follows. Insert(i) finds the predecessor-to-be of i by calling Search(i), inserts i into the list after the predecessor, and updates the dictionary. If S is a multiset, i is inserted instead into its bucket and the dictionary is updated only if the bucket didn't previously exist. Delete(N ) deletes the element from the list (or from its bucket) and updates the dictionary appropriately.
How Search works depends on the size of the universe. The remainder of this section describes Search queries and how Insert and Delete maintain the additional structure needed to support Search queries.

Bit-vectors.
For a universe of size b, the additional structure required is a single b-bit word w. As described in Section 1.1, the word represents a bit vector; the ith bit is 1 iff the dictionary contains an element i. Insert sets this bit; Delete unsets it if no occurrences of i remain in the set. Setting or unsetting bits can be done with a few constant time operations.
The Search(i) operation is implemented as follows. If the list is empty or i is less than the minimum element, return nil. Otherwise, let j ← MSB(w bitwise-and ((1 left-shift i) − 1)) , i.e., let j be the index of the most significant 1-bit in w that is at most as significant as the ith bit. Return j's name from the dictionary.
Analysis. On universes of size b, all operations require only a few constant-time operations. If hashing is used to implement the dictionary, the total space (number of words) required at any time is proportional to the number of elements currently in the set.

5.4
Intermediate data structure. The fully recursive data structure is a straightforward modification of the original van Emde Boas data structure. For those not familiar with the original data structure, we first give an intermediate data structure that is conceptually simpler as a stepping stone. The additional data structures to support Search(i) for a universe {0, 1, ..., b j − 1} are as follows.
Divide the problem into b + 1 subproblems: if the current set of elements is S, let S k denote the set {i ∈ S : i div b j−1 = k}. Inductively maintain a veb data structure for each non-empty set S k . Note that the universe size for each S k is b j−1 . Each S k can be a multiset only if S is.
Let T denote the set {k : S k not empty }. Inductively maintain a veb data structure for the set T . The datum for each element k is the data structure for S k . Note that the universe size for T is b. Note also that T need not support multi-elements.
Implement Search(i) as follows. If i is in the dictionary, return i's name. Otherwise, determine k such that i would be in S k if i were in S. Recursively search in T for the largest element k ′ less than or equal to k. If k ′ < k or i is less than the minimum element of S k , return the maximum element of S k ′ . Otherwise, recursively search for the largest element less than or equal to i in S k and return it.
Insert and Delete maintain the additional data structures as follows. Insert(i) inserts i recursively into the appropriate S k . If S k was previously empty, it creates the data structure for S k and recursively inserts k into T . Delete(N ) recursively deletes the element from the appropriate S k . If S k becomes empty, it deletes k from T .

Analysis.
Because the universe of the set T is of size b, all operations maintaining T take constant time. Thus, each Search, Insert, and Delete for a set with universe of size U = b j requires a few constanttime operations and possibly one recursive call on a universe of size b j−1 . Thus, each such operation requires To analyze the space requirement, note that the size of the data structure depends only on the elements in the current set. Assuming hashing is used to implement the dictionaries, the space required is proportional to the number of elements in the current set plus the space that would have been required if the distinct elements of the current set had simply been inserted into the data structure. The latter space would be at worst proportional to the time taken for the insertions. Thus, the total space required is proportional to the number of elements plus O(log b U ) times the number of distinct elements.

Full recursion.
We exponentially decrease the above time by balancing the subdivision of the problem exactly as is done in the original van Emde Boas data structure.
The first modification is to balance the universe sizes of the set T and the sets {S k }. Assume the universe size is b 2 j . Note that b 2 j = b 2 j−1 × b 2 j−1 . Define S k = {i ∈ S : i div b 2 j−1 = k} and define T = {k : S k is not empty}. Note that the universe size of each S k and of T is b 2 j−1 .
With this modification, Search, Insert, and Delete are still well defined. Inspection of Search shows that if Search finds k in T , it does so in constant time, and otherwise it does not search recursively in S k . Thus, only one non-constant-time recursion is required, into a universe of size b 2 j−1 . Thus, Search requires O(j) time.
Insert and Delete, however, do not quite have this nice property. In the event that S k was previously empty, Insert descends recursively into both S k and T . Similarly, when S k becomes empty, Delete descends recursively into both S k and T .
The following modification to the data structure fixes this problem, just as in the original van Emde Boas data structure. Note that Insert only updates T when an element is inserted into an empty S k . Similarly, Delete only updates T when the last element is deleted from the set S k . Modify the data structure (and all recursive data structures) so that the recursive data structures exist only when |S| ≥ 2. When |S| = 1, the single element is simply held in the list. Thus, insertion into an empty set and deletion from a set of one element require only constant time. This insures that if Insert or Delete spends more than constant time in T , it will require only constant time in S k .
This modification requires that when S has one element and a new element is inserted, Insert instantiates the recursive data structures and inserts both elements appropriately. The first element inserted will bring both T and some S k to size one; this requires constant time. If the second element is inserted into the same set S k as the first element, T is unchanged. Otherwise, the insertion into its newly created set S k ′ requires only constant time. In either case, only one non-constant-time recursion is required.
Similarly, when S has two elements and one of them is deleted, after the appropriate recursive deletions, Delete destroys the recursive data structures and leaves the data structure holding just the single remaining element. If the two elements were in the same set S k , then T was already of size one, so only the deletion from S k requires more than constant time. Otherwise, each set S k and S k ′ was already of size one, so only the deletion of the second element from T took more than constant time.
Analysis. With the two modifications, each Search, Insert, and Delete for a universe of size U = b 2 j requires at most one non-constant-time recursive call, on a set with universe size b 2 j−1 . Thus, the time required for each operation is O(j) = O(log log b U ). As for the intermediate data structure, the total space is at worst proportional to the number of elements, plus the time per operation (now O(log log b U )) times the number of distinct elements.

Conclusions
The approximate data structures described in this paper are simple and efficient. No large constants are hidden in the asymptotic notations-in fact, a "back of the envelope" calculation indicates significant speed-up in comparison to the standard van Emde Boas data structure. The degree of speed-up in practice will depend upon the machines on which they are implemented. Machines on which binary arithmetic and bitwise operations on words are nearly as fast as, say, comparison between two words will obtain the most speed-up. Practically, our results encourage the development of machines which support fast binary arithmetic and bitwise operations on large words. Theoretically, our results suggest the need for a model of computation that more accurately measures the cost of operations that are considered to require constant time in traditional models.
The applicability of approximate data structures to specific algorithms depends on the robustness of such algorithms to inaccurate intermediate computations.
In this sense, the use of approximate data structures has an effect similar to computational errors that arise from the use of finite precision arithmetic. In recent years there has been an increasing interest in studying the effect of such errors on algorithms. Of particular interest were algorithms in computational geometry. Frameworks such as the "epsilon geometry" of Guibas, Salesin and Stolfi [14] may be therefore relevant in our context. The "robust algorithms" described by Fortune and Milenkovic [8,9,21,22,23] are natural candidates for approximate data structures.
Expanding the range of applications of approximate data structures is a fruitful area for further research. Other possible candidates include algorithms in computational geometry that use the well-known sweeping technique, provided that they are appropriately robust. For instance, in the sweeping algorithm for the line arrangement problem with approximate arithmetic, presented by Fortune and Milenkovic [9], the priority queue can be replaced by an approximate priority queue with minor adjustments, to obtain an output with similar accuracy. If the sweeping algorithm of Chew and Fortune [4] can be shown to be appropriately robust then the use of the van Emde Boas priority queue there can be replaced by an approximate variant; an improved running time may imply better performance for algorithms described in [3].


extfieldsofstudy:
Computer Science
Mathematics

text:
Axiomatic Aspects of Default Inference

This paper studies axioms for nonmonotonic consequences from a semantics-based point of view, focusing on a class of mathematical structures for reasoning about partial information without a predefined syntax/logic. This structure is called a default structure. We study axioms for the nonmonotonic consequence relation derived from extensions as in Reiter's default logic, using skeptical reasoning, but extensions are now used for the construction of possible worlds in a default information structure. In previous work we showed that skeptical reasoning arising from default-extensions obeys a well-behaved set of axioms including the axiom of cautious cut. We show here that, remarkably, the converse is also true: any consequence relation obeying this set of axioms can be represented as one constructed from skeptical reasoning. We provide representation theorems to relate axioms for nonmonotonic consequence relation and properties about extensions, and provide one-to-one correspondence between nonmonotonic systems which satisfies the law of cautious monotony and default structures with unique extensions. Our results give a theoretical justification for a set of basic rules governing the update of nonmonotonic knowledge bases, demonstrating the derivation of them from the more concrete and primitive construction of extensions. It is also striking to note that proofs of the representation theorems show that only shallow extensions are necessary, in the sense that the number of iterations needed to achieve an extension is at most three. All of these developments are made possible by taking a more liberal view of consistency: consistency is a user defined predicate, satisfying some basic properties.

Introduction
Reasoning in general is concerned with drawing conclusions from a set of premises. Mathematical reasoning is monotonic, in the sense that if the set of premises becomes bigger, the set of conclusions also grows larger (or stays the same). Reasoning in daily life, however, is nonmonotonic, because conclusions drawn earlier due to the lack of information may have to be withdrawn later in light of new information. This nonmonotonic phenomenon can be avoided by putting time-stamps on conclusions. Thus, the conclusions drawn earlier and the conclusions withdrawn later have different time-stamps and are treated as different conclusions. The cost of this temporal approach, which will not be discussed further here, is the "frame problem", referring to the issue of keeping track of much of background information that stays unchanged as time goes on.
Nonmonotonicity arises when explicit time-stamps are avoided when we are in fact dealing with time-sensitive, partial information. For example, in databases data are not time-stamped, but they evolve continuously over time.
A well-known formalism for nonmonotonic reasoning is Reiter's default logic [18], in which the so-called extension construction was introduced as a important method to extend current knowledge using default rules. Reiter's treatment is syntactic, in the sense that default rules are used as extended proof rules for first order logic, allowing more conclusions derived provided that the global property of consistency is not violated. It should be of no surprise that this treatment has caused some anomalies, because first order logic was invented for mathematical reasoning rather than commonsense reasoning.
There is a conceptually cleaner view of default reasoning under the paradigm of modal logic with Kripke structure as models [26]. We can think of a state in a Kripke structure as a state of knowledge/information. Possible worlds represent hypothetical worlds which may evolve from a given state. Modal logic can then be adapted for the purpose of reasoning about belief. The role of default is now relegated to the semantic structure as a concrete way for constructing possible worlds using extensions. Nonmonotonic reasoning in this new setting becomes model-checking: given a state (a knowledge base) in the Kripke structure and a belief formula (expressed in modal logic), determine whether or not the belief is supported. Nonmonotonicity corresponds to the fact that a belief supported in the current state may become unsupported in a possible future state.
This semantic view of default reasoning is developed in detail in the so-called default domain theory [19]. The idea is to use Scott's information system [21] as the basic semantic structure for representing information states (the underlying Kripke structure), extended with default rules in order to construct possible worlds. Here are some specific achievements of default domain theory.
-Power default reasoning. Domain theory is a powerful and elegant framework developed by Scott and others for the denotational semantics of programming languages. A routine practice in domain theory is that an object of one type can be embedded/projected to different type in order to facilitate a more appropriate treatment. The idea of power default reasoning [29] is to encode default rules in a higher-order setting so that a nonmonotonic operator at the base level induces a better behaved operator in the higher-order space of Smyth powerdomain. Under power default reasoning, the extension construction has nice structural properties. For example, one can show a dichotomy theorem [29] which states that with respect to a set of default constraints on a Scott domain D lifted as power defaults Γ on the Smyth powerdomain P(D), an element either has a safe, unique Γ -extension, or else the multiple Γ -extensions will all be singleton generated. The Extension Splitting Theorem [29] states that any extension of the union of two compact open sets can be split into the union of two corresponding extensions. This allowed us to prove, among other things, the law of reasoning by cases and the law of cautious monotony, as discussed in [12]. Note that the cases law and cautious monotony law do not hold for standard propositional default logic, which is among the anomalies of default logic discussed in the literature. -Complexity. These structural properties have direct algorithmic consequences.
Based on the Dichotomy Theorem, an algorithm [28] has been developed for skeptical normal default inference in propositional logic to show that the problem is complete for co-NP(3), the third level of the Boolean hierarchy. This contrasts favorably with standard propositional default reasoning based on default logic, which was proved to be Π P 2 -complete [10,4]. -Semantics of disjunctive logic programming. Our domain-theoretic investigation to logic programming started with the basic observation that the information system representation of domains [21] bears a remarkable similarity to the syntax of definite logic programs (the so-called Horn clauses).
Our work [20] shows that a general disjunctive logic programming paradigm can be developed on coherent domains -algebraic cpos on which the intersection of any two compact open sets remains compact open. From the domain-theoretic point of view, these are very general spaces which contain several prominent categories already (such as Scott domains and SFP domains). More concretely, a disjunctive logic program can be regarded as a sequent structure. Such a structure generates spatial locales (the so-called pointless topology [11]), which provide models and proof rules for which completeness is guaranteed [3].
In this paper we continue the semantics-based study of nonmonotonic inference by providing representation theorems for the skeptical nonmonotonic consequence relation. We show that an abstract nonmonotonic relation satisfies the law of cautious monotony (among other reasonable axioms) if and only if it can be generated from a set of normal default rules with unique extensions. We then provide some preliminary discussions on a possible categorical setting in which to discuss properties of these constructions. These developments are made possible by taking a less restricted view of consistency: we view consistency as a user defined predicate, satisfying some basic properties, as precisely captured by information systems -Con. There is no prescribed global notion of consistency; a set of tokens can be consistent in one information system while inconsistent in another. We believe that the meaning for "paraconsistency" ultimately lies in this local, user-defined interpretation.
Related work. The idea of extension was introduced by Reiter [18]. Makinson [13] and others [9] have provided extensive study of many axioms discussed here, sometimes from the belief-revision point of view. Marek, Nerode, and Remmel [14] have studied structures similar to default information structures, from a recursion-theoretic point of view. The first representation result similar to the ones studied here was given in [27]. Hitzler and Seda [22,23], in a sequence of papers, studied logic programming semantics using the tools of Topology and Analysis. The edited volume [25] contains a number of discussions on the role of partiality of information for commonsense reasoning. These are philosophically allied to our domain-theoretic approach to logic programming and nonmonotonic reasoning. Fitting [5,6,7] was among the first ones to introduce order to the study of logic programming in a systematic way. There are also other kinds of representation results in the literature. For example, Marek, Treur, and Truszczynski [15] studied the problem of when a family of theories can be represented as the extension family of normal defaults. Our work differs from this in that we relate default theory to axioms for the nonmonotonic consequence relation, establishing connections between two independent paradigms.

Default domain theory
This section provides an overview of the basic structure of default domain theory -default information structures. We refer to [21,30] for more discussion on information systems, and [1,2,16] for background on nonmonotonic reasoning.

Information systems
In order to study the properties of nonmonotonic systems, let's first take a look at monotonic systems, as captured in Scott's information systems.
An information system consists of a set A of tokens, a subset Con of the set of finite subsets of A, denoted as Fin(A), and a relation ⊢ between Con and A. The subset Con on A is often called the consistency predicate, and the relation ⊢ is called the entailment relation. Both the consistency predicate and the entailment relation satisfy some axioms due to Tarski, made precise in the following definition.
Moreover, the consistency predicate and entailment relation satisfy the following properties: Although monotonicity for ⊢ is not explicitly given, it is a derivable property. Suppose Y ⊢ a and Y ⊆ X with X ∈ Con. By (4), X ⊢ b for every b ∈ Y . Now apply (5) and we get X ⊢ a. Thus monotonicity is an inherent property of ⊢: The notion of consistency can be easily extended to arbitrary token sets by enforcing compactness, i.e., a set is consistent if every finite subset of it is consistent. By overloading notation, we write X ∈ Con when every finite subset of X is consistent.
The monotonicity of ⊢ induces a monotonic operator F : Con → Con for an information system (A, Con, ⊢): The reflexivity property (4) implies that F is inflationary, in the sense that X ⊆ F (X) for any X ⊆ A. The continuity of F follows from the finiteness (or compactness) of ⊢ on its left-hand-side.
From these we can easily show that for any given subset X of tokens, F has a least fixed-point containing X. F is in fact a closure operator (often denoted as Cn in the literature), with the following defining properties: Idempotency of F follows from the transitivity (5) of ⊢. To show the nontrivial containment F (F (X)) ⊆ F (X), let a ∈ F (F (X)). This means that for and so a ∈ F (X), as required.
The information states of an information system are precisely sets of the form F (X) with X ∈ Con, where Con is understood in the generalized sense to include infinite sets through the compactness condition. Moreover, the set of all information state {F (X) | X ∈ Con} is precisely the set of fixed-points of F .
The importance of information systems lies in the fact that they provide a concrete representation of Scott domains 2 . 1 Here we deliberately dropped the X ∈ Con condition. One can, as in logic, define Con in such a way that X ∈ Con if and only if X ⊢ a for some a ∈ A, as suggested by Peter Aczel in a personal communication. However, this "logical" definition is more limited, in that it insists on the whole set A to be inconsistent. 2 Exactly what a Scott domain is need not concern us here. It should suffice to say that a Scott domain is a complete lattice with the top element removed.

Theorem 1. (Scott) For any information system A, the collection of its information states |A| under inclusion forms a Scott domain. Conversely, every Scott
domain is order-isomorphic to the partial order of information states of some information system.

Normal default structures
We now introduce the main definitions of default domain theory. Normal default structures are information systems extended with a set of default rules of the form X : a a , with X a finite consistent set, and a a single token of the underlying information system. The idea of a default rule is that one can generate models (states of belief) by finding X as a subset of tokens in a state under construction, checking that a is consistent with the current state, and then adding the token a.

Definition 2. A normal default structure is a tuple
If each default is of the form ∅ : a a , we call the default structure precondition free.
Extensions are a key notion related to a default structure. An extension of an information state x is intuitively an information state y extending x, constructed in such a way that everything in y reflects an agent's belief expressed by defaults. If the current situation is x, then because it is a partial model, it may not contain enough information to settle an issue (either positively or negatively). Extensions of x are partial models containing at least as much information as x, but the extra information in an extension is only plausible, not factual.
The following definition is just a reformulation, in information-theoretic terms, of Reiter's own notion of extension in default logic.
Definition 3. Let A = (A, Con, ∆, ⊢) be a default structure, and x an information state of the information system (A, Con, ⊢). For any S ⊆ A, define Φ(x, S) to be the union i≥0 φ(x, S, i), where (note that F is given in the previous subsection) Call y an extension of x if Φ(x, y) = y. In this case we also write x ǫ A y, with the subscript omitted when the default structure under consideration is clear.
Basic properties of extensions are stated next, which will be used in the proof of main representation theorems in the next section. These properties are parallel to those for Reiter's default logic, and so their proofs are omitted.
Theorem 2. Let A = (A, Con, ∆, ⊢) be a normal default structure, and x, y information states of the information system (A, Con, ⊢). We have 1. x has at least one extension. 2. if x ǫ y then y ⊇ x. 3. if x ǫ y, then y ǫ z if and only if y = z for any information state z. 4. for any information state z, if x ǫ y and x ǫ z, then either y = z or y∪z ∈ Con.
In terms of possible world semantics, normal default structures give rise to Kripke structures in which every state has either a transition to a different state or loops to itself. Moreover, if a state does contain a transition to a new state, then such future states are pairwise incompatible (there is no common future states).

Axioms for nonmonotonic consequence
There is little disagreement about what properties should a (monotonic) entailment relation have: these were given by Tarski, as captured in information systems. The situation is quite different for the nonmonotonic consequence relation. To motivate the discussion, we first take a look at the skeptical nonmonotonic consequence relation determined by a normal default information structure with a trivial ⊢. The default structures will have only three components, as (A, Con, ∆), with ⊢ understood as X ⊢ a if and only if a ∈ X. The closure operator F will now be the identity function: F (X) = X. Definition 4. The skeptical nonmonotonic consequence relation |∼ A with respect to a normal default structure (A, Con, ∆) is defined as X |∼ A a if a belongs to every extension y of X. Here X is a finite consistent subset of A, and a ∈ A.
Since extensions exist in normal default structures, we have X |∼ A a ⇐⇒ a ∈ {y | Xǫ A y}.
The next example shows that |∼ A is not monotonic: X |∼ A a and X ⊆ Y does not imply Y |∼ a. Failing monotonicity, what other properties can we say about |∼ A ? For sake of brevity, we write, for finite sets X and Y , X |∼ Y to mean that X |∼ b for every b ∈ Y . Certainly we have X |∼ X for every consistent finite set X. The only non-trivial property we can say about |∼ in general seems to be cautious cut: X |∼ T & T, X |∼ Y ⇒ X |∼ Y. We call it cautious cut because the standard cut axiom takes the following form: This is equivalent to cautious cut when monotonicity is assumed, but cut is stronger in the nonmonotonic case.
We need the following property to prove cautious cut.
Lemma 1. For any finite consistent sets P, Q of a default structure (A, Con, ∆), if P ǫ R and Q ⊆ R, then (P ∪ Q) ǫ R.
A proof for this can be found in [27]. Proof. Let X |∼ A T and T, X |∼ A Y for finite consistent sets X, T, Y . We have We need to show that Y ⊆ {e | Xǫ A e}. Let e be an extension of X. We have T ⊆ e since X |∼ A T . By Lemma 1, e is an extension of X ∪ T . However, Y is a subset of every extension of X ∪ T ; in particular, Y ⊆ e. Therefore, Y is a subset of every extension of X, as required for X |∼ A Y . 2 We take the properties satisfied by |∼ A as the minimal set of properties that any nonmonotonic consequence relation should satisfy. This brings us to the notion of abstract nonmonotonic system. Definition 5. An abstract nonmonotonic system is a triple (A, Con, |∼), where Con is a collection of finite subsets X of A, called the consistent sets, |∼ is a subset of Con × Con, called the relation of nonmonotonic entailment, which satisfies the following axioms: Note that Axiom 4 is reflexivity, and Axiom 5 is cautious cut. The rest of the properties are routine. Axioms 4 and 6 together allow us to view a nonmonotonic system as one generated from instances of the form X |∼ {a}. One can then define X |∼ Y if and only if X |∼ {b} for every b ∈ Y . X |∼ ∅ is vacuously true. [27]). For any a normal default structure (A, Con, ∆), (A, Con, |∼ A ) is an abstract nonmonotonic system, where the relation |∼ A is given in Definition 4.

Theorem 4 (Zhang and Rounds
We will not go through the formality of the proof here, but only note that cautious cut follows from Theorem 3, and Axiom 3 follows from the fact that extensions always exist and each one of them is a consistent set.

Representation theorems
Theorem 4 says that any normal default structure determines an abstract nonmonotonic system -a nonmonotonic relation satisfying a minimal set of properties including reflexivity and cautious cut.
The more interesting question is the converse: is it true that every abstract nonmonotonic system can be represented concretely as one derived from a normal default structure? In other words, for each abstract nonmonotonic system (A, Con, |∼), is there a normal default structure (B, Con, ∆) such that |∼ = |∼ B ?
We show that the converse of Theorem 4 is indeed true. Such a representation result bears much resemblance to the fundamental Cayley's Theorem for finite groups, saying that any finite group is isomorphic to a permutation group. The next theorem says that every abstract nonmonotonic relation is determined by some normal default structure. This shows that the framework of default rules with extensions, although a concrete nonmonotonic formalism, is expressive enough to represent any reasonable nonmonotonic consequence relation.
Theorem 5. Let (A, Con, |∼) be an abstract nonmonotonic system. There is a normal default structure B = (B, Con * , ∆) satisfying the following properties: for any X ⊆ B, X ∈ Con if and only if X ⊆ A and X ∈ Con * , 3. for every X, Y ∈ Con, X |∼ Y if and only if X |∼ B Y.
Conditions 2 states that Con * is a conservative extension of Con, and condition 3 says that |∼ B is a conservative extension of |∼. Example 2. An example will be helpful to illustrate the idea of the proof. Consider the abstract nonmonotonic system (A, Con, |∼) with A = {a, b}, Con = 2 A and |∼ generated by requiring ∅ |∼ {a} and ∅ |∼ {b} (i.e., reflexivity and cautious cut is always assumed; note that we have neither {a} |∼ {b}, nor {b} |∼ {a}). We would like to construct a default structure B = (B, Con * , ∆) which determines this nonmonotonic entailment relation 3 .
The idea is to introduce, for each consistent set X, a new token [X], similar to the powerset construction in automata theory. The consistency predicate Con * is defined in such a way that it extends Con, but new tokens are inconsistent with each other. Moreover, for a set containing a new token [X] to be consistent, every other element in the set must be a nonmonotonic consequence of X. Therefore, the consistent sets in Con * are sets (as well as their subsets) of the form We now describe a general procedure to construct the required default structure B = (B, Con * , ∆) from an abstract nonmonotonic system (A, Con, |∼).
The token set B is A∪{[X] | X ∈ Con}. The idea is to introduce a new token for each consistent set X and use sets of given tokens to encode new tokens. Note that we need only introduce [X] for (consistent) finite sets X in the powerset of A here, even though A may be infinite.
We have two kinds of default rules. One is for each X ∈ Con, and the other is {[X]} : a a for each nonmonotonic instance X |∼ a with a ∈ X. Thus For any subset W of B, W ∈ Con * if and only if all of the following three conditions hold: 1. W ∩ A ∈ Con, i.e., the old tokens in W form a consistent set in Con;

at most one token of the form [X] is in
It is straightforward to check that the consistency predicate defined this way has the required properties. Each individual token is indeed consistent. For any subset Z of W ∈ Con * , we have Z ∈ Con * by examining the three conditions above.
The remaining task is to show that the default structure B has the properties as stated in Theorem 5. This will be achieved in several lemmas.
An auxiliary notation is needed. We define X := {t | X |∼ {t}}, i.e., X is the set of all nonmonotonic consequences of X. Lemma 2. Let (A, Con, |∼) be an abstract nonmonotonic system. We have, for any consistent set X, Proof. We prove the non- Given any a in X, we can rewrite this as The axiomatization of the nonmonotonic operator ( ) has been studied in depth, notably by Makinson and others. Here we only indicate that it is not monotonic (of course), and it is not necessarily true that X = X.
Lemma 3. Let P, Q be finite consistent sets in an abstract nonmonotonic system (A, Con, |∼) and B = (B, Con * , ∆) the corresponding default structure. If Proof. It is easy to see that the set Q ∪ {[Q]} is consistent with respect to Con * .
We need to verify the defining equality ρ(Q) = i≥0 φ(P, ρ(Q), i). By definition, The only applicable rules in ∆ are of the form X : [X] [X] with X ⊆ P ; but only [Q] will meet the consistency requirement. Therefore, φ(P, ρ(Q), 1) = P ∪ The second iteration φ(P, ρ(Q), 2) is the set This time all and only tokens in Q \ Q gets added to φ(P, ρ(Q), 1), since the applicable default rules are of the form This proof conveys the additional information that extensions such as ρ(Q) can be attained in two iterations. This offers an explanation of why default reasoning need not be hard (see [24] as well), because deep iterations for building extensions may not be needed. Proof. Suppose W is an extension of P . We have W = P since otherwise P : [P ] [P ] is applicable, forcing [P ] to be added to W .
By design (of ∆), the first token added to φ(P, W, 1) must be of the form The consistency constraint requires that P ⊆ Q. It also requires that no other tokens of the form [X] belong to W . So in the second iteration one can (and must) apply all defaults of the form Proof (Theorem 5). The first two items are obvious from the definition of B. We show the third item: for every X, Y ∈ Con, X |∼ Y if and only if X |∼ B Y. Let X, Y be consistent subsets of A such that X |∼ Y . By Lemma 3 and Lemma 4, extensions of X in B are precisely sets of the form Q ∪ {[Q]} with Q ⊆ X ⊆ Q. For any such Q, we have, by Lemma 2, X ⊆ Q. Therefore Y ⊆ Q and Y is a subset of every extension of X in B. This proves X |∼ B Y.
Suppose, on the other hand, X |∼ B Y for subsets X, Y of A. By Lemma 3 and Lemma 4, This means Y ⊆ X, by Lemma 2. Therefore, X |∼ Y . 2

Cautious monotony and unique extension
The axiom of cautious monotony, considered by Gabbay, Kraus, Lehmann, and Magidor and others [8,12], takes the form (We will drop the { } for singletons and write X |∼ a & X |∼ b ⇒ X, a | ∼ b as well.) This axiom intuitively says that a nonmonotonic consequence can always be added as a premise without affecting what was originally entailed.
It is arguably one of the most fundamental assumptions for a nonmonotonic knowledge base to work: if your knowledge base X can support several beliefs, say a, b, then you should be able to adjoin these beliefs to enlarge the knowledge base to X ∪{a, b}. Now, applying the reflexivity axiom -Axiom 4 of Definition 5, we get X ∪ {a} |∼ b.
An easy induction shows that cautious monotony is equivalent to the more general form X |∼ Y & X |∼ Z ⇒ X, Y |∼ Z, with X, Y, Z being finite (consistent) sets. If an abstract nonmonotonic system (A, Con, ∆) satisfies cautious monotony, we will call it a cumulative nonmonotonic system.
Here is an example showing that the skeptical nonmonotonic consequence relation derived from a generic default structure need not satisfy cautious monotony.
Example 3. Consider the default structure (A, Con, ∆) with There is a unique extension for ∅: {a, b}. ). This prevents an existing consequence (such as a) from being present in all extensions of the changed situation.
Cautious monotony, however, does hold when extensions are unique. The reason is that in this case, a nonmonotonic consequence can be added without changing the (unique) extension.
Theorem 6 (Zhang and Rounds [27]). Let (A, Con, ∆) be a normal default structure such that extensions are unique for any information state. Then the derived nonmonotonic consequence relation |∼ A is cumulative, i.e., it satisfies cautious monotony.
In the rest of the section we show (which is new) that the converse of the above is also true, leading to another representation result.
Theorem 7. For any cumulative nonmonotonic system (A, Con, |∼), there exists a normal default structure B = (B, Con * , ∆) with the following properties: for any X ⊆ B, we have X ∈ Con if and only if X ⊆ A and X ∈ Con * , -for every X, Y ∈ Con, it is the case that X |∼ Y if and only if X |∼ B Y, -there exists a unique extension for every information state of B.
Since any cumulative nonmonotonic system is an abstract nonmonotonic system in the sense of Definition 5, Theorem 5 tells us that it can be represented by a normal default structure. The point of Theorem 7 is that, we can require the normal default structure to have unique extensions, which the construction given earlier for Theorem 5 does not provide 4 .
A lemma is needed to support the new construction.
Lemma 5. Let (A, Con, |∼) be a cumulative nonmonotonic system. For finite consistent sets P, Q of A, if Q ⊆ P ⊆ Q, then P = Q.
Proof. Lemma 2 gives P ⊆ Q and we need to show the other way round. Suppose Q |∼ a. We need to show that P |∼ a. Since P ⊆ Q, we have Q |∼ P . Applying cautious monotony to Q |∼ P and Q |∼ a, we get P ∪ Q |∼ a. This is the same as P |∼ a since Q is a subset of P , by assumption. 2 One can see from the proof of Theorem 5 that there is a 1-1 correspondence among sets Qs with Q ⊆ P ⊆ Q and extensions of P , labeled by [Q]. The previous lemma suggests that we should now collect all such [Q]s in one extension, with the proviso that Q ⊆ P and P = Q. This is in fact the key idea for the proof of Theorem 7. Let (A, Con, |∼) be an abstract nonmonotonic system satisfying cautious monotony. Define B = (B, Con * , ∆), where -W ∈ Con * if and only if all of the following three conditions hold: 1. W ∩ A ∈ Con, i.e., the old tokens in W form a consistent set in Con; 2. for each pair [X], [Y ] of (new) tokens in W , X = Y ; 3. if [X] ∈ W , then X |∼ W ∩ A.
Note that the difference from the previous construction is in the consistency predicate Con * . Two distinct tokens [X], [Y ] need not to be in conflict, as long as X = Y . Theorem 7 is now an immediate consequence of the following lemma.
Lemma 6. Let B = (B, Con * , ∆) be the normal default structure for a cumulative nonmonotonic system (A, Con, |∼) (as given in the procedure above). Every finite consistent set P ⊆ A has a unique extension, which is Proof. As a sanity check, we see that δ(P ) is indeed consistent. Suppose W is an extension of P in B. We show that W = δ(P ). By definition, W satisfies the equality W = i≥0 φ(P, W, i). Clearly W = P , since P : [P ] [P ] is one of the default rules in ∆. But the first default rules applied must add tokens of the form [X], so W contains a token of the form [Q], with Q ⊆ P . Consistency requires further that P ⊆ Q, since P ⊆ W . By Lemma 5, Q ⊆ P and P ⊆ Q implies Q = P . [R] may be applicable, with R = P and R ⊆ P (note the relaxed condition here). This shows φ(P, W, 3) = δ(P ), and there is no additional applicable default rules from now on. 2