OpenRaiser/Intern-Atlas huggingface dataset:
Two- versus three-dimensional connectivity testing of first-order queries to semi-algebraic sets
Venue: arXiv cs.LO 2003
Year: 2003

This paper addresses the question whether one can determine the connectivity of a semi-algebraic set in three dimensions by testing the connectivity of a finite number of two-dimensional ``samples'' of the set, where these samples are defined by first-order queries. The question is answered negatively for two classes of first-order queries: cartesian-product-free, and positive one-pass.
A Grid Based Architecture for High-Performance NLP
Venue: arXiv cs.DC 2003
Year: 2003

We describe the design and early implementation of an extensible, component-based software architecture for natural language engineering applications which interfaces with high performance distributed computing services. The architecture leverages existing linguistic resource description and discovery mechanisms based on metadata descriptions, combining these in a compatible fashion with other software definition abstractions. Within this architecture, application design is highly flexible, allowing disparate components to be combined to suit the overall application functionality, and formally described independently of processing concerns. An application specification language provides abstraction from the programming environment and allows ease of interface with high performance computational grids via a broker.
Information Revolution
Venue: arXiv cs.CL 2003
Year: 2003

The world is passing through a major revolution called the information revolution, in which information and knowledge is becoming available to people in unprecedented amounts wherever and whenever they need it. Those societies which fail to take advantage of the new technology will be left behind, just like in the industrial revolution. The information revolution is based on two major technologies: computers and communication. These technologies have to be delivered in a COST EFFECTIVE manner, and in LANGUAGES accessible to people. One way to deliver them in cost effective manner is to make suitable technology choices (discussed later), and to allow people to access through shared resources. This could be done throuch street corner shops (for computer usage, e-mail etc.), schools, community centers and local library centres.
Language Access: An Information Based Approach
Venue: arXiv cs.CL 2003
Year: 2003

The anusaaraka system (a kind of machine translation system) makes text in one Indian language accessible through another Indian language. The machine presents an image of the source text in a language close to the target language. In the image, some constructions of the source language (which do not have equivalents in the target language) spill over to the output. Some special notation is also devised. Anusaarakas have been built from five pairs of languages: Telugu,Kannada, Marathi, Bengali and Punjabi to Hindi. They are available for use through Email servers. Anusaarkas follows the principle of substitutibility and reversibility of strings produced. This implies preservation of information while going from a source language to a target language. For narrow subject areas, specialized modules can be built by putting subject domain knowledge into the system, which produce good quality grammatical output. However, it should be remembered, that such modules will work only in narrow areas, and will sometimes go wrong. In such a situation, anusaaraka output will still remain useful.
Controlled hierarchical filtering: Model of neocortical sensory processing
Venue: arXiv cs.NE 2003
Year: 2003

A model of sensory information processing is presented. The model assumes that learning of internal (hidden) generative models, which can predict the future and evaluate the precision of that prediction, is of central importance for information extraction. Furthermore, the model makes a bridge to goal-oriented systems and builds upon the structural similarity between the architecture of a robust controller and that of the hippocampal entorhinal loop. This generative control architecture is mapped to the neocortex and to the hippocampal entorhinal loop. Implicit memory phenomena; priming and prototype learning are emerging features of the model. Mathematical theorems ensure stability and attractive learning properties of the architecture. Connections to reinforcement learning are also established: both the control network, and the network with a hidden model converge to (near) optimal policy under suitable conditions. Falsifying predictions, including the role of the feedback connections between neocortical areas are made.
Improvements to time bracketed authentication
Venue: arXiv cs.CR 2003
Year: 2003

We describe a collection of techniques whereby audiovisual or other recordings of significant events can be made in a way that hinders falsification, pre-dating, or post-dating by interested parties, even by the makers and operators of the recording equipment. A central feature of these techniques is the interplay between private information, which by its nature is untrustworthy and susceptible to suppression or manipulation by interested parties, and public information, which is too widely known to be manipulated by anyone. While authenticated recordings may be infeasible to falsify, they can be abused in other ways, such as being used for blackmail or harassment; but susceptibility to these abuses can be reduced by encryption and secret sharing.
Artificial Neural Networks for Beginners
Venue: arXiv cs.NE 2003
Year: 2003

