OpenRaiser/Intern-Atlas huggingface dataset:
Orthonormal RBF wavelet and ridgelet-like series and transforms for high-dimensional problems
Venue: arXiv cs.SC 2002
Year: 2002

This paper developed a systematic strategy establishing RBF on the wavelet analysis, which includes continuous and discrete RBF orthonormal wavelet transforms respectively in terms of singular fundamental solutions and nonsingular general solutions of differential operators. In particular, the harmonic Bessel RBF transforms were presented for high-dimensional data processing. It was also found that the kernel functions of convection-diffusion operator are feasible to construct some stable ridgelet-like RBF transforms. We presented time-space RBF transforms based on non-singular solution and fundamental solution of time-dependent differential operators. The present methodology was further extended to analysis of some known RBFs such as the MQ, Gaussian and pre-wavelet kernel RBFs.
Computing Elementary Symmetric Polynomials with a Sublinear Number of Multiplications
Venue: arXiv cs.CC 2002
Year: 2002

Elementary symmetric polynomials $S_n^k$ are used as a benchmark for the bounded-depth arithmetic circuit model of computation. In this work we prove that $S_n^k$ modulo composite numbers $m=p_1p_2$ can be computed with much fewer multiplications than over any field, if the coefficients of monomials $x_{i_1}x_{i_2}... x_{i_k}$ are allowed to be 1 either mod $p_1$ or mod $p_2$ but not necessarily both. More exactly, we prove that for any constant $k$ such a representation of $S_n^k$ can be computed modulo $p_1p_2$ using only $\exp(O(\sqrt{\log n}\log\log n))$ multiplications on the most restricted depth-3 arithmetic circuits, for $\min({p_1,p_2})>k!$. Moreover, the number of multiplications remain sublinear while $k=O(\log\log n).$ In contrast, the well-known Graham-Pollack bound yields an $n-1$ lower bound for the number of multiplications even for the exact computation (not the representation) of $S_n^2$. Our results generalize for other non-prime power composite moduli as well. The proof uses the famous BBR-polynomial of Barrington, Beigel and Rudich.
Definitions of distance function in radial basis function approach
Venue: arXiv cs.CE 2002
Year: 2002

Very few studies involve how to construct the efficient RBFs by means of problem features. Recently the present author presented general solution RBF (GS-RBF) methodology to create operator-dependent RBFs successfully [1]. On the other hand, the normal radial basis function (RBF) is defined via Euclidean space distance function or the geodesic distance [2]. This purpose of this note is to redefine distance function in conjunction with problem features, which include problem-dependent and time-space distance function.
On Concise Encodings of Preferred Extensions
Venue: arXiv cs.AI 2002
Year: 2002

Much work on argument systems has focussed on preferred extensions which define the maximal collectively defensible subsets. Identification and enumeration of these subsets is (under the usual assumptions) computationally demanding. We consider approaches to deciding if a subset S is a preferred extension which query a representations encoding all such extensions, so that the computational effort is invested once only (for the initial enumeration) rather than for each separate query.
Reducing the Computational Requirements of the Differential Quadrature Method
Venue: arXiv cs.CE 2002
Year: 2002

This paper shows that the weighting coefficient matrices of the differential quadrature method (DQM) are centrosymmetric or skew-centrosymmetric if the grid spacings are symmetric irrespective of whether they are equal or unequal. A new skew centrosymmetric matrix is also discussed. The application of the properties of centrosymmetric and skew centrosymmetric matrix can reduce the computational effort of the DQM for calculations of the inverse, determinant, eigenvectors and eigenvalues by 75%. This computational advantage are also demonstrated via several numerical examples.
Some logics of belief and disbelief
Venue: arXiv cs.AI 2002
Year: 2002

The introduction of explicit notions of rejection, or disbelief, into logics for knowledge representation can be justified in a number of ways. Motivations range from the need for versions of negation weaker than classical negation, to the explicit recording of classic belief contraction operations in the area of belief change, and the additional levels of expressivity obtained from an extended version of belief change which includes disbelief contraction. In this paper we present four logics of disbelief which address some or all of these intuitions. Soundness and completeness results are supplied and the logics are compared with respect to applicability and utility.
Preferred well-founded semantics for logic programming by alternating fixpoints: Preliminary report
Venue: arXiv cs.AI 2002
Year: 2002

