OpenRaiser/Intern-Atlas huggingface dataset:
The Integration of Connectionism and First-Order Knowledge Representation and Reasoning as a Challenge for Artificial Intelligence
Venue: arXiv cs.AI 2004
Year: 2004

Intelligent systems based on first-order logic on the one hand, and on artificial neural networks (also called connectionist systems) on the other, differ substantially. It would be very desirable to combine the robust neural networking machinery with symbolic knowledge representation and reasoning paradigms like logic programming in such a way that the strengths of either paradigm will be retained. Current state-of-the-art research, however, fails by far to achieve this ultimate goal. As one of the main obstacles to be overcome we perceive the question how symbolic knowledge can be encoded by means of connectionist systems: Satisfactory answers to this will naturally lead the way to knowledge extraction algorithms and to integrated neural-symbolic systems.
ScheduleNanny: Using GPS to Learn the User's Significant Locations, Travel Times and Schedule
Venue: arXiv cs.AI 2004
Year: 2004

As computing technology becomes more pervasive, personal devices such as the PDA, cell-phone, and notebook should use context to determine how to act. Location is one form of context that can be used in many ways. We present a multiple-device system that collects and clusters GPS data into significant locations. These locations are then used to determine travel times and a probabilistic model of the user's schedule, which is used to intelligently alert the user. We evaluate our system and suggest how it should be integrated with a variety of applications.
Checking modes of HAL programs
Venue: arXiv cs.PL 2004
Year: 2004

Recent constraint logic programming (CLP) languages, such as HAL and Mercury, require type, mode and determinism declarations for predicates. This information allows the generation of efficient target code and the detection of many errors at compile-time. Unfortunately, mode checking in such languages is difficult. One of the main reasons is that, for each predicate mode declaration, the compiler is required to appropriately re-order literals in the predicate's definition. The task is further complicated by the need to handle complex instantiations (which interact with type declarations and higher-order predicates) and automatic initialization of solver variables. Here we define mode checking for strongly typed CLP languages which require reordering of clause body literals. In addition, we show how to handle a simple case of polymorphic modes by using the corresponding polymorphic types.
A Directed -Threshold Multi-Signature Scheme
Venue: arXiv cs.CR 2004
Year: 2004

In this paper, we propose a Directed Threshold Multi-Signature Scheme. In this threshold signature scheme, any malicious set of signers cannot impersonate any other set of signers to forge the signatures. In case of forgery, it is possible to trace the signing set. This threshold signature scheme is applicable when the message is sensitive to the signature receiver; and the signatures are generated by the cooperation of a number of people from a given group of senders.
Some Applications of Directed Signature Scheme
Venue: arXiv cs.CR 2004
Year: 2004

Directed signature scheme is applicable when the signed message contains information sensitive to the receiver, because only receiver can directly verify the signature and that he/she can prove its validity to any third party, whenever necessary. This paper presents two applications of directed signature scheme. (i) Directed –Delegated Signature Scheme. This scheme combines the idea of proxy signatures with directed signature scheme. (ii) Allocation of registration number. This scheme proposes a registration scheme in which the registration number cannot be forged and misused.
Quantum Complexity Classes
Venue: arXiv cs.CC 2004
Year: 2004

In our thesis, we try to shed more light onto the complexity of quantum complexity classes by refining the related part of the hierarchy. First, we review the basic concepts of quantum computing in general. Then, inspired by BQP, we define new complexity classes. They are placed between BPP and PSPACE. We show that they incorporate the current important quantum algorithms. Furthermore, the importance of the unitarity constraint given by quantum mechanics is revealed. Without this requirement, we naturally arrive at the class AWPP, which was up to now thought to be just an artificially defined class. We hope that some of our newly defined classes could find their use in proving results about BQP.
Better Quasi-Ordered Transition Systems
Venue: arXiv cs.LO 2004
Year: 2004

Many existing algorithms for model checking of infinite-state systems operate on constraints which are used to represent (potentially infinite) sets of states. A general powerful technique which can be employed for proving termination of these algorithms is that of well quasi-orderings. Several methodologies have been proposed for derivation of new well quasi-ordered constraint systems. However, many of these constraint systems suffer from a "constraint explosion problem", as the number of the generated constraints grows exponentially with the size of the problem. In this paper, we demonstrate that a refinement of the theory of well quasi-orderings, called the theory of better quasi-orderings, is more appropriate for symbolic model checking, since it allows inventing constraint systems which are both well quasi-ordered and compact. As a main application, we introduce existential zones, a constraint system for verification of systems with unboundedly many clocks and use our methodology to prove that existential zones are better quasi-ordered. We show how to use existential zones in verification of timed Petri nets and present some experimental results. Also, we apply our methodology to derive new constraint systems for verification of broadcast protocols, lossy channel systems, and integral relational automata. The new constraint systems are exponentially more succinct than existing ones, and their well quasi-ordering cannot be shown by previous methods in the literature.
Strategy in Ulam's Game and Tree Code Give Error-Resistant Protocols
Venue: arXiv cs.DC 2004
Year: 2004

