OpenRaiser/Intern-Atlas huggingface dataset:
Combining decision procedures for the reals
Venue: arXiv cs.LO 2006
Year: 2006

<p>We address the general problem of determining the validity of boolean combinations of equalities and inequalities between real-valued expressions. In particular, we consider methods of establishing such assertions using only restricted forms of distributivity. At the same time, we explore ways in which "local" decision or heuristic procedures for fragments of the theory of the reals can be amalgamated into global ones. </p> <p>Let <em>Tadd[Q]</em> be the first-order theory of the real numbers in the language of ordered groups, with negation, a constant <em>1</em>, and function symbols for multiplication by rational constants. Let <em>Tmult[Q]</em> be the analogous theory for the multiplicative structure, and let <em>T[Q]</em> be the union of the two. We show that although <em>T[Q]</em> is undecidable, the universal fragment of <em>T[Q]</em> is decidable. We also show that terms of <em>T[Q]</em>can fruitfully be put in a normal form. We prove analogous results for theories in which <em>Q</em> is replaced, more generally, by suitable subfields <em>F</em> of the reals. Finally, we consider practical methods of establishing quantifier-free validities that approximate our (impractical) decidability results.</p>
Strategies of Loop Recombination in Ciliates
Venue: arXiv cs.LO 2006
Year: 2006

Gene assembly in ciliates is an extremely involved DNA transformation process, which transforms a nucleus, the micronucleus, to another functionally different nucleus, the macronucleus. In this paper we characterize which loop recombination operations (one of the three types of molecular operations that accomplish gene assembly) can possibly be applied in the transformation of a given gene from its micronuclear form to its macronuclear form. We also characterize in which order these loop recombination operations are applicable. This is done in the abstract and more general setting of so-called legal strings.
Watermarking Using Decimal Sequences
Venue: arXiv cs.CR 2006
Year: 2006

This paper introduces the use of decimal sequences in a code division multiple access (CDMA) based watermarking system to hide information for authentication in black and white images. Matlab version 6.5 was used to implement the algorithms discussed in this paper. The advantage of using d-sequences over PN sequences is that one can choose from a variety of prime numbers which provides a more flexible system.
A Visual Query Language for Complex-Value Databases
Venue: arXiv cs.DB 2006
Year: 2006

In this paper, a visual language, VCP, for queries on complex-value databases is proposed. The main strength of the new language is that it is purely visual: (i) It has no notion of variable, quantification, partiality, join, pattern matching, regular expression, recursion, or any other construct proper to logical, functional, or other database query languages and (ii) has a very natural, strong, and intuitive design metaphor. The main operation is that of copying and pasting in a schema tree. We show that despite its simplicity, VCP precisely captures complex-value algebra without powerset, or equivalently, monad algebra with union and difference. Thus, its expressive power is precisely that of the language that is usually considered to play the role of relational algebra for complex-value databases.
The intuitionistic fragment of computability logic at the propositional level
Venue: arXiv cs.LO 2006
Year: 2006

This paper presents a soundness and completeness proof for propositional intuitionistic calculus with respect to the semantics of computability logic. The latter interprets formulas as interactive computational problems, formalized as games between a machine and its environment. Intuitionistic implication is understood as algorithmic reduction in the weakest possible -- and hence most natural -- sense, disjunction and conjunction as deterministic-choice combinations of problems (disjunction = machine's choice, conjunction = environment's choice), and "absurd" as a computational problem of universal strength. See http://www.cis.upenn.edu/~giorgi/cl.html for a comprehensive online source on computability logic.
An Optimal Distributed Edge-Biconnectivity Algorithm
Venue: arXiv cs.DC 2006
Year: 2006

We describe a synchronous distributed algorithm which identifies the edge-biconnected components of a connected network. It requires a leader, and uses messages of size O(log |V|). The main idea is to preorder a BFS spanning tree, and then to efficiently compute least common ancestors so as to mark cycle edges. This algorithm takes O(Diam) time and uses O(|E|) messages. Furthermore, we show that no correct singly-initiated edge-biconnectivity algorithm can beat either bound on any graph by more than a constant factor. We also describe a near-optimal local algorithm for edge-biconnectivity.
Inter-Block Permuted Turbo Codes
Venue: arXiv cs.IT 2006
Year: 2006

