OpenRaiser/Intern-Atlas huggingface dataset:
Exploiting multilingual nomenclatures and language-independent text features as an interlingua for cross-lingual text analysis applications
Venue: arXiv cs.CL 2006
Year: 2006

We are proposing a simple, but efficient basic approach for a number of multilingual and cross-lingual language technology applications that are not limited to the usual two or three languages, but that can be applied with relatively little effort to larger sets of languages. The approach consists of using existing multilingual linguistic resources such as thesauri, nomenclatures and gazetteers, as well as exploiting the existence of additional more or less language-independent text items such as dates, currency expressions, numbers, names and cognates. Mapping texts onto the multilingual resources and identifying word token links between texts in different languages are basic ingredients for applications such as cross-lingual document similarity calculation, multilingual clustering and categorisation, cross-lingual document retrieval, and tools to provide cross-lingual information access.
A tool set for the quick and efficient exploration of large document collections
Venue: arXiv cs.CL 2006
Year: 2006

We are presenting a set of multilingual text analysis tools that can help analysts in any field to explore large document collections quickly in order to determine whether the documents contain information of interest, and to find the relevant text passages. The automatic tool, which currently exists as a fully functional prototype, is expected to be particularly useful when users repeatedly have to sieve through large collections of documents such as those downloaded automatically from the internet. The proposed system takes a whole document collection as input. It first carries out some automatic analysis tasks (named entity recognition, geo-coding, clustering, term extraction), annotates the texts with the generated meta-information and stores the meta-information in a database. The system then generates a zoomable and hyperlinked geographic map enhanced with information on entities and terms found. When the system is used on a regular basis, it builds up a historical database that contains information on which names have been mentioned together with which other names or places, and users can query this database to retrieve information extracted in the past.
Coverage and Connectivity in Three-Dimensional Networks
Venue: arXiv cs.NI 2006
Year: 2006

Most wireless terrestrial networks are designed based on the assumption that the nodes are deployed on a two-dimensional (2D) plane. However, this 2D assumption is not valid in underwater, atmospheric, or space communications. In fact, recent interest in underwater acoustic ad hoc and sensor networks hints at the need to understand how to design networks in 3D. Unfortunately, the design of 3D networks is surprisingly more difficult than the design of 2D networks. For example, proofs of Kelvin's conjecture and Kepler's conjecture required centuries of research to achieve breakthroughs, whereas their 2D counterparts are trivial to solve. In this paper, we consider the coverage and connectivity issues of 3D networks, where the goal is to find a node placement strategy with 100% sensing coverage of a 3D space, while minimizing the number of nodes required for surveillance. Our results indicate that the use of the Voronoi tessellation of 3D space to create truncated octahedral cells results in the best strategy. In this truncated octahedron placement strategy, the transmission range must be at least 1.7889 times the sensing range in order to maintain connectivity among nodes. If the transmission range is between 1.4142 and 1.7889 times the sensing range, then a hexagonal prism placement strategy or a rhombic dodecahedron placement strategy should be used. Although the required number of nodes in the hexagonal prism and the rhombic dodecahedron placement strategies is the same, this number is 43.25% higher than the number of nodes required by the truncated octahedron placement strategy. We verify by simulation that our placement strategies indeed guarantee ubiquitous coverage. We believe that our approach and our results presented in this paper could be used for extending the processes of 2D network design to 3D networks.
A Non-anchored Unified Naming System for Ad Hoc Computing Environments
Venue: arXiv cs.DC 2006
Year: 2006

A ubiquitous computing environment consists of many resources that need to be identified by users and applications. Users and developers require some way to identify resources by human readable names. In addition, ubiquitous computing environments impose additional requirements such as the ability to work well with ad hoc situations and the provision of names that depend on context. The Non-anchored Unified Naming (NUN) system was designed to satisfy these requirements. It is based on relative naming among resources and provides the ability to name arbitrary types of resources. By having resources themselves take part in naming, resources are able to able contribute their specialized knowledge into the name resolution process, making context-dependent mapping of names to resources possible. The ease of which new resource types can be added makes it simple to incorporate new types of contextual information within names. In this paper, we describe the naming system and evaluate its use.
On Intentional Attacks and Protections in Complex Communication Networks
Venue: arXiv cs.NI 2006
Year: 2006