We present a new approach to construction of protocols which are proof against communication errors. The construction is based on a generalization of the well known Ulam's game. We show equivalence between winning strategies in this game and robust protocols for multi-party computation. We do not give any complete theory. We want rather to describe a new fresh idea. We use a tree code defined by Schulman. The tree code is the most important part of the interactive version of Shannon's Coding Theorem proved by Schulman. He uses probabilistic argument for the existence of a tree code without giving any effective construction. We show another proof yielding a randomized construction which in contrary to his proof almost surely gives a good code. Moreover our construction uses much smaller alphabet.
An Extended Generalized Disjunctive Paraconsistent Data Model for Disjunctive Information
Venue: arXiv cs.DB 2004
Year: 2004

This paper presents an extension of generalized disjunctive paraconsistent relational data model in which pure disjunctive positive and negative information as well as mixed disjunctive positive and negative information can be represented explicitly and manipulated. We consider explicit mixed disjunctive information in the context of disjunctive databases as there is an interesting interplay between these two types of information. Extended generalized disjunctive paraconsistent relation is introduced as the main structure in this model. The relational algebra is appropriately generalized to work on extended generalized disjunctive paraconsistent relations and their correctness is established.
Mathematical knowledge management is needed
Venue: arXiv cs.IR 2004
Year: 2004

In this lecture I discuss some aspects of MKM, Mathematical Knowledge Management, with particuar emphasis on information storage and information retrieval.
Robust Dialogue Understanding in HERALD
Venue: arXiv cs.CL 2004
Year: 2004

We tackle the problem of robust dialogue processing from the perspective of language engineering. We propose an agent-oriented architecture that allows us a flexible way of composing robust processors. Our approach is based on Shoham's Agent Oriented Programming (AOP) paradigm. We will show how the AOP agent model can be enriched with special features and components that allow us to deal with classical problems of dialogue understanding.
A knowledge-based approach to semi-automatic annotation of multimedia documents via user adaptation
Venue: arXiv cs.DL 2004
Year: 2004

Current approaches to the annotation process focus on annotation schemas, languages for annotation, or are very application driven. In this paper it is proposed that a more flexible architecture for annotation requires a knowledge component to allow for flexible search and navigation of the annotated material. In particular, it is claimed that a general approach must take into account the needs, competencies, and goals of the producers, annotators, and consumers of the annotated material. We propose that a user-model based approach is, therefore, necessary.
Semantic filtering by inference on domain knowledge in spoken dialogue systems
Venue: arXiv cs.CL 2004
Year: 2004

General natural dialogue processing requires large amounts of domain knowledge as well as linguistic knowledge in order to ensure acceptable coverage and understanding. There are several ways of integrating lexical resources (e.g. dictionaries, thesauri) and knowledge bases or ontologies at different levels of dialogue processing. We concentrate in this paper on how to exploit domain knowledge for filtering interpretation hypotheses generated by a robust semantic parser. We use domain knowledge to semantically constrain the hypothesis space. Moreover, adding an inference mechanism allows us to complete the interpretation when information is not explicitly available. Further, we discuss briefly how this can be generalized towards a predictive natural interactive system.
INSPIRE: Evaluation of a Smart-Home System for Infotainment Management and Device Control
Venue: arXiv cs.HC 2004
Year: 2004

This paper gives an overview of the assessment and evaluation methods which have been used to determine the quality of the INSPIRE smart home system. The system allows different home appliances to be controlled via speech, and consists of speech and speaker recognition, speech understanding, dialogue management, and speech output components. The performance of these components is first assessed individually, and then the entire system is evaluated in an interaction experiment with test users. Initial results of the assessment and evaluation are given, in particular with respect to the transmission channel impact on speech and speaker recognition, and the assessment of speech output for different system metaphors.
Analyzing and Improving Performance of a Class of Anomaly-based Intrusion Detectors
Venue: arXiv cs.CR 2004
Year: 2004

