OpenRaiser/Intern-Atlas huggingface dataset:
On Modal Logics of Partial Recursive Functions
Venue: arXiv cs.LO 2004
Year: 2004

The classical propositional logic is known to be sound and complete with respect to the set semantics that interprets connectives as set operations. The paper extends propositional language by a new binary modality that corresponds to partial recursive function type constructor under the above interpretation. The cases of deterministic and non-deterministic functions are considered and for both of them semantically complete modal logics are described and decidability of these logics is established.
On the Complexity of Case-Based Planning
Venue: arXiv cs.AI 2004
Year: 2004

We analyze the computational complexity of problems related to case-based planning: planning when a plan for a similar instance is known, and planning from a library of plans. We prove that planning from a single case has the same complexity than generative planning (i.e., planning "from scratch"); using an extended definition of cases, complexity is reduced if the domain stored in the case is similar to the one to search plans for. Planning from a library of cases is shown to have the same complexity. In both cases, the complexity of planning remains, in the worst case, PSPACE-complete.
Exploiting Semidefinite Relaxations in Constraint Programming
Venue: arXiv cs.DM 2004
Year: 2004

Constraint programming uses enumeration and search tree pruning to solve combinatorial optimization problems. In order to speed up this solution process, we investigate the use of semidefinite relaxations within constraint programming. In principle, we use the solution of a semidefinite relaxation to guide the traversal of the search tree, using a limited discrepancy search strategy. Furthermore, a semidefinite relaxation produces a bound for the solution value, which is used to prune parts of the search tree. Experimental results on stable set and maximum clique problem instances show that constraint programming can indeed greatly benefit from semidefinite relaxations.
Preferred Answer Sets for Ordered Logic Programs
Venue: arXiv cs.LO 2004
Year: 2004

We extend answer set semantics to deal with inconsistent programs (containing classical negation), by finding a ``best'' answer set. Within the context of inconsistent programs, it is natural to have a partial order on rules, representing a preference for satisfying certain rules, possibly at the cost of violating less important ones. We show that such a rule order induces a natural order on extended answer sets, the minimal elements of which we call preferred answer sets. We characterize the expressiveness of the resulting semantics and show that it can simulate negation as failure, disjunction and some other formalisms such as logic programs with ordered disjunction. The approach is shown to be useful in several application areas, e.g. repairing database, where minimal repairs correspond to preferred answer sets. To appear in Theory and Practice of Logic Programming (TPLP).
Universal Convergence of Semimeasures on Individual Random Sequences
Venue: arXiv cs.LG 2004
Year: 2004

Solomonoff's central result on induction is that the posterior of a universal semimeasure M converges rapidly and with probability 1 to the true sequence generating posterior mu, if the latter is computable. Hence, M is eligible as a universal sequence predictor in case of unknown mu. Despite some nearby results and proofs in the literature, the stronger result of convergence for all (Martin-Loef) random sequences remained open. Such a convergence result would be particularly interesting and natural, since randomness can be defined in terms of M itself. We show that there are universal semimeasures M which do not converge for all random sequences, i.e. we give a partial negative answer to the open problem. We also provide a positive answer for some non-universal semimeasures. We define the incomputable measure D as a mixture over all computable measures and the enumerable semimeasure W as a mixture over all enumerable nearly-measures. We show that W converges to D and D to mu on all random sequences. The Hellinger distance measuring closeness of two distributions plays a central role.
A Sequent Calculus and a Theorem Prover for Standard Conditional Logics
Venue: arXiv cs.LO 2004
Year: 2004

In this paper we present a cut-free sequent calculus, called SeqS, for some standard conditional logics, namely CK, CK+ID, CK+MP and CK+MP+ID. The calculus uses labels and transition formulas and can be used to prove decidability and space complexity bounds for the respective logics. We also present CondLean, a theorem prover for these logics implementing SeqS calculi written in SICStus Prolog.
Semantic Linking - a Context-Based Approach to Interactivity in Hypermedia
Venue: arXiv cs.IR 2004
Year: 2004