Being motivated by recent developments in the theory of complex networks, we examine the robustness of communication networks under intentional attack that takes down network nodes in a decreasing order of their nodal degrees. In this paper, we study two different effects that have been largely missed in the existing results: (i) some communication networks, like Internet, are too large for anyone to have global information of their topologies, which makes the accurate intentional attack practically impossible; and (ii) most attacks in communication networks are propagated from one node to its neighborhood node(s), utilizing local network-topology information only. We show that incomplete global information has different impacts to the intentional attack in different circumstances, while local information-based attacks can be actually highly efficient. Such insights would be helpful for the future developments of efficient network attack/protection schemes.
Solution of a Problem of Barendregt on Sensible lambda-Theories
Venue: arXiv cs.LO 2006
Year: 2006

<i>H</i> is the theory extending β-conversion by identifying all closed unsolvables. <i>H</i>ω is the closure of this theory under the ω-rule (and β-conversion). A long-standing conjecture of H. Barendregt states that the provable equations of <i>H</i>ω form Π<sub>1</sub><sup>1</sup>-complete set. Here we prove that conjecture.
Finite-State Dimension and Lossy Decompressors
Venue: arXiv cs.CC 2006
Year: 2006

This paper examines information-theoretic questions regarding the difficulty of compressing data versus the difficulty of decompressing data and the role that information loss plays in this interaction. Finite-state compression and decompression are shown to be of equivalent difficulty, even when the decompressors are allowed to be lossy. Inspired by Kolmogorov complexity, this paper defines the optimal *decompression *ratio achievable on an infinite sequence by finite-state decompressors (that is, finite-state transducers outputting the sequence in question). It is shown that the optimal compression ratio achievable on a sequence S by any *information lossless* finite state compressor, known as the finite-state dimension of S, is equal to the optimal decompression ratio achievable on S by any finite-state decompressor. This result implies a new decompression characterization of finite-state dimension in terms of lossy finite-state transducers.
Throughput Optimal Distributed Control of Stochastic Wireless Networks
Venue: arXiv cs.NI 2006
Year: 2006

The Maximum Differential Backlog (MDB) control policy of Tassiulas and Ephremides has been shown to adaptively maximize the stable throughput of multi-hop wireless networks with random traffic arrivals and queueing. The practical implementation of the MDB policy in wireless networks with mutually interfering links, however, requires the development of distributed optimization algorithms. Within the context of CDMA-based multi-hop wireless networks, we develop a set of node-based scaled gradient projection power control algorithms which solves the MDB optimization problem in a distributed manner using low communication overhead. As these algorithms require time to converge to a neighborhood of the optimum, the optimal rates determined by the MDB policy can only be found iteratively over time. For this, we show that the iterative MDB policy with convergence time remains throughput optimal.
A multipurpose Hopf deformation of the Algebra of Feynman-like Diagrams
Venue: arXiv cs.OH 2006
Year: 2006

We construct a three parameter deformation of the Hopf algebra $\mathbf{LDIAG}$. This new algebra is a true Hopf deformation which reduces to $\mathbf{LDIAG}$ on one hand and to $\mathbf{MQSym}$ on the other, relating $\mathbf{LDIAG}$ to other Hopf algebras of interest in contemporary physics. Further, its product law reproduces that of the algebra of polyzeta functions.
A Richer Understanding of the Complexity of Election Systems
Venue: arXiv cs.GT 2006
Year: 2006

We provide an overview of some recent progress on the complexity of election systems. The issues studied include the complexity of the winner, manipulation, bribery, and control problems.
Constructing LDPC Codes by 2-Lifts
Venue: arXiv cs.IT 2006
Year: 2006