The scope of this teaching package is to make a brief induction to Artificial Neural Networks (ANNs) for people who have no previous knowledge of them. We first make a brief introduction to models of networks, for then describing in general terms ANNs. As an application, we explain the backpropagation algorithm, since it is widely used and many other algorithms are derived from it. The user should know algebra and the handling of functions and vectors. Differential calculus is recommendable, but not necessary. The contents of this package should be understood by people with high school education. It would be useful for people who are just curious about what are ANNs, or for people who want to become familiar with them, so when they study them more fully, they will already have clear notions of ANNs. Also, people who only want to apply the backpropagation algorithm without a detailed and formal explanation of it will find this material useful. This work should not be seen as "Nets for dummies", but of course it is not a treatise. Much of the formality is skipped for the sake of simplicity. Detailed explanations and demonstrations can be found in the referred readings. The included exercises complement the understanding of the theory. The on-line resources are highly recommended for extending this brief induction.
Image Analysis in Astronomy for very large vision machine
Venue: arXiv cs.CV 2003
Year: 2003

It is developed a very complex system (hardware/software) to detect luminosity variations connected with the discovery of new planets outside the Solar System. Traditional imaging approaches are very demanding in terms of computing time; then, the implementation of an automatic vision and decision software architecture is presented. It allows to perform an on-line discrimination of interesting events by using two levels of triggers. A fundamental challenge was to work with very large CCD camera (even 16k*16k pixels) in line with very large telescopes. Then, the architecture can use a distributed parallel network system based on a maximum of 256 standard workstations.
Reliable and Efficient Inference of Bayesian Networks from Sparse Data by Statistical Learning Theory
Venue: arXiv cs.LG 2003
Year: 2003

To learn (statistical) dependencies among random variables requires exponentially large sample size in the number of observed random variables if any arbitrary joint probability distribution can occur. We consider the case that sparse data strongly suggest that the probabilities can be described by a simple Bayesian network, i.e., by a graph with small in-degree Δ. Then this simple law will also explain further data with high confidence. This is shown by calculating bounds on the VC dimension of the set of those probability measures that correspond to simple graphs. This allows to select networks by structural risk minimization and gives reliability bounds on the error of the estimated joint measure without (in contrast to a previous paper) any prior assumptions on the set of possible joint measures. The complexity for searching the optimal Bayesian networks of in-degree Δincreases only polynomially in the number of random varibales for constant Δand the optimal joint measure associated with a given graph can be found by convex optimization.
Results on the quantitative mu-calculus qMu
Venue: arXiv cs.LO 2003
Year: 2003

The mu-calculus is a powerful tool for specifying and verifying transition systems, including those with both demonic and angelic choice; its quantitative generalisation qMu extends that to probabilistic choice. We show that for a finite-state system the logical interpretation of qMu, via fixed-points in a domain of real-valued functions into [0,1], is equivalent to an operational interpretation given as a turn-based gambling game between two players. The logical interpretation provides direct access to axioms, laws and meta-theorems. The operational, game- based interpretation aids the intuition and continues in the more general context to provide a surprisingly practical specification tool. A corollary of our proofs is an extension of Everett's singly-nested games result in the finite turn-based case: we prove well-definedness of the minimax value, and existence of fixed memoriless strategies, for all qMu games/formulae, of arbitrary (including alternating) nesting structure.
A thought experiment on Quantum Mechanics and Distributed Failure Detection
Venue: arXiv cs.DC 2003
Year: 2003

One of the biggest problems in current distributed systems is that presented by one machine attempting to determine the liveness of another in a timely manner. Unfortunately, the symptoms exhibited by a failed machine can also be the result of other causes, e.g., an overloaded machine or network which drops messages, making it impossible to detect a machine failure with cetainty until that machine recovers. This is a well understood problem and one which has led to a large body of research into failure suspectors: since it is not possible to detect a failure, the best one can do is suspect a failure and program accordingly. However, one machine's suspicions may not be the same as another's; therefore, these algorithms spend a considerable effort in ensuring a consistent view among all available machines of who is suspects of being failed. This paper describes a thought experiment on how quantum mechanics may be used to provide a failure detector that is guaranteed to give both accurate and instantaneous information about the liveness of machines, no matter the distances involved.
A novel evolutionary formulation of the maximum independent set problem
Venue: arXiv cs.NE 2003
Year: 2003

We introduce a novel evolutionary formulation of the problem of finding a maximum independent set of a graph. The new formulation is based on the relationship that exists between a graph's independence number and its acyclic orientations. It views such orientations as individuals and evolves them with the aid of evolutionary operators that are very heavily based on the structure of the graph and its acyclic orientations. The resulting heuristic has been tested on some of the Second DIMACS Implementation Challenge benchmark graphs, and has been found to be competitive when compared to several of the other heuristics that have also been tested on those graphs.
New Lattice Based Cryptographic Constructions
Venue: arXiv cs.CR 2003
Year: 2003

