OpenRaiser/Intern-Atlas huggingface dataset:
Distance function wavelets - Part II: Extended results and conjectures
Venue: arXiv cs.CE 2002
Year: 2002

Report II is concerned with the extended results of distance function wavelets (DFW). The fractional DFW transforms are first addressed relating to the fractal geometry and fractional derivative, and then, the discrete Helmholtz-Fourier transform is briefly presented. The Green second identity may be an alternative devise in developing the theoretical framework of the DFW transform and series. The kernel solutions of the Winkler plate equation and the Burger's equation are used to create the DFW transforms and series. Most interestingly, it is found that the translation invariant monomial solutions of the high-order Laplace equations can be used to make very simple harmonic polynomial DFW series. In most cases of this study, solid mathematical analysis is missing and results are obtained intuitively in the conjecture status.
Japanese/English Cross-Language Information Retrieval: Exploration of Query Translation and Transliteration
Venue: arXiv cs.CL 2002
Year: 2002

Cross-language information retrieval (CLIR), where queries and documents are in different languages, has of late become one of the major topics within the information retrieval community. This paper proposes a Japanese/English CLIR system, where we combine a query translation and retrieval modules. We currently target the retrieval of technical documents, and therefore the performance of our system is highly dependent on the quality of the translation of technical terms. However, the technical term translation is still problematic in that technical terms are often compound words, and thus new terms are progressively created by combining existing base words. In addition, Japanese often represents loanwords based on its special phonogram. Consequently, existing dictionaries find it difficult to achieve sufficient coverage. To counter the first problem, we produce a Japanese/English dictionary for base words, and translate compound words on a word-by-word basis. We also use a probabilistic method to resolve translation ambiguity. For the second problem, we use a transliteration method, which corresponds words unlisted in the base word dictionary to their phonetic equivalents in the target language. We evaluate our system using a test collection for CLIR, and show that both the compound word translation and transliteration methods improve the system performance.
Distance function wavelets - Part III: "Exotic" transforms and series
Venue: arXiv cs.CE 2002
Year: 2002

Part III of the reports consists of various unconventional distance function wavelets (DFW). The dimension and the order of partial differential equation (PDE) are first used as a substitute of the scale parameter in the DFW transforms and series, especially with the space and time-space potential problems. It is noted that the recursive multiple reciprocity formulation is the DFW series. The Green second identity is used to avoid the singularity of the zero-order fundamental solution in creating the DFW series. The fundamental solutions of various composite PDEs are found very flexible and efficient to handle a borad range of problems. We also discuss the underlying connections between the crucial concepts of dimension, scale and the order of PDE through the analysis of dissipative acoustic wave propagation. The shape parameter of the potential problems is also employed as the "scale parameter" to create the non-orthogonal DFW. This paper also briefly discusses and conjectures the DFW correspondences of a variety of coordinate variable transforms and series. Practically important, the anisotropic and inhomogeneous DFW's are developed by using the geodesic distance variable. The DFW and the related basis functions are also used in making the kernel distance sigmoidal functions, which are potentially useful in the artificial neural network and machine learning. As or even worse than the preceding two reports, this study scarifies mathematical rigor and in turn unfetter imagination. Most results are intuitively obtained without rigorous analysis. Follow-up research is still under way. The paper is intended to inspire more research into this promising area.
The Prioritized Inductive Logic Programs
Venue: arXiv cs.AI 2002
Year: 2002

The limit behavior of inductive logic programs has not been explored, but when considering incremental or online inductive learning algorithms which usually run ongoingly, such behavior of the programs should be taken into account. An example is given to show that some inductive learning algorithm may not be correct in the long run if the limit behavior is not considered. An inductive logic program is convergent if given an increasing sequence of example sets, the program produces a corresponding sequence of the Horn logic programs which has the set-theoretic limit, and is limit-correct if the limit of the produced sequence of the Horn logic programs is correct with respect to the limit of the sequence of the example sets. It is shown that the GOLEM system is not limit-correct. Finally, a limit-correct inductive logic system, called the prioritized GOLEM system, is proposed as a solution.
The Lattice of Fuzzy Intervals and Sufficient Conditions for its Distributivity
Venue: arXiv cs.OH 2002
Year: 2002

Given a reference lattice, we define fuzzy intervals to be the fuzzy sets such that their p-cuts are crisp closed intervals. We show that: given a complete reference lattice, the collection of its fuzzy intervals is a complete lattice. Furthermore we show that: if the reference lattice is completely distributive then the lattice of its fuzzy intervals is distributive.
Language Modeling for Multi-Domain Speech-Driven Text Retrieval
Venue: arXiv cs.CL 2002
Year: 2002

