OpenRaiser/Intern-Atlas huggingface dataset:
Tracing and Explaining Execution of CLP(FD) Programs
Venue: arXiv cs.SE 2002
Year: 2002

Previous work in the area of tracing CLP(FD) programs mainly focuses on providing information about control of execution and domain modification. In this paper, we present a trace structure that provides information about additional important aspects. We incorporate explanations in the trace structure, i.e. reasons for why certain solver actions occur. Furthermore, we come up with a format for describing the execution of the filtering algorithms of global constraints. Some new ideas about the design of the trace are also presented. For example, we have modeled our trace as a nested block structure in order to achieve a hierarchical view. Also, new ways about how to represent and identify different entities such as constraints and domain variables are presented.
Small Large-Scale Wireless Networks: Mobility-Assisted Resource Discovery
Venue: arXiv cs.NI 2002
Year: 2002

In this study, the concept of small worlds is investigated in the context of large-scale wireless ad hoc and sensor networks. Wireless networks are spatial graphs that are usually much more clustered than random networks and have much higher path length characteristics. We observe that by adding only few random links, path length of wireless networks can be reduced drastically without affecting clustering. What is even more interesting is that such links need not be formed randomly but may be confined to a limited number of hops between the connected nodes. This has an important practical implication, as now we can introduce a distributed algorithm in large-scale wireless networks, based on what we call contacts, to improve the performance of resource discovery in such networks, without resorting to global flooding. We propose new contact-based protocols for adding logical short cuts in wireless networks efficiently. The new protocols take advantage of mobility in order to increase reachability of the search. We study the performance of our proposed contact-based architecture, and clarify the context in which large-scale wireless networks can be turned into small world networks.
Paraconsistency of Interactive Computation
Venue: arXiv cs.LO 2002
Year: 2002

The goal of computational logic is to allow us to model computation as well as to reason about it. We argue that a computational logic must be able to model interactive computation. We show that first-order logic cannot model interactive computation due to the incompleteness of interaction. We show that interactive computation is necessarily paraconsistent, able to model both a fact and its negation, due to the role of the world (environment) in determining the course of the computation. We conclude that paraconsistency is a necessary property for a logic that can model interactive computation.
Axiomatic Aspects of Default Inference
Venue: arXiv cs.LO 2002
Year: 2002

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.
Preference Queries
Venue: arXiv cs.DB 2002
Year: 2002

The handling of user preferences is becoming an increasingly important issue in present-day information systems. Among others, preferences are used for information filtering and extraction to reduce the volume of data presented to the user. They are also used to keep track of user profiles and formulate policies to improve and automate decision making. We propose here a simple, logical framework for formulating preferences as preference formulas. The framework does not impose any restrictions on the preference relations and allows arbitrary operation and predicate signatures in preference formulas. It also makes the composition of preference relations straightforward. We propose a simple, natural embedding of preference formulas into relational algebra (and SQL) through a single winnow operator parameterized by a preference formula. The embedding makes possible the formulation of complex preference queries, e.g., involving aggregation, by piggybacking on existing SQL constructs. It also leads in a natural way to the definition of further, preference-related concepts like ranking. Finally, we present general algebraic laws governing the winnow operator and its interaction with other relational algebra operators. The preconditions on the applicability of the laws are captured by logical formulas. The laws provide a formal foundation for the algebraic optimization of preference queries. We demonstrate the usefulness of our approach through numerous examples.
A Unified Theory of Shared Memory Consistency
Venue: arXiv cs.DC 2002
Year: 2002

Memory consistency models have been developed to specify what values may be returned by a read given that, in a distributed system, memory operations may only be partially ordered. Before this work, consistency models were defined independently. Each model followed a set of rules which was separate from the rules of every other model. In our work we have defined a set of four consistency properties. Any subset of the four properties yields a set of rules which constitute a consistency model. Every consistency model previously described in the literature can be defined based on our four properties. Therefore, we present these properties as a unfied theory of shared memory consistency.
A logical reconstruction of SPKI
Venue: arXiv cs.CR 2002
Year: 2002

SPKI/SDSI is a proposed public key infrastructure standard that incorporates the SDSI public key infrastructure. SDSI's key innovation was the use of local names. We previously introduced a Logic of Local Name Containment that has a clear semantics and was shown to completely characterize SDSI name resolution. Here we show how our earlier approach can be extended to deal with a number of key features of SPKI, including revocation, expiry dates, and tuple reduction. We show that these extensions add relatively little complexity to the logic. In particular, we do not need a nonmonotonic logic to capture revocation. We then use our semantics to examine SPKI's tuple reduction rules. Our analysis highlights places where SPKI's informal description of tuple reduction is somewhat vague, and shows that extra reduction rules are necessary in order to capture general information about binding and authorization.
Parameterized Type Definitions in Mathematica: Methods and Advantages
Venue: arXiv cs.SC 2002
Year: 2002