We introduce the use of Fourier analysis on lattices as an integral part of a lattice based construction. The tools we develop provide an elegant description of certain Gaussian distributions around lattice points. Our results include two cryptographic constructions which are based on the worst-case hardness of the unique shortest vector problem. The main result is a new public key cryptosystem whose security guarantee is considerably stronger than previous results ($O(n^{1.5})$ instead of $O(n^7)$). This provides the first alternative to Ajtai and Dwork's original 1996 cryptosystem. Our second result is a family of collision resistant hash functions which, apart from improving the security in terms of the unique shortest vector problem, is also the first example of an analysis which is not based on Ajtai's iterative step. Surprisingly, both results are derived from one theorem which presents two indistinguishable distributions on the segment $[0,1)$. It seems that this theorem can have further applications and as an example we mention how it can be used to solve an open problem related to quantum computation.
A Hierarchical Situation Calculus
Venue: arXiv cs.AI 2003
Year: 2003

A situation calculus is presented that provides a solution to the frame problem for hierarchical situations, that is, situations that have a modular structure in which parts of the situation behave in a relatively independent manner. This situation calculus is given in a relational, functional, and modal logic form. Each form permits both a single level hierarchy or a multiple level hierarchy, giving six versions of the formalism in all, and a number of sub-versions of these. For multiple level hierarchies, it is possible to give equations between parts of the situation to impose additional structure on the problem. This approach is compared to others in the literature.
Active Internet Traffic Filtering: Real-time Response to Denial of Service Attacks
Venue: arXiv cs.NI 2003
Year: 2003

Denial of Service (DoS) attacks are one of the most challenging threats to Internet security. An attacker typically compromises a large number of vulnerable hosts and uses them to flood the victim's site with malicious traffic, clogging its tail circuit and interfering with normal traffic. At present, the network operator of a site under attack has no other resolution but to respond manually by inserting filters in the appropriate edge routers to drop attack traffic. However, as DoS attacks become increasingly sophisticated, manual filter propagation becomes unacceptably slow or even infeasible. In this paper, we present Active Internet Traffic Filtering, a new automatic filter propagation protocol. We argue that this system provides a guaranteed, significant level of protection against DoS attacks in exchange for a reasonable, bounded amount of router resources. We also argue that the proposed system cannot be abused by a malicious node to interfere with normal Internet operation. Finally, we argue that it retains its efficiency in the face of continued Internet growth.
The Wake Up and Report Problem is Time-Equivalent to the Firing Squad Synchronization Problem
Venue: arXiv cs.DC 2003
Year: 2003

We consider several problems relating to strongly-connected directed networks of identical finite-state processors that work synchronously in discrete time steps. The conceptually simplest of these is the Wake Up and Report Problem; this is the problem of having a unique "root" processor send a signal to all other processors in the network and then enter a special "done" state only when all other processors have received the signal. The most difficult of the problems we consider is the classic Firing Squad Synchronization Problem; this is the much-studied problem of achieving macro-synchronization in a network given micro-synchronization. We show via a complex algorithmic application of the "snake" data structure first introduced in Even, Litman, and Winkler [ELW], that these two problems are asymptotically time-equivalent up to a constant factor. This result leads immediately to the inclusion of several other related problems into this new asymptotic time-class.
Using Artificial Intelligence for Model Selection
Venue: arXiv cs.AI 2003
Year: 2003

We apply the optimization algorithm Adaptive Simulated Annealing (ASA) to the problem of analyzing data on a large population and selecting the best model to predict that an individual with various traits will have a particular disease. We compare ASA with traditional forward and backward regression on computer simulated data. We find that the traditional methods of modeling are better for smaller data sets whereas a numerically stable ASA seems to perform better on larger and more complicated data sets.
The Lowell Database Research Self Assessment
Venue: arXiv cs.DB 2003
Year: 2003

A group of senior database researchers gathers every few years to assess the state of database research and to point out problem areas that deserve additional focus. This report summarizes the discussion and conclusions of the sixth ad-hoc meeting held May 4-6, 2003 in Lowell, Mass. It observes that information management continues to be a critical component of most complex software systems. It recommends that database researchers increase focus on: integration of text, data, code, and streams; fusion of information from heterogeneous data sources; reasoning about uncertain data; unsupervised data mining for interesting correlations; information privacy; and self-adaptation and repair.
Event-based Program Analysis with DeWiz
Venue: arXiv cs.SE 2003
Year: 2003

Due to the increased complexity of parallel and distributed programs, debugging of them is considered to be the most difficult and time consuming part of the software lifecycle. Tool support is hence a crucial necessity to hide complexity from the user. However, most existing tools seem inadequate as soon as the program under consideration exploits more than a few processors over a long execution time. This problem is addressed by the novel debugging tool DeWiz (Debugging Wizard), whose focus lies on scalability. DeWiz has a modular, scalable architecture, and uses the event graph model as a representation of the investigated program. DeWiz provides a set of modules, which can be combined to generate, analyze, and visualize event graph data. Within this processing pipeline the toolset tries to extract useful information, which is presented to the user at an arbitrary level of abstraction. Additionally, DeWiz is a framework, which can be used to easily implement arbitrary user-defined modules.
Poster on MPI application in Computational Fluid Dynamics
Venue: arXiv cs.DC 2003
Year: 2003

