OpenRaiser/Intern-Atlas huggingface dataset:
Harmonic Analysis and Qualitative Uncertainty Principle
Venue: arXiv cs.IT 2010
Year: 2010

This paper investigates the mathematical nature of qualitative uncertainty principle (QUP), which plays an important role in mathematics, physics and engineering fields. Consider a 3-tuple (K, H1, H2) that K: H1 -> H2 is an integral operator. Suppose a signal f in H1, Ω1 and Ω2 are domains on which f, Kf define respectively. Does this signal f vanish if |Σ(f)|<|Ω1|and|Σ(Kf)|<|Ω2|? The excesses and deficiencies of integral kernel K(ω, t) are found to be greatly related to this general formulation of QUP. The complete point theory of integral kernel is so established to deal with the QUP. This theory addresses the density and linear independence of integral kernels. Some algebraic and geometric properties of complete points are presented. It is shown that the satisfaction of QUP depends on the existence of some complete points. By recognizing complete points of their corresponding integral kernels, the QUP with Fourier transform, Wigner-Ville distribution, Gabor transform and wavelet are studied. It is shown the QUP only holds for good behaved integral operators. An investigation of full violation of QUP shows that L2 space is large for high resolution harmonic analysis. And the invertible linear integral transforms whose kernels are complete in L2 probably lead to the satisfaction of QUP. It indicates the performance limitation of linear integral transforms in harmonic analysis. Two possible ways bypassing uncertainty principle, nonlinear method and sparse representation, are thus suggested. The notion of operator family is developed and is applied to understand remarkable performances of recent sparse representation.
New Constant-Weight Codes from Propagation Rules
Venue: arXiv cs.IT 2010
Year: 2010

This paper proposes some simple propagation rules which give rise to new binary constant-weight codes.
Operational State Complexity of Deterministic Unranked Tree Automata
Venue: arXiv cs.FL 2010
Year: 2010

We consider the state complexity of basic operations on tree languages recognized by deterministic unranked tree automata. For the operations of union and intersection the upper and lower bounds of both weakly and strongly deterministic tree automata are obtained. For tree concatenation we establish a tight upper bound that is of a different order than the known state complexity of concatenation of regular string languages. We show that (n+1) ( (m+1)2^n-2^(n-1) )-1 vertical states are sufficient, and necessary in the worst case, to recognize the concatenation of tree languages recognized by (strongly or weakly) deterministic automata with, respectively, m and n vertical states.
Transformations Between Different Types of Unranked Bottom-Up Tree Automata
Venue: arXiv cs.FL 2010
Year: 2010

