OpenRaiser/Intern-Atlas huggingface dataset:
Tarski's influence on computer science
Venue: arXiv cs.GL 2006
Year: 2006

The influence of Alfred Tarski on computer science was indirect but significant in a number of directions and was in certain respects fundamental. Here surveyed is the work of Tarski on the decision procedure for algebra and geometry, the method of elimination of quantifiers, the semantics of formal languages, modeltheoretic preservation theorems, and algebraic logic; various connections of each with computer science are taken up.
k-Connectivity in the Semi-Streaming Model
Venue: arXiv cs.DM 2006
Year: 2006

We present the first semi-streaming algorithms to determine k-connectivity of an undirected graph with k being any constant. The semi-streaming model for graph algorithms was introduced by Muthukrishnan in 2003 and turns out to be useful when dealing with massive graphs streamed in from an external storage device. Our two semi-streaming algorithms each compute a sparse subgraph of an input graph G and can use this subgraph in a postprocessing step to decide k-connectivity of G. To this end the first algorithm reads the input stream only once and uses time O(k^2*n) to process each input edge. The second algorithm reads the input k+1 times and needs time O(k+alpha(n)) per input edge. Using its constructed subgraph the second algorithm can also generate all l-separators of the input graph for all l<k.
Algorithmic linear dimension reduction in the l_1 norm for sparse vectors
Venue: arXiv cs.DS 2006
Year: 2006

This paper develops a new method for recovering m-sparse signals that is simultaneously uniform and quick. We present a reconstruction algorithm whose run time, O(m log^2(m) log^2(d)), is sublinear in the length d of the signal. The reconstruction error is within a logarithmic factor (in m) of the optimal m-term approximation error in l_1. In particular, the algorithm recovers m-sparse signals perfectly and noisy signals are recovered with polylogarithmic distortion. Our algorithm makes O(m log^2 (d)) measurements, which is within a logarithmic factor of optimal. We also present a small-space implementation of the algorithm. These sketching techniques and the corresponding reconstruction algorithms provide an algorithmic dimension reduction in the l_1 norm. In particular, vectors of support m in dimension d can be linearly embedded into O(m log^2 d) dimensions with polylogarithmic distortion. We can reconstruct a vector from its low-dimensional sketch in time O(m log^2(m) log^2(d)). Furthermore, this reconstruction is stable and robust under small perturbations.
Analog Codes on Graphs
Venue: arXiv cs.IT 2006
Year: 2006

We consider the problem of transmission of a sequence of real data produced by a Nyquist sampled band-limited analog source over a band-limited analog channel, which introduces an additive white Gaussian noise. An analog coding scheme is described, which can achieve a mean-squared error distortion proportional to $(1+SNR)^{-B}$ for a bandwidth expansion factor of $B/R$, where $0 < R < 1$ is the rate of individual component binary codes used in the construction and $B \geq 1$ is an integer. Thus, over a wide range of SNR values, the proposed code performs much better than any single previously known analog coding system.
Automated verification of weak equivalence within the SMODELS system
Venue: arXiv cs.AI 2006
Year: 2006

In answer set programming (ASP), a problem at hand is solved by (i) writing a logic program whose answer sets correspond to the solutions of the problem, and by (ii) computing the answer sets of the program using an answer set solver as a search engine. Typically, a programmer creates a series of gradually improving logic programs for a particular problem when optimizing program length and execution time on a particular solver. This leads the programmer to a meta-level problem of ensuring that the programs are equivalent, i.e., they give rise to the same answer sets. To ease answer set programming at methodological level, we propose a translation-based method for verifying the equivalence of logic programs. The basic idea is to translate logic programs P and Q under consideration into a single logic program EQT(P,Q) whose answer sets (if such exist) yield counter-examples to the equivalence of P and Q. The method is developed here in a slightly more general setting by taking the visibility of atoms properly into account when comparing answer sets. The translation-based approach presented in the paper has been implemented as a translator called lpeq that enables the verification of weak equivalence within the smodels system using the same search engine as for the search of models. Our experiments with lpeq and smodels suggest that establishing the equivalence of logic programs in this way is in certain cases much faster than naive cross-checking of answer sets.
Spherical Indexing for Neighborhood Queries
Venue: arXiv cs.DS 2006
Year: 2006