The structure and size of the interleaver used in a turbo code critically affect the distance spectrum and the covariance property of a component decoder's information input and soft output. This paper introduces a new class of interleavers, the inter-block permutation (IBP) interleavers, that can be build on any existing "good" block-wise interleaver by simply adding an IBP stage. The IBP interleavers reduce the above-mentioned correlation and increase the effective interleaving size. The increased effective interleaving size improves the distance spectrum while the reduced covariance enhances the iterative decoder's performance. Moreover, the structure of the IBP(-interleaved) turbo codes (IBPTC) is naturally fit for high rate applications that necessitate parallel decoding. We present some useful bounds and constraints associated with the IBPTC that can be used as design guidelines. The corresponding codeword weight upper bounds for weight-2 and weight-4 input sequences are derived. Based on some of the design guidelines, we propose a simple IBP algorithm and show that the associated IBPTC yields 0.3 to 1.2 dB performance gain, or equivalently, an IBPTC renders the same performance with a much reduced interleaving delay. The EXIT and covariance behaviors provide another numerical proof of the superiority of the proposed IBPTC.
Using Domain Knowledge in Evolutionary System Identification
Venue: arXiv cs.AI 2006
Year: 2006

Two example of Evolutionary System Identification are presented to highlight the importance of incorporating Domain Knowledge: the discovery of an analytical indentation law in Structural Mechanics using constrained Genetic Programming, and the identification of the repartition of underground velocities in Seismic Prospection. Critical issues for sucessful ESI are discussed in the light of these results.
Bulk Scheduling with DIANA Scheduler
Venue: arXiv cs.DC 2006
Year: 2006

Results from and progress on the development of a Data Intensive and Network Aware (DIANA) Scheduling engine, primarily for data intensive sciences such as physics analysis, are described. Scientific analysis tasks can involve thousands of computing, data handling, and network resources and the size of the input and output files and the amount of overall storage space allocated to a user necessarily can have significant bearing on the scheduling of data intensive applications. If the input or output files must be retrieved from a remote location, then the time required transferring the files must also be taken into consideration when scheduling compute resources for the given application. The central problem in this study is the coordinated management of computation and data at multiple locations and not simply data movement. However, this can be a very costly operation and efficient scheduling can be a challenge if compute and data resources are mapped without network cost. We have implemented an adaptive algorithm within the DIANA Scheduler which takes into account data location and size, network performance and computation capability to make efficient global scheduling decisions. DIANA is a performance-aware as well as an economy-guided Meta Scheduler. It iteratively allocates each job to the site that is likely to produce the best performance as well as optimizing the global queue for any remaining pending jobs. Therefore it is equally suitable whether a single job is being submitted or bulk scheduling is being performed. Results suggest that considerable performance improvements are to be gained by adopting the DIANA scheduling approach.
Single-Symbol Maximum Likelihood Decodable Linear STBCs
Venue: arXiv cs.IT 2006
Year: 2006

Space-Time block codes (STBC) from Orthogonal Designs (OD) and Co-ordinate Interleaved Orthogonal Designs (CIOD) have been attracting wider attention due to their amenability for fast (single-symbol) ML decoding, and full-rate with full-rank over quasi-static fading channels. However, these codes are instances of single-symbol decodable codes and it is natural to ask, if there exist codes other than STBCs form ODs and CIODs that allow single-symbol coding? In this paper, the above question is answered in the affirmative by characterizing all linear STBCs, that allow single-symbol ML decoding (not necessarily full-diversity) over quasi-static fading channels-calling them single-symbol decodable designs (SDD). The class SDD includes ODs and CIODs as proper subclasses. Further, among the SDD, a class of those that offer full-diversity, called Full-rank SDD (FSDD) are characterized and classified.
Minimum Cost Homomorphisms to Proper Interval Graphs and Bigraphs
Venue: arXiv cs.DM 2006
Year: 2006