We report experimental results associated with speech-driven text retrieval, which facilitates retrieving information in multiple domains with spoken queries. Since users speak contents related to a target collection, we produce language models used for speech recognition based on the target collection, so as to improve both the recognition and retrieval accuracy. Experiments using existing test collections combined with dictated queries showed the effectiveness of our method.
A Multilevel Approach to Topology-Aware Collective Operations in Computational Grids
Venue: arXiv cs.DC 2002
Year: 2002

The efficient implementation of collective communiction operations has received much attention. Initial efforts produced "optimal" trees based on network communication models that assumed equal point-to-point latencies between any two processes. This assumption is violated in most practical settings, however, particularly in heterogeneous systems such as clusters of SMPs and wide-area "computational Grids," with the result that collective operations perform suboptimally. In response, more recent work has focused on creating topology-aware trees for collective operations that minimize communication across slower channels (e.g., a wide-area network). While these efforts have significant communication benefits, they all limit their view of the network to only two layers. We present a strategy based upon a multilayer view of the network. By creating multilevel topology-aware trees we take advantage of communication cost differences at every level in the network. We used this strategy to implement topology-aware versions of several MPI collective operations in MPICH-G2, the Globus Toolkit[tm]-enabled version of the popular MPICH implementation of the MPI standard. Using information about topology provided by MPICH-G2, we construct these multilevel topology-aware trees automatically during execution. We present results demonstrating the advantages of our multilevel approach by comparing it to the default (topology-unaware) implementation provided by MPICH and a topology-aware two-layer implementation.
Improving Web Database Access Using Decision Diagrams
Venue: arXiv cs.LO 2002
Year: 2002

In some areas of management and commerce, especially in Electronic commerce (E-commerce), that are accelerated by advances in Web technologies, it is essential to support the decision making process using formal methods. Among the problems of E-commerce applications: reducing the time of data access so that huge databases can be searched quickly; decreasing the cost of database design ... etc. We present the application of Decision Diagrams design using Information Theory approach to improve database access speeds. We show that such utilization provides systematic and visual ways of applying Decision Making methods to simplify complex Web engineering problems.
Synthesis of Low-Power Digital Circuits Derived from Binary Decision Diagrams
Venue: arXiv cs.AR 2002
Year: 2002

This paper introduces a novel method for synthesizing digital circuits derived from Binary Decision Diagrams (BDDs) that can yield to reduction in power dissipation. The power reduction is achieved by decreasing the switching activity in a circuit while paying close attention to information measures as an optimization criterion. We first present the technique of efficient BDD-based computation of information measures which are used to guide the power optimization procedures. Using this technique, we have developed an algorithm of BDD reordering which leads to reducing the power consumption of the circuits derived from BDDs. Results produced by the synthesis on the ISCAS benchmark circuits are very encouraging.
New Insights in Boundary-only and Domain-type RBF Methods
Venue: arXiv cs.CE 2002
Year: 2002

This paper has made some significant advances in the boundary-only and domain-type 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, we also presents a general solution RBF (GSR) methodology to construct efficient RBFs in the domain-type RBF collocation method and dual reciprocity method. The GSR approach first establishes an explicit relationship between the BEM and RBF itself on the ground of the potential theory. This paper also discusses some essential issues relating to the RBF computing, which include time-space RBFs, direct and indirect RBF schemes, finite RBF method, and the application of multipole and wavelet to the RBF solution of the PDEs.
Two Representations for Iterative Non-prioritized Change
Venue: arXiv cs.AI 2002
Year: 2002

We address a general representation problem for belief change, and describe two interrelated representations for iterative non-prioritized change: a logical representation in terms of persistent epistemic states, and a constructive representation in terms of flocks of bases.
Intuitions and the modelling of defeasible reasoning: some case studies
Venue: arXiv cs.AI 2002
Year: 2002

The purpose of this paper is to address some criticisms recently raised by John Horty in two articles against the validity of two commonly accepted defeasible reasoning patterns, viz. reinstatement and floating conclusions. I shall argue that Horty's counterexamples, although they significantly raise our understanding of these reasoning patterns, do not show their invalidity. Some of them reflect patterns which, if made explicit in the formalisation, avoid the unwanted inference without having to give up the criticised inference principles. Other examples seem to involve hidden assumptions about the specific problem which, if made explicit, are nothing but extra information that defeat the defeasible inference. These considerations will be put in a wider perspective by reflecting on the nature of defeasible reasoning principles as principles of justified acceptance rather than `real' logical inference.
A Lyapunov Formulation for Efficient Solution of the Poisson and Convection-Diffusion Equations by the Differential Quadrature Method
Venue: arXiv cs.CE 2002
Year: 2002