We propose a new low-density parity-check code construction scheme based on 2-lifts. The proposed codes have an advantage of admitting efficient hardware implementations. With the motivation of designing codes with low error floors, we present an analysis of the low-weight stopping set distributions of the proposed codes. Based on this analysis, we propose design criteria for designing codes with low error floors. Numerical results show that the resulting codes have low error probabilities over binary erasure channels.
Verification, Validation and Integrity of Distributed and Interchanged Rule Based Policies and Contracts in the Semantic Web
Venue: arXiv cs.AI 2006
Year: 2006

Rule-based policy and contract systems have rarely been studied in terms of their software engineering properties. This is a serious omission, because in rule-based policy or contract representation languages rules are being used as a declarative programming language to formalize real-world decision logic and create IS production systems upon. This paper adopts an SE methodology from extreme programming, namely test driven development, and discusses how it can be adapted to verification, validation and integrity testing (V&V&I) of policy and contract specifications. Since, the test-driven approach focuses on the behavioral aspects and the drawn conclusions instead of the structure of the rule base and the causes of faults, it is independent of the complexity of the rule language and the system under test and thus much easier to use and understand for the rule engineer and the user.
Optimal Design of Multiple Description Lattice Vector Quantizers
Venue: arXiv cs.IT 2006
Year: 2006

In the design of multiple description lattice vector quantizers (MDLVQ), index assignment plays a critical role. In addition, one also needs to choose the Voronoi cell size of the central lattice v, the sublattice index N, and the number of side descriptions K to minimize the expected MDLVQ distortion, given the total entropy rate of all side descriptions Rt and description loss probability p. In this paper we propose a linear-time MDLVQ index assignment algorithm for any K >= 2 balanced descriptions in any dimensions, based on a new construction of so-called K-fraction lattice. The algorithm is greedy in nature but is proven to be asymptotically (N -> infinity) optimal for any K >= 2 balanced descriptions in any dimensions, given Rt and p. The result is stronger when K = 2: the optimality holds for finite N as well, under some mild conditions. For K > 2, a local adjustment algorithm is developed to augment the greedy index assignment, and conjectured to be optimal for finite N. Our algorithmic study also leads to better understanding of v, N and K in optimal MDLVQ design. For K = 2 we derive, for the first time, a non-asymptotical closed form expression of the expected distortion of optimal MDLVQ in p, Rt, N. For K > 2, we tighten the current asymptotic formula of the expected distortion, relating the optimal values of N and K to p and Rt more precisely.
Problem Evolution: A new approach to problem solving systems
Venue: arXiv cs.NE 2006
Year: 2006

In this paper we present a novel tool to evaluate problem solving systems. Instead of using a system to solve a problem, we suggest using the problem to evaluate the system. By finding a numerical representation of a problem's complexity, one can implement genetic algorithm to search for the most complex problem the given system can solve. This allows a comparison between different systems that solve the same set of problems. In this paper we implement this approach on pattern recognition neural networks to try and find the most complex pattern a given configuration can solve. The complexity of the pattern is calculated using linguistic complexity. The results demonstrate the power of the problem evolution approach in ranking different neural network configurations according to their pattern recognition abilities. Future research and implementations of this technique are also discussed.
Semantic Description of Parameters in Web Service Annotations
Venue: arXiv cs.AI 2006
Year: 2006

A modification of OWL-S regarding parameter description is proposed. It is strictly based on Description Logic. In addition to class description of parameters it also allows the modelling of relations between parameters and the precise description of the size of data to be supplied to a service. In particular, it solves two major issues identified within current proposals for a Semantic Web Service annotation standard.
Dynamic Spectrum Access: Signal Processing, Networking, and Regulatory Policy
Venue: arXiv cs.NI 2006
Year: 2006