Anomaly-based intrusion detection (AID) techniques are useful for detecting novel intrusions into computing resources. One of the most successful AID detectors proposed to date is stide, which is based on analysis of system call sequences. In this paper, we present a detailed formal framework to analyze, understand and improve the performance of stide and similar AID techniques. Several important properties of stide-like detectors are established through formal proofs, and validated by carefully conducted experiments using test datasets. Finally, the framework is utilized to design two applications to improve the cost and performance of stide-like detectors which are based on sequence analysis. The first application reduces the cost of developing AID detectors by identifying the critical sections in the training dataset, and the second application identifies the intrusion context in the intrusive dataset, that helps to fine-tune the detectors. Such fine-tuning in turn helps to improve detection rate and reduce false alarm rate, thereby increasing the effectiveness and efficiency of the intrusion detectors.
Selfish peering and routing in the Internet
Venue: arXiv cs.GT 2004
Year: 2004

The Internet is a loose amalgamation of independent service providers acting in their own self-interest. We examine the implications of this economic reality on peering relationships. Specifically, we consider how the incentives of the providers might determine where they choose to interconnect with each other. We consider a game where two selfish network providers must establish peering points between their respective network graphs, given knowledge of traffic conditions and a nearest-exit routing policy for out-going traffic, as well as costs based on congestion and peering connectivity. We focus on the pairwise stability equilibrium concept and use a stochastic procedure to solve for the stochastically pairwise stable configurations. Stochastically stable networks are selected for their robustness to deviations in strategy and are therefore posited as the more likely networks to emerge in a dynamic setting. We note a paucity of stochastically stable peering configurations under asymmetric conditions, particularly to unequal interdomain traffic flow, with adverse effects on system-wide efficiency. Under bilateral flow conditions, we find that as the cost associated with the establishment of peering links approaches zero, the variance in the number of peering links of stochastically pairwise stable equilibria increases dramatically.
The Cyborg Astrobiologist: First Field Experience
Venue: arXiv cs.CV 2004
Year: 2004