Civan and Sliepcevich [1, 2] suggested that special matrix solver should be developed to further reduce the computing effort in applying the differential quadrature (DQ) method for the Poisson and convection-diffusion equations. Therefore, the purpose of the present communication is to introduce and apply the Lyapunov formulation which can be solved much more efficiently than the Gaussian elimination method. Civan and Sliepcevich [2] first presented DQ approximate formulas in polynomial form for partial derivatives in tow-dimensional variable domain. For simplifying formulation effort, Chen et al. [3] proposed the compact matrix form of these DQ approximate formulas. In this study, by using these matrix approximate formulas, the DQ formulations for the Poisson and convection-diffusion equations can be expressed as the Lyapunov algebraic matrix equation. The formulation effort is simplified, and a simple and explicit matrix formulation is obtained. A variety of fast algorithms in the solution of the Lyapunov equation [4-6] can be successfully applied in the DQ analysis of these two-dimensional problems, and, thus, the computing effort can be greatly reduced. Finally, we also point out that the present reduction technique can be easily extended to the three-dimensional cases.
System Description for a Scalable, Fault-Tolerant, Distributed Garbage Collector
Venue: arXiv cs.DC 2002
Year: 2002

We describe an efficient and fault-tolerant algorithm for distributed cyclic garbage collection. The algorithm imposes few requirements on the local machines and allows for flexibility in the choice of local collector and distributed acyclic garbage collector to use with it. We have emphasized reducing the number and size of network messages without sacrificing the promptness of collection throughout the algorithm. Our proposed collector is a variant of back tracing to avoid extensive synchronization between machines. We have added an explicit forward tracing stage to the standard back tracing stage and designed a tuned heuristic to reduce the total amount of work done by the collector. Of particular note is the development of fault-tolerant cooperation between traces and a heuristic that aggressively reduces the set of suspect objects.
A meshless, integration-free, and boundary-only RBF technique
Venue: arXiv cs.CE 2002
Year: 2002

Based on the radial basis function (RBF), non-singular general solution and dual reciprocity method (DRM), this paper presents an inherently meshless, integration-free, boundary-only RBF collocation techniques for numerical solution of various partial differential equation systems. The basic ideas behind this methodology are very mathematically simple. In this study, the RBFs are employed to approximate the inhomogeneous terms via the DRM, while non-singular general solution leads to a boundary-only RBF formulation for homogenous solution. The present scheme is named as the boundary knot method (BKM) to differentiate it from the other numerical techniques. In particular, due to the use of nonsingular general solutions rather than singular fundamental solutions, the BKM is different from the method of fundamental solution in that the former does no require the artificial boundary and results in the symmetric system equations under certain conditions. The efficiency and utility of this new technique are validated through a number of typical numerical examples. Completeness concern of the BKM due to the only use of non-singular part of complete fundamental solution is also discussed.
CLPGUI: a generic graphical user interface for constraint logic programming over finite domains
Venue: arXiv cs.SE 2002
Year: 2002

CLPGUI is a graphical user interface for visualizing and interacting with constraint logic programs over finite domains. In CLPGUI, the user can control the execution of a CLP program through several views of constraints, of finite domain variables and of the search tree. CLPGUI is intended to be used both for teaching purposes, and for debugging and improving complex programs of realworld scale. It is based on a client-server architecture for connecting the CLP process to a Java-based GUI process. Communication by message passing provides an open architecture which facilitates the reuse of graphical components and the porting to different constraint programming systems. Arbitrary constraints and goals can be posted incrementally from the GUI. We propose several dynamic 2D and 3D visualizations of the search tree and of the evolution of finite domain variables. We argue that the 3D representation of search trees proposed in this paper provides the most appropriate visualization of large search trees. We describe the current implementation of the annotations and of the interactive execution model in GNU-Prolog, and report some evaluation results.
Value withdrawal explanations: a theoretical tool for programming environments
Venue: arXiv cs.SE 2002
Year: 2002

Constraint logic programming combines declarativity and efficiency thanks to constraint solvers implemented for specific domains. Value withdrawal explanations have been efficiently used in several constraints programming environments but there does not exist any formalization of them. This paper is an attempt to fill this lack. Furthermore, we hope that this theoretical tool could help to validate some programming environments. A value withdrawal explanation is a tree describing the withdrawal of a value during a domain reduction by local consistency notions and labeling. Domain reduction is formalized by a search tree using two kinds of operators: operators for local consistency notions and operators for labeling. These operators are defined by sets of rules. Proof trees are built with respect to these rules. For each removed value, there exists such a proof tree which is the withdrawal explanation of this value.
The Rise and Fall of the Church-Turing Thesis
Venue: arXiv cs.CC 2002
Year: 2002

