OpenRaiser/Intern-Atlas huggingface dataset:
DepAnn - An Annotation Tool for Dependency Treebanks
Venue: arXiv cs.CL 2006
Year: 2006

DepAnn is an interactive annotation tool for dependency treebanks, providing both graphical and text-based annotation interfaces. The tool is aimed for semi-automatic creation of treebanks. It aids the manual inspection and correction of automatically created parses, making the annotation process faster and less error-prone. A novel feature of the tool is that it enables the user to view outputs from several parsers as the basis for creating the final tree to be saved to the treebank. DepAnn uses TIGER-XML, an XML-based general encoding format for both, representing the parser outputs and saving the annotated treebank. The tool includes an automatic consistency checker for sentence structures. In addition, the tool enables users to build structures manually, add comments on the annotations, modify the tagsets, and mark sentences for further revision.
Proof Nets and the Identity of Proofs
Venue: arXiv cs.LO 2006
Year: 2006

These are the notes for a 5-lecture-course given at ESSLLI 2006 in Malaga, Spain. The URL of the school is http://esslli2006.lcc.uma.es/ . This version slightly differs from the one which has been distributed at the school because typos have been removed and comments and suggestions by students have been worked in. The course is intended to be introductory. That means no prior knowledge of proof nets is required. However, the student should be familiar with the basics of propositional logic, and should have seen formal proofs in some formal deductive system (e.g., sequent calculus, natural deduction, resolution, tableaux, calculus of structures, Frege-Hilbert-systems, ...). It is probably helpful if the student knows already what cut elimination is, but this is not strictly necessary. In these notes, I will introduce the concept of ``proof nets'' from the viewpoint of the problem of the identity of proofs. I will proceed in a rather informal way. The focus will be more on presenting ideas than on presenting technical details. The goal of the course is to give the student an overview of the theory of proof nets and make the vast amount of literature on the topic easier accessible to the beginner. For introducing the basic concepts of the theory, I will in the first part of the course stick to the unit-free multiplicative fragment of linear logic because of its rather simple notion of proof nets. In the second part of the course we will see proof nets for more sophisticated logics. This is a basic introduction into proof nets from the perspective of the identity of proofs. We discuss how deductive proofs can be translated into proof nets and what a correctness criterion is.
How to beat the sphere-packing bound with feedback
Venue: arXiv cs.IT 2006
Year: 2006

The sphere-packing bound $E_{sp}(R)$ bounds the reliability function for fixed-length block-codes. For symmetric channels, it remains a valid bound even when strictly causal noiseless feedback is allowed from the decoder to the encoder. To beat the bound, the problem must be changed. While it has long been known that variable-length block codes can do better when trading-off error probability with expected block-length, this correspondence shows that the {\em fixed-delay} setting also presents such an opportunity for generic channels. While $E_{sp}(R)$ continues to bound the tradeoff between bit error and fixed end-to-end latency for symmetric channels used {\em without} feedback, a new bound called the ``focusing bound'' gives the limits on what can be done with feedback. If low-rate reliable flow-control is free (ie. the noisy channel has strictly positive zero-error capacity), then the focusing bound can be asymptotically achieved. Even when the channel has no zero-error capacity, it is possible to substantially beat the sphere-packing bound by synthesizing an appropriately reliable channel to carry the flow-control information.
Coding into a source: a direct inverse Rate-Distortion theorem
Venue: arXiv cs.IT 2006
Year: 2006

Shannon proved that if we can transmit bits reliably at rates larger than the rate distortion function $R(D)$, then we can transmit this source to within a distortion $D$. We answer the converse question ``If we can transmit a source to within a distortion $D$, can we transmit bits reliably at rates less than the rate distortion function?'' in the affirmative. This can be viewed as a direct converse of the rate distortion theorem.
On LAO Testing of Multiple Hypotheses for Many Independent Objects
Venue: arXiv cs.IT 2006
Year: 2006