The theme of symbolic computation in algebraic categories has become of utmost importance in the last decade since it enables the automatic modeling of modern algebra theories. On this theoretical background, the present paper reveals the utility of the parameterized categorical approach by deriving a multivariate polynomial category (over various coefficient domains), which is used by our Mathematica implementation of Buchberger's algorithms for determining the Groebner basis. These implementations are designed according to domain and category parameterization principles underlining their advantages: operation protection, inheritance, generality, easy extendibility. In particular, such an extension of Mathematica, a widely used symbolic computation system, with a new type system has a certain practical importance. The approach we propose for Mathematica is inspired from D. Gruntz and M. Monagan's work in Gauss, for Maple.
Rerendering Semantic Ontologies: Automatic Extensions to UMLS through Corpus Analytics
Venue: arXiv cs.CL 2002
Year: 2002

In this paper, we discuss the utility and deficiencies of existing ontology resources for a number of language processing applications. We describe a technique for increasing the semantic type coverage of a specific ontology, the National Library of Medicine's UMLS, with the use of robust finite state methods used in conjunction with large-scale corpus analytics of the domain corpus. We call this technique "semantic rerendering" of the ontology. This research has been done in the context of Medstract, a joint Brandeis-Tufts effort aimed at developing tools for analyzing biomedical language (i.e., Medline), as well as creating targeted databases of bio-entities, biological relations, and pathway data for biological researchers. Motivating the current research is the need to have robust and reliable semantic typing of syntactic elements in the Medline corpus, in order to improve the overall performance of the information extraction applications mentioned above.
Sampling from a couple of positively correlated binomial variables
Venue: arXiv cs.DM 2002
Year: 2002

We know that the marginals in a multinomial distribution are binomial variates exhibiting a negative correlation. But we can construct two linear combinations of such marginals in such a way to obtain a positive correlation. We discuss the restrictions that are to be imposed on the parameters of the given marginals to accomplish such a result. Next we discuss the regression function, showing that it is a linear function but not homoscedastic.
Does NP not equal P?
Venue: arXiv cs.CC 2002
Year: 2002

Stephen Cook posited SAT is NP-Complete in 1971. If SAT is NP-Complete then, as is generally accepted, any polynomial solution of it must also present a polynomial solution of all NP decision problems. It is here argued, however, that NP is not of necessity equivalent to P where it is shown that SAT is contained in P. This due to a paradox, of nature addressed by both Godel and Russell, in regards to the P-NP system in total.
Probabilistic Reversible Automata and Quantum Automata
Venue: arXiv cs.CC 2002
Year: 2002

To study relationship between quantum finite automata and probabilistic finite automata, we introduce a notion of probabilistic reversible automata (PRA, or doubly stochastic automata). We find that there is a strong relationship between different possible models of PRA and corresponding models of quantum finite automata. We also propose a classification of reversible finite 1-way automata.
Reasoning about Evolving Nonmonotonic Knowledge Bases
Venue: arXiv cs.AI 2002
Year: 2002

Recently, several approaches to updating knowledge bases modeled as extended logic programs have been introduced, ranging from basic methods to incorporate (sequences of) sets of rules into a logic program, to more elaborate methods which use an update policy for specifying how updates must be incorporated. In this paper, we introduce a framework for reasoning about evolving knowledge bases, which are represented as extended logic programs and maintained by an update policy. We first describe a formal model which captures various update approaches, and we define a logical language for expressing properties of evolving knowledge bases. We then investigate semantical and computational properties of our framework, where we focus on properties of knowledge states with respect to the canonical reasoning task of whether a given formula holds on a given evolving knowledge base. In particular, we present finitary characterizations of the evolution for certain classes of framework instances, which can be exploited for obtaining decidability results. In more detail, we characterize the complexity of reasoning for some meaningful classes of evolving knowledge bases, ranging from polynomial to double exponential space complexity.
Compilability of Abduction
Venue: arXiv cs.AI 2002
Year: 2002

