OpenRaiser/Intern-Atlas huggingface dataset:
Advanced phase retrieval: maximum likelihood technique with sparse regularization of phase and amplitude
Venue: arXiv cs.CV 2011
Year: 2011

Sparse modeling is one of the efficient techniques for imaging that allows recovering lost information. In this paper, we present a novel iterative phase-retrieval algorithm using a sparse representation of the object amplitude and phase. The algorithm is derived in terms of a constrained maximum likelihood, where the wave field reconstruction is performed using a number of noisy intensity-only observations with a zero-mean additive Gaussian noise. The developed algorithm enables the optimal solution for the object wave field reconstruction. Our goal is an improvement of the reconstruction quality with respect to the conventional algorithms. Sparse regularization results in advanced reconstruction accuracy, and numerical simulations demonstrate significant enhancement of imaging.
A General Achievable Rate Region for Multiple-Access Relay Channels and Some Certain Capacity Theorems
Venue: arXiv cs.IT 2011
Year: 2011

In this paper, we obtain a general achievable rate region and some certain capacity theorems for multiple-access relay channel (MARC), using decode and forward (DAF) strategy at the relay, superposition coding at the transmitters. Our general rate region (i) generalizes the achievability part of Slepian-Wolf multiple-access capacity theorem to the MARC, (ii) extends the Cover-El Gamal best achievable rate for the relay channel with DAF strategy to the MARC, (iii) gives the Kramer-Wijengaarden rate region for the MARC, (iv) meets max-flow min-cut upper bound and leads to the capacity regions of some important classes of the MARC.
Frequency-Hopping Sequence Sets With Low Average and Maximum Hamming Correlation
Venue: arXiv cs.IT 2011
Year: 2011

In frequency-hopping multiple-access (FHMA) systems, the average Hamming correlation (AHC) among frequency-hopping sequences (FHSs) as well as the maximum Hamming correlation (MHC) is an important performance measure. Therefore, it is a challenging problem to design FHS sets with good AHC and MHC properties for application. In this paper, we analyze the AHC properties of an FHS set, and present new constructions for FHS sets with optimal AHC. We first calculate the AHC of some known FHS sets with optimal MHC, and check their optimalities. We then prove that any uniformly distributed FHS set has optimal AHC. We also present two constructions of FHS sets with optimal AHC based on cyclotomy. Finally, we show that if an FHS set is obtained from another FHS set with optimal AHC by an interleaving, it has optimal AHC.
The Exponent of a Polarizing Matrix Constructed from the Kronecker Product
Venue: arXiv cs.IT 2011
Year: 2011

The asymptotic performance of a polar code under successive cancellation decoding is determined by the exponent of its polarizing matrix. We first prove that the partial distances of a polarizing matrix constructed from the Kronecker product are simply expressed as a product of those of its component matrices. We then show that the exponent of the polarizing matrix is shown to be a weighted sum of the exponents of its component matrices. These results may be employed in the design of a large polarizing matrix with high exponent.
Brane Calculi Systems: A Static Preview of their Possible Behaviour
Venue: arXiv cs.LO 2011
Year: 2011

We improve the precision of a previous Control Flow Analysis for Brane Calculi, by adding information on the context and introducing causality information on the membranes. This allows us to prove some biological properties on the behaviour of systems specified in Brane Calculi.
Synchronization of P Systems with Simplex Channels
Venue: arXiv cs.DC 2011
Year: 2011