The essay consists of three parts. In the first part, it is explained how theory of algorithms and computations evaluates the contemporary situation with computers and global networks. In the second part, it is demonstrated what new perspectives this theory opens through its new direction that is called theory of super-recursive algorithms. These algorithms have much higher computing power than conventional algorithmic schemes. In the third part, we explicate how realization of what this theory suggests might influence life of people in future. It is demonstrated that now the theory is far ahead computing practice and practice has to catch up with the theory. We conclude with a comparison of different approaches to the development of information technology.
Parallel Delaunay Refinement: Algorithms and Analyses
Venue: arXiv cs.CG 2002
Year: 2002

In this paper, we analyze the complexity of natural parallelizations of Delaunay refinement methods for mesh generation. The parallelizations employ a simple strategy: at each iteration, they choose a set of ``independent'' points to insert into the domain, and then update the Delaunay triangulation. We show that such a set of independent points can be constructed efficiently in parallel and that the number of iterations needed is $O(\log^2(L/s))$, where $L$ is the diameter of the domain, and $s$ is the smallest edge in the output mesh. In addition, we show that the insertion of each independent set of points can be realized sequentially by Ruppert's method in two dimensions and Shewchuk's in three dimensions. Therefore, our parallel Delaunay refinement methods provide the same element quality and mesh size guarantees as the sequential algorithms in both two and three dimensions. For quasi-uniform meshes, such as those produced by Chew's method, we show that the number of iterations can be reduced to $O(\log(L/s))$. To the best of our knowledge, these are the first provably polylog$(L/s)$ parallel time Delaunay meshing algorithms that generate well-shaped meshes of size optimal to within a constant.
On the existence and multiplicity of extensions in dialectical argumentation
Venue: arXiv cs.AI 2002
Year: 2002

In the present paper, the existence and multiplicity problems of extensions are addressed. The focus is on extension of the stable type. The main result of the paper is an elegant characterization of the existence and multiplicity of extensions in terms of the notion of dialectical justification, a close cousin of the notion of admissibility. The characterization is given in the context of the particular logic for dialectical argumentation DEFLOG. The results are of direct relevance for several well-established models of defeasible reasoning (like default logic, logic programming and argumentation frameworks), since elsewhere dialectical argumentation has been shown to have close formal connections with these models.
Knuth-Bendix constraint solving is NP-complete
Venue: arXiv cs.LO 2002
Year: 2002

We show the NP-completeness of the existential theory of term algebras with the Knuth-Bendix order by giving a nondeterministic polynomial-time algorithm for solving Knuth-Bendix ordering constraints.
A Polynomial Translation of Logic Programs with Nested Expressions into Disjunctive Logic Programs: Preliminary Report
Venue: arXiv cs.AI 2002
Year: 2002

Nested logic programs have recently been introduced in order to allow for arbitrarily nested formulas in the heads and the bodies of logic program rules under the answer sets semantics. Nested expressions can be formed using conjunction, disjunction, as well as the negation as failure operator in an unrestricted fashion. This provides a very flexible and compact framework for knowledge representation and reasoning. Previous results show that nested logic programs can be transformed into standard (unnested) disjunctive logic programs in an elementary way, applying the negation as failure operator to body literals only. This is of great practical relevance since it allows us to evaluate nested logic programs by means of off-the-shelf disjunctive logic programming systems, like DLV. However, it turns out that this straightforward transformation results in an exponential blow-up in the worst-case, despite the fact that complexity results indicate that there is a polynomial translation among both formalisms. In this paper, we take up this challenge and provide a polynomial translation of logic programs with nested expressions into disjunctive logic programs. Moreover, we show that this translation is modular and (strongly) faithful. We have implemented both the straightforward as well as our advanced transformation; the resulting compiler serves as a front-end to DLV and is publicly available on the Web.
Reinforcing Reachable Routes
Venue: arXiv cs.NI 2002
Year: 2002

This paper studies the evaluation of routing algorithms from the perspective of reachability routing, where the goal is to determine all paths between a sender and a receiver. Reachability routing is becoming relevant with the changing dynamics of the Internet and the emergence of low-bandwidth wireless/ad-hoc networks. We make the case for reinforcement learning as the framework of choice to realize reachability routing, within the confines of the current Internet infrastructure. The setting of the reinforcement learning problem offers several advantages, including loop resolution, multi-path forwarding capability, cost-sensitive routing, and minimizing state overhead, while maintaining the incremental spirit of current backbone routing algorithms. We identify research issues in reinforcement learning applied to the reachability routing problem to achieve a fluid and robust backbone routing framework. The paper is targeted toward practitioners seeking to implement a reachability routing algorithm.