OpenRaiser/Intern-Atlas huggingface dataset:
A Scalable Architecture for Harvest-Based Digital Libraries - The ODU/Southampton Experiments
Venue: arXiv cs.DL 2002
Year: 2002

This paper discusses the requirements of current and emerging applications based on the Open Archives Initiative (OAI) and emphasizes the need for a common infrastructure to support them. Inspired by HTTP proxy, cache, gateway and web service concepts, a design for a scalable and reliable infrastructure that aims at satisfying these requirements is presented. Moreover it is shown how various applications can exploit the services included in the proposed infrastructure. The paper concludes by discussing the current status of several prototype implementations.
Unsupervised Learning of Morphology without Morphemes
Venue: arXiv cs.CL 2002
Year: 2002

The first morphological learner based upon the theory of Whole Word Morphology Ford et al. (1997) is outlined, and preliminary evaluation results are presented. The program, Whole Word Morphologizer, takes a POS-tagged lexicon as input, induces morphological relationships without attempting to discover or identify morphemes, and is then able to generate new words beyond the learning sample. The accuracy (precision) of the generated new words is as high as 80% using the pure Whole Word theory, and 92% after a post-hoc adjustment is added to the routine.
Complexity of Mechanism Design
Venue: arXiv cs.GT 2002
Year: 2002

The aggregation of conflicting preferences is a central problem in multiagent systems. The key difficulty is that the agents may report their preferences insincerely. Mechanism design is the art of designing the rules of the game so that the agents are motivated to report their preferences truthfully and a (socially) desirable outcome is chosen. We propose an approach where a mechanism is automatically created for the preference aggregation setting at hand. This has several advantages, but the downside is that the mechanism design optimization problem needs to be solved anew each time. Focusing on settings where side payments are not possible, we show that the mechanism design problem is NP-complete for deterministic mechanisms. This holds both for dominant-strategy implementation and for Bayes-Nash implementation. We then show that if we allow randomized mechanisms, the mechanism design problem becomes tractable. In other words, the coordinator can tackle the computational complexity introduced by its uncertainty about the agents' preferences by making the agents face additional uncertainty. This comes at no loss, and in some cases at a gain, in the (social) objective.
Designing Multi-Commodity Flow Trees
Venue: arXiv cs.DS 2002
Year: 2002

The traditional multi-commodity flow problem assumes a given flow network in which multiple commodities are to be maximally routed in response to given demands. This paper considers the multi-commodity flow network-design problem: given a set of multi-commodity flow demands, find a network subject to certain constraints such that the commodities can be maximally routed. This paper focuses on the case when the network is required to be a tree. The main result is an approximation algorithm for the case when the tree is required to be of constant degree. The algorithm reduces the problem to the minimum-weight balanced-separator problem; the performance guarantee of the algorithm is within a factor of 4 of the performance guarantee of the balanced-separator procedure. If Leighton and Rao's balanced-separator procedure is used, the performance guarantee is O(log n). This improves the O(log^2 n) approximation factor that is trivial to obtain by a direct application of the balanced-separator method.
Building Space-Time Meshes over Arbitrary Spatial Domains
Venue: arXiv cs.CG 2002
Year: 2002