The problem of many hypotheses logarithmically asymptotically optimal (LAO) testing for a model consisting of three or more independent objects is solved. It is supposed that $M$ probability distributions are known and each object independently of others follows to one of them. The matrix of asymptotic interdependencies (reliability--reliability functions) of all possible pairs of the error probability exponents (reliabilities) in optimal testing for this model is studied. This problem was introduced (and solved for the case of two objects and two given probability distributions) by Ahlswede and Haroutunian. The model with two independent objects with $M$ hypotheses was explored by Haroutunian and Hakobyan.
Nonlinear Estimators and Tail Bounds for Dimension Reduction in $l_1$ Using Cauchy Random Projections
Venue: arXiv cs.DS 2006
Year: 2006

For dimension reduction in $l_1$, the method of {\em Cauchy random projections} multiplies the original data matrix $\mathbf{A} \in\mathbb{R}^{n\times D}$ with a random matrix $\mathbf{R} \in \mathbb{R}^{D\times k}$ ($k\ll\min(n,D)$) whose entries are i.i.d. samples of the standard Cauchy C(0,1). Because of the impossibility results, one can not hope to recover the pairwise $l_1$ distances in $\mathbf{A}$ from $\mathbf{B} = \mathbf{AR} \in \mathbb{R}^{n\times k}$, using linear estimators without incurring large errors. However, nonlinear estimators are still useful for certain applications in data stream computation, information retrieval, learning, and data mining. We propose three types of nonlinear estimators: the bias-corrected sample median estimator, the bias-corrected geometric mean estimator, and the bias-corrected maximum likelihood estimator. The sample median estimator and the geometric mean estimator are asymptotically (as $k\to \infty$) equivalent but the latter is more accurate at small $k$. We derive explicit tail bounds for the geometric mean estimator and establish an analog of the Johnson-Lindenstrauss (JL) lemma for dimension reduction in $l_1$, which is weaker than the classical JL lemma for dimension reduction in $l_2$. Asymptotically, both the sample median estimator and the geometric mean estimators are about 80% efficient compared to the maximum likelihood estimator (MLE). We analyze the moments of the MLE and propose approximating the distribution of the MLE by an inverse Gaussian.
Coupling of quantum angular momenta: an insight into analogic/discrete and local/global models of computation
Venue: arXiv cs.CC 2006
Year: 2006

In the past few years there has been a tumultuous activity aimed at introducing novel conceptual schemes for quantum computing. The approach proposed in (Marzuoli A and Rasetti M 2002, 2005a) relies on the (re)coupling theory of SU(2) angular momenta and can be viewed as a generalization to arbitrary values of the spin variables of the usual quantum-circuit model based on `qubits' and Boolean gates. Computational states belong to finite-dimensional Hilbert spaces labelled by both discrete and continuous parameters, and unitary gates may depend on quantum numbers ranging over finite sets of values as well as continuous (angular) variables. Such a framework is an ideal playground to discuss discrete (digital) and analogic computational processes, together with their relationships occuring when a consistent semiclassical limit takes place on discrete quantum gates. When working with purely discrete unitary gates, the simulator is naturally modelled as families of quantum finite states--machines which in turn represent discrete versions of topological quantum computation models. We argue that our model embodies a sort of unifying paradigm for computing inspired by Nature and, even more ambitiously, a universal setting in which suitably encoded quantum symbolic manipulations of combinatorial, topological and algebraic problems might find their `natural' computational reference model.
A Scalable Protocol for Cooperative Time Synchronization Using Spatial Averaging
Venue: arXiv cs.NI 2006
Year: 2006

Time synchronization is an important aspect of sensor network operation. However, it is well known that synchronization error accumulates over multiple hops. This presents a challenge for large-scale, multi-hop sensor networks with a large number of nodes distributed over wide areas. In this work, we present a protocol that uses spatial averaging to reduce error accumulation in large-scale networks. We provide an analysis to quantify the synchronization improvement achieved using spatial averaging and find that in a basic cooperative network, the skew and offset variance decrease approximately as $1/\bar{N}$ where $\bar{N}$ is the number of cooperating nodes. For general networks, simulation results and a comparison to basic cooperative network results are used to illustrate the improvement in synchronization performance.
Interactive Problem Solving in Prolog
Venue: arXiv cs.HC 2006
Year: 2006