Abduction is one of the most important forms of reasoning; it has been successfully applied to several practical problems such as diagnosis. In this paper we investigate whether the computational complexity of abduction can be reduced by an appropriate use of preprocessing. This is motivated by the fact that part of the data of the problem (namely, the set of all possible assumptions and the theory relating assumptions and manifestations) are often known before the rest of the problem. In this paper, we show some complexity results about abduction when compilation is allowed.
A Note on Induction Schemas in Bounded Arithmetic
Venue: arXiv cs.LO 2002
Year: 2002

As is well known, Buss' theory of bounded arithmetic $S^{1}_{2}$ proves $Σ_{0}^{b}(Σ_{1}^{b})-LIND$; however, we show that Allen's $D_{2}^{1}$ does not prove $Σ_{0}^{b}(Σ_{1}^{b})-LLIND$ unless $P = NC$. We also give some interesting alternative axiomatisations of $S^{1}_{2}$.
Selection of future events from a time series in relation to estimations of forecasting uncertainty
Venue: arXiv cs.NE 2002
Year: 2002

A new general procedure for a priori selection of more predictable events from a time series of observed variable is proposed. The procedure is applicable to time series which contains different types of events that feature significantly different predictability, or, in other words, to heteroskedastic time series. A priori selection of future events in accordance to expected uncertainty of their forecasts may be helpful for making practical decisions. The procedure first implies creation of two neural network based forecasting models, one of which is aimed at prediction of conditional mean and other - conditional dispersion, and then elaboration of the rule for future event selection into groups of more and less predictable events. The method is demonstrated and tested by the example of the computer generated time series, and then applied to the real world time series, Dow Jones Industrial Average index.
Current state of the Sonix -- the IBR-2 instrument control software and plans for future developments
Venue: arXiv cs.HC 2002
Year: 2002

The Sonix is the main control software for the IBR-2 instruments. This is a modular configurable and flexible system created using the Varman (real time database) and the X11/OS9 graphical package in the OS-9 environment. In the last few years we were mostly focused on making this system more reliable and user friendly. Because the VME hardware and software upgrade is rather expensive we would like to replace existing VME + OS9 control computers with the PC+Windows XP ones in the future. This could be done with the help of VME-PCI adapters.
A New Interpretation of Amdahl's Law and Geometric Scalability
Venue: arXiv cs.DC 2002
Year: 2002

The multiprocessor effect refers to the loss of computing cycles due to processing overhead. Amdahl's law and the Multiprocessing Factor (MPF) are two scaling models used in industry and academia for estimating multiprocessor capacity in the presence of this multiprocessor effect. Both models express different laws of diminishing returns. Amdahl's law identifies diminishing processor capacity with a fixed degree of serialization in the workload, while the MPF model treats it as a constant geometric ratio. The utility of both models for performance evaluation stems from the presence of a single parameter that can be determined easily from a small set of benchmark measurements. This utility, however, is marred by a dilemma. The two models produce different results, especially for large processor configurations that are so important for today's applications. The question naturally arises: Which of these two models is the correct one to use? Ignoring this question merely reduces capacity prediction to arbitrary curve-fitting. Removing the dilemma requires a dynamical interpretation of these scaling models. We present a physical interpretation based on queueing theory and show that Amdahl's law corresponds to synchronous queueing in a bus model while the MPF model belongs to a Coxian server model. The latter exhibits unphysical effects such as sublinear response times hence, we caution against its use for large multiprocessor configurations.
Equivalences Among Aggregate Queries with Negation
Venue: arXiv cs.DB 2002
Year: 2002

Query equivalence is investigated for disjunctive aggregate queries with negated subgoals, constants and comparisons. A full characterization of equivalence is given for the aggregation functions count, max, sum, prod, toptwo and parity. A related problem is that of determining, for a given natural number N, whether two given queries are equivalent over all databases with at most N constants. We call this problem bounded equivalence. A complete characterization of decidability of bounded equivalence is given. In particular, it is shown that this problem is decidable for all the above aggregation functions as well as for count distinct and average. For quasilinear queries (i.e., queries where predicates that occur positively are not repeated) it is shown that equivalence can be decided in polynomial time for the aggregation functions count, max, sum, parity, prod, toptwo and average. A similar result holds for count distinct provided that a few additional conditions hold. The results are couched in terms of abstract characteristics of aggregation functions, and new proof techniques are used. Finally, the results above also imply that equivalence, under bag-set semantics, is decidable for non-aggregate queries with negation.
Intelligence and Cooperative Search by Coupled Local Minimizers
Venue: arXiv cs.AI 2002
Year: 2002