We present an algorithm to construct meshes suitable for space-time discontinuous Galerkin finite-element methods. Our method generalizes and improves the `Tent Pitcher' algorithm of Üngör and Sheffer. Given an arbitrary simplicially meshed domain M of any dimension and a time interval [0,T], our algorithm builds a simplicial mesh of the space-time domain Mx[0,T], in constant time per element. Our algorithm avoids the limitations of previous methods by carefully adapting the durations of space-time elements to the local quality and feature size of the underlying space mesh.
Handling Defeasibilities in Action Domains
Venue: arXiv cs.AI 2002
Year: 2002

Representing defeasibility is an important issue in common sense reasoning. In reasoning about action and change, this issue becomes more difficult because domain and action related defeasible information may conflict with general inertia rules. Furthermore, different types of defeasible information may also interfere with each other during the reasoning. In this paper, we develop a prioritized logic programming approach to handle defeasibilities in reasoning about action. In particular, we propose three action languages {\cal AT}^{0}, {\cal AT}^{1} and {\cal AT}^{2} which handle three types of defeasibilities in action domains named defeasible constraints, defeasible observations and actions with defeasible and abnormal effects respectively. Each language with a higher superscript can be viewed as an extension of the language with a lower superscript. These action languages inherit the simple syntax of {\cal A} language but their semantics is developed in terms of transition systems where transition functions are defined based on prioritized logic programs. By illustrating various examples, we show that our approach eventually provides a powerful mechanism to handle various defeasibilities in temporal prediction and postdiction. We also investigate semantic properties of these three action languages and characterize classes of action domains that present more desirable solutions in reasoning about action within the underlying action languages.
Robust Feature Selection by Mutual Information Distributions
Venue: arXiv cs.AI 2002
Year: 2002

Mutual information is widely used in artificial intelligence, in a descriptive way, to measure the stochastic dependence of discrete random variables. In order to address questions such as the reliability of the empirical value, one must consider sample-to-population inferential approaches. This paper deals with the distribution of mutual information, as obtained in a Bayesian framework by a second-order Dirichlet prior distribution. The exact analytical expression for the mean and an analytical approximation of the variance are reported. Asymptotic approximations of the distribution are proposed. The results are applied to the problem of selecting features for incremental learning and classification of the naive Bayes classifier. A fast, newly defined method is shown to outperform the traditional approach based on empirical mutual information on a number of real data sets. Finally, a theoretical development is reported that allows one to efficiently extend the above methods to incomplete samples in an easy and effective way.
Performance Comparison of Function Evaluation Methods
Venue: arXiv cs.SC 2002
Year: 2002

We perform a comparison of the performance and efficiency of four different function evaluation methods: black-box functions, binary trees, $n$-ary trees and string parsing. The test consists in evaluating 8 different functions of two variables $x,y$ over 5000 floating point values of the pair $(x,y)$. The outcome of the test indicates that the $n$-ary tree representation of algebraic expressions is the fastest method, closely followed by black-box function method, then by binary trees and lastly by string parsing.
A Statistical Physics Perspective on Web Growth
Venue: arXiv cs.NI 2002
Year: 2002

Approaches from statistical physics are applied to investigate the structure of network models whose growth rules mimic aspects of the evolution of the world-wide web. We first determine the degree distribution of a growing network in which nodes are introduced one at a time and attach to an earlier node of degree k with rate A_ksim k^gamma. Very different behaviors arise for gamma<1, gamma=1, and gamma>1. We also analyze the degree distribution of a heterogeneous network, the joint age-degree distribution, the correlation between degrees of neighboring nodes, as well as global network properties. An extension to directed networks is then presented. By tuning model parameters to reasonable values, we obtain distinct power-law forms for the in-degree and out-degree distributions with exponents that are in good agreement with current data for the web. Finally, a general growth process with independent introduction of nodes and links is investigated. This leads to independently growing sub-networks that may coalesce with other sub-networks. General results for both the size distribution of sub-networks and the degree distribution are obtained.
Fast Deterministic Consensus in a Noisy Environment
Venue: arXiv cs.DS 2002
Year: 2002

It is well known that the consensus problem cannot be solved deterministically in an asynchronous environment, but that randomized solutions are possible. We propose a new model, called noisy scheduling, in which an adversarial schedule is perturbed randomly, and show that in this model randomness in the environment can substitute for randomness in the algorithm. In particular, we show that a simplified, deterministic version of Chandra's wait-free shared-memory consensus algorithm (PODC, 1996, pp. 166-175) solves consensus in time at most logarithmic in the number of active processes. The proof of termination is based on showing that a race between independent delayed renewal processes produces a winner quickly. In addition, we show that the protocol finishes in constant time using quantum and priority-based scheduling on a uniprocessor, suggesting that it is robust against the choice of model over a wide range.
Knowledge management for enterprises (Wissensmanagement fuer Unternehmen)
Venue: arXiv cs.IR 2002
Year: 2002

Although knowledge is one of the most valuable resource of enterprises and an important production and competition factor, this intellectual potential is often used (or maintained) only inadequate by the enterprises. Therefore, in a globalised and growing market the optimal usage of existing knowledge represents a key factor for enterprises of the future. Here, knowledge management systems should engage facilitating. Because geographically far distributed establishments cause, however, a distributed system, this paper should uncover the spectrum connected with it and present a possible basic approach which is based on ontologies and modern, platform independent technologies. Last but not least this attempt, as well as general questions of the knowledge management, are discussed.
A correct proof of the heuristic GCD algorithm
Venue: arXiv cs.SC 2002
Year: 2002

In this note, we fill a gap in the proof of the heuristic GCD in the multivariate case made by Char, Geddes and Gonnet (JSC 1989) and give some additionnal information on this method.
Applying a Hybrid Query Translation Method to Japanese/English Cross-Language Patent Retrieval
Venue: arXiv cs.CL 2002
Year: 2002

This paper applies an existing query translation method to cross-language patent retrieval. In our method, multiple dictionaries are used to derive all possible translations for an input query, and collocational statistics are used to resolve translation ambiguity. We used Japanese/English parallel patent abstracts to perform comparative experiments, where our method outperformed a simple dictionary-based query translation method, and achieved 76% of monolingual retrieval in terms of average precision.
PRIME: A System for Multi-lingual Patent Retrieval
Venue: arXiv cs.CL 2002
Year: 2002

Given the growing number of patents filed in multiple countries, users are interested in retrieving patents across languages. We propose a multi-lingual patent retrieval system, which translates a user query into the target language, searches a multilingual database for patents relevant to the query, and improves the browsing efficiency by way of machine translation and clustering. Our system also extracts new translations from patent families consisting of comparable patents, to enhance the translation dictionary.
Optimally cutting a surface into a disk
Venue: arXiv cs.CG 2002
Year: 2002

We consider the problem of cutting a set of edges on a polyhedral manifold surface, possibly with boundary, to obtain a single topological disk, minimizing either the total number of cut edges or their total length. We show that this problem is NP-hard, even for manifolds without boundary and for punctured spheres. We also describe an algorithm with running time n^{O(g+k)}, where n is the combinatorial complexity, g is the genus, and k is the number of boundary components of the input surface. Finally, we describe a greedy algorithm that outputs a O(log^2 g)-approximation of the minimum cut graph in O(g^2 n log n) time.
Efficient Deep Processing of Japanese
Venue: arXiv cs.CL 2002
Year: 2002

We present a broad coverage Japanese grammar written in the HPSG formalism with MRS semantics. The grammar is created for use in real world applications, such that robustness and performance issues play an important role. It is connected to a POS tagging and word segmentation tool. This grammar is being developed in a multilingual context, requiring MRS structures that are easily comparable across languages.
Agent Programming with Declarative Goals
Venue: arXiv cs.AI 2002
Year: 2002

A long and lasting problem in agent research has been to close the gap between agent logics and agent programming frameworks. The main reason for this problem of establishing a link between agent logics and agent programming frameworks is identified and explained by the fact that agent programming frameworks have not incorporated the concept of a `declarative goal'. Instead, such frameworks have focused mainly on plans or `goals-to-do' instead of the end goals to be realised which are also called `goals-to-be'. In this paper, a new programming language called GOAL is introduced which incorporates such declarative goals. The notion of a `commitment strategy' - one of the main theoretical insights due to agent logics, which explains the relation between beliefs and goals - is used to construct a computational semantics for GOAL. Finally, a proof theory for proving properties of GOAL agents is introduced. Thus, we offer a complete theory of agent programming in the sense that our theory provides both for a programming framework and a programming logic for such agents. An example program is proven correct by using this programming logic.
Relationship between boundary integral equation and radial basis function
Venue: arXiv cs.CE 2002
Year: 2002