This is an algorithm for finding neighbors when the objects can freely move and have no predefined position. The query consists in finding neighbors for a center location and a given radius. Space is discretized in cubic cells. This algorithm introduces a direct spherical indexing that gives the list of all cells making up the query sphere, for any radius and any center location. It can additionally take in account both cyclic and non-cyclic regions of interest. Finding only the K nearest neighbors naturally benefits from the spherical indexing by minimally running through the sphere from center to edge, and reducing the maximum distance when K neighbors have been found.
An Architectural Style for Ajax
Venue: arXiv cs.SE 2006
Year: 2006

A new breed of web application, dubbed AJAX, is emerging in response to a limited degree of interactivity in large-grain stateless Web interactions. At the heart of this new approach lies a single page interaction model that facilitates rich interactivity. We have studied and experimented with several AJAX frameworks trying to understand their architectural properties. In this paper, we summarize three of these frameworks and examine their properties and introduce the SPIAR architectural style. We describe the guiding software engineering principles and the constraints chosen to induce the desired properties. The style emphasizes user interface component development, and intermediary delta-communication between client/server components, to improve user interactivity and ease of development. In addition, we use the concepts and principles to discuss various open issues in AJAX frameworks and application development.
A Java Based Architecture of P2P-Grid Middleware
Venue: arXiv cs.DC 2006
Year: 2006

During the last decade there has been a huge interest in Grid technologies, and numerous Grid projects have been initiated with various visions of the Grid. While all these visions have the same goal of resource sharing, they differ in the functionality that a Grid supports, characterization, programming environments, etc. We present a new Grid system dedicated to dealing with data issues, called DGET (Data Grid Environment and Tools). DGET is characterized by its peerto- peer communication system and entity-based architecture, therefore, taking advantage of the main functionality of both systems; P2P and Grid. DGET is currently under development and a prototype implementing the main components is in its first phase of testing. In this paper we limit our description to the system architectural features and to the main differences with other systems. Keywords: Grid Computing, Peer to Peer, Peer to Peer Grid
Neural Network Clustering Based on Distances Between Objects
Venue: arXiv cs.CV 2006
Year: 2006

We present an algorithm of clustering of many-dimensional objects, where only the distances between objects are used. Centers of classes are found with the aid of neuron-like procedure with lateral inhibition. The result of clustering does not depend on starting conditions. Our algorithm makes it possible to give an idea about classes that really exist in the empirical data. The results of computer simulations are presented.
Security Analysis of A Chaos-based Image Encryption Algorithm
Venue: arXiv cs.MM 2006
Year: 2006

The security of Fridrich Image Encryption Algorithm against brute-force attack, statistical attack, known-plaintext attack and select-plaintext attack is analyzed by investigating the properties of the involved chaotic maps and diffusion functions. Based on the given analyses, some means are proposed to strengthen the overall performance of the focused cryptosystem.
On the confluence of lambda-calculus with conditional rewriting
Venue: arXiv cs.LO 2006
Year: 2006

The confluence of untyped lambda-calculus with unconditional rewriting has already been studied in various directions. In this paper, we investigate the confluence of lambda-calculus with conditional rewriting and provide general results in two directions. First, when conditional rules are algebraic. This extends results of Muller and Dougherty for unconditional rewriting. Two cases are considered, whether beta-reduction is allowed or not in the evaluation of conditions. Moreover, Dougherty's result is improved from the assumption of strongly normalizing beta-reduction to weakly normalizing beta-reduction. We also provide examples showing that outside these conditions, modularity of confluence is difficult to achieve. Second, we go beyond the algebraic framework and get new confluence results using an extended notion of orthogonality that takes advantage of the conditional part of rewrite rules.
In Quest of Image Semantics: Are We Looking for It Under the Right Lamppost?
Venue: arXiv cs.CV 2006
Year: 2006