We analyze the problem of defining well-founded semantics for ordered logic programs within a general framework based on alternating fixpoint theory. We start by showing that generalizations of existing answer set approaches to preference are too weak in the setting of well-founded semantics. We then specify some informal yet intuitive criteria and propose a semantical framework for preference handling that is more suitable for defining well-founded semantics for ordered logic programs. The suitability of the new approach is convinced by the fact that many attractive properties are satisfied by our semantics. In particular, our semantics is still correct with respect to various existing answer sets semantics while it successfully overcomes the weakness of their generalization to well-founded semantics. Finally, we indicate how an existing preferred well-founded semantics can be captured within our semantical framework.
Embedding Default Logic in Propositional Argumentation Systems
Venue: arXiv cs.AI 2002
Year: 2002

In this paper we present a transformation of finite propositional default theories into so-called propositional argumentation systems. This transformation allows to characterize all notions of Reiter's default logic in the framework of argumentation systems. As a consequence, computing extensions, or determining wether a given formula belongs to one extension or all extensions can be answered without leaving the field of classical propositional logic. The transformation proposed is linear in the number of defaults.
Introducing Dynamic Behavior in Amalgamated Knowledge Bases
Venue: arXiv cs.PL 2002
Year: 2002

The problem of integrating knowledge from multiple and heterogeneous sources is a fundamental issue in current information systems. In order to cope with this problem, the concept of mediator has been introduced as a software component providing intermediate services, linking data resources and application programs, and making transparent the heterogeneity of the underlying systems. In designing a mediator architecture, we believe that an important aspect is the definition of a formal framework by which one is able to model integration according to a declarative style. To this purpose, the use of a logical approach seems very promising. Another important aspect is the ability to model both static integration aspects, concerning query execution, and dynamic ones, concerning data updates and their propagation among the various data sources. Unfortunately, as far as we know, no formal proposals for logically modeling mediator architectures both from a static and dynamic point of view have already been developed. In this paper, we extend the framework for amalgamated knowledge bases, presented by Subrahmanian, to deal with dynamic aspects. The language we propose is based on the Active U-Datalog language, and extends it with annotated logic and amalgamation concepts. We model the sources of information and the mediator (also called supervisor) as Active U-Datalog deductive databases, thus modeling queries, transactions, and active rules, interpreted according to the PARK semantics. By using active rules, the system can efficiently perform update propagation among different databases. The result is a logical environment, integrating active and deductive rules, to perform queries and update propagation in an heterogeneous mediated framework.
Paraconsistent Reasoning via Quantified Boolean Formulas,I: Axiomatising Signed Systems
Venue: arXiv cs.LO 2002
Year: 2002

Signed systems were introduced as a general, syntax-independent framework for paraconsistent reasoning, that is, non-trivialised reasoning from inconsistent information. In this paper, we show how the family of corresponding paraconsistent consequence relations can be axiomatised by means of quantified Boolean formulas. This approach has several benefits. First, it furnishes an axiomatic specification of paraconsistent reasoning within the framework of signed systems. Second, this axiomatisation allows us to identify upper bounds for the complexity of the different signed consequence relations. We strengthen these upper bounds by providing strict complexity results for the considered reasoning tasks. Finally, we obtain an implementation of different forms of paraconsistent reasoning by appeal to the existing system QUIP.
Answer Sets for Consistent Query Answering in Inconsistent Databases
Venue: arXiv cs.DB 2002
Year: 2002

A relational database is inconsistent if it does not satisfy a given set of integrity constraints. Nevertheless, it is likely that most of the data in it is consistent with the constraints. In this paper we apply logic programming based on answer sets to the problem of retrieving consistent information from a possibly inconsistent database. Since consistent information persists from the original database to every of its minimal repairs, the approach is based on a specification of database repairs using disjunctive logic programs with exceptions, whose answer set semantics can be represented and computed by systems that implement stable model semantics. These programs allow us to declare persistence by defaults and repairing changes by exceptions. We concentrate mainly on logic programs for binary integrity constraints, among which we find most of the integrity constraints found in practice.
Theoretical limit of the compression for the information
Venue: arXiv cs.CR 2002
Year: 2002

The pit recording of file, the coefficient of compression are introduced. The theoretical limit of the information compression as minimal coefficient of compression for the given length of alphabet are found.
Offline Specialisation in Prolog Using a Hand-Written Compiler Generator
Venue: arXiv cs.PL 2002
Year: 2002