The semantic Web initiates new, high level access schemes to online content and applications. One area of superior need for a redefined content exploration is given by on-line educational applications and their concepts of interactivity in the framework of open hypermedia systems. In the present paper we discuss aspects and opportunities of gaining interactivity schemes from semantic notions of components. A transition from standard educational annotation to semantic statements of hyperlinks is discussed. Further on we introduce the concept of semantic link contexts as an approach to manage a coherent rhetoric of linking. A practical implementation is introduced, as well. Our semantic hyperlink implementation is based on the more general Multimedia Information Repository MIR, an open hypermedia system supporting the standards XML, Corba and JNDI.
Multi-Embedding of Metric Spaces
Venue: arXiv cs.DS 2004
Year: 2004

Metric embedding has become a common technique in the design of algorithms. Its applicability is often dependent on how high the embedding's distortion is. For example, embedding finite metric space into trees may require linear distortion as a function of its size. Using probabilistic metric embeddings, the bound on the distortion reduces to logarithmic in the size. We make a step in the direction of bypassing the lower bound on the distortion in terms of the size of the metric. We define "multi-embeddings" of metric spaces in which a point is mapped onto a set of points, while keeping the target metric of polynomial size and preserving the distortion of paths. The distortion obtained with such multi-embeddings into ultrametrics is at most O(log Delta loglog Delta) where Delta is the aspect ratio of the metric. In particular, for expander graphs, we are able to obtain constant distortion embeddings into trees in contrast with the Omega(log n) lower bound for all previous notions of embeddings. We demonstrate the algorithmic application of the new embeddings for two optimization problems: group Steiner tree and metrical task systems.
Educational Content Management - A Cellular Approach
Venue: arXiv cs.CY 2004
Year: 2004

In recent times online educational applications more and more are requested to provide self-consistent learning offers for students at the university level. Consequently they need to cope with the wide range of complexity and interrelations university course teaching brings along. An urgent need to overcome simplistically linked HTMLc ontent pages becomes apparent. In the present paper we discuss a schematic concept of educational content construction from information cells and introduce its implementation on the storage and runtime layer. Starting from cells content is annotated according to didactic needs, structured for dynamic arrangement, dynamically decorated with hyperlinks and, as all works are based on XML, open to any presentation layer. Data can be variably accessed through URIs built on semantic path-names and edited via an adaptive authoring toolbox. Our content management approach is based on the more general Multimedia Information Repository MIR. and allows for personalisation, as well. MIR is an open system supporting the standards XML, Corba and JNDI.
Iterative Quantization Using Codes On Graphs
Venue: arXiv cs.IT 2004
Year: 2004

We study codes on graphs combined with an iterative message passing algorithm for quantization. Specifically, we consider the binary erasure quantization (BEQ) problem which is the dual of the binary erasure channel (BEC) coding problem. We show that duals of capacity achieving codes for the BEC yield codes which approach the minimum possible rate for the BEQ. In contrast, low density parity check codes cannot achieve the minimum rate unless their density grows at least logarithmically with block length. Furthermore, we show that duals of efficient iterative decoding algorithms for the BEC yield efficient encoding algorithms for the BEQ. Hence our results suggest that graphical models may yield near optimal codes in source coding as well as in channel coding and that duality plays a key role in such constructions.
On the Theory of Structural Subtyping
Venue: arXiv cs.LO 2004
Year: 2004

