OpenRaiser/Intern-Atlas huggingface dataset:
The Munich Rent Advisor: A Success for Logic Programming on the Internet
Venue: arXiv cs.AI 2004
Year: 2004

Most cities in Germany regularly publish a booklet called the {\em Mietspiegel}. It basically contains a verbal description of an expert system. It allows the calculation of the estimated fair rent for a flat. By hand, one may need a weekend to do so. With our computerized version, the {\em Munich Rent Advisor}, the user just fills in a form in a few minutes and the rent is calculated immediately. We also extended the functionality and applicability of the {\em Mietspiegel} so that the user need not answer all questions on the form. The key to computing with partial information using high-level programming was to use constraint logic programming. We rely on the internet, and more specifically the World Wide Web, to provide this service to a broad user group. More than ten thousand people have used our service in the last three years. This article describes the experiences in implementing and using the {\em Munich Rent Advisor}. Our results suggests that logic programming with constraints can be an important ingredient in intelligent internet systems.
Pattern Reification as the Basis for Description-Driven Systems
Venue: arXiv cs.DB 2004
Year: 2004

One of the main factors driving object-oriented software development for information systems is the requirement for systems to be tolerant to change. To address this issue in designing systems, this paper proposes a pattern-based, object-oriented, description-driven system (DDS) architecture as an extension to the standard UML four-layer meta-model. A DDS architecture is proposed in which aspects of both static and dynamic systems behavior can be captured via descriptive models and meta-models. The proposed architecture embodies four main elements - firstly, the adoption of a multi-layered meta-modeling architecture and reflective meta-level architecture, secondly the identification of four data modeling relationships that can be made explicit such that they can be modified dynamically, thirdly the identification of five design patterns which have emerged from practice and have proved essential in providing reusable building blocks for data management, and fourthly the encoding of the structural properties of the five design patterns by means of one fundamental pattern, the Graph pattern. A practical example of this philosophy, the CRISTAL project, is used to demonstrate the use of description-driven data objects to handle system evolution.
Mapping Topics and Topic Bursts in PNAS
Venue: arXiv cs.IR 2004
Year: 2004

Scientific research is highly dynamic. New areas of science continually evolve;others gain or lose importance, merge or split. Due to the steady increase in the number of scientific publications it is hard to keep an overview of the structure and dynamic development of one's own field of science, much less all scientific domains. However, knowledge of hot topics, emergent research frontiers, or change of focus in certain areas is a critical component of resource allocation decisions in research labs, governmental institutions, and corporations. This paper demonstrates the utilization of Kleinberg's burst detection algorithm, co-word occurrence analysis, and graph layout techniques to generate maps that support the identification of major research topics and trends. The approach was applied to analyze and map the complete set of papers published in the Proceedings of the National Academy of Sciences (PNAS) in the years 1982-2001. Six domain experts examined and commented on the resulting maps in an attempt to reconstruct the evolution of major research areas covered by PNAS.
Fitness inheritance in the Bayesian optimization algorithm
Venue: arXiv cs.NE 2004
Year: 2004

This paper describes how fitness inheritance can be used to estimate fitness for a proportion of newly sampled candidate solutions in the Bayesian optimization algorithm (BOA). The goal of estimating fitness for some candidate solutions is to reduce the number of fitness evaluations for problems where fitness evaluation is expensive. Bayesian networks used in BOA to model promising solutions and generate the new ones are extended to allow not only for modeling and sampling candidate solutions, but also for estimating their fitness. The results indicate that fitness inheritance is a promising concept in BOA, because population-sizing requirements for building appropriate models of promising solutions lead to good fitness estimates even if only a small proportion of candidate solutions is evaluated using the actual fitness function. This can lead to a reduction of the number of actual fitness evaluations by a factor of 30 or more.
Kolmogorov complexity and symmetric relational structures
Venue: arXiv cs.CC 2004
Year: 2004

We study partitions of Fra\"ıssé limits of classes of finite relational structures where the partitions are encoded by infinite binary sequences which are random in the sense of Kolmogorov, Chaitin and Solomonoff. It is shown that partition by a random sequence of a Fra\"ıssé limit preserves the limit property of the object.
Towards a Mathematical Theory of the Delays of the Asynchronous Circuits
Venue: arXiv cs.LO 2004
Year: 2004

The inequations of the delays of the asynchronous circuits are written, by making use of pseudo-Boolean differential calculus. We consider these efforts to be a possible starting point in the semi-formalized reconstruction of the digital electrical engineering (which is a non-formalized theory).
A philosophical essay on life and its connections with genetic algorithms
Venue: arXiv cs.NE 2004
Year: 2004

