OpenRaiser/Intern-Atlas huggingface dataset:
New advances in dual reciprocity and boundary-only RBF methods
Venue: arXiv cs.CE 2002
Year: 2002

This paper made some significant advances in the dual reciprocity and boundary-only RBF techniques. The proposed boundary knot method (BKM) is different from the standard boundary element method in a number of important aspects. Namely, it is truly meshless, exponential convergence, integration-free (of course, no singular integration), boundary-only for general problems, and leads to symmetric matrix under certain conditions (able to be extended to general cases after further modified). The BKM also avoids the artificial boundary in the method of fundamental solution. An amazing finding is that the BKM can formulate linear modeling equations for nonlinear partial differential systems with linear boundary conditions. This merit makes it circumvent all perplexing issues in the iteration solution of nonlinear equations. On the other hand, by analogy with Green's second identity, this paper also presents a general solution RBF (GSR) methodology to construct efficient RBFs in the dual reciprocity and domain-type RBF collocation methods. The GSR approach first establishes an explicit relationship between the BEM and RBF itself on the ground of the weighted residual principle. This paper also discusses the RBF convergence and stability problems within the framework of integral equation theory.
What is a Joint Goal? Games with Beliefs and Defeasible Desires
Venue: arXiv cs.MA 2002
Year: 2002

In this paper we introduce a qualitative decision and game theory based on belief (B) and desire (D) rules. We show that a group of agents acts as if it is maximizing achieved joint goals.
A Note on the DQ Analysis of Anisotropic Plates
Venue: arXiv cs.SC 2002
Year: 2002

Recently, Bert, Wang and Striz [1, 2] applied the differential quadrature (DQ) and harmonic differential quadrature (HDQ) methods to analyze static and dynamic behaviors of anisotropic plates. Their studies showed that the methods were conceptually simple and computationally efficient in comparison to other numerical techniques. Based on some recent work by the present author [3, 4], the purpose of this note is to further simplify the formulation effort and improve computing efficiency in applying the DQ and HDQ methods for these cases.
RBF-based meshless boundary knot method and boundary particle method
Venue: arXiv cs.CE 2002
Year: 2002

This paper is concerned with the two new boundary-type radial basis function collocation schemes, boundary knot method (BKM) and boundary particle method (BPM). The BKM is developed based on the dual reciprocity theorem, while the BPM employs the multiple reciprocity technique. Unlike the method of fundamental solution, the wto methods use the nonsingular general solutions instead of singular fundamental solution to circumvent the controversial artificial boundary outside physical domain. Compared with the boundary element method, both the BKM and BPM are meshfree, superconvergent, meshfree, integration free, symmetric, and mathematically simple collocation techniques for general PDEs. In particular, the BPM does not require any inner nodes for inhomogeneous problems. In this study, the accuracy and efficiency of the two methods are numerically demonstrated to some 2D, 3D Helmholtz and convection-diffusion problems under complicated geometries.
Declarative program development in Prolog with GUPU
Venue: arXiv cs.SE 2002
Year: 2002

We present GUPU, a side-effect free environment specialized for programming courses. It seamlessly guides and supports students during all phases of program development, covering specification, implementation, and program debugging. GUPU features several innovations in this area. The specification phase is supported by reference implementations augmented with diagnostic facilities. During implementation, immediate feedback from test cases and from visualization tools helps the programmer's program understanding. A set of slicing techniques narrows down programming errors. The whole process is guided by a marking system.
COINS: a constraint-based interactive solving system
Venue: arXiv cs.SE 2002
Year: 2002

This paper describes the COINS (COnstraint-based INteractive Solving) system: a conflict-based constraint solver. It helps understanding inconsistencies, simulates constraint additions and/or retractions (without any propagation), determines if a given constraint belongs to a conflict and provides diagnosis tools (e.g. why variable v cannot take value val). COINS also uses user-friendly representation of conflicts and explanations.
More Precise Yet Efficient Type Inference for Logic Programs
Venue: arXiv cs.SE 2002
Year: 2002

Type analyses of logic programs which aim at inferring the types of the program being analyzed are presented in a unified abstract interpretation-based framework. This covers most classical abstract interpretation-based type analyzers for logic programs, built on either top-down or bottom-up interpretation of the program. In this setting, we discuss the widening operator, arguably a crucial one. We present a new widening which is more precise than those previously proposed. Practical results with our analysis domain are also presented, showing that it also allows for efficient analysis.
An Architecture for Making Object-Oriented Systems Available from Prolog
Venue: arXiv cs.SE 2002
Year: 2002