We show that the first-order theory of structural subtyping of non-recursive types is decidable. Let $Σ$ be a language consisting of function symbols (representing type constructors) and $C$ a decidable structure in the relational language $L$ containing a binary relation $\leq$. $C$ represents primitive types; $\leq$ represents a subtype ordering. We introduce the notion of $Σ$-term-power of $C$, which generalizes the structure arising in structural subtyping. The domain of the $Σ$-term-power of $C$ is the set of $Σ$-terms over the set of elements of $C$. We show that the decidability of the first-order theory of $C$ implies the decidability of the first-order theory of the $Σ$-term-power of $C$. Our decision procedure makes use of quantifier elimination for term algebras and Feferman-Vaught theorem. Our result implies the decidability of the first-order theory of structural subtyping of non-recursive types.
Diagnosabilities of regular networks
Venue: arXiv cs.NI 2004
Year: 2004

In this paper, we study diagnosabilities of multiprocessor systems under two diagnosis models: the PMC model and the comparison model. In each model, we further consider two different diagnosis strategies: the precise diagnosis strategy proposed by Preparata et al. and the pessimistic diagnosis strategy proposed by Friedman. The main result of this paper is to determine diagnosabilities of regular networks with certain conditions, which include several widely used multiprocessor systems such as variants of hypercubes and many others.
Tsnnls: A solver for large sparse least squares problems with non-negative variables
Venue: arXiv cs.MS 2004
Year: 2004

The solution of large, sparse constrained least-squares problems is a staple in scientific and engineering applications. However, currently available codes for such problems are proprietary or based on MATLAB. We announce a freely available C implementation of the fast block pivoting algorithm of Portugal, Judice, and Vicente. Our version is several times faster than Matstoms' MATLAB implementation of the same algorithm. Further, our code matches the accuracy of MATLAB's built-in lsqnonneg function.
Performance Characterisation of Intra-Cluster Collective Communications
Venue: arXiv cs.DC 2004
Year: 2004

Although recent works try to improve collective communication in grid systems by separating intra and inter-cluster communication, the optimisation of communications focus only on inter-cluster communications. We believe, instead, that the overall performance of the application may be improved if intra-cluster collective communications performance is known in advance. Hence, it is important to have an accurate model of the intra-cluster collective communications, which provides the necessary evidences to tune and to predict their performance correctly. In this paper we present our experience on modelling such communication strategies. We describe and compare different implementation strategies with their communication models, evaluating the models' accuracy and describing the practical challenges that can be found when modelling collective communications.
Fast Tuning of Intra-Cluster Collective Communications
Venue: arXiv cs.DC 2004
Year: 2004

Recent works try to optimise collective communication in grid systems focusing mostly on the optimisation of communications among different clusters. We believe that intra-cluster collective communications should also be optimised, as a way to improve the overall efficiency and to allow the construction of multi-level collective operations. Indeed, inside homogeneous clusters, a simple optimisation approach rely on the comparison from different implementation strategies, through their communication models. In this paper we evaluate this approach, comparing different implementation strategies with their predicted performances. As a result, we are able to choose the communication strategy that better adapts to each network environment.
Monitoring, Analyzing, and Controlling Internet-scale Systems with ACME
Venue: arXiv cs.DC 2004
Year: 2004

Analyzing and controlling large distributed services under a wide range of conditions is difficult. Yet these capabilities are essential to a number of important development and operational tasks such as benchmarking, testing, and system management. To facilitate these tasks, we have built the Application Control and Monitoring Environment (ACME), a scalable, flexible infrastructure for monitoring, analyzing, and controlling Internet-scale systems. ACME consists of two parts. ISING, the Internet Sensor In-Network agGregator, queries sensors and aggregates the results as they are routed through an overlay network. ENTRIE, the ENgine for TRiggering Internet Events, uses the data streams supplied by ISING, in combination with a user's XML configuration file, to trigger actuators such as killing processes during a robustness benchmark or paging a system administrator when predefined anomalous conditions are observed. In this paper we describe the design, implementation, and evaluation of ACME and its constituent parts. We find that for a 512-node system running atop an emulated Internet topology, ISING's use of in-network aggregation can reduce end-to-end query-response latency by more than 50% compared to using either direct network connections or the same overlay network without aggregation. We also find that an untuned implementation of ACME can invoke an actuator on one or all nodes in response to a discrete or aggregate event in less than four seconds, and we illustrate ACME's applicability to concrete benchmarking and monitoring scenarios.
Dynamic Localization Protocols for Mobile Sensor Networks
Venue: arXiv cs.NI 2004
Year: 2004