This paper makes a number of connections between life and various facets of genetic and evolutionary algorithms research. Specifically, it addresses the topics of adaptation, multiobjective optimization, decision making, deception, and search operators, among others. It argues that human life, from birth to death, is an adaptive or dynamic optimization problem where people are continuously searching for happiness. More important, the paper speculates that genetic algorithms can be used as a source of inspiration for helping people make decisions in their everyday life.
Continued fractions and RSA with small secret exponent
Venue: arXiv cs.CR 2004
Year: 2004

Extending the classical Legendre's result, we describe all solutions of the inequality |x - a/b| < c/b^2 in terms of convergents of continued fraction expansion of x. Namely, we show that a/b = (rp_{m+1} +- sp_m) / (rq_{m+1} +- sq_m) for some nonnegative integers m,r,s such that rs < 2c. As an application of this result, we describe a modification of Verheul and van Tilborg variant of Wiener's attack on RSA cryptosystem with small secret exponent.
Genetic Algorithms and Quantum Computation
Venue: arXiv cs.NE 2004
Year: 2004

Recently, researchers have applied genetic algorithms (GAs) to address some problems in quantum computation. Also, there has been some works in the designing of genetic algorithms based on quantum theoretical concepts and techniques. The so called Quantum Evolutionary Programming has two major sub-areas: Quantum Inspired Genetic Algorithms (QIGAs) and Quantum Genetic Algorithms (QGAs). The former adopts qubit chromosomes as representations and employs quantum gates for the search of the best solution. The later tries to solve a key question in this field: what GAs will look like as an implementation on quantum hardware? As we shall see, there is not a complete answer for this question. An important point for QGAs is to build a quantum algorithm that takes advantage of both the GA and quantum computing parallelism as well as true randomness provided by quantum computers. In the first part of this paper we present a survey of the main works in GAs plus quantum computing including also our works in this area. Henceforth, we review some basic concepts in quantum computation and GAs and emphasize their inherent parallelism. Next, we review the application of GAs for learning quantum operators and circuit design. Then, quantum evolutionary programming is considered. Finally, we present our current research in this field and some perspectives.
Specialization of Functional Logic Programs Based on Needed Narrowing
Venue: arXiv cs.PL 2004
Year: 2004

Many functional logic languages are based on narrowing, a unification-based goal-solving mechanism which subsumes the reduction mechanism of functional languages and the resolution principle of logic languages. Needed narrowing is an optimal evaluation strategy which constitutes the basis of modern (narrowing-based) lazy functional logic languages. In this work, we present the fundamentals of partial evaluation in such languages. We provide correctness results for partial evaluation based on needed narrowing and show that the nice properties of this strategy are essential for the specialization process. In particular, the structure of the original program is preserved by partial evaluation and, thus, the same evaluation strategy can be applied for the execution of specialized programs. This is in contrast to other partial evaluation schemes for lazy functional logic programs which may change the program structure in a negative way. Recent proposals for the partial evaluation of declarative multi-paradigm programs use (some form of) needed narrowing to perform computations at partial evaluation time. Therefore, our results constitute the basis for the correctness of such partial evaluators.
Predictable Software -- A Shortcut to Dependable Computing ?
Venue: arXiv cs.OS 2004
Year: 2004

Many dependability techniques expect certain behaviors from the underlying subsystems and fail in chaotic ways if these expectations are not met. Under expected circumstances, however, software tends to work quite well. This paper suggests that, instead of fixing elusive bugs or rewriting software, we improve the predictability of conditions faced by our programs. This approach might be a cheaper and faster way to improve dependability of software. After identifying some of the common triggers of unpredictability, the paper describes three engineering principles that hold promise in combating unpredictability, suggests a way to benchmark predictability, and outlines a brief research agenda.
Belle Computing System
Venue: arXiv cs.DC 2004
Year: 2004

We describe the present status of the computing system in the Belle experiment at the KEKB $e^+e^-$ asymmetric-energy collider. So far, we have logged more than 160 fb$^{-1}$ of data, corresponding to the world's largest data sample of 170M $B\bar{B}$ pairs at the $Υ(4S)$ energy region. A large amount of event data has to be processed to produce an analysis event sample in a timely fashion. In addition, Monte Carlo events have to be created to control systematic errors accurately. This requires stable and efficient usage of computing resources. Here we review our computing model and then describe how we efficiently proceed DST/MC productions in our system.
A Comparative Study of Arithmetic Constraints on Integer Intervals
Venue: arXiv cs.PL 2004
Year: 2004

We propose here a number of approaches to implement constraint propagation for arithmetic constraints on integer intervals. To this end we introduce integer interval arithmetic. Each approach is explained using appropriate proof rules that reduce the variable domains. We compare these approaches using a set of benchmarks.
Fast Multipoint-Evaluation of Bivariate Polynomials
Venue: arXiv cs.DS 2004
Year: 2004