This paper aims to survey our recent work relating to the radial basis function (RBF) from some new views of points. In the first part, we established the RBF on numerical integration analysis based on an intrinsic relationship between the Green's boundary integral representation and RBF. It is found that the kernel function of integral equation is important to create efficient RBF. The fundamental solution RBF (FS-RBF) was presented as a novel strategy constructing operator-dependent RBF. We proposed a conjecture formula featuring the dimension affect on error bound to show the independent-dimension merit of the RBF techniques. We also discussed wavelet RBF, localized RBF schemes, and the influence of node placement on the RBF solution accuracy. The centrosymmetric matrix structure of the RBF interpolation matrix under symmetric node placing is proved. The second part of this paper is concerned with the boundary knot method (BKM), a new boundary-only, meshless, spectral convergent, integration-free RBF collocation technique. The BKM was tested to the Helmholtz, Laplace, linear and nonlinear convection-diffusion problems. In particular, we introduced the response knot-dependent nonsingular general solution to calculate varying-parameter and nonlinear steady convection-diffusion problems very efficiently. By comparing with the multiple dual reciprocity method, we discussed the completeness issue of the BKM. Finally, the nonsingular solutions for some known differential operators were given in appendix. Also we expanded the RBF concepts by introducing time-space RBF for transient problems.
Information Measures in Detecting and Recognizing Symmetries
Venue: arXiv cs.OH 2002
Year: 2002

This paper presents a method to detect and recognize symmetries in Boolean functions. The idea is to use information theoretic measures of Boolean functions to detect sub-space of possible symmetric variables. Coupled with the new techniques of efficient estimations of information measures on Binary Decision Diagrams (BDDs) we obtain promised results in symmetries detection for large-scale functions.
"Minimal defence": a refinement of the preferred semantics for argumentation frameworks
Venue: arXiv cs.AI 2002
Year: 2002

Dung's abstract framework for argumentation enables a study of the interactions between arguments based solely on an ``attack'' binary relation on the set of arguments. Various ways to solve conflicts between contradictory pieces of information have been proposed in the context of argumentation, nonmonotonic reasoning or logic programming, and can be captured by appropriate semantics within Dung's framework. A common feature of these semantics is that one can always maximize in some sense the set of acceptable arguments. We propose in this paper to extend Dung's framework in order to allow for the representation of what we call ``restricted'' arguments: these arguments should only be used if absolutely necessary, that is, in order to support other arguments that would otherwise be defeated. We modify Dung's preferred semantics accordingly: a set of arguments becomes acceptable only if it contains a minimum of restricted arguments, for a maximum of unrestricted arguments.
Greedy Facility Location Algorithms Analyzed using Dual Fitting with Factor-Revealing LP
Venue: arXiv cs.DS 2002
Year: 2002