The ability of a sensor node to determine its physical location within a network (Localization) is of fundamental importance in sensor networks. Interpretating data from sensors will not be possible unless the context of the data is known; this is most often accomplished by tracking its physical location. Existing research has focused on localization in static sensor networks where localization is a one-time (or low frequency) activity. In contrast, this paper considers localization for mobile sensors: when sensors are mobile, localization must be invoked periodically to enable the sensors to track their location. The higher the frequency of localization, the lower the error introduced because of mobility. However, localization is a costly operation since it involves both communication and computation. In this paper, we propose and investigate adaptive and predictive protocols that control the frequency of localization based on sensor mobility behavior to reduce the energy requirements for localization while bounding the localization error. We show that such protocols can significantly reduce the localization energy without sacrificing accuracy (in fact, improving accuracy for most situations). Using simulation and analysis we explore the tradeoff between energy efficiency and localization error due to mobility for several protocols.
An electronic dictionary as a basis for NLP tools: The Greek case
Venue: arXiv cs.CL 2004
Year: 2004

The existence of a Dictionary in electronic form for Modern Greek (MG) is mandatory if one is to process MG at the morphological and syntactic levels since MG is a highly inflectional language with marked stress and a spelling system with many characteristics carried over from Ancient Greek. Moreover, such a tool becomes necessary if one is to create efficient and sophisticated NLP applications with substantial linguistic backing and coverage. The present paper will focus on the deployment of such an electronic dictionary for Modern Greek, which was built in two phases: first it was constructed to be the basis for a spelling correction schema and then it was reconstructed in order to become the platform for the deployment of a wider spectrum of NLP tools.
Sharing Computer Network Logs for Security and Privacy: A Motivation for New Methodologies of Anonymization
Venue: arXiv cs.CR 2004
Year: 2004

Logs are one of the most fundamental resources to any security professional. It is widely recognized by the government and industry that it is both beneficial and desirable to share logs for the purpose of security research. However, the sharing is not happening or not to the degree or magnitude that is desired. Organizations are reluctant to share logs because of the risk of exposing sensitive information to potential attackers. We believe this reluctance remains high because current anonymization techniques are weak and one-size-fits-all--or better put, one size tries to fit all. We must develop standards and make anonymization available at varying levels, striking a balance between privacy and utility. Organizations have different needs and trust other organizations to different degrees. They must be able to map multiple anonymization levels with defined risks to the trust levels they share with (would-be) receivers. It is not until there are industry standards for multiple levels of anonymization that we will be able to move forward and achieve the goal of widespread sharing of logs for security researchers.
The strength of replacement in weak arithmetic
Venue: arXiv cs.LO 2004
Year: 2004

The replacement (or collection or choice) axiom scheme asserts bounded quantifier exchange. We prove the independence of this scheme from various weak theories of arithmetic, sometimes under a complexity assumption.
Using a hierarchy of Domain Specific Languages in complex software systems design
Venue: arXiv cs.PL 2004
Year: 2004

A new design methodology is introduced, with some examples on building Domain Specific Languages hierarchy on top of Scheme.
A Generalized Disjunctive Paraconsistent Data Model for Negative and Disjunctive Information
Venue: arXiv cs.DB 2004
Year: 2004