This paper presents an environment for solving Prolog problems which has been implemented as a module for the virtual laboratory VILAB. During the problem solving processes the learners get fast adaptive feedback. As a result analysing the learner's actions the system suggests the use of suitable auxiliary predicates which will also be checked for proper implementation. The focus of the environment has been set on robustness and the integration in VILAB.
Efficient and Dynamic Group Key Agreement in Ad hoc Networks
Venue: arXiv cs.CR 2006
Year: 2006

Confidentiality, integrity and authentication are more relevant issues in Ad hoc networks than in wired fixed networks. One way to address these issues is the use of symmetric key cryptography, relying on a secret key shared by all members of the network. But establishing and maintaining such a key (also called the session key) is a non-trivial problem. We show that Group Key Agreement (GKA) protocols are suitable for establishing and maintaining such a session key in these dynamic networks. We take an existing GKA protocol, which is robust to connectivity losses and discuss all the issues for good functioning of this protocol in Ad hoc networks. We give implementation details and network parameters, which significantly reduce the computational burden of using public key cryptography in such networks.
Strategies for Replica Placement in Tree Networks
Venue: arXiv cs.DC 2006
Year: 2006

In this paper, we discuss and compare several policies to place replicas in tree networks, subject to server capacity and QoS constraints. The client requests are known beforehand, while the number and location of the servers are to be determined. The standard approach in the literature is to enforce that all requests of a client be served by the closest server in the tree. We introduce and study two new policies. In the first policy, all requests from a given client are still processed by the same server, but this server can be located anywhere in the path from the client to the root. In the second policy, the requests of a given client can be processed by multiple servers. One major contribution of this paper is to assess the impact of these new policies on the total replication cost. Another important goal is to assess the impact of server heterogeneity, both from a theoretical and a practical perspective. In this paper, we establish several new complexity results, and provide several efficient polynomial heuristics for NP-complete instances of the problem. These heuristics are compared to an absolute lower bound provided by the formulation of the problem in terms of the solution of an integer linear program.
Nonsymmetric entropy I: basic concepts and results
Venue: arXiv cs.IT 2006
Year: 2006

A new concept named nonsymmetric entropy which generalizes the concepts of Boltzman's entropy and shannon's entropy, was introduced. Maximal nonsymmetric entropy principle was proven. Some important distribution laws were derived naturally from maximal nonsymmetric entropy principle.
Groebner Bases Applied to Systems of Linear Difference Equations
Venue: arXiv cs.SC 2006
Year: 2006

In this paper we consider systems of partial (multidimensional) linear difference equations. Specifically, such systems arise in scientific computing under discretization of linear partial differential equations and in computational high energy physics as recurrence relations for multiloop Feynman integrals. The most universal algorithmic tool for investigation of linear difference systems is based on their transformation into an equivalent Groebner basis form. We present an algorithm for this transformation implemented in Maple. The algorithm and its implementation can be applied to automatic generation of difference schemes for linear partial differential equations and to reduction of Feynman integrals. Some illustrative examples are given.
Analytic Tableaux Calculi for KLM Logics of Nonmonotonic Reasoning
Venue: arXiv cs.LO 2006
Year: 2006

We present tableau calculi for some logics of nonmonotonic reasoning, as defined by Kraus, Lehmann and Magidor. We give a tableau proof procedure for all KLM logics, namely preferential, loop-cumulative, cumulative and rational logics. Our calculi are obtained by introducing suitable modalities to interpret conditional assertions. We provide a decision procedure for the logics considered, and we study their complexity.
HowTo Authenticate and Encrypt
Venue: arXiv cs.CR 2006
Year: 2006

Recently, various side-channel attacks on widely used encryption methods have been discovered. Extensive research is currently undertaken to develop new types of combined encryption and authentication mechanisms. Developers of security systems ask whether to implement methods recommended by international standards or to choose one of the new proposals. We explain the nature of the attacks and how they can be avoided, and recommend a sound, provably secure solution: the CCM standard.
Capacity of a Class of Deterministic Relay Channels
Venue: arXiv cs.IT 2006
Year: 2006