The so called ``cogen approach'' to program specialisation, writing a compiler generator instead of a specialiser, has been used with considerable success in partial evaluation of both functional and imperative languages. This paper demonstrates that the cogen approach is also applicable to the specialisation of logic programs (also called partial deduction) and leads to effective specialisers. Moreover, using good binding-time annotations, the speed-ups of the specialised programs are comparable to the speed-ups obtained with online specialisers. The paper first develops a generic approach to offline partial deduction and then a specific offline partial deduction method, leading to the offline system LIX for pure logic programs. While this is a usable specialiser by itself, it is used to develop the cogen system LOGEN. Given a program, a specification of what inputs will be static, and an annotation specifying which calls should be unfolded, LOGEN generates a specialised specialiser for the program at hand. Running this specialiser with particular values for the static inputs results in the specialised program. While this requires two steps instead of one, the efficiency of the specialisation process is improved in situations where the same program is specialised multiple times. The paper also presents and evaluates an automatic binding-time analysis that is able to derive the annotations. While the derived annotations are still suboptimal compared to hand-crafted ones, they enable non-expert users to use the LOGEN system in a fully automated way. Finally, LOGEN is extended so as to directly support a large part of Prolog's declarative and non-declarative features and so as to be able to perform so called mixline specialisations.
TerraService.NET: An Introduction to Web Services
Venue: arXiv cs.DL 2002
Year: 2002

This article explores the design and construction of a geo-spatial Internet web service application from the host web site perspective and from the perspective of an application using the web service. The TerraService.NET web service was added to the popular TerraServer database and web site with no major structural changes to the database. The article discusses web service design, implementation, and deployment concepts and design guidelines. Web services enable applications that aggregate and interact with information and resources from Internet-scale distributed servers. The article presents the design of two USDA applications that interoperate with database and web service resources in Fort Collins Colorado and the TerraService web service located in Tukwila Washington.
Does P = NP?
Venue: arXiv cs.CC 2002
Year: 2002

This paper considers the question of P = NP in context of the polynomial time SAT algorithm. It posits proposition dependent on existence of conjectured problem that even where the algorithm is shown to solve SAT in polynomial time it remains theoretically possible for there to yet exist a non-deterministically polynomial (NP) problem for which the algorithm does not provide a polynomial (P) time solution. The paper leaves open as subject of continuing research the question of existence of instance of conjectured problem.
Implicit Simulations using Messaging Protocols
Venue: arXiv cs.DC 2002
Year: 2002

A novel algorithm for performing parallel, distributed computer simulations on the Internet using IP control messages is introduced. The algorithm employs carefully constructed ICMP packets which enable the required computations to be completed as part of the standard IP communication protocol. After providing a detailed description of the algorithm, experimental applications in the areas of stochastic neural networks and deterministic cellular automata are discussed. As an example of the algorithms potential power, a simulation of a deterministic cellular automaton involving 10^5 Internet connected devices was performed.
The STRESS Method for Boundary-point Performance Analysis of End-to-end Multicast Timer-Suppression Mechanisms
Venue: arXiv cs.NI 2002
Year: 2002

Evaluation of Internet protocols usually uses random scenarios or scenarios based on designers' intuition. Such approach may be useful for average-case analysis but does not cover boundary-point (worst or best-case) scenarios. To synthesize boundary-point scenarios a more systematic approach is needed.In this paper, we present a method for automatic synthesis of worst and best case scenarios for protocol boundary-point evaluation. Our method uses a fault-oriented test generation (FOTG) algorithm for searching the protocol and system state space to synthesize these scenarios. The algorithm is based on a global finite state machine (FSM) model. We extend the algorithm with timing semantics to handle end-to-end delays and address performance criteria. We introduce the notion of a virtual LAN to represent delays of the underlying multicast distribution tree. The algorithms used in our method utilize implicit backward search using branch and bound techniques and start from given target events. This aims to reduce the search complexity drastically. As a case study, we use our method to evaluate variants of the timer suppression mechanism, used in various multicast protocols, with respect to two performance criteria: overhead of response messages and response time. Simulation results for reliable multicast protocols show that our method provides a scalable way for synthesizing worst-case scenarios automatically. Results obtained using stress scenarios differ dramatically from those obtained through average-case analyses. We hope for our method to serve as a model for applying systematic scenario generation to other multicast protocols.
Cooperation between Pronoun and Reference Resolution for Unrestricted Texts
Venue: arXiv cs.CL 2002
Year: 2002

Anaphora resolution is envisaged in this paper as part of the reference resolution process. A general open architecture is proposed, which can be particularized and configured in order to simulate some classic anaphora resolution methods. With the aim of improving pronoun resolution, the system takes advantage of elementary cues about characters of the text, which are represented through a particular data structure. In its most robust configuration, the system uses only a general lexicon, a local morpho-syntactic parser and a dictionary of synonyms. A short comparative corpus analysis shows that narrative texts are the most suitable for testing such a system.
Proving correctness of Timed Concurrent Constraint Programs
Venue: arXiv cs.LO 2002
Year: 2002