Poster-presentation of the paper "Message Passing Fluids: molecules as processes in parallel computational fluids" held at "EURO PVMMPI 2003" Congress; the paper is on the proceedings "Recent Advances in Parallel Virtual Machine and Message Passing Interface", 10th European PVM/MPI User's Group Meeting, LNCS 2840, Springer-Verlag, Dongarra-Laforenza-Orlando editors, pp. 550-554.
On Interference of Signals and Generalization in Feedforward Neural Networks
Venue: arXiv cs.NE 2003
Year: 2003

This paper studies how the generalization ability of neurons can be affected by mutual processing of different signals. This study is done on the basis of a feedforward artificial neural network. The mutual processing of signals can possibly be a good model of patterns in a set generalized by a neural network and in effect may improve generalization. In this paper it is discussed that the interference may also cause a highly random generalization. Adaptive activation functions are discussed as a way of reducing that type of generalization. A test of a feedforward neural network is performed that shows the discussed random generalization.
WebTeach in practice: the entrance test to the Engineering faculty in Florence
Venue: arXiv cs.HC 2003
Year: 2003

We present the WebTeach project, formed by a web interface to database for test management, a wiki site for the diffusion of teaching material and student forums, and a suite for the generation of multiple-choice mathematical quiz with automatic elaboration of forms. This system has been massively tested for the entrance test to the Engineering Faculty of the University of Florence, Italy
The Study of the Application of a Keywords-based Chatbot System on the Teaching of Foreign Languages
Venue: arXiv cs.CY 2003
Year: 2003

This paper reports the findings of a study conducted on the application of an on-line human-computer dialog system with natural language (chatbot) on the teaching of foreign languages. A keywords-based human-computer dialog system makes it possible that the user could chat with the computer using a natural language, i.e. in English or in German to some extent. So an experiment has been made using this system online to work as a chat partner with the users learning the foreign languages. Dialogs between the users and the chatbot are collected. Findings indicate that the dialogs between the human and the computer are mostly very short because the user finds the responses from the computer are mostly repeated and irrelevant with the topics and context and the program does not understand the language at all. With analysis of the keywords or pattern-matching mechanism used in this chatbot it can be concluded that this kind of system can not work as a teaching assistant program in foreign language learning.
A combinatorial characterization of higher-dimensional orthogonal packing
Venue: arXiv cs.DS 2003
Year: 2003

Higher-dimensional orthogonal packing problems have a wide range of practical applications, including packing, cutting, and scheduling. Previous efforts for exact algorithms have been unable to avoid structural problems that appear for instances in two- or higher-dimensional space. We present a new approach for modeling packings, using a graph-theoretical characterization of feasible packings. Our characterization allows it to deal with classes of packings that share a certain combinatorial structure, instead of having to consider one packing at a time. In addition, we can make use of elegant algorithmic properties of certain classes of graphs. This allows our characterization to be the basis for a successful branch-and-bound framework. This is the first in a series of papers describing new approaches to higher-dimensional packing.
Automated Fault Localization Using Potential Invariants
Venue: arXiv cs.SE 2003
Year: 2003

We present a general method for fault localization based on abstracting over program traces, and a tool that implements the method using Ernst's notion of potential invariants. Our experiments so far have been unsatisfactory, suggesting that further research is needed before invariants can be used to locate faults.
The Algebra of Utility Inference
Venue: arXiv cs.AI 2003
Year: 2003

Richard Cox [1] set the axiomatic foundations of probable inference and the algebra of propositions. He showed that consistency within these axioms requires certain rules for updating belief. In this paper we use the analogy between probability and utility introduced in [2] to propose an axiomatic foundation for utility inference and the algebra of preferences. We show that consistency within these axioms requires certain rules for updating preference. We discuss a class of utility functions that stems from the axioms of utility inference and show that this class is the basic building block for any general multiattribute utility function. We use this class of utility functions together with the algebra of preferences to construct utility functions represented by logical operations on the attributes.
Kleene algebra with domain
Venue: arXiv cs.LO 2003
Year: 2003

We propose Kleene algebra with domain (KAD), an extension of Kleene algebra with two equational axioms for a domain and a codomain operation, respectively. KAD considerably augments the expressiveness of Kleene algebra, in particular for the specification and analysis of state transition systems. We develop the basic calculus, discuss some related theories and present the most important models of KAD. We demonstrate applicability by two examples: First, an algebraic reconstruction of Noethericity and well-foundedness; second, an algebraic reconstruction of propositional Hoare logic.