We show how coupling of local optimization processes can lead to better solutions than multi-start local optimization consisting of independent runs. This is achieved by minimizing the average energy cost of the ensemble, subject to synchronization constraints between the state vectors of the individual local minimizers. From an augmented Lagrangian which incorporates the synchronization constraints both as soft and hard constraints, a network is derived wherein the local minimizers interact and exchange information through the synchronization constraints. From the viewpoint of neural networks, the array can be considered as a Lagrange programming network for continuous optimization and as a cellular neural network (CNN). The penalty weights associated with the soft state synchronization constraints follow from the solution to a linear program. This expresses that the energy cost of the ensemble should maximally decrease. In this way successful local minimizers can implicitly impose their state to the others through a mechanism of master-slave dynamics resulting into a cooperative search mechanism. Improved information spreading within the ensemble is obtained by applying the concept of small-world networks. This work suggests, in an interdisciplinary context, the importance of information exchange and state synchronization within ensembles, towards issues as evolution, collective behaviour, optimality and intelligence.
Evaluation of the Performance of the Markov Blanket Bayesian Classifier Algorithm
Venue: arXiv cs.LG 2002
Year: 2002

The Markov Blanket Bayesian Classifier is a recently-proposed algorithm for construction of probabilistic classifiers. This paper presents an empirical comparison of the MBBC algorithm with three other Bayesian classifiers: Naive Bayes, Tree-Augmented Naive Bayes and a general Bayesian network. All of these are implemented using the K2 framework of Cooper and Herskovits. The classifiers are compared in terms of their performance (using simple accuracy measures and ROC curves) and speed, on a range of standard benchmark data sets. It is concluded that MBBC is competitive in terms of speed and accuracy with the other algorithms considered.
Maximing the Margin in the Input Space
Venue: arXiv cs.AI 2002
Year: 2002

We propose a novel criterion for support vector machine learning: maximizing the margin in the input space, not in the feature (Hilbert) space. This criterion is a discriminative version of the principal curve proposed by Hastie et al. The criterion is appropriate in particular when the input space is already a well-designed feature space with rather small dimensionality. The definition of the margin is generalized in order to represent prior knowledge. The derived algorithm consists of two alternating steps to estimate the dual parameters. Firstly, the parameters are initialized by the original SVM. Then one set of parameters is updated by Newton-like procedure, and the other set is updated by solving a quadratic programming problem. The algorithm converges in a few steps to a local optimum under mild conditions and it preserves the sparsity of support vectors. Although the complexity to calculate temporal variables increases the complexity to solve the quadratic programming problem for each step does not change. It is also shown that the original SVM can be seen as a special case. We further derive a simplified algorithm which enables us to use the existing code for the original SVM.
Improved Phylogeny Comparisons: Non-Shared Edges Nearest Neighbor Interchanges, and Subtree Transfers
Venue: arXiv cs.DS 2002
Year: 2002

The number of the non-shared edges of two phylogenies is a basic measure of the dissimilarity between the phylogenies. The non-shared edges are also the building block for approximating a more sophisticated metric called the nearest neighbor interchange (NNI) distance. In this paper, we give the first subquadratic-time algorithm for finding the non-shared edges, which are then used to speed up the existing approximating algorithm for the NNI distance from $O(n^2)$ time to $O(n \log n)$ time. Another popular distance metric for phylogenies is the subtree transfer (STT) distance. Previous work on computing the STT distance considered degree-3 trees only. We give an approximation algorithm for the STT distance for degree-$d$ trees with arbitrary $d$ and with generalized STT operations.
Intersection Types and Lambda Theories
Venue: arXiv cs.LO 2002
Year: 2002

We illustrate the use of intersection types as a semantic tool for showing properties of the lattice of lambda theories. Relying on the notion of easy intersection type theory we successfully build a filter model in which the interpretation of an arbitrary simple easy term is any filter which can be described in an uniform way by a predicate. This allows us to prove the consistency of a well-know lambda theory: this consistency has interesting consequences on the algebraic structure of the lattice of lambda theories.
Probabilistic Parsing Strategies
Venue: arXiv cs.CL 2002
Year: 2002

We present new results on the relation between purely symbolic context-free parsing strategies and their probabilistic counter-parts. Such parsing strategies are seen as constructions of push-down devices from grammars. We show that preservation of probability distribution is possible under two conditions, viz. the correct-prefix property and the property of strong predictiveness. These results generalize existing results in the literature that were obtained by considering parsing strategies in isolation. From our general results we also derive negative results on so-called generalized LR parsing.