This paper presents a generalization of the disjunctive paraconsistent relational data model in which disjunctive positive and negative information can be represented explicitly and manipulated. There are situations where the closed world assumption to infer negative facts is not valid or undesirable and there is a need to represent and reason with negation explicitly. We consider explicit disjunctive negation in the context of disjunctive databases as there is an interesting interplay between these two types of information. Generalized disjunctive paraconsistent relation is introduced as the main structure in this model. The relational algebra is appropriately generalized to work on generalized disjunctive paraconsistent relations and their correctness is established.
Should Cyberspace Chat Rooms be closed to protect Children?
Venue: arXiv cs.CY 2004
Year: 2004

The explosion of people networking in cyberspace, disseminating terabytes of information, is being promoted through the use of broadband, bluetooth technology, and wireless mobile computing facilities. New communities within such venues as virtual chat rooms discussion groups, newsgroups etc are being created daily and even hourly. This is raising issues of cyberethics concerning privacy,security, crime, human needs, e-business, e-healthcare, e-government and intellectual property among others that need to be evaluated and reflected upon. With this new freedom come new moral and ethical responsibilities, which raise questions as to whether anything can be published or whether there should be restrictions. This paper addresses one specific area, that has come into the public eye, the closure by Microsoft of all of its free chat rooms.
Topics in asynchronous systems
Venue: arXiv cs.AR 2004
Year: 2004

In the paper we define and characterize the asynchronous systems from the point of view of their autonomy, determinism, order, non-anticipation, time invariance, symmetry, stability and other important properties. The study is inspired by the models of the asynchronous circuits.
A TCSP-like decidable constraint language generalising existing cardinal direction relations
Venue: arXiv cs.AI 2004
Year: 2004

We define a quantitative constraint language subsuming two calculi well-known in QSR (Qualitative Spatial Reasoning): Frank's cone-shaped and projection-based calculi of cardinal direction relations. We show how to solve a CSP (Constraint Satisfaction Problem) expressed in the language.
All Superlinear Inverse Schemes are coNP-Hard
Venue: arXiv cs.CC 2004
Year: 2004

How hard is it to invert NP-problems? We show that all superlinearly certified inverses of NP problems are coNP-hard. To do so, we develop a novel proof technique that builds diagonalizations against certificates directly into a circuit.
Frequent Knot Discovery
Venue: arXiv cs.DB 2004
Year: 2004

We explore the possibility of applying the framework of frequent pattern mining to a class of continuous objects appearing in nature, namely knots. We introduce the frequent knot mining problem and present a solution. The key observation is that a database consisting of knots can be transformed into a transactional database. This observation is based on the Prime Decomposition Theorem of knots.
Neural Architectures for Robot Intelligence
Venue: arXiv cs.RO 2004
Year: 2004

We argue that the direct experimental approaches to elucidate the architecture of higher brains may benefit from insights gained from exploring the possibilities and limits of artificial control architectures for robot systems. We present some of our recent work that has been motivated by that view and that is centered around the study of various aspects of hand actions since these are intimately linked with many higher cognitive abilities. As examples, we report on the development of a modular system for the recognition of continuous hand postures based on neural nets, the use of vision and tactile sensing for guiding prehensile movements of a multifingered hand, and the recognition and use of hand gestures for robot teaching. Regarding the issue of learning, we propose to view real-world learning from the perspective of data mining and to focus more strongly on the imitation of observed actions instead of purely reinforcement-based exploration. As a concrete example of such an effort we report on the status of an ongoing project in our lab in which a robot equipped with an attention system with a neurally inspired architecture is taught actions by using hand gestures in conjunction with speech commands. We point out some of the lessons learnt from this system, and discuss how systems of this kind can contribute to the study of issues at the junction between natural and artificial cognitive systems.
A 2-chain can interlock with a k-chain
Venue: arXiv cs.CG 2004
Year: 2004

One of the open problems posed in [3] is: what is the minimal number k such that an open, flexible k-chain can interlock with a flexible 2-chain? In this paper, we establish the assumption behind this problem, that there is indeed some k that achieves interlocking. We prove that a flexible 2-chain can interlock with a flexible, open 16-chain.