In the last years we witness a dramatic growth of research focused on semantic image understanding. Indeed, without understanding image content successful accomplishment of any image-processing task is simply incredible. Up to the recent times, the ultimate need for such understanding has been met by the knowledge that a domain expert or a vision system supervisor have contributed to every image-processing application. The advent of the Internet has drastically changed this situation. Internet sources of visual information are diffused and dispersed over the whole Web, so the duty of information content discovery and evaluation must be relegated now to an image understanding agent (a machine or a computer program) capable to perform image content assessment at a remote image location. Development of Content Based Image Retrieval (CBIR) techniques was a right move in a right direction, launched about ten years ago. Unfortunately, very little progress has been made since then. The reason for this can be seen in a rank of long lasting misconceptions that CBIR designers are continuing to adhere to. I hope, my arguments will help them to change their minds.
Finding heaviest H-subgraphs in real weighted graphs, with applications
Venue: arXiv cs.DS 2006
Year: 2006

For a graph G with real weights assigned to the vertices (edges), the MAX H-SUBGRAPH problem is to find an H-subgraph of G with maximum total weight, if one exists. The all-pairs MAX H-SUBGRAPH problem is to find for every pair of vertices u,v, a maximum H-subgraph containing both u and v, if one exists. Our main results are new strongly polynomial algorithms for the all-pairs MAX H-SUBGRAPH problem for vertex weighted graphs. We also give improved algorithms for the MAX-H SUBGRAPH problem for edge weighted graphs, and various related problems, including computing the first k most significant bits of the distance product of two matrices. Some of our algorithms are based, in part, on fast matrix multiplication.
Novel Reversible TSG Gate and Its Application for Designing Components of Primitive Reversible/Quantum ALU
Venue: arXiv cs.AR 2006
Year: 2006

In recent years, reversible logic has emerged as a promising computing paradigm having application in low power CMOS, quantum computing, nanotechnology, and optical computing. The classical set of gates such as AND, OR, and EXOR are not reversible. This paper utilizes a new 4 * 4 reversible gate called TSG gate to build the components of a primitive reversible/quantum ALU. The most significant aspect of the TSG gate is that it can work singly as a reversible full adder, that is reversible full adder can now be implemented with a single gate only. A Novel reversible 4:2 compressor is also designed from the TSG gate which is later used to design a novel 8x8 reversible Wallace tree multiplier. It is proved that the adder, 4:2 compressor and multiplier architectures designed using the TSG gate are better than their counterparts available in literature, in terms of number of reversible gates and garbage outputs. This is perhaps, the first attempt to design a reversible 4:2 compressor and a reversible Wallace tree multiplier as far as existing literature and our knowledge is concerned. Thus, this paper provides an initial threshold to build more complex systems which can execute complicated operations using reversible logic.
Approximation Algorithms for the Bipartite Multi-cut Problem
Venue: arXiv cs.CC 2006
Year: 2006

We introduce the {\it Bipartite Multi-cut} problem. This is a generalization of the {\it st-Min-cut} problem, is similar to the {\it Multi-cut} problem (except for more stringent requirements) and also turns out to be an immediate generalization of the {\it Min UnCut} problem. We prove that this problem is {\bf NP}-hard and then present LP and SDP based approximation algorithms. While the LP algorithm is based on the Garg-Vazirani-Yannakakis algorithm for {\it Multi-cut}, the SDP algorithm uses the {\it Structure Theorem} of $\ell_2^2$ Metrics.
On Performance of Event-to-Sink Transport in Transmit-Only Sensor Networks
Venue: arXiv cs.NI 2006
Year: 2006