The capacity of a class of deterministic relay channels with the transmitter input X, the receiver output Y, the relay output Y_1 = f(X, Y), and a separate communication link from the relay to the receiver with capacity R_0, is shown to be C(R_0) = \max_{p(x)} \min \{I(X;Y)+R_0, I(X;Y, Y_1) \}. Thus every bit from the relay is worth exactly one bit to the receiver. Two alternative coding schemes are presented that achieve this capacity. The first scheme, ``hash-and-forward'', is based on a simple yet novel use of random binning on the space of relay outputs, while the second scheme uses the usual ``compress-and-forward''. In fact, these two schemes can be combined together to give a class of optimal coding schemes. As a corollary, this relay capacity result confirms a conjecture by Ahlswede and Han on the capacity of a channel with rate-limited state information at the decoder in the special case when the channel state is recoverable from the channel input and the output.
Distributed Link Scheduling with Constant Overhead
Venue: arXiv cs.NI 2006
Year: 2006

This paper proposes a new class of simple, distributed algorithms for scheduling in wireless networks. The algorithms generate new schedules in a distributed manner via simple local changes to existing schedules. The class is parameterized by integers $k\geq 1$. We show that algorithm $k$ of our class achieves $k/(k+2)$ of the capacity region, for every $k\geq 1$. The algorithms have small and constant worst-case overheads: in particular, algorithm $k$ generates a new schedule using {\em (a)} time less than $4k+2$ round-trip times between neighboring nodes in the network, and {\em (b)} at most three control transmissions by any given node, for any $k$. The control signals are explicitly specified, and face the same interference effects as normal data transmissions. Our class of distributed wireless scheduling algorithms are the first ones guaranteed to achieve any fixed fraction of the capacity region while using small and constant overheads that do not scale with network size. The parameter $k$ explicitly captures the tradeoff between control overhead and scheduler throughput performance and provides a tuning knob protocol designers can use to harness this trade-off in practice.
Capabilities Engineering: Constructing Change-Tolerant Systems
Venue: arXiv cs.SE 2006
Year: 2006

We propose a Capabilities-based approach for building long-lived, complex systems that have lengthy development cycles. User needs and technology evolve during these extended development periods, and thereby, inhibit a fixed requirements-oriented solution specification. In effect, for complex emergent systems, the traditional approach of baselining requirements results in an unsatisfactory system. Therefore, we present an alternative approach, Capabilities Engineering, which mathematically exploits the structural semantics of the Function Decomposition graph - a representation of user needs - to formulate Capabilities. For any given software system, the set of derived Capabilities embodies change-tolerant characteristics. More specifically, each individual Capability is a functional abstraction constructed to be highly cohesive and to be minimally coupled with its neighbors. Moreover, the Capability set is chosen to accommodate an incremental development approach, and to reflect the constraints of technology feasibility and implementation schedules. We discuss our validation activities to empirically prove that the Capabilities-based approach results in change-tolerant systems.
Evolutionary Optimization in an Algorithmic Setting
Venue: arXiv cs.NE 2006
Year: 2006

Evolutionary processes proved very useful for solving optimization problems. In this work, we build a formalization of the notion of cooperation and competition of multiple systems working toward a common optimization goal of the population using evolutionary computation techniques. It is justified that evolutionary algorithms are more expressive than conventional recursive algorithms. Three subclasses of evolutionary algorithms are proposed here: bounded finite, unbounded finite and infinite types. Some results on completeness, optimality and search decidability for the above classes are presented. A natural extension of Evolutionary Turing Machine model developed in this paper allows one to mathematically represent and study properties of cooperation and competition in a population of optimized species.
Fuzzy Logic Classification of Imaging Laser Desorption Fourier Transform Mass Spectrometry Data
Venue: arXiv cs.AI 2006
Year: 2006