We generalize univariate multipoint evaluation of polynomials of degree n at sublinear amortized cost per point. More precisely, it is shown how to evaluate a bivariate polynomial p of maximum degree less than n, specified by its n^2 coefficients, simultaneously at n^2 given points using a total of O(n^{2.667}) arithmetic operations. In terms of the input size N being quadratic in n, this amounts to an amortized cost of O(N^{0.334}) per point.
Secure Transmission of Sensitive data using multiple channels
Venue: arXiv cs.CR 2004
Year: 2004

A new scheme for transmitting sensitive data is proposed, the proposed scheme depends on partitioning the output of a block encryption module using the Chinese Remainder Theorem among a set of channels. The purpose of using the Chinese Remainder Theorem is to hide the cipher text in order to increase the difficulty of attacking the cipher. The theory, implementation and the security of this scheme are described in this paper.
A Theory of Computation Based on Quantum Logic (I)
Venue: arXiv cs.LO 2004
Year: 2004

The (meta)logic underlying classical theory of computation is Boolean (two-valued) logic. Quantum logic was proposed by Birkhoff and von Neumann as a logic of quantum mechanics more than sixty years ago. The major difference between Boolean logic and quantum logic is that the latter does not enjoy distributivity in general. The rapid development of quantum computation in recent years stimulates us to establish a theory of computation based on quantum logic. The present paper is the first step toward such a new theory and it focuses on the simplest models of computation, namely finite automata. It is found that the universal validity of many properties of automata depend heavily upon the distributivity of the underlying logic. This indicates that these properties does not universally hold in the realm of quantum logic. On the other hand, we show that a local validity of them can be recovered by imposing a certain commutativity to the (atomic) statements about the automata under consideration. This reveals an essential difference between the classical theory of computation and the computation theory based on quantum logic.
Protecting Public-Access Sites Against Distributed Denial-of-Service Attacks
Venue: arXiv cs.NI 2004
Year: 2004

A distributed denial-of-service (DDoS) attack can flood a victim site with malicious traffic, causing service disruption or even complete failure. Public-access sites like amazon or ebay are particularly vulnerable to such attacks, because they have no way of a priori blocking unauthorized traffic. We present Active Internet Traffic Filtering (AITF), a mechanism that protects public-access sites from highly distributed attacks by causing undesired traffic to be blocked as close as possible to its sources. We identify filters as a scarce resource and show that AITF protects a significant amount of the victim's bandwidth, while requiring from each participating router a number of filters that can be accommodated by today's routers. AITF is incrementally deployable, because it offers a substantial benefit even to the first sites that deploy it.
XML framework for concept description and knowledge representation
Venue: arXiv cs.AI 2004
Year: 2004

An XML framework for concept description is given, based upon the fact that the tree structure of XML implies the logical structure of concepts as defined by attributional calculus. Especially, the attribute-value representation is implementable in the XML framework. Since the attribute-value representation is an important way to represent knowledge in AI, the framework offers a further and simpler way than the powerful RDF technology.
Characterisations of Intersection Graphs by Vertex Orderings
Venue: arXiv cs.DM 2004
Year: 2004

Characterisations of interval graphs, comparability graphs, co-comparability graphs, permutation graphs, and split graphs in terms of linear orderings of the vertex set are presented. As an application, it is proved that interval graphs, co-comparability graphs, AT-free graphs, and split graphs have bandwidth bounded by their maximum degree.
When Do Differences Matter? On-Line Feature Extraction Through Cognitive Economy
Venue: arXiv cs.LG 2004
Year: 2004

For an intelligent agent to be truly autonomous, it must be able to adapt its representation to the requirements of its task as it interacts with the world. Most current approaches to on-line feature extraction are ad hoc; in contrast, this paper presents an algorithm that bases judgments of state compatibility and state-space abstraction on principled criteria derived from the psychological principle of cognitive economy. The algorithm incorporates an active form of Q-learning, and partitions continuous state-spaces by merging and splitting Voronoi regions. The experiments illustrate a new methodology for testing and comparing representations by means of learning curves. Results from the puck-on-a-hill task demonstrate the algorithm's ability to learn effective representations, superior to those produced by some other, well-known, methods.
Exploiting Cross-Document Relations for Multi-document Evolving Summarization
Venue: arXiv cs.CL 2004
Year: 2004

This paper presents a methodology for summarization from multiple documents which are about a specific topic. It is based on the specification and identification of the cross-document relations that occur among textual elements within those documents. Our methodology involves the specification of the topic-specific entities, the messages conveyed for the specific entities by certain textual elements and the specification of the relations that can hold among these messages. The above resources are necessary for setting up a specific topic for our query-based summarization approach which uses these resources to identify the query-specific messages within the documents and the query-specific relations that connect these messages across documents.
Multi-Threading And Message Communication In Qu-Prolog
Venue: arXiv cs.PL 2004
Year: 2004