We present results from the first geological field tests of the `Cyborg Astrobiologist', which is a wearable computer and video camcorder system that we are using to test and train a computer-vision system towards having some of the autonomous decision-making capabilities of a field-geologist and field-astrobiologist. The Cyborg Astrobiologist platform has thus far been used for testing and development of these algorithms and systems: robotic acquisition of quasi-mosaics of images, real-time image segmentation, and real-time determination of interesting points in the image mosaics. The hardware and software systems function reliably, and the computer-vision algorithms are adequate for the first field tests. In addition to the proof-of-concept aspect of these field tests, the main result of these field tests is the enumeration of those issues that we can improve in the future, including: first, detection and accounting for shadows caused by 3D jagged edges in the outcrop; second, reincorporation of more sophisticated texture-analysis algorithms into the system; third, creation of hardware and software capabilities to control the camera's zoom lens in an intelligent manner; and fourth, development of algorithms for interpretation of complex geological scenery. Nonetheless, despite these technical inadequacies, this Cyborg Astrobiologist system, consisting of a camera-equipped wearable-computer and its computer-vision algorithms, has demonstrated its ability of finding genuinely interesting points in real-time in the geological scenery, and then gathering more information about these interest points in an automated manner.
A Directed Threshold - Signature Scheme
Venue: arXiv cs.CR 2004
Year: 2004

Directed signature is the solution of such problems when the signed message contains information sensitive to the signature receiver. Generally, in many application of directed signature, the signer is generally a single person. But when the message is on behalf of an organization, a valid sensitive message may require the approval of several people. Threshold signature schemes are used to solve these problems. This paper presents a threshold directed signature scheme.
The equations of the ideal latches
Venue: arXiv cs.GL 2004
Year: 2004

The latches are simple circuits with feedback from the digital electrical engineering. We have included in our work the C element of Muller, the RS latch, the clocked RS latch, the D latch and also circuits containing two interconnected latches: the edge triggered RS flip-flop, the D flip-flop, the JK flip-flop, the T flip-flop. The purpose of this study is to model with equations the previous circuits, considered to be ideal, i.e. non-inertial. The technique of analysis is the pseudoboolean differential calculus.
Bounded Input Bounded Predefined Control Bounded Output
Venue: arXiv cs.AI 2004
Year: 2004

The paper is an attempt to generalize a methodology, which is similar to the bounded-input bounded-output method currently widely used for the system stability studies. The presented earlier methodology allows decomposition of input space into bounded subspaces and defining for each subspace its bounding surface. It also defines a corresponding predefined control, which maps any point of a bounded input into a desired bounded output subspace. This methodology was improved by providing a mechanism for the fast defining a bounded surface. This paper presents enhanced bounded-input bounded-predefined-control bounded-output approach, which provides adaptability feature to the control and allows transferring of a controlled system along a suboptimal trajectory.
Space Robotics Part 2: Space-based Manipulators
Venue: arXiv cs.RO 2004
Year: 2004

In this second of three short papers, I introduce some of the basic concepts of space robotics with an emphasis on some specific challenging areas of research that are peculiar to the application of robotics to space infrastructure development. The style of these short papers is pedagogical and the concepts in this paper are developed from fundamental manipulator robotics. This second paper considers the application of space manipulators to on-orbit servicing (OOS), an application which has considerable commercial application. I provide some background to the notion of robotic on-orbit servicing and explore how manipulator control algorithms may be modified to accommodate space manipulators which operate in the micro-gravity of space.
A machine-independent port of the SR language run-time system to the NetBSD operating system
Venue: arXiv cs.DC 2004
Year: 2004

SR (synchronizing resources) is a PASCAL - style language enhanced with constructs for concurrent programming developed at the University of Arizona in the late 1980s. MPD (presented in Gregory Andrews' book about Foundations of Multithreaded, Parallel, and Distributed Programming) is its successor, providing the same language primitives with a different syntax. The run-time system (in theory, identical) of both languages provides the illusion of a multiprocessor machine on a single single- or multi- CPU Unix-like system or a (local area) network of Unix-like machines. Chair V of the Computer Science Department of the University of Bonn is operating a laboratory for a practical course in parallel programming consisting of computing nodes running NetBSD/arm, normally used via PVM, MPI etc. We are considering to offer SR and MPD for this, too. As the original language distributions are only targeted at a few commercial Unix systems, some porting effort is needed, outlined in the SR porting guide. The integrated POSIX threads support of NetBSD-2.0 should allow us to use library primitives provided for NetBSD's phtread system to implement the primitives needed by the SR run-time system, thus implementing 13 target CPUs at once and automatically making use of SMP on VAX, Alpha, PowerPC, Sparc, 32-bit Intel and 64 bit AMD CPUs. This paper describes work in progress.
Modules and Logic Programming
Venue: arXiv cs.LO 2004
Year: 2004

We study conditions for a concurrent construction of proof-nets in the framework developed by Andreoli in recent papers. We define specific correctness criteria for that purpose. We first study closed modules (i.e. validity of the execution of a logic program), then extend the criterion to open modules (i.e. validity during the execution) distinguishing criteria for acyclicity and connectability in order to allow incremental verification.
On Invariance and Convergence in Time Complexity theory
Venue: arXiv cs.CC 2004
Year: 2004

This article introduces three invariance principles under which P is different from NP. In the second part a theorem of convergence is proven. This theorem states that for any language L there exists an infinite sequence of languages from O(n) that converges to L.
A Note on Bulk Quantum Turing Machine
Venue: arXiv cs.CC 2004
Year: 2004

Recently, among experiments for realization of quantum computers, NMR quantum computers have achieved the most impressive succession. There is a model of the NMR quantum computation,namely Atsumi and Nishino's bulk quantum Turing Machine. It assumes, however, an unnatural assumption with quantum mechanics. We, then, define a more natural and quantum mechanically realizable modified bulk quantum Turing Machine, and show its computational ability by comparing complexity classes with quantum Turing Machine's counter part.
SDS : Une infrastructure d'installation de logiciels libres pour des organisations multi-sites
Venue: arXiv cs.NI 2004
Year: 2004

Les developpements logiciels sur les systemes UNIX font de plus en plus appel aux logiciels libres. Nous proposons une solution de deploiement et de controle de ces logiciels libres au sein d'une grande organisation. Nous nous attachons particulierement a resoudre les problemes lies au deploiement multi-sites ainsi qu'a la gestion de configuration de ces deploiements. L'originalite de notre approche repose sur sa capacite a etre mise en oeuvre et controlee par les utilisateurs plutot que par les administrateurs, sans necessiter d'expertise particuliere, et par les possibilites de deploiement dans des environnements heterogenes. ----- Free and open source software is more and more used for software developments on UNIX systems. We are proposing a solution to control the deployment of free software in the context of a large corporation, focusing on multi-site deployment and configuration management. The originality of our approach rests on its ability to be implemented and controlled by users rather than administrators, without requiring any particular expertise, and on its facility to be deployed in heterogeneous environments.
Adaptation dynamique de services
Venue: arXiv cs.NI 2004
Year: 2004

This paper proposes a software architecture for dynamical service adaptation. The services are constituted by reusable software components. The adaptation's goal is to optimize the service function of their execution context. For a first step, the context will take into account just the user needs but other elements will be added. A particular feature in our proposition is the profiles that are used not only to describe the context's elements but also the components itself. An Adapter analyzes the compatibility between all these profiles and detects the points where the profiles are not compatibles. The same Adapter search and apply the possible adaptation solutions: component customization, insertion, extraction or replacement.