We solve the Firing Squad Synchronization Problem (FSSP), for P systems based on digraphs with simplex channels, where communication is restricted by the direction of structural arcs. Previous work on FSSP for P systems focused exclusively on P systems with duplex channels, where communication between parents and children is bidirectional. Our P solution, the first for simplex channels, requires cell IDs, strongly connected digraphs and some awareness of the local topology (such as each cell's outdegree)---we argue that these requirements are necessary. Compared to the known solutions for cellular automata, our solution is substantially simpler and faster.
Generalized Communicating P Systems Working in Fair Sequential Model
Venue: arXiv cs.DC 2011
Year: 2011

In this article we consider a new derivation mode for generalized communicating P systems (GCPS) corresponding to the functioning of population protocols (PP) and based on the sequential derivation mode and a fairness condition. We show that PP can be seen as a particular variant of GCPS. We also consider a particular stochastic evolution satisfying the fairness condition and obtain that it corresponds to the run of a Gillespie's SSA. This permits to further describe the dynamics of GCPS by a system of ODEs when the population size goes to the infinity.
Abstracting Asynchronous Multi-Valued Networks: An Initial Investigation
Venue: arXiv cs.DC 2011
Year: 2011

Multi-valued networks provide a simple yet expressive qualitative state based modelling approach for biological systems. In this paper we develop an abstraction theory for asynchronous multi-valued network models that allows the state space of a model to be reduced while preserving key properties of the model. The abstraction theory therefore provides a mechanism for coping with the state space explosion problem and supports the analysis and comparison of multi-valued networks. We take as our starting point the abstraction theory for synchronous multi-valued networks which is based on the finite set of traces that represent the behaviour of such a model. The problem with extending this approach to the asynchronous case is that we can now have an infinite set of traces associated with a model making a simple trace inclusion test infeasible. To address this we develop a decision procedure for checking asynchronous abstractions based on using the finite state graph of an asynchronous multi-valued network to reason about its trace semantics. We illustrate the abstraction techniques developed by considering a detailed case study based on a multi-valued network model of the regulation of tryptophan biosynthesis in Escherichia coli.
New separation between $s(f)$ and $bs(f)$
Venue: arXiv cs.CC 2011
Year: 2011

In this note we give a new separation between sensitivity and block sensitivity of Boolean functions: $bs(f)=(2/3)s(f)^2-(1/3)s(f)$.
A theory of robust software synthesis
Venue: arXiv cs.SY 2011
Year: 2011

A key property for systems subject to uncertainty in their operating environment is robustness, ensuring that unmodelled, but bounded, disturbances have only a proportionally bounded effect upon the behaviours of the system. Inspired by ideas from robust control and dissipative systems theory, we present a formal definition of robustness and algorithmic tools for the design of optimally robust controllers for omega-regular properties on discrete transition systems. Formally, we define metric automata - automata equipped with a metric on states - and strategies on metric automata which guarantee robustness for omega-regular properties. We present fixed point algorithms to construct optimally robust strategies in polynomial time. In contrast to strategies computed by classical graph theoretic approaches, the strategies computed by our algorithm ensure that the behaviours of the controlled system gracefully degrade under the action of disturbances; the degree of degradation is parameterized by the magnitude of the disturbance. We show an application of our theory to the design of controllers that tolerate infinitely many transient errors provided they occur infrequently enough.
Gaussian Channel with Noisy Feedback and Peak Energy Constraint
Venue: arXiv cs.IT 2011
Year: 2011

Optimal coding over the additive white Gaussian noise channel under the peak energy constraint is studied when there is noisy feedback over an orthogonal additive white Gaussian noise channel. As shown by Pinsker, under the peak energy constraint, the best error exponent for communicating an M-ary message, M >= 3, with noise-free feedback is strictly larger than the one without feedback. This paper extends Pinsker's result and shows that if the noise power in the feedback link is sufficiently small, the best error exponent for conmmunicating an M-ary message can be strictly larger than the one without feedback. The proof involves two feedback coding schemes. One is motivated by a two-stage noisy feedback coding scheme of Burnashev and Yamamoto for binary symmetric channels, while the other is a linear noisy feedback coding scheme that extends Pinsker's noise-free feedback coding scheme. When the feedback noise power $α$ is sufficiently small, the linear coding scheme outperforms the two-stage (nonlinear) coding scheme, and is asymptotically optimal as $α$ tends to zero. By contrast, when $α$ is relatively larger, the two-stage coding scheme performs better.
Substitutions over infinite alphabet generating (-β)-integers
Venue: arXiv cs.DM 2011
Year: 2011

This contribution is devoted to the study of positional numeration systems with negative base introduced by Ito and Sadahiro in 2009, called (-β)-expansions. We give an admissibility criterion for more general case of (-β)-expansions and discuss the properties of the set of (-β)-integers. We give a description of distances within this set and show that this set can be coded by an infinite word over an infinite alphabet, which is a fixed point of a non-erasing non-trivial morphism.
Permutation Complexity Related to the Letter Doubling Map
Venue: arXiv cs.DM 2011
Year: 2011

Given a countable set X (usually taken to be the natural numbers or integers), an infinite permutation, π, of X is a linear ordering of X. This paper investigates the combinatorial complexity of infinite permutations on the natural numbers associated with the image of uniformly recurrent aperiodic binary words under the letter doubling map. An upper bound for the complexity is found for general words, and a formula for the complexity is established for the Sturmian words and the Thue-Morse word.
Modeling Routing Overhead Generated by Wireless Reactive Routing Protocols
Venue: arXiv cs.NI 2011
Year: 2011

In this paper, we have modeled the routing over- head generated by three reactive routing protocols; Ad-hoc On-demand Distance Vector (AODV), Dynamic Source Routing (DSR) and DYnamic MANET On-deman (DYMO). Routing performed by reactive protocols consists of two phases; route discovery and route maintenance. Total cost paid by a protocol for efficient routing is sum of the cost paid in the form of energy consumed and time spent. These protocols majorly focus on the optimization performed by expanding ring search algorithm to control the flooding generated by the mechanism of blind flooding. So, we have modeled the energy consumed and time spent per packet both for route discovery and route maintenance. The proposed framework is evaluated in NS-2 to compare performance of the chosen routing protocols.
Computational Models of Certain Hyperspaces of Quasi-metric Spaces
Venue: arXiv cs.LO 2011
Year: 2011

In this paper, for a given sequentially Yoneda-complete T_1 quasi-metric space (X,d), the domain theoretic models of the hyperspace K_0(X) of nonempty compact subsets of (X,d) are studied. To this end, the $ω$-Plotkin domain of the space of formal balls BX, denoted by CBX is considered. This domain is given as the chain completion of the set of all finite subsets of BX with respect to the Egli-Milner relation. Further, a map $ϕ:K_0(X)\rightarrow CBX$ is established and proved that it is an embedding whenever K_0(X) is equipped with the Vietoris topology and respectively CBX with the Scott topology. Moreover, if any compact subset of (X,d) is d^{-1}-precompact, ϕis an embedding with respect to the topology of Hausdorff quasi-metric H_d on K_0(X). Therefore, it is concluded that (CBX,\sqsubseteq,ϕ) is an $ω$-computational model for the hyperspace K_0(X) endowed with the Vietoris and respectively the Hausdorff topology. Next, an algebraic sequentially Yoneda-complete quasi-metric D on CBX$ is introduced in such a way that the specialization order $\sqsubseteq_D$ is equivalent to the usual partial order of CBX and, furthermore, $ϕ:({\cal K}_0(X),H_d)\rightarrow({\bf C}{\bf B}X,D)$ is an isometry. This shows that (CBX,\sqsubseteq,ϕ,D) is a quantitative $ω$-computational model for (K_(X),H_d).
Language understanding as a step towards human level intelligence - automatizing the construction of the initial dictionary from example sentences
Venue: arXiv cs.CL 2011
Year: 2011

For a system to understand natural language, it needs to be able to take natural language text and answer questions given in natural language with respect to that text; it also needs to be able to follow instructions given in natural language. To achieve this, a system must be able to process natural language and be able to capture the knowledge within that text. Thus it needs to be able to translate natural language text into a formal language. We discuss our approach to do this, where the translation is achieved by composing the meaning of words in a sentence. Our initial approach uses an inverse lambda method that we developed (and other methods) to learn meaning of words from meaning of sentences and an initial lexicon. We then present an improved method where the initial lexicon is also learned by analyzing the training sentence and meaning pairs. We evaluate our methods and compare them with other existing methods on a corpora of database querying and robot command and control.
Implicit learning of object geometry by reducing contact forces and increasing smoothness
Venue: arXiv cs.SY 2011
Year: 2011

Moving our hands smoothly is essential to execute ordinary tasks, such as carrying a glass of water without spilling. Past studies have revealed a natural tendency to generate smooth trajectories when moving the hand from one point to another in free space. Here we provide a new perspective on movement smoothness by showing that smoothness is also enforced when the hand maintains contact with a curved surface. Maximally smooth motions over curved surfaces occur along geodesic lines that depend on fundamental features of the surface, such as its radius and center of curvature. Subjects were requested to execute movements of the hand while in contact with a virtual sphere that they could not see. We found that with practice, subjects tended to move their hand along smooth trajectories, near geodesic pathways joining start to end positions, to reduce contact forces with constrained boundary, variance of contact force, tangential velocity profile error and sum of square jerk along the time span of movement. Furthermore, after practicing movements in a region of the sphere, subjects executed near-geodesic movements, less contact forces, less contact force variance, less tangential velocity profile error and less sum of square jerk in a different region. These findings suggest that the execution of smooth movements while the hand is in contact with a surface is a means for extracting information about the surface's geometrical features.
Three-dimensional Torques and Power of Horse Forelimb Joints at Trot
Venue: arXiv cs.RO 2011
Year: 2011

Reasons for Performing Study: Equine gait analysis has focused on 2D analysis in the sagittal plane, while descriptions of 3D kinetics and ground reaction force could provide more information on the Equine gait analysis. Hypothesis or Objectives: The aim of this study was to characterize the 3D torques and powers of the forelimb joints at trotting. Methods: Eight sound horses were used in the study. A full 3D torque and power for elbow, carpus, fetlock, pastern and coffin joints of right forelimb in horses at trot were obtained by calculating the inverse kinetics of simplified link segmental model. Results: Over two third of energy (70%) generated by all joints come from stance phase, and most of energy generated was by elbow joint both in stance (77%) and sway (88%) phases. Energy absorbed by all joints during stance (40%) and sway (60%) phases respectively is not a big difference. During stance phase, all most two third of energy (65%) absorbed was by fetlock joint, while over two third of energy (74%) absorbed was by carpus joint during sway phase. Conclusions & Clinical Relevance: This study presents a full 3D kinetic analysis of the relative motion of the humerus, radius, cannon, pastern and coffin segments of the forelimb at the trot. The results could provide for a more sensitive measure for kinetic analysis.
Multihop Adjustment for the Number of Nodes in Contention-Based MAC Protocols for Wireless Ad hoc Networks
Venue: arXiv cs.NI 2011
Year: 2011

The number of contending neighbors of a node in a multihop ad hoc network has to be adjusted while analyzing the performance of the network such as computing the end-to-end delays along a path from a given source to a destination. In this paper, we describe a method to adjust the number of contending neighbors of a node in a multihop wireless ad hoc network. Our method is based on the minimum number of neighbors that has to be common between two consecutive nodes along a path. We derive an analytical expression for the adjustment factor.
On the Network-Wide Gain of Memory-Assisted Source Coding
Venue: arXiv cs.IT 2011
Year: 2011

Several studies have identified a significant amount of redundancy in the network traffic. For example, it is demonstrated that there is a great amount of redundancy within the content of a server over time. This redundancy can be leveraged to reduce the network flow by the deployment of memory units in the network. The question that arises is whether or not the deployment of memory can result in a fundamental improvement in the performance of the network. In this paper, we answer this question affirmatively by first establishing the fundamental gains of memory-assisted source compression and then applying the technique to a network. Specifically, we investigate the gain of memory-assisted compression in random network graphs consisted of a single source and several randomly selected memory units. We find a threshold value for the number of memories deployed in a random graph and show that if the number of memories exceeds the threshold we observe network-wide reduction in the traffic.
The relationship between acquaintanceship and coauthorship in scientific collaboration networks
Venue: arXiv cs.CY 2011
Year: 2011

This article examines the relationship between acquaintanceship and coauthorship patterns in a multi-disciplinary, multi-institutional, geographically distributed research center. Two social networks are constructed and compared: a network of coauthorship, representing how researchers write articles with one another, and a network of acquaintanceship, representing how those researchers know each other on a personal level, based on their responses to an online survey. Statistical analyses of the topology and community structure of these networks point to the importance of small-scale, local, personal networks predicated upon acquaintanceship for accomplishing collaborative work in scientific communities.
Tight Bounds on the Optimization Time of the (1+1) EA on Linear Functions
Venue: arXiv cs.NE 2011
Year: 2011

The analysis of randomized search heuristics on classes of functions is fundamental for the understanding of the underlying stochastic process and the development of suitable proof techniques. Recently, remarkable progress has been made in bounding the expected optimization time of the simple (1+1) EA on the class of linear functions. We improve the best known bound in this setting from $(1.39+o(1))en\ln n$ to $en\ln n+O(n)$ in expectation and with high probability, which is tight up to lower-order terms. Moreover, upper and lower bounds for arbitrary mutations probabilities $p$ are derived, which imply expected polynomial optimization time as long as $p=O((\ln n)/n)$ and which are tight if $p=c/n$ for a constant $c$. As a consequence, the standard mutation probability $p=1/n$ is optimal for all linear functions, and the (1+1) EA is found to be an optimal mutation-based algorithm. The proofs are based on adaptive drift functions and the recent multiplicative drift theorem.
Linear Complexity of Ding-Helleseth Generalized Cyclotomic Binary Sequences of Any Order
Venue: arXiv cs.IT 2011
Year: 2011

This paper gives the linear complexity of binary Ding-Helleseth generalized cyclotomic sequences of any order.
The Parametric Solution of Underdetermined linear ODEs
Venue: arXiv cs.SC 2011
Year: 2011

The purpose of this paper is twofold. An immediate practical use of the presented algorithm is its applicability to the parametric solution of underdetermined linear ordinary differential equations (ODEs) with coefficients that are arbitrary analytic functions in the independent variable. A second conceptual aim is to present an algorithm that is in some sense dual to the fundamental Euclids algorithm, and thus an alternative to the special case of a Groebner basis algorithm as it is used for solving linear ODE-systems. In the paper Euclids algorithm and the new `dual version' are compared and their complementary strengths are analysed on the task of solving underdetermined ODEs. An implementation of the described algorithm is interactively accessible under http://lie.math.brocku.ca/crack/demo.
Parameterized Complexity of MaxSat Above Average
Venue: arXiv cs.CC 2011
Year: 2011

In MaxSat, we are given a CNF formula $F$ with $n$ variables and $m$ clauses and asked to find a truth assignment satisfying the maximum number of clauses. Let $r_1,..., r_m$ be the number of literals in the clauses of $F$. Then $asat(F)=\sum_{i=1}^m (1-2^{-r_i})$ is the expected number of clauses satisfied by a random truth assignment (the truth values to the variables are distributed uniformly and independently). It is well-known that, in polynomial time, one can find a truth assignment satisfying at least $asat(F)$ clauses. In the parameterized problem MaxSat-AA, we are to decide whether there is a truth assignment satisfying at least $asat(F)+k$ clauses, where $k$ is the parameter. We prove that MaxSat-AA is para-NP-complete and, thus, MaxSat-AA is not fixed-parameter tractable unless P$=$NP. This is in sharp contrast to MaxLin2-AA which was recently proved to be fixed-parameter tractable by Crowston et al. (arXiv:1104.1135v3). In fact, we consider a more refined version of {\sc MaxSat-AA}, {\sc Max-$r(n)$-Sat-AA}, where $r_j\le r(n)$ for each $j$. Alon {\em et al.} (SODA 2010) proved that if $r=r(n)$ is a constant, then {\sc Max-$r$-Sat-AA} is fixed-parameter tractable. We prove that {\sc Max-$r(n)$-Sat-AA} is para-NP-complete for $r(n)=\lceil \log n\rceil.$ We also prove that assuming the exponential time hypothesis, {\sc Max-$r(n)$-Sat-AA} is not in XP already for any $r(n)\ge \log \log n +ϕ(n)$, where $ϕ(n)$ is any unbounded strictly increasing function. This lower bound on $r(n)$ cannot be decreased much further as we prove that {\sc Max-$r(n)$-Sat-AA} is (i) in XP for any $r(n)\le \log \log n - \log \log \log n$ and (ii) fixed-parameter tractable for any $r(n)\le \log \log n - \log \log \log n - ϕ(n)$, where $ϕ(n)$ is any unbounded strictly increasing function. The proof uses some results on {\sc MaxLin2-AA}.