We consider the representational state complexity of unranked tree automata. The bottom-up computation of an unranked tree automaton may be either deterministic or nondeterministic, and further variants arise depending on whether the horizontal string languages defining the transitions are represented by a DFA or an NFA. Also, we consider for unranked tree automata the alternative syntactic definition of determinism introduced by Cristau et al. (FCT'05, Lect. Notes Comput. Sci. 3623, pp. 68-79). We establish upper and lower bounds for the state complexity of conversions between different types of unranked tree automata.
Nondeterministic State Complexity for Suffix-Free Regular Languages
Venue: arXiv cs.FL 2010
Year: 2010

We investigate the nondeterministic state complexity of basic operations for suffix-free regular languages. The nondeterministic state complexity of an operation is the number of states that are necessary and sufficient in the worst-case for a minimal nondeterministic finite-state automaton that accepts the language obtained from the operation. We consider basic operations (catenation, union, intersection, Kleene star, reversal and complementation) and establish matching upper and lower bounds for each operation. In the case of complementation the upper and lower bounds differ by an additive constant of two.
Complexity in Prefix-Free Regular Languages
Venue: arXiv cs.FL 2010
Year: 2010

We examine deterministic and nondeterministic state complexities of regular operations on prefix-free languages. We strengthen several results by providing witness languages over smaller alphabets, usually as small as possible. We next provide the tight bounds on state complexity of symmetric difference, and deterministic and nondeterministic state complexity of difference and cyclic shift of prefix-free languages.
Finite-State Complexity and the Size of Transducers
Venue: arXiv cs.FL 2010
Year: 2010

Finite-state complexity is a variant of algorithmic information theory obtained by replacing Turing machines with finite transducers. We consider the state-size of transducers needed for minimal descriptions of arbitrary strings and, as our main result, we show that the state-size hierarchy with respect to a standard encoding is infinite. We consider also hierarchies yielded by more general computable encodings.
State Complexity of Testing Divisibility
Venue: arXiv cs.FL 2010
Year: 2010

Under some mild assumptions, we study the state complexity of the trim minimal automaton accepting the greedy representations of the multiples of m >= 2 for a wide class of linear numeration systems. As an example, the number of states of the trim minimal automaton accepting the greedy representations of the multiples of m in the Fibonacci system is exactly 2m^2.
Interoperability, Trust Based Information Sharing Protocol and Security: Digital Government Key Issues
Venue: arXiv cs.CR 2010
Year: 2010

Improved interoperability between public and private organizations is of key significance to make digital government newest triumphant. Digital Government interoperability, information sharing protocol and security are measured the key issue for achieving a refined stage of digital government. Flawless interoperability is essential to share the information between diverse and merely dispersed organisations in several network environments by using computer based tools. Digital government must ensure security for its information systems, including computers and networks for providing better service to the citizens. Governments around the world are increasingly revolving to information sharing and integration for solving problems in programs and policy areas. Evils of global worry such as syndrome discovery and manage, terror campaign, immigration and border control, prohibited drug trafficking, and more demand information sharing, harmonization and cooperation amid government agencies within a country and across national borders. A number of daunting challenges survive to the progress of an efficient information sharing protocol. A secure and trusted information-sharing protocol is required to enable users to interact and share information easily and perfectly across many diverse networks and databases globally.
A Deterministic Polynomial-time Approximation Scheme for Counting Knapsack Solutions
Venue: arXiv cs.DS 2010
Year: 2010

Given n elements with nonnegative integer weights w1,..., wn and an integer capacity C, we consider the counting version of the classic knapsack problem: find the number of distinct subsets whose weights add up to at most the given capacity. We give a deterministic algorithm that estimates the number of solutions to within relative error 1+-eps in time polynomial in n and 1/eps (fully polynomial approximation scheme). More precisely, our algorithm takes time O(n^3 (1/eps) log (n/eps)). Our algorithm is based on dynamic programming. Previously, randomized polynomial time approximation schemes were known first by Morris and Sinclair via Markov chain Monte Carlo techniques, and subsequently by Dyer via dynamic programming and rejection sampling.
On Modeling the Response of Synovial Fluid: Unsteady Flow of a Shear-Thinning, Chemically-Reacting Fluid Mixture
Venue: arXiv cs.NA 2010
Year: 2010

We study the flow of a shear-thinning, chemically-reacting fluid that could be used to model the flow of the synovial fluid. The actual geometry where the flow of the synovial fluid takes place is very complicated, and therefore the governing equations are not amenable to simple mathematical analysis. In order to understand the response of the model, we choose to study the flow in a simple geometry. While the flow domain is not a geometry relevant to the flow of the synovial fluid in the human body it yet provides a flow which can be used to assess the efficacy of different models that have been proposed to describe synovial fluids. We study the flow in the annular region between two cylinders, one of which is undergoing unsteady oscillations about their common axis, in order to understand the quintessential behavioral characteristics of the synovial fluid. We use the three models suggested by Hron et al. [ J. Hron, J. Málek, P. Pustějovská, K. R. Rajagopal, On concentration dependent shear-thinning behavior in modeling of synovial fluid flow, Adv. in Tribol. (In Press).] to study the problem, by appealing to a semi-inverse method. The assumed structure for the velocity field automatically satisfies the constraint of incompressibility, and the balance of linear momentum is solved together with a convection-diffusion equation. The results are compared to those associated with the Newtonian model. We also study the case in which an external pressure gradient is applied along the axis of the cylindrical annulus.
Structural Decomposition of Reactions of Graph-Like Objects
Venue: arXiv cs.LO 2010
Year: 2010

Inspired by decomposition problems in rule-based formalisms in Computational Systems Biology and recent work on compositionality in graph transformation, this paper proposes to use arbitrary colimits to "deconstruct" models of reactions in which states are represented as objects of adhesive categories. The fundamental problem is the decomposition of complex reactions of large states into simpler reactions of smaller states. The paper defines the local decomposition problem for transformations. To solve this problem means to "reconstruct" a given transformation as the colimit of "smaller" ones where the shape of the colimit and the decomposition of the source object of the transformation are fixed in advance. The first result is the soundness of colimit decomposition for arbitrary double pushout transformations in any category, which roughly means that several "local" transformations can be combined into a single "global" one. Moreover, a solution for a certain class of local decomposition problems is given, which generalizes and clarifies recent work on compositionality in graph transformation.
A Light-Weight Communication Library for Distributed Computing
Venue: arXiv cs.DC 2010
Year: 2010

We present MPWide, a platform independent communication library for performing message passing between computers. Our library allows coupling of several local MPI applications through a long distance network and is specifically optimized for such communications. The implementation is deliberately kept light-weight, platform independent and the library can be installed and used without administrative privileges. The only requirements are a C++ compiler and at least one open port to a wide area network on each site. In this paper we present the library, describe the user interface, present performance tests and apply MPWide in a large scale cosmological N-body simulation on a network of two computers, one in Amsterdam and the other in Tokyo.
Comparison of different Broadcast Schemes for Multi-Hop Wireless Sensor Networks
Venue: arXiv cs.NI 2010
Year: 2010

In this paper, we present the performance of different broadcast schemes for multihop sensor networks based on mathematical modeling. In near future many applications will demand multicast (Broadcast) communication feature from the sensor networks. This broadcast feature does not use virtual carrier sensing but relies on physical carrier sensing to reduce collision. For this paper, we analyze the different broadcast schemes for multihop wireless sensor networks and also calculated the achievable throughput.
Faster Radix Sort via Virtual Memory and Write-Combining
Venue: arXiv cs.DS 2010
Year: 2010

Sorting algorithms are the deciding factor for the performance of common operations such as removal of duplicates or database sort-merge joins. This work focuses on 32-bit integer keys, optionally paired with a 32-bit value. We present a fast radix sorting algorithm that builds upon a microarchitecture-aware variant of counting sort. Taking advantage of virtual memory and making use of write-combining yields a per-pass throughput corresponding to at least 88 % of the system's peak memory bandwidth. Our implementation outperforms Intel's recently published radix sort by a factor of 1.5. It also compares favorably to the reported performance of an algorithm for Fermi GPUs when data-transfer overhead is included. These results indicate that scalar, bandwidth-sensitive sorting algorithms remain competitive on current architectures. Various other memory-intensive applications can benefit from the techniques described herein.
Minimum Entropy Combinatorial Optimization Problems
Venue: arXiv cs.DS 2010
Year: 2010

We survey recent results on combinatorial optimization problems in which the objective function is the entropy of a discrete distribution. These include the minimum entropy set cover, minimum entropy orientation, and minimum entropy coloring problems.
Time Critical Social Mobilization: The DARPA Network Challenge Winning Strategy
Venue: arXiv cs.CY 2010
Year: 2010

It is now commonplace to see the Web as a platform that can harness the collective abilities of large numbers of people to accomplish tasks with unprecedented speed, accuracy and scale. To push this idea to its limit, DARPA launched its Network Challenge, which aimed to "explore the roles the Internet and social networking play in the timely communication, wide-area team-building, and urgent mobilization required to solve broad-scope, time-critical problems." The challenge required teams to provide coordinates of ten red weather balloons placed at different locations in the continental United States. This large-scale mobilization required the ability to spread information about the tasks widely and quickly, and to incentivize individuals to act. We report on the winning team's strategy, which utilized a novel recursive incentive mechanism to find all balloons in under nine hours. We analyze the theoretical properties of the mechanism, and present data about its performance in the challenge.
An Analysis on the Influence of Network Topologies on Local and Global Dynamics of Metapopulation Systems
Venue: arXiv cs.CE 2010
Year: 2010

Metapopulations are models of ecological systems, describing the interactions and the behavior of populations that live in fragmented habitats. In this paper, we present a model of metapopulations based on the multivolume simulation algorithm tau-DPP, a stochastic class of membrane systems, that we utilize to investigate the influence that different habitat topologies can have on the local and global dynamics of metapopulations. In particular, we focus our analysis on the migration rate of individuals among adjacent patches, and on their capability of colonizing the empty patches in the habitat. We compare the simulation results obtained for each habitat topology, and conclude the paper with some proposals for other research issues concerning metapopulations.
Celer: an Efficient Program for Genotype Elimination
Venue: arXiv cs.DS 2010
Year: 2010

This paper presents an efficient program for checking Mendelian consistency in a pedigree. Since pedigrees may contain incomplete and/or erroneous information, geneticists need to pre-process them before performing linkage analysis. Removing superfluous genotypes that do not respect the Mendelian inheritance laws can speed up the linkage analysis. We have described in a formal way the Mendelian consistency problem and algorithms known in literature. The formalization helped to polish the algorithms and to find efficient data structures. The performance of the tool has been tested on a wide range of benchmarks. The results are promising if compared to other programs that treat Mendelian consistency.
Maximum entropy models and subjective interestingness: an application to tiles in binary databases
Venue: arXiv cs.AI 2010
Year: 2010

Recent research has highlighted the practical benefits of subjective interestingness measures, which quantify the novelty or unexpectedness of a pattern when contrasted with any prior information of the data miner (Silberschatz and Tuzhilin, 1995; Geng and Hamilton, 2006). A key challenge here is the formalization of this prior information in a way that lends itself to the definition of an interestingness subjective measure that is both meaningful and practical. In this paper, we outline a general strategy of how this could be achieved, before working out the details for a use case that is important in its own right. Our general strategy is based on considering prior information as constraints on a probabilistic model representing the uncertainty about the data. More specifically, we represent the prior information by the maximum entropy (MaxEnt) distribution subject to these constraints. We briefly outline various measures that could subsequently be used to contrast patterns with this MaxEnt model, thus quantifying their subjective interestingness.
Synthesis of Fault Tolerant Reversible Logic Circuits
Venue: arXiv cs.AR 2010
Year: 2010

Reversible logic is emerging as an important research area having its application in diverse fields such as low power CMOS design, digital signal processing, cryptography, quantum computing and optical information processing. This paper presents a new 4*4 universal reversible logic gate, IG. It is a parity preserving reversible logic gate, that is, the parity of the inputs matches the parity of the outputs. The proposed parity preserving reversible gate can be used to synthesize any arbitrary Boolean function. It allows any fault that affects no more than a single signal readily detectable at the circuit's primary outputs. Finally, it is shown how a fault tolerant reversible full adder circuit can be realized using only two IGs. It has also been demonstrated that the proposed design offers less hardware complexity and is efficient in terms of gate count, garbage outputs and constant inputs than the existing counterparts.
A Miniature-Based Image Retrieval System
Venue: arXiv cs.CV 2010
Year: 2010

Due to the rapid development of World Wide Web (WWW) and imaging technology, more and more images are available in the Internet and stored in databases. Searching the related images by the querying image is becoming tedious and difficult. Most of the images on the web are compressed by methods based on discrete cosine transform (DCT) including Joint Photographic Experts Group(JPEG) and H.261. This paper presents an efficient content-based image indexing technique for searching similar images using discrete cosine transform features. Experimental results demonstrate its superiority with the existing techniques.
Variable Block Carry Skip Logic using Reversible Gates
Venue: arXiv cs.AR 2010
Year: 2010

Reversible circuits have applications in digital signal processing, computer graphics, quantum computation and cryptography. In this paper, a generalized k*k reversible gate family is proposed and a 3*3 gate of the family is discussed. Inverter, AND, OR, NAND, NOR, and EXOR gates can be realized by this gate. Implementation of a full-adder circuit using two such 3*3 gates is given. This full-adder circuit contains only two reversible gates and produces no extra garbage outputs. The proposed full-adder circuit is efficient in terms of gate count, garbage outputs and quantum cost. A 4-bit carry skip adder is designed using this full-adder circuit and a variable block carry skip adder is discussed. Necessary equations required to evaluate these adder are presented.
Modeling Corporate Epidemiology
Venue: arXiv cs.CY 2010
Year: 2010

Corporate responses to illness is currently an ad-hoc, subjective process that has little basis in data on how disease actually spreads at the workplace. Additionally, many studies have shown that productivity is not an individual factor but a social one: in any study on epidemic responses this social factor has to be taken into account. The barrier to addressing this problem has been the lack of data on the interaction and mobility patterns of people in the workplace. We have created a wearable Sociometric Badge that senses interactions between individuals using an infra-red (IR) transceiver and proximity using a radio transmitter. Using the data from the Sociometric Badges, we are able to simulate diseases spreading through face-to-face interactions with realistic epidemiological parameters. In this paper we construct a curve trading off productivity with epidemic potential. We are able to take into account impacts on productivity that arise from social factors, such as interaction diversity and density, which studies that take an individual approach ignore. We also propose new organizational responses to diseases that take into account behavioral patterns that are associated with a more virulent disease spread. This is advantageous because it will allow companies to decide appropriate responses based on the organizational context of a disease outbreak.
Maximum Betweenness Centrality: Approximability and Tractable Cases
Venue: arXiv cs.DS 2010
Year: 2010

The Maximum Betweenness Centrality problem (MBC) can be defined as follows. Given a graph find a $k$-element node set $C$ that maximizes the probability of detecting communication between a pair of nodes $s$ and $t$ chosen uniformly at random. It is assumed that the communication between $s$ and $t$ is realized along a shortest $s$--$t$ path which is, again, selected uniformly at random. The communication is detected if the communication path contains a node of $C$. Recently, Dolev et al. (2009) showed that MBC is NP-hard and gave a $(1-1/e)$-approximation using a greedy approach. We provide a reduction of MBC to Maximum Coverage that simplifies the analysis of the algorithm of Dolev et al. considerably. Our reduction allows us to obtain a new algorithm with the same approximation ratio for a (generalized) budgeted version of MBC. We provide tight examples showing that the analyses of both algorithms are best possible. Moreover, we prove that MBC is APX-complete and provide an exact polynomial-time algorithm for MBC on tree graphs.