For graphs $G$ and $H$, a mapping $f: V(G)\dom V(H)$ is a homomorphism of $G$ to $H$ if $uv\in E(G)$ implies $f(u)f(v)\in E(H).$ If, moreover, each vertex $u \in V(G)$ is associated with costs $c_i(u), i \in V(H)$, then the cost of the homomorphism $f$ is $\sum_{u\in V(G)}c_{f(u)}(u)$. For each fixed graph $H$, we have the {\em minimum cost homomorphism problem}, written as MinHOM($H)$. The problem is to decide, for an input graph $G$ with costs $c_i(u),$ $u \in V(G), i\in V(H)$, whether there exists a homomorphism of $G$ to $H$ and, if one exists, to find one of minimum cost. Minimum cost homomorphism problems encompass (or are related to) many well studied optimization problems. We describe a dichotomy of the minimum cost homomorphism problems for graphs $H$, with loops allowed. When each connected component of $H$ is either a reflexive proper interval graph or an irreflexive proper interval bigraph, the problem MinHOM($H)$ is polynomial time solvable. In all other cases the problem MinHOM($H)$ is NP-hard. This solves an open problem from an earlier paper. Along the way, we prove a new characterization of the class of proper interval bigraphs.
Path Summaries and Path Partitioning in Modern XML Databases
Venue: arXiv cs.DB 2006
Year: 2006

We study the applicability of XML path summaries in the context of current-day XML databases. We find that summaries provide an excellent basis for optimizing data access methods, which furthermore mixes very well with path-partitioned stores. We provide practical algorithms for building and exploiting summaries, and prove its benefits through extensive experiments.
New security and control protocol for VoIP based on steganography and digital watermarking
Venue: arXiv cs.CR 2006
Year: 2006

In this paper new security and control protocol for Voice over Internet Protocol (VoIP) service is presented. It is the alternative for the IETF's (Internet Engineering Task Force) RTCP (Real-Time Control Protocol) for real-time application's traffic. Additionally this solution offers authentication and integrity, it is capable of exchanging and verifying QoS and security parameters. It is based on digital watermarking and steganography that is why it does not consume additional bandwidth and the data transmitted is inseparably bound to the voice content.
Analysis of LDGM and compound codes for lossy compression and binning
Venue: arXiv cs.IT 2006
Year: 2006

Recent work has suggested that low-density generator matrix (LDGM) codes are likely to be effective for lossy source coding problems. We derive rigorous upper bounds on the effective rate-distortion function of LDGM codes for the binary symmetric source, showing that they quickly approach the rate-distortion function as the degree increases. We also compare and contrast the standard LDGM construction with a compound LDPC/LDGM construction introduced in our previous work, which provably saturates the rate-distortion bound with finite degrees. Moreover, this compound construction can be used to generate nested codes that are simultaneously good as source and channel codes, and are hence well-suited to source/channel coding with side information. The sparse and high-girth graphical structure of our constructions render them well-suited to message-passing encoding.
On the Optimality of the ARQ-DDF Protocol
Venue: arXiv cs.IT 2006
Year: 2006

The performance of the automatic repeat request-dynamic decode and forward (ARQ-DDF) cooperation protocol is analyzed in two distinct scenarios. The first scenario is the multiple access relay (MAR) channel where a single relay is dedicated to simultaneously help several multiple access users. For this setup, it is shown that the ARQ-DDF protocol achieves the optimal diversity multiplexing tradeoff (DMT) of the channel. The second scenario is the cooperative vector multiple access (CVMA) channel where the users cooperate in delivering their messages to a destination equipped with multiple receiving antennas. For this setup, we develop a new variant of the ARQ-DDF protocol where the users are purposefully instructed not to cooperate in the first round of transmission. Lower and upper bounds on the achievable DMT are then derived. These bounds are shown to converge to the optimal tradeoff as the number of transmission rounds increases.
Cooperative Lattice Coding and Decoding
Venue: arXiv cs.IT 2006
Year: 2006