We consider a hybrid wireless sensor network with regular and transmit-only sensors. The transmit-only sensors do not have receiver circuit, hence are cheaper and less energy consuming, but their transmissions cannot be coordinated. Regular sensors, also called cluster-heads, are responsible for receiving information from transmit-only sensors and forwarding it to sinks. The main goal of such a hybrid network is to reduce the cost of deployment while achieving some performance constraints (minimum coverage, sensing rate, etc). In this paper we are interested in the communication between transmit-only sensors and cluster-heads. We develop a detailed analytical model of the physical and MAC layer using tools from queuing theory and stochastic geometry. (The MAC model, that we call Erlang's loss model with interference, might be of independent interest as adequate for any non-slotted; i.e., unsynchronized, wireless communication channel.) We give an explicit formula for the frequency of successful packet reception by a cluster-head, given sensors' locations. We further define packet admission policies at a cluster-head, and we calculate the optimal policies for different performance criteria. Finally we show that the proposed hybrid network, using the optimal policies, can achieve substantial cost savings as compared to conventional architectures.
On Divergence-Power Inequalities
Venue: arXiv cs.IT 2006
Year: 2006

Expressions for (EPI Shannon type) Divergence-Power Inequalities (DPI) in two cases (time-discrete and band-limited time-continuous) of stationary random processes are given. The new expressions connect the divergence rate of the sum of independent processes, the individual divergence rate of each process, and their power spectral densities. All divergences are between a process and a Gaussian process with same second order statistics, and are assumed to be finite. A new proof of the Shannon entropy-power inequality EPI, based on the relationship between divergence and causal minimum mean-square error (CMMSE) in Gaussian channels with large signal-to-noise ratio, is also shown.
The role of time in considering collections
Venue: arXiv cs.CL 2006
Year: 2006

The paper concerns the understanding of plurals in the framework of Artificial Intelligence and emphasizes the role of time. The construction of collection(s) and their evolution across time is often crucial and has to be accounted for. The paper contrasts a "de dicto" collection where the collection can be considered as persisting over these situations even if its members change with a "de re" collection whose composition does not vary through time. It expresses different criteria of choice between the two interpretations (de re and de dicto) depending on the context of enunciation.
On the logical definability of certain graph and poset languages
Venue: arXiv cs.LO 2006
Year: 2006

We show that it is equivalent, for certain sets of finite graphs, to be definable in CMS (counting monadic second-order logic, a natural extension of monadic second-order logic), and to be recognizable in an algebraic framework induced by the notion of modular decomposition of a finite graph. More precisely, we consider the set $F\_\infty$ of composition operations on graphs which occur in the modular decomposition of finite graphs. If $F$ is a subset of $F\_{\infty}$, we say that a graph is an $\calF$-graph if it can be decomposed using only operations in $F$. A set of $F$-graphs is recognizable if it is a union of classes in a finite-index equivalence relation which is preserved by the operations in $F$. We show that if $F$ is finite and its elements enjoy only a limited amount of commutativity -- a property which we call weak rigidity, then recognizability is equivalent to CMS-definability. This requirement is weak enough to be satisfied whenever all $F$-graphs are posets, that is, transitive dags. In particular, our result generalizes Kuske's recent result on series-parallel poset languages.
Exact Spectral Analysis of Single-h and Multi-h CPM Signals through PAM decomposition and Matrix Series Evaluation
Venue: arXiv cs.IT 2006
Year: 2006

In this paper we address the problem of closed-form spectral evaluation of CPM. We show that the multi-h CPM signal can be conveniently generated by a PTI SM. The output is governed by a Markov chain with the unusual peculiarity of being cyclostationary and reducible; this holds also in the single-h context. Judicious reinterpretation of the result leads to a formalization through a stationary and irreducible Markov chain, whose spectral evaluation is known in closed-form from the literature. Two are the major outcomes of this paper. First, unlike the literature, we obtain a PSD in true closed-form. Second, we give novel insights into the CPM format.
Undecidability of the unification and admissibility problems for modal and description logics
Venue: arXiv cs.LO 2006
Year: 2006

We show that the unification problem `is there a substitution instance of a given formula that is provable in a given logic?' is undecidable for basic modal logics K and K4 extended with the universal modality. It follows that the admissibility problem for inference rules is undecidable for these logics as well. These are the first examples of standard decidable modal logics for which the unification and admissibility problems are undecidable. We also prove undecidability of the unification and admissibility problems for K and K4 with at least two modal operators and nominals (instead of the universal modality), thereby showing that these problems are undecidable for basic hybrid logics. Recently, unification has been introduced as an important reasoning service for description logics. The undecidability proof for K with nominals can be used to show the undecidability of unification for boolean description logics with nominals (such as ALCO and SHIQO). The undecidability proof for K with the universal modality can be used to show that the unification problem relative to role boxes is undecidable for Boolean description logic with transitive roles, inverse roles, and role hierarchies (such as SHI and SHIQ).
Cross-lingual keyword assignment
Venue: arXiv cs.CL 2006
Year: 2006

This paper presents a language-independent approach to controlled vocabulary keyword assignment using the EUROVOC thesaurus. Due to the multilingual nature of EUROVOC, the keywords for a document written in one language can be displayed in all eleven official European Union languages. The mapping of documents written in different languages to the same multilingual thesaurus furthermore allows cross-language document comparison. The assignment of the controlled vocabulary thesaurus descriptors is achieved by applying a statistical method that uses a collection of manually indexed documents to identify, for each thesaurus descriptor, a large number of lemmas that are statistically associated to the descriptor. These associated words are then used during the assignment procedure to identify a ranked list of those EUROVOC terms that are most likely to be good keywords for a given document. The paper also describes the challenges of this task and discusses the achieved results of the fully functional prototype.
Geocoding multilingual texts: Recognition, disambiguation and visualisation
Venue: arXiv cs.CL 2006
Year: 2006

We are presenting a method to recognise geographical references in free text. Our tool must work on various languages with a minimum of language-dependent resources, except a gazetteer. The main difficulty is to disambiguate these place names by distinguishing places from persons and by selecting the most likely place out of a list of homographic place names world-wide. The system uses a number of language-independent clues and heuristics to disambiguate place name homographs. The final aim is to index texts with the countries and cities they mention and to automatically visualise this information on geographical maps using various tools.
Exploring Computer Science Concepts with a Ready-made Computer Game Framework
Venue: arXiv cs.OH 2006
Year: 2006

Leveraging the prevailing interest in computer games among college students, both for entertainment and as a possible career path, is a major reason for the increasing prevalence of computer game design courses in computer science curricula. Because implementing a computer game requires strong programming skills, game design courses are most often restricted to more advanced computer science students. This paper reports on a ready-made game design and experimentation framework, implemented in Java, that makes game programming more widely accessible. This framework, called Labyrinth, enables students at all programming skill levels to participate in computer game design. We describe the architecture of the framework, and discuss programming projects suitable for a wide variety of computer science courses, from capstone to non-major.
Deriving the Normalized Min-Sum Algorithm from Cooperative Optimization
Venue: arXiv cs.IT 2006
Year: 2006

The normalized min-sum algorithm can achieve near-optimal performance at decoding LDPC codes. However, it is a critical question to understand the mathematical principle underlying the algorithm. Traditionally, people thought that the normalized min-sum algorithm is a good approximation to the sum-product algorithm, the best known algorithm for decoding LDPC codes and Turbo codes. This paper offers an alternative approach to understand the normalized min-sum algorithm. The algorithm is derived directly from cooperative optimization, a newly discovered general method for global/combinatorial optimization. This approach provides us another theoretical basis for the algorithm and offers new insights on its power and limitation. It also gives us a general framework for designing new decoding algorithms.
Using shifted conjugacy in braid-based cryptography
Venue: arXiv cs.CR 2006
Year: 2006

Conjugacy is not the only possible primitive for designing braid-based protocols. To illustrate this principle, we describe a Fiat--Shamir-style authentication protocol that be can be implemented using any binary operation that satisfies the left self-distributive law. Conjugation is an example of such an operation, but there are other examples, in particular the shifted conjugation on Artin's braid group B\_oo, and the finite Laver tables. In both cases, the underlying structures have a high combinatorial complexity, and they lead to difficult problems.