It is next to impossible to develop real-life applications in just pure Prolog. With XPCE we realised a mechanism for integrating Prolog with an external object-oriented system that turns this OO system into a natural extension to Prolog. We describe the design and how it can be applied to other external OO systems.
Enhancing Usefulness of Declarative Programming Frameworks through Complete Integration
Venue: arXiv cs.SE 2002
Year: 2002

The Gisela framework for declarative programming was developed with the specific aim of providing a tool that would be useful for knowledge representation and reasoning within real-world applications. To achieve this, a complete integration into an object-oriented application development environment was used. The framework and methodology developed provide two alternative application programming interfaces (APIs): Programming using objects or programming using a traditional equational declarative style. In addition to providing complete integration, Gisela also allows extensions and modifications due to the general computation model and well-defined APIs. We give a brief overview of the declarative model underlying Gisela and we present the methodology proposed for building applications together with some real examples.
Modeling Complex Domains of Actions and Change
Venue: arXiv cs.AI 2002
Year: 2002

This paper studies the problem of modeling complex domains of actions and change within high-level action description languages. We investigate two main issues of concern: (a) can we represent complex domains that capture together different problems such as ramifications, non-determinism and concurrency of actions, at a high-level, close to the given natural ontology of the problem domain and (b) what features of such a representation can affect, and how, its computational behaviour. The paper describes the main problems faced in this representation task and presents the results of an empirical study, carried out through a series of controlled experiments, to analyze the computational performance of reasoning in these representations. The experiments compare different representations obtained, for example, by changing the basic ontology of the domain or by varying the degree of use of indirect effect laws through domain constraints. This study has helped to expose the main sources of computational difficulty in the reasoning and suggest some methodological guidelines for representing complex domains. Although our work has been carried out within one particular high-level description language, we believe that the results, especially those that relate to the problems of representation, are independent of the specific modeling language.
Value Based Argumentation Frameworks
Venue: arXiv cs.AI 2002
Year: 2002

This paper introduces the notion of value-based argumentation frameworks, an extension of the standard argumentation frameworks proposed by Dung, which are able toshow how rational decision is possible in cases where arguments derive their force from the social values their acceptance would promote.
Interpolation Theorems for Nonmonotonic Reasoning Systems
Venue: arXiv cs.AI 2002
Year: 2002

Craig's interpolation theorem (Craig 1957) is an important theorem known for propositional logic and first-order logic. It says that if a logical formula $β$ logically follows from a formula $α$, then there is a formula $γ$, including only symbols that appear in both $α,β$, such that $β$ logically follows from $γ$ and $γ$ logically follows from $α$. Such theorems are important and useful for understanding those logics in which they hold as well as for speeding up reasoning with theories in those logics. In this paper we present interpolation theorems in this spirit for three nonmonotonic systems: circumscription, default logic and logic programs with the stable models semantics (a.k.a. answer set semantics). These results give us better understanding of those logics, especially in contrast to their nonmonotonic characteristics. They suggest that some \emph{monotonicity} principle holds despite the failure of classic monotonicity for these logics. Also, they sometimes allow us to use methods for the decomposition of reasoning for these systems, possibly increasing their applicability and tractability. Finally, they allow us to build structured representations that use those logics.
Complexity of Nested Circumscription and Nested Abnormality Theories
Venue: arXiv cs.AI 2002
Year: 2002

The need for a circumscriptive formalism that allows for simple yet elegant modular problem representation has led Lifschitz (AIJ, 1995) to introduce nested abnormality theories (NATs) as a tool for modular knowledge representation, tailored for applying circumscription to minimize exceptional circumstances. Abstracting from this particular objective, we propose L_{CIRC}, which is an extension of generic propositional circumscription by allowing propositional combinations and nesting of circumscriptive theories. As shown, NATs are naturally embedded into this language, and are in fact of equal expressive capability. We then analyze the complexity of L_{CIRC} and NATs, and in particular the effect of nesting. The latter is found to be a source of complexity, which climbs the Polynomial Hierarchy as the nesting depth increases and reaches PSPACE-completeness in the general case. We also identify meaningful syntactic fragments of NATs which have lower complexity. In particular, we show that the generalization of Horn circumscription in the NAT framework remains CONP-complete, and that Horn NATs without fixed letters can be efficiently transformed into an equivalent Horn CNF, which implies polynomial solvability of principal reasoning tasks. Finally, we also study extensions of NATs and briefly address the complexity in the first-order case. Our results give insight into the ``cost'' of using L_{CIRC} (resp. NATs) as a host language for expressing other formalisms such as action theories, narratives, or spatial theories.
Dynamic Generators of Topologically Embedded Graphs
Venue: arXiv cs.DS 2002
Year: 2002