In this paper, we will formalize the method of dual fitting and the idea of factor-revealing LP. This combination is used to design and analyze two greedy algorithms for the metric uncapacitated facility location problem. Their approximation factors are 1.861 and 1.61, with running times of O(mlog m) and O(n^3), respectively, where n is the total number of vertices and m is the number of edges in the underlying complete bipartite graph between cities and facilities. The algorithms are used to improve recent results for several variants of the problem.
Collective Argumentation
Venue: arXiv cs.AI 2002
Year: 2002

An extension of an abstract argumentation framework, called collective argumentation, is introduced in which the attack relation is defined directly among sets of arguments. The extension turns out to be suitable, in particular, for representing semantics of disjunctive logic programs. Two special kinds of collective argumentation are considered in which the opponents can share their arguments.
Iterated revision and the axiom of recovery: a unified treatment via epistemic states
Venue: arXiv cs.AI 2002
Year: 2002

The axiom of recovery, while capturing a central intuition regarding belief change, has been the source of much controversy. We argue briefly against putative counterexamples to the axiom--while agreeing that some of their insight deserves to be preserved--and present additional recovery-like axioms in a framework that uses epistemic states, which encode preferences, as the object of revisions. This provides a framework in which iterated revision becomes possible and makes explicit the connection between iterated belief change and the axiom of recovery. We provide a representation theorem that connects the semantic conditions that we impose on iterated revision and the additional syntactical properties mentioned. We also show some interesting similarities between our framework and that of Darwiche-Pearl. In particular, we show that the intuitions underlying the controversial (C2) postulate are captured by the recovery axiom and our recovery-like postulates (the latter can be seen as weakenings of (C2).
Dual reciprocity BEM and dynamic programming filter for inverse elastodynamic problems
Venue: arXiv cs.CE 2002
Year: 2002

This paper presents the first coupling application of the dual reciprocity BEM (DRBEM) and dynamic programming filter to inverse elastodynamic problem. The DRBEM is the only BEM method, which does not require domain discretization for general linear and nonlinear dynamic problems. Since the size of numerical discretization system has a great effect on the computing effort of recursive or iterative calculations of inverse analysis, the intrinsic boundary-only merit of the DRBEM causes a considerable computational saving. On the other hand, the strengths of the dynamic programming filter lie in its mathematical simplicity, easy to program and great flexibility in the type, number and locations of measurements and unknown inputs. The combination of these two techniques is therefore very attractive for the solution of practical inverse problems. In this study, the spatial and temporal partial derivatives of the governing equation are respectively discretized first by the DRBEM and the precise integration method, and then, by using dynamic programming with regularization, dynamic load is estimated based on noisy measurements of velocity and displacement at very few locations. Numerical experiments involved with the periodic and Heaviside impact load are conducted to demonstrate the applicability, efficiency and simplicity of this strategy. The affect of noise level, regularization parameter, and measurement types on the estimation is also investigated.
Moebius-Invariant Natural Neighbor Interpolation
Venue: arXiv cs.CG 2002
Year: 2002

We propose an interpolation method that is invariant under Moebius transformations; that is, interpolation followed by transformation gives the same result as transformation followed by interpolation. The method uses natural (Delaunay) neighbors, but weights neighbors according to angles formed by Delaunay circles.
Packet delay in models of data networks
Venue: arXiv cs.NI 2002
Year: 2002

We investigate individual packet delay in a model of data networks with table-free, partial table and full table routing. We present analytical estimation for the average packet delay in a network with small partial routing table. Dependence of the delay on the size of the network and on the size of the partial routing table is examined numerically. Consequences for network scalability are discussed.
Detecting Race Conditions in Parallel Programs that Use Semaphores
Venue: arXiv cs.DS 2002
Year: 2002

We address the problem of detecting race conditions in programs that use semaphores for synchronization. Netzer and Miller showed that it is NP-complete to detect race conditions in programs that use many semaphores. We show in this paper that it remains NP-complete even if only two semaphores are used in the parallel programs. For the tractable case, i.e., using only one semaphore, we give two algorithms for detecting race conditions from the trace of executing a parallel program on p processors, where n semaphore operations are executed. The first algorithm determines in O(n) time whether a race condition exists between any two given operations. The second algorithm runs in O(np log n) time and outputs a compact representation from which one can determine in O(1) time whether a race condition exists between any two given operations. The second algorithm is near-optimal in that the running time is only O(log n) times the time required simply to write down the output.