A fuzzy logic based classification engine has been developed for classifying mass spectra obtained with an imaging internal source Fourier transform mass spectrometer (I^2LD-FTMS). Traditionally, an operator uses the relative abundance of ions with specific mass-to-charge (m/z) ratios to categorize spectra. An operator does this by comparing the spectrum of m/z versus abundance of an unknown sample against a library of spectra from known samples. Automated positioning and acquisition allow I^2LD-FTMS to acquire data from very large grids, this would require classification of up to 3600 spectrum per hour to keep pace with the acquisition. The tedious job of classifying numerous spectra generated in an I^2LD-FTMS imaging application can be replaced by a fuzzy rule base if the cues an operator uses can be encapsulated. We present the translation of linguistic rules to a fuzzy classifier for mineral phases in basalt. This paper also describes a method for gathering statistics on ions, which are not currently used in the rule base, but which may be candidates for making the rule base more accurate and complete or to form new rule bases based on data obtained from known samples. A spatial method for classifying spectra with low membership values, based on neighboring sample classifications, is also presented.
Reliable Multi-Path Routing Schemes for Real-Time Streaming
Venue: arXiv cs.NI 2006
Year: 2006

In off-line streaming, packet level erasure resilient Forward Error Correction (FEC) codes rely on the unrestricted buffering time at the receiver. In real-time streaming, the extremely short playback buffering time makes FEC inefficient for protecting a single path communication against long link failures. It has been shown that one alternative path added to a single path route makes packet level FEC applicable even when the buffering time is limited. Further path diversity, however, increases the number of underlying links increasing the total link failure rate, requiring from the sender possibly more FEC packets. We introduce a scalar coefficient for rating a multi-path routing topology of any complexity. It is called Redundancy Overall Requirement (ROR) and is proportional to the total number of adaptive FEC packets required for protection of the communication. With the capillary routing algorithm, introduced in this paper we build thousands of multi-path routing patterns. By computing their ROR coefficients, we show that contrary to the expectations the overall requirement in FEC codes is reduced when the further diversity of dual-path routing is achieved by the capillary routing algorithm.
Analysis of an Efficient Distributed Algorithm for Mutual Exclusion (Average-Case Analysis of Path Reversal)
Venue: arXiv cs.DC 2006
Year: 2006

The algorithm analysed by Naïmi, Trehe and Arnold was the very first distributed algorithm to solve the mutual exclusion problem in complete networks by using a dynamic logical tree structure as its basic distributed data structure, viz. a path reversal transformation in rooted n-node trees; besides, it was also the first one to achieve a logarithmic average-case message complexity. The present paper proposes a direct and general approach to compute the moments of the cost of path reversal. It basically uses one-one correspondences between combinatorial structures and the associated probability generating functions: the expected cost of path reversal is thus proved to be exactly $H_{n-1}$. Moreover, time and message complexity of the algorithm as well as randomized bounds on its worst-case message complexity in arbitrary networks are also given. The average-case analysis of path reversal and the analysis of this distributed algorithm for mutual exclusion are thus fully completed in the paper. The general techniques used should also prove available and fruitful when adapted to the most efficient recent tree-based distributed algorithms for mutual exclusion which require powerful tools, particularly for average-case analyses.
On the space complexity of one-pass compression
Venue: arXiv cs.IT 2006
Year: 2006

We study how much memory one-pass compression algorithms need to compete with the best multi-pass algorithms. We call a one-pass algorithm an (f (n, \ell))-footprint compressor if, given $n$, $\ell$ and an $n$-ary string $S$, it stores $S$ in ((\rule{0ex}{2ex} O (H_\ell (S)) + o (\log n)) |S| + O (n^{\ell + 1} \log n)) bits -- where (H_\ell (S)) is the $\ell$th-order empirical entropy of $S$ -- while using at most (f (n, \ell)) bits of memory. We prove that, for any (ε> 0) and some (f (n, \ell) \in O (n^{\ell + ε} \log n)), there is an (f (n, \ell))-footprint compressor; on the other hand, there is no (f (n, \ell))-footprint compressor for (f (n, \ell) \in o (n^\ell \log n)).