We provide a data structure for maintaining an embedding of a graph on a surface (represented combinatorially by a permutation of edges around each vertex) and computing generators of the fundamental group of the surface, in amortized time O(log n + log g(log log g)^3) per update on a surface of genus g; we can also test orientability of the surface in the same time, and maintain the minimum and maximum spanning tree of the graph in time O(log n + log^4 g) per update. Our data structure allows edge insertion and deletion as well as the dual operations; these operations may implicitly change the genus of the embedding surface. We apply similar ideas to improve the constant factor in a separator theorem for low-genus graphs, and to find in linear time a tree-decomposition of low-genus low-diameter graphs.
Evaluating Defaults
Venue: arXiv cs.AI 2002
Year: 2002

We seek to find normative criteria of adequacy for nonmonotonic logic similar to the criterion of validity for deductive logic. Rather than stipulating that the conclusion of an inference be true in all models in which the premises are true, we require that the conclusion of a nonmonotonic inference be true in ``almost all'' models of a certain sort in which the premises are true. This ``certain sort'' specification picks out the models that are relevant to the inference, taking into account factors such as specificity and vagueness, and previous inferences. The frequencies characterizing the relevant models reflect known frequencies in our actual world. The criteria of adequacy for a default inference can be extended by thresholding to criteria of adequacy for an extension. We show that this avoids the implausibilities that might otherwise result from the chaining of default inferences. The model proportions, when construed in terms of frequencies, provide a verifiable grounding of default rules, and can become the basis for generating default rules from statistics.
Repairing Inconsistent Databases: A Model-Theoretic Approach and Abductive Reasoning
Venue: arXiv cs.LO 2002
Year: 2002

In this paper we consider two points of views to the problem of coherent integration of distributed data. First we give a pure model-theoretic analysis of the possible ways to `repair' a database. We do so by characterizing the possibilities to `recover' consistent data from an inconsistent database in terms of those models of the database that exhibit as minimal inconsistent information as reasonably possible. Then we introduce an abductive application to restore the consistency of a given database. This application is based on an abductive solver (A-system) that implements an SLDNFA-resolution procedure, and computes a list of data-facts that should be inserted to the database or retracted from it in order to keep the database consistent. The two approaches for coherent data integration are related by soundness and completeness results.
An Almost Classical Logic for Logic Programming and Nonmonotonic Reasoning
Venue: arXiv cs.LO 2002
Year: 2002

The model theory of a first-order logic called N^4 is introduced. N^4 does not eliminate double negations, as classical logic does, but instead reduces fourfold negations. N^4 is very close to classical logic: N^4 has two truth values; implications in N^4 are material, like in classical logic; and negation distributes over compound formulas in N^4 as it does in classical logic. Results suggest that the semantics of normal logic programs is conveniently formalized in N^4: Classical logic Herbrand interpretations generalize straightforwardly to N^4; the classical minimal Herbrand model of a positive logic program coincides with its unique minimal N^4 Herbrand model; the stable models of a normal logic program and its so-called complete minimal N^4 Herbrand models coincide.
Classification of Random Boolean Networks
Venue: arXiv cs.CC 2002
Year: 2002

We provide the first classification of different types of Random Boolean Networks (RBNs). We study the differences of RBNs depending on the degree of synchronicity and determinism of their updating scheme. For doing so, we first define three new types of RBNs. We note some similarities and differences between different types of RBNs with the aid of a public software laboratory we developed. Particularly, we find that the point attractors are independent of the updating scheme, and that RBNs are more different depending on their determinism or non-determinism rather than depending on their synchronicity or asynchronicity. We also show a way of mapping non-synchronous deterministic RBNs into synchronous RBNs. Our results are important for justifying the use of specific types of RBNs for modelling natural phenomena.
Rectangle Size Bounds and Threshold Covers in Communication Complexity
Venue: arXiv cs.CC 2002
Year: 2002

We investigate the power of the most important lower bound technique in randomized communication complexity, which is based on an evaluation of the maximal size of approximately monochromatic rectangles, minimized over all distributions on the inputs. While it is known that the 0-error version of this bound is polynomially tight for deterministic communication, nothing in this direction is known for constant error and randomized communication complexity. We first study a one-sided version of this bound and obtain that its value lies between the MA- and AM-complexities of the considered function. Hence the lower bound actually works for a (communication complexity) class between MA cap co-MA and AM cap co-AM. We also show that the MA-complexity of the disjointness problem is Omega(sqrt(n)). Following this we consider the conjecture that the lower bound method is polynomially tight for randomized communication complexity. First we disprove a distributional version of this conjecture. Then we give a combinatorial characterization of the value of the lower bound method, in which the optimization over all distributions is absent. This characterization is done by what we call a uniform threshold cover. We also study relaxations of this notion, namely approximate majority covers and majority covers, and compare these three notions in power, exhibiting exponential separations. Each of these covers captures a lower bound method previously used for randomized communication complexity.
TeraScale SneakerNet: Using Inexpensive Disks for Backup, Archiving, and Data Exchange
Venue: arXiv cs.NI 2002
Year: 2002