A temporal logic is presented for reasoning about the correctness of timed concurrent constraint programs. The logic is based on modalities which allow one to specify what a process produces as a reaction to what its environment inputs. These modalities provide an assumption/commitment style of specification which allows a sound and complete compositional axiomatization of the reactive behavior of timed concurrent constraint programs.
Introduction to the CoNLL-2002 Shared Task: Language-Independent Named Entity Recognition
Venue: arXiv cs.CL 2002
Year: 2002

We describe the CoNLL-2002 shared task: language-independent named entity recognition. We give background information on the data sets and the evaluation method, present a general overview of the systems that have taken part in the task and discuss their performance.
Analysis of a Cone-Based Distributed Topology Control Algorithm for Wireless Multi-hop Networks
Venue: arXiv cs.NI 2002
Year: 2002

The topology of a wireless multi-hop network can be controlled by varying the transmission power at each node. In this paper, we give a detailed analysis of a cone-based distributed topology control algorithm. This algorithm, introduced in [16], does not assume that nodes have GPS information available; rather it depends only on directional information. Roughly speaking, the basic idea of the algorithm is that a node $u$ transmits with the minimum power $p_{u,α}$ required to ensure that in every cone of degree $α$ around $u$, there is some node that $u$ can reach with power $p_{u,α}$. We show that taking $α= 5π/6$ is a necessary and sufficient condition to guarantee that network connectivity is preserved. More precisely, if there is a path from $s$ to $t$ when every node communicates at maximum power, then, if $α<= 5π/6$, there is still a path in the smallest symmetric graph $G_α$ containing all edges $(u,v)$ such that $u$ can communicate with $v$ using power $p_{u,α}$. On the other hand, if $α> 5π/6$, connectivity is not necessarily preserved. We also propose a set of optimizations that further reduce power consumption and prove that they retain network connectivity. Dynamic reconfiguration in the presence of failures and mobility is also discussed. Simulation results are presented to demonstrate the effectiveness of the algorithm and the optimizations.
Mapping the Gnutella Network: Properties of Large-Scale Peer-to-Peer Systems and Implications for System Design
Venue: arXiv cs.DC 2002
Year: 2002

Despite recent excitement generated by the peer-to-peer (P2P) paradigm and the surprisingly rapid deployment of some P2P applications, there are few quantitative evaluations of P2P systems behavior. The open architecture, achieved scale, and self-organizing structure of the Gnutella network make it an interesting P2P architecture to study. Like most other P2P applications, Gnutella builds, at the application level, a virtual network with its own routing mechanisms. The topology of this virtual network and the routing mechanisms used have a significant influence on application properties such as performance, reliability, and scalability. We have built a "crawler" to extract the topology of Gnutella's application level network. In this paper we analyze the topology graph and evaluate generated network traffic. Our two major findings are that: (1) although Gnutella is not a pure power-law network, its current configuration has the benefits and drawbacks of a power-law structure, and (2) the Gnutella virtual network topology does not match well the underlying Internet topology, hence leading to ineffective use of the physical networking infrastructure. These findings guide us to propose changes to the Gnutella protocol and implementations that may bring significant performance and scalability improvements. We believe that our findings as well as our measurement and analysis techniques have broad applicability to P2P systems and provide unique insights into P2P system design tradeoffs.
Extremal Optimization: an Evolutionary Local-Search Algorithm
Venue: arXiv cs.NE 2002
Year: 2002

A recently introduced general-purpose heuristic for finding high-quality solutions for many hard optimization problems is reviewed. The method is inspired by recent progress in understanding far-from-equilibrium phenomena in terms of {\em self-organized criticality,} a concept introduced to describe emergent complexity in physical systems. This method, called {\em extremal optimization,} successively replaces the value of extremely undesirable variables in a sub-optimal solution with new, random ones. Large, avalanche-like fluctuations in the cost function self-organize from this dynamics, effectively scaling barriers to explore local optima in distant neighborhoods of the configuration space while eliminating the need to tune parameters. Drawing upon models used to simulate the dynamics of granular media, evolution, or geology, extremal optimization complements approximation methods inspired by equilibrium statistical physics, such as {\em simulated annealing}. It may be but one example of applying new insights into {\em non-equilibrium phenomena} systematically to hard optimization problems. This method is widely applicable and so far has proved competitive with -- and even superior to -- more elaborate general-purpose heuristics on testbeds of constrained optimization problems with up to $10^5$ variables, such as bipartitioning, coloring, and satisfiability. Analysis of a suitable model predicts the only free parameter of the method in accordance with all experimental results.
Cellular automata and communication complexity
Venue: arXiv cs.CC 2002
Year: 2002

The model of cellular automata is fascinating because very simple local rules can generate complex global behaviors. The relationship between local and global function is subject of many studies. We tackle this question by using results on communication complexity theory and, as a by-product, we provide (yet another) classification of cellular automata.