A novel lattice coding framework is proposed for outage-limited cooperative channels. This framework provides practical implementations for the optimal cooperation protocols proposed by Azarian et al. In particular, for the relay channel we implement a variant of the dynamic decode and forward protocol, which uses orthogonal constellations to reduce the channel seen by the destination to a single-input single-output time-selective one, while inheriting the same diversity-multiplexing tradeoff. This simplification allows for building the receiver using traditional belief propagation or tree search architectures. Our framework also generalizes the coding scheme of Yang and Belfiore in the context of amplify and forward cooperation. For the cooperative multiple access channel, a tree coding approach, matched to the optimal linear cooperation protocol of Azarain et al, is developed. For this scenario, the MMSE-DFE Fano decoder is shown to enjoy an excellent tradeoff between performance and complexity. Finally, the utility of the proposed schemes is established via a comprehensive simulation study.
Revisiting Evolutionary Algorithms with On-the-Fly Population Size Adjustment
Venue: arXiv cs.NE 2006
Year: 2006

In an evolutionary algorithm, the population has a very important role as its size has direct implications regarding solution quality, speed, and reliability. Theoretical studies have been done in the past to investigate the role of population sizing in evolutionary algorithms. In addition to those studies, several self-adjusting population sizing mechanisms have been proposed in the literature. This paper revisits the latter topic and pays special attention to the genetic algorithm with adaptive population size (APGA), for which several researchers have claimed to be very effective at autonomously (re)sizing the population. As opposed to those previous claims, this paper suggests a complete opposite view. Specifically, it shows that APGA is not capable of adapting the population size at all. This claim is supported on theoretical grounds and confirmed by computer simulations.
Building Scenarios for Environmental Management and Planning: An IT-Based Approach
Venue: arXiv cs.MA 2006
Year: 2006

Oftentimes, the need to build multidiscipline knowledge bases, oriented to policy scenarios, entails the involvement of stakeholders in manifold domains, with a juxtaposition of different languages whose semantics can hardly allow inter-domain transfers. A useful support for planning is the building up of durable IT based interactive platforms, where it is possible to modify initial positions toward a semantic convergence. The present paper shows an area-based application of these tools, for the integrated distance-management of different forms of knowledge expressed by selected stakeholders about environmental planning issues, in order to build alternative development scenarios. Keywords: Environmental planning, Scenario building, Multi-source knowledge, IT-based
Group Signature Schemes Using Braid Groups
Venue: arXiv cs.CR 2006
Year: 2006

Artin's braid groups have been recently suggested as a new source for public-key cryptography. In this paper we propose the first group signature schemes based on the conjugacy problem, decomposition problem and root problem in the braid groups which are believed to be hard problems.
Similarity of Objects and the Meaning of Words
Venue: arXiv cs.CV 2006
Year: 2006

We survey the emerging area of compression-based, parameter-free, similarity distance measures useful in data-mining, pattern recognition, learning and automatic semantics extraction. Given a family of distances on a set of objects, a distance is universal up to a certain precision for that family if it minorizes every distance in the family between every two objects in the set, up to the stated precision (we do not require the universal distance to be an element of the family). We consider similarity distances for two types of objects: literal objects that as such contain all of their meaning, like genomes or books, and names for objects. The latter may have literal embodyments like the first type, but may also be abstract like ``red'' or ``christianity.'' For the first type we consider a family of computable distance measures corresponding to parameters expressing similarity according to particular featuresdistances generated by web users corresponding to particular semantic relations between the (names for) the designated objects. For both families we give universal similarity distance measures, incorporating all particular distance measures in the family. In the first case the universal distance is based on compression and in the second case it is based on Google page counts related to search terms. In both cases experiments on a massive scale give evidence of the viability of the approaches. between pairs of literal objects. For the second type we consider similarity
Faster Algorithms for Constructing a Concept (Galois) Lattice
Venue: arXiv cs.DM 2006
Year: 2006