In this article, we first provide a taxonomy of dynamic spectrum access. We then focus on opportunistic spectrum access, the overlay approach under the hierarchical access model of dynamic spectrum access. we aim to provide an overview of challenges and recent developments in both technological and regulatory aspects of opportunistic spectrum access.
Modelling and Simulation of Scheduling Policies Implemented in Ethernet Switch by Using Coloured Petri Nets
Venue: arXiv cs.NI 2006
Year: 2006

The objective of this paper is to propose models enabling to study the behaviour of Ethernet switch for Networked Control Systems. Two scheduler policies are analyzed: the static priority and the WRR (Weighted Round Robin). The modelling work is based on Coloured Petri Nets. A temporal validation step based on the simulation of these modelling, shows that the obtained results are near to the expected behaviour of these scheduler policies.
Use of upper bound delay estimate in stability analysis and robust control compensation in networked control systems
Venue: arXiv cs.NI 2006
Year: 2006

Recent interest in networked control systems (NCS) has instigated research in various areas of both communication networks and control. The analysis of NCS has often been performed either from the network, or the control point of view and not many papers exist were the analysis of both is done in the same context. Here a simple overall analysis is presented. In the paper the procedure of obtaining the upper bound delay value in the switched Ethernet network is proposed and the obtained delay estimate is used in stability analysis of the feedback loop and in the control compensation. The upper bound delay algorithm is based on the network calculus theory, the stability analysis uses the small gain theorem, and control compensating strategy is based on Smith predictor, where however the upper bound delay is utilised in obtaining the delay estimate.
Entangled Graphs
Venue: arXiv cs.IT 2006
Year: 2006

In this paper we prove a separability criterion for mixed states in $\mathbb C^p\otimes\mathbb C^q$. We also show that the density matrix of a graph with only one entangled edge is entangled.
A Fast Image Encryption Scheme based on Chaotic Standard Map
Venue: arXiv cs.CR 2006
Year: 2006

In recent years, a variety of effective chaos-based image encryption schemes have been proposed. The typical structure of these schemes has the permutation and the diffusion stages performed alternatively. The confusion and diffusion effect is solely contributed by the permutation and the diffusion stage, respectively. As a result, more overall rounds than necessary are required to achieve a certain level of security. In this paper, we suggest to introduce certain diffusion effect in the confusion stage by simple sequential add-and-shift operations. The purpose is to reduce the workload of the time-consuming diffusion part so that fewer overall rounds and hence a shorter encryption time is needed. Simulation results show that at a similar performance level, the proposed cryptosystem needs less than one-third the encryption time of an existing cryptosystem. The effective acceleration of the encryption speed is thus achieved.
Redundancies of Correction-Capability-Optimized Reed-Muller Codes
Venue: arXiv cs.IT 2006
Year: 2006

This article is focused on some variations of Reed-Muller codes that yield improvements to the rate for a prescribed decoding performance under the Berlekamp-Massey-Sakata algorithm with majority voting. Explicit formulas for the redundancies of the new codes are given.
On Semigroups Generated by Two Consecutive Integers and Improved Hermitian Codes
Venue: arXiv cs.IT 2006
Year: 2006

Analysis of the Berlekamp-Massey-Sakata algorithm for decoding one-point codes leads to two methods for improving code rate. One method, due to Feng and Rao, removes parity checks that may be recovered by their majority voting algorithm. The second method is to design the code to correct only those error vectors of a given weight that are also geometrically generic. In this work, formulae are given for the redundancies of Hermitian codes optimized with respect to these criteria as well as the formula for the order bound on the minimum distance. The results proceed from an analysis of numerical semigroups generated by two consecutive integers. The formula for the redundancy of optimal Hermitian codes correcting a given number of errors answers an open question stated by Pellikaan and Torres in 1999.
Domain Wall Displacement Detection Technology Research Report
Venue: arXiv cs.OH 2006
Year: 2006

This article introduce a new data storage method called DWDD(Domain Wall Displacement Detection) and tell you why it succeed.
Cooperative Processes for Scientific Workflows
Venue: arXiv cs.NI 2006
Year: 2006