This paper presents the multi-threading and internet message communication capabilities of Qu-Prolog. Message addresses are symbolic and the communications package provides high-level support that completely hides details of IP addresses and port numbers as well as the underlying TCP/IP transport layer. The combination of the multi-threads and the high level inter-thread message communications provide simple, powerful support for implementing internet distributed intelligent applications.
Constraint Logic Programming with Hereditary Harrop Formula
Venue: arXiv cs.PL 2004
Year: 2004

Constraint Logic Programming (CLP) and Hereditary Harrop formulas (HH) are two well known ways to enhance the expressivity of Horn clauses. In this paper, we present a novel combination of these two approaches. We show how to enrich the syntax and proof theory of HH with the help of a given constraint system, in such a way that the key property of HH as a logic programming language (namely, the existence of uniform proofs) is preserved. We also present a procedure for goal solving, showing its soundness and completeness for computing answer constraints. As a consequence of this result, we obtain a new strong completeness theorem for CLP that avoids the need to build disjunctions of computed answers, as well as a more abstract formulation of a known completeness theorem for HH.
New Covert Channels in HTTP
Venue: arXiv cs.CR 2004
Year: 2004

This paper presents new methods enabling anonymous communication on the Internet. We describe a new protocol that allows us to create an anonymous overlay network by exploiting the web browsing activities of regular users. We show that the overlay network provides an anonymity set greater than the set of senders and receivers in a realistic threat model. In particular, the protocol provides unobservability in our threat model.
Finite-Tree Analysis for Constraint Logic-Based Languages: The Complete Unabridged Version
Venue: arXiv cs.PL 2004
Year: 2004

Logic languages based on the theory of rational, possibly infinite, trees have much appeal in that rational trees allow for faster unification (due to the safe omission of the occurs-check) and increased expressivity (cyclic terms can provide very efficient representations of grammars and other useful objects). Unfortunately, the use of infinite rational trees has problems. For instance, many of the built-in and library predicates are ill-defined for such trees and need to be supplemented by run-time checks whose cost may be significant. Moreover, some widely-used program analysis and manipulation techniques are correct only for those parts of programs working over finite trees. It is thus important to obtain, automatically, a knowledge of the program variables (the finite variables) that, at the program points of interest, will always be bound to finite terms. For these reasons, we propose here a new data-flow analysis, based on abstract interpretation, that captures such information.
A lambda calculus for quantum computation with classical control
Venue: arXiv cs.LO 2004
Year: 2004

The objective of this paper is to develop a functional programming language for quantum computers. We develop a lambda calculus for the classical control model, following the first author's work on quantum flow-charts. We define a call-by-value operational semantics, and we give a type system using affine intuitionistic linear logic. The main results of this paper are the safety properties of the language and the development of a type inference algorithm.
Efficient coroutine generation of constrained Gray sequences
Venue: arXiv cs.DS 2004
Year: 2004

We study an interesting family of cooperating coroutines, which is able to generate all patterns of bits that satisfy certain fairly general ordering constraints, changing only one bit at a time. (More precisely, the directed graph of constraints is required to be cycle-free when it is regarded as an undirected graph.) If the coroutines are implemented carefully, they yield an algorithm that needs only a bounded amount of computation per bit change, thereby solving an open problem in the field of combinatorial pattern generation.
"In vivo" spam filtering: A challenge problem for data mining
Venue: arXiv cs.AI 2004
Year: 2004

Spam, also known as Unsolicited Commercial Email (UCE), is the bane of email communication. Many data mining researchers have addressed the problem of detecting spam, generally by treating it as a static text classification problem. True in vivo spam filtering has characteristics that make it a rich and challenging domain for data mining. Indeed, real-world datasets with these characteristics are typically difficult to acquire and to share. This paper demonstrates some of these characteristics and argues that researchers should pursue in vivo spam filtering as an accessible domain for investigating them.
Neuro Fuzzy Systems: Sate-of-the-Art Modeling Techniques
Venue: arXiv cs.AI 2004
Year: 2004

Fusion of Artificial Neural Networks (ANN) and Fuzzy Inference Systems (FIS) have attracted the growing interest of researchers in various scientific and engineering areas due to the growing need of adaptive intelligent systems to solve the real world problems. ANN learns from scratch by adjusting the interconnections between layers. FIS is a popular computing framework based on the concept of fuzzy set theory, fuzzy if-then rules, and fuzzy reasoning. The advantages of a combination of ANN and FIS are obvious. There are several approaches to integrate ANN and FIS and very often it depends on the application. We broadly classify the integration of ANN and FIS into three categories namely concurrent model, cooperative model and fully fused model. This paper starts with a discussion of the features of each model and generalize the advantages and deficiencies of each model. We further focus the review on the different types of fused neuro-fuzzy systems and citing the advantages and disadvantages of each model.