Large datasets are most economically trnsmitted via parcel post given the current economics of wide-area networking. This article describes how the Sloan Digital Sky Survey ships terabyte scale datasets both within the US and to Europe and Asia. We 3GT storage bricks (Ghz processor, GB ram, GbpsEthernet, TB disk) for about 2k$ each. These bricks act as database servers on the LAN. They are loaded at one site and read at the second site. The paper describes the bricks, their economics, and some software issues that they raise.
Petabyte Scale Data Mining: Dream or Reality?
Venue: arXiv cs.DB 2002
Year: 2002

Science is becoming very data intensive1. Today's astronomy datasets with tens of millions of galaxies already present substantial challenges for data mining. In less than 10 years the catalogs are expected to grow to billions of objects, and image archives will reach Petabytes. Imagine having a 100GB database in 1996, when disk scanning speeds were 30MB/s, and database tools were immature. Such a task today is trivial, almost manageable with a laptop. We think that the issue of a PB database will be very similar in six years. In this paper we scale our current experiments in data archiving and analysis on the Sloan Digital Sky Survey2,3 data six years into the future. We analyze these projections and look at the requirements of performing data mining on such data sets. We conclude that the task scales rather well: we could do the job today, although it would be expensive. There do not seem to be any show-stoppers that would prevent us from storing and using a Petabyte dataset six years from today.
A note on fractional derivative modeling of broadband frequency-dependent absorption: Model III
Venue: arXiv cs.CE 2002
Year: 2002

By far, the fractional derivative model is mainly related to the modelling of complicated solid viscoelastic material. In this study, we try to build the fractional derivative PDE model for broadband ultrasound propagation through human tissues.
Using the DIFF Command for Natural Language Processing
Venue: arXiv cs.CL 2002
Year: 2002

Diff is a software program that detects differences between two data sets and is useful in natural language processing. This paper shows several examples of the application of diff. They include the detection of differences between two different datasets, extraction of rewriting rules, merging of two different datasets, and the optimal matching of two different data sets. Since diff comes with any standard UNIX system, it is readily available and very easy to use. Our studies showed that diff is a practical tool for research into natural language processing.
Symbolic Methodology in Numeric Data Mining: Relational Techniques for Financial Applications
Venue: arXiv cs.CE 2002
Year: 2002

Currently statistical and artificial neural network methods dominate in financial data mining. Alternative relational (symbolic) data mining methods have shown their effectiveness in robotics, drug design and other applications. Traditionally symbolic methods prevail in the areas with significant non-numeric (symbolic) knowledge, such as relative location in robot navigation. At first glance, stock market forecast looks as a pure numeric area irrelevant to symbolic methods. One of our major goals is to show that financial time series can benefit significantly from relational data mining based on symbolic methods. The paper overviews relational data mining methodology and develops this techniques for financial data mining.
Efficient Micro-Mobility using Intra-domain Multicast-based Mechanisms (M&M)
Venue: arXiv cs.NI 2002
Year: 2002

One of the most important metrics in the design of IP mobility protocols is the handover performance. The current Mobile IP (MIP) standard has been shown to exhibit poor handover performance. Most other work attempts to modify MIP to slightly improve its efficiency, while others propose complex techniques to replace MIP. Rather than taking these approaches, we instead propose a new architecture for providing efficient and smooth handover, while being able to co-exist and inter-operate with other technologies. Specifically, we propose an intra-domain multicast-based mobility architecture, where a visiting mobile is assigned a multicast address to use while moving within a domain. Efficient handover is achieved using standard multicast join/prune mechanisms. Two approaches are proposed and contrasted. The first introduces the concept proxy-based mobility, while the other uses algorithmic mapping to obtain the multicast address of visiting mobiles. We show that the algorithmic mapping approach has several advantages over the proxy approach, and provide mechanisms to support it. Network simulation (using NS-2) is used to evaluate our scheme and compare it to other routing-based micro-mobility schemes - CIP and HAWAII. The proactive handover results show that both M&M and CIP shows low handoff delay and packet reordering depth as compared to HAWAII. The reason for M&M's comparable performance with CIP is that both use bi-cast in proactive handover. The M&M, however, handles multiple border routers in a domain, where CIP fails. We also provide a handover algorithm leveraging the proactive path setup capability of M&M, which is expected to outperform CIP in case of reactive handover.