In this paper, we present a fast algorithm for constructing a concept (Galois) lattice of a binary relation, including computing all concepts and their lattice order. We also present two efficient variants of the algorithm, one for computing all concepts only, and one for constructing a frequent closed itemset lattice. The running time of our algorithms depends on the lattice structure and is faster than all other existing algorithms for these problems.
Exploring term-document matrices from matrix models in text mining
Venue: arXiv cs.IR 2006
Year: 2006

We explore a matrix-space model, that is a natural extension to the vector space model for Information Retrieval. Each document can be represented by a matrix that is based on document extracts (e.g. sentences, paragraphs, sections). We focus on the performance of this model for the specific case in which documents are originally represented as term-by-sentence matrices. We use the singular value decomposition to approximate the term-by-sentence matrices and assemble these results to form the pseudo-``term-document'' matrix that forms the basis of a text mining method alternative to traditional VSM and LSI. We investigate the singular values of this matrix and provide experimental evidence suggesting that the method can be particularly effective in terms of accuracy for text collections with multi-topic documents, such as web pages with news.
Associative Memory For Reversible Programming and Charge Recovery
Venue: arXiv cs.AR 2006
Year: 2006

Presented below is an interesting type of associative memory called toggle memory based on the concept of T flip flops, as opposed to D flip flops. Toggle memory supports both reversible programming and charge recovery. Circuits designed using the principles delineated below permit matchlines to charge and discharge with near zero energy dissipation. The resulting lethargy is compensated by the massive parallelism of associative memory. Simulation indicates over 33x reduction in energy dissipation using a sinusoidal power supply at 2 MHz, assuming realistic 50 nm MOSFET models.
Lamarckian Evolution and the Baldwin Effect in Evolutionary Neural Networks
Venue: arXiv cs.NE 2006
Year: 2006

Hybrid neuro-evolutionary algorithms may be inspired on Darwinian or Lamarckian evolu- tion. In the case of Darwinian evolution, the Baldwin effect, that is, the progressive incorporation of learned characteristics to the genotypes, can be observed and leveraged to improve the search. The purpose of this paper is to carry out an exper- imental study into how learning can improve G-Prop genetic search. Two ways of combining learning and genetic search are explored: one exploits the Baldwin effect, while the other uses a Lamarckian strategy. Our experiments show that using a Lamarckian op- erator makes the algorithm find networks with a low error rate, and the smallest size, while using the Bald- win effect obtains MLPs with the smallest error rate, and a larger size, taking longer to reach a solution. Both approaches obtain a lower average error than other BP-based algorithms like RPROP, other evolu- tionary methods and fuzzy logic based methods
On the MacWilliams Identity for Convolutional Codes
Venue: arXiv cs.IT 2006
Year: 2006

The adjacency matrix associated with a convolutional code collects in a detailed manner information about the weight distribution of the code. A MacWilliams Identity Conjecture, stating that the adjacency matrix of a code fully determines the adjacency matrix of the dual code, will be formulated, and an explicit formula for the transformation will be stated. The formula involves the MacWilliams matrix known from complete weight enumerators of block codes. The conjecture will be proven for the class of convolutional codes where either the code itself or its dual does not have Forney indices bigger than one. For the general case the conjecture is backed up by many examples, and a weaker version will be established.
Object-Oriented Modeling of Programming Paradigms
Venue: arXiv cs.SE 2006
Year: 2006

For the right application, the use of programming paradigms such as functional or logic programming can enormously increase productivity in software development. But these powerful paradigms are tied to exotic programming languages, while the management of software development dictates standardization on a single language. This dilemma can be resolved by using object-oriented programming in a new way. It is conventional to analyze an application by object-oriented modeling. In the new approach, the analysis identifies the paradigm that is ideal for the application; development starts with object-oriented modeling of the paradigm. In this paper we illustrate the new approach by giving examples of object-oriented modeling of dataflow and constraint programming. These examples suggest that it is no longer necessary to embody a programming paradigm in a language dedicated to it.