The work described in this paper is a contribution to the problems of managing in data-intensive scientific applications. First, we discuss scientific workflows and motivate there use in scientific applications. Then, we introduce the concept of cooperative processes and describe their interactions and uses in a flexible cooperative workflow system called \textit{Bonita}. Finally, we propose an approach to integrate and synthesize the data exchanged by the mapping of data-intensive science into Bonita, using a binary approach, and illustrate the endeavors done to enhance the performance computations within a dynamic environment.
The Capacity Region of a Class of Discrete Degraded Interference Channels
Venue: arXiv cs.IT 2006
Year: 2006

We provide a single-letter characterization for the capacity region of a class of discrete degraded interference channels (DDICs). The class of DDICs considered includes the discrete additive degraded interference channel (DADIC) studied by Benzel. We show that for the class of DDICs studied, encoder cooperation does not increase the capacity region, and therefore, the capacity region of the class of DDICs is the same as the capacity region of the corresponding degraded broadcast channel.
Capacity of the Trapdoor Channel with Feedback
Venue: arXiv cs.IT 2006
Year: 2006

We establish that the feedback capacity of the trapdoor channel is the logarithm of the golden ratio and provide a simple communication scheme that achieves capacity. As part of the analysis, we formulate a class of dynamic programs that characterize capacities of unifilar finite-state channels. The trapdoor channel is an instance that admits a simple analytic solution.
The Mathematical Parallels Between Packet Switching and Information Transmission
Venue: arXiv cs.IT 2006
Year: 2006

All communication networks comprise of transmission systems and switching systems, even though they are usually treated as two separate issues. Communication channels are generally disturbed by noise from various sources. In circuit switched networks, reliable communication requires the error-tolerant transmission of bits over noisy channels. In packet switched networks, however, not only can bits be corrupted with noise, but resources along connection paths are also subject to contention. Thus, quality of service (QoS) is determined by buffer delays and packet losses. The theme of this paper is to show that transmission noise and packet contention actually have similar characteristics and can be tamed by comparable means to achieve reliable communication, and a number of analogies between switching and transmission are identified. The sampling theorem of bandlimited signals provides the cornerstone of digital communication and signal processing. Recently, the Birkhoff-von Neumann decomposition of traffic matrices has been widely applied to packet switches. With respect to the complexity reduction of packet switching, we show that the decomposition of a doubly stochastic traffic matrix plays a similar role to that of the sampling theorem in digital transmission. We conclude that packet switching systems are governed by mathematical laws that are similar to those of digital transmission systems as envisioned by Shannon in his seminal 1948 paper, A Mathematical Theory of Communication.
Finite-Dimensional Bounds on Zm and Binary LDPC Codes with Belief Propagation Decoders
Venue: arXiv cs.IT 2006
Year: 2006

This paper focuses on finite-dimensional upper and lower bounds on decodable thresholds of Zm and binary low-density parity-check (LDPC) codes, assuming belief propagation decoding on memoryless channels. A concrete framework is presented, admitting systematic searches for new bounds. Two noise measures are considered: the Bhattacharyya noise parameter and the soft bit value for a maximum a posteriori probability (MAP) decoder on the uncoded channel. For Zm LDPC codes, an iterative m-dimensional bound is derived for m-ary-input/symmetric-output channels, which gives a sufficient stability condition for Zm LDPC codes and is complemented by a matched necessary stability condition introduced herein. Applications to coded modulation and to codes with non-equiprobable distributed codewords are also discussed. For binary codes, two new lower bounds are provided for symmetric channels, including a two-dimensional iterative bound and a one-dimensional non-iterative bound, the latter of which is the best known bound that is tight for binary symmetric channels (BSCs), and is a strict improvement over the bound derived by the channel degradation argument. By adopting the reverse channel perspective, upper and lower bounds on the decodable Bhattacharyya noise parameter are derived for non-symmetric channels, which coincides with the existing bound for symmetric channels.