OpenRaiser/Intern-Atlas huggingface dataset:
Uncurrying for Innermost Termination and Derivational Complexity
Venue: arXiv cs.LO 2011
Year: 2011

First-order applicative term rewriting systems provide a natural framework for modeling higher-order aspects. In earlier work we introduced an uncurrying transformation which is termination preserving and reflecting. In this paper we investigate how this transformation behaves for innermost termination and (innermost) derivational complexity. We prove that it reflects innermost termination and innermost derivational complexity and that it preserves and reflects polynomial derivational complexity. For the preservation of innermost termination and innermost derivational complexity we give counterexamples. Hence uncurrying may be used as a preprocessing transformation for innermost termination proofs and establishing polynomial upper and lower bounds on the derivational complexity. Additionally it may be used to establish upper bounds on the innermost derivational complexity while it neither is sound for proving innermost non-termination nor for obtaining lower bounds on the innermost derivational complexity.
A standardisation proof for algebraic pattern calculi
Venue: arXiv cs.LO 2011
Year: 2011

This work gives some insights and results on standardisation for call-by-name pattern calculi. More precisely, we define standard reductions for a pattern calculus with constructor-based data terms and patterns. This notion is based on reduction steps that are needed to match an argument with respect to a given pattern. We prove the Standardisation Theorem by using the technique developed by Takahashi and Crary for lambda-calculus. The proof is based on the fact that any development can be specified as a sequence of head steps followed by internal reductions, i.e. reductions in which no head steps are involved.
Quantum Anticipation Explorer
Venue: arXiv cs.MS 2011
Year: 2011

Quantum anticipation explorer is a computer program allowing the numerical exploration of quantum anticipation which has been analyzed in arXiv:0810.183v1 and arXiv:1003.1090v1 for H-Atom, equidistant, random and custom spectra. This tool determines the anticipation strength at those times orthogonal evolution is possible. This paper is the user's guide explaining its capabilities, installation and usage, and documenting the mathematics and algorithms implemented in the software. A zip file containing the setup and documentation can be downloaded from http://www.thomannconsulting.ch/public/aboutus/aboutus-en.htm free of cost.
Treatment of Semantic Heterogeneity in Information Retrieval
Venue: arXiv cs.IR 2011
Year: 2011

The first step to handle semantic heterogeneity should be the attempt to enrich the semantic information about documents, i.e. to fill up the gaps in the documents meta-data automatically. Section 2 describes a set of cascading deductive and heuristic extraction rules, which were developed in the project CARMEN for the domain of Social Sciences. The mapping between different terminologies can be done by using intellectual, statistical and/or neural network transfer modules. Intellectual transfers use cross-concordances between different classification schemes or thesauri. Section 3 describes the creation, storage and handling of such transfers.
The YAP Prolog System
Venue: arXiv cs.PL 2011
Year: 2011

Yet Another Prolog (YAP) is a Prolog system originally developed in the mid-eighties and that has been under almost constant development since then. This paper presents the general structure and design of the YAP system, focusing on three important contributions to the Logic Programming community. First, it describes the main techniques used in YAP to achieve an efficient Prolog engine. Second, most Logic Programming systems have a rather limited indexing algorithm. YAP contributes to this area by providing a dynamic indexing mechanism, or just-in-time indexer (JITI). Third, a important contribution of the YAP system has been the integration of both or-parallelism and tabling in a single Logic Programming system.
Artificial Immune Privileged Sites as an Enhancement to Immuno-Computing Paradigm
Venue: arXiv cs.CR 2011
Year: 2011

The immune system is a highly parallel and distributed intelligent system which has learning, memory, and associative capabilities. Artificial Immune System is an evolutionary paradigm inspired by the biological aspects of the immune system of mammals. The immune system can inspire to form new algorithms learning from its course of action. The human immune system has motivated scientists and engineers for finding powerful information processing algorithms that has solved complex engineering problems. This work is the result of an attempt to explore a different perspective of the immune system namely the Immune Privileged Site (IPS) which has the ability to make an exception to different parts of the body by not triggering immune response to some of the foreign agent in these parts of the body. While the complete system is secured by an Immune System at certain times it may be required that the system allows certain activities which may be harmful to other system which is useful to it and learns over a period of time through the immune privilege model as done in case of Immune Privilege Sites in Natural Immune System.
Approximating the Online Set Multicover Problems Via Randomized Winnowing
Venue: arXiv cs.DS 2011
Year: 2011

In this paper, we consider the weighted online set k-multicover problem. In this problem, we have a universe V of elements, a family S of subsets of V with a positive real cost for every set in S and a "coverage factor" (positive integer) k. A subset of elements are presented online in an arbitrary order. When each element, say i, is presented, we are also told the collection of all (at least k) sets and their costs to which i belongs and we need to select additional sets from these sets containing i, if necessary, such that our collection of selected sets contains at least k sets that contain the element i. The goal is to minimize the total cost of the selected sets (our algorithm and competitive ratio bounds can be extended to the case when a set can be selected at most a pre-specified number of times instead of just once; we do not report these extensions for simplicity and also because they have no relevance to the biological applications that motivated our work). In this paper, we describe a new randomized algorithm for the online multicover problem based on a randomized version of the winnowing approach of Littlestone. This algorithm generalizes and improves some earlier results by N. Alon, B. Awerbuch, Y. Azar, N. Buchbinder, and J. Naor. We also discuss lower bounds on competitive ratios for deterministic algorithms for general $k$.
Antilope - A Lagrangian Relaxation Approach to the de novo Peptide Sequencing Problem
Venue: arXiv cs.DS 2011
Year: 2011

Peptide sequencing from mass spectrometry data is a key step in proteome research. Especially de novo sequencing, the identification of a peptide from its spectrum alone, is still a challenge even for state-of-the-art algorithmic approaches. In this paper we present Antilope, a new fast and flexible approach based on mathematical programming. It builds on the spectrum graph model and works with a variety of scoring schemes. Antilope combines Lagrangian relaxation for solving an integer linear programming formulation with an adaptation of Yen's k shortest paths algorithm. It shows a significant improvement in running time compared to mixed integer optimization and performs at the same speed like other state-of-the-art tools. We also implemented a generic probabilistic scoring scheme that can be trained automatically for a dataset of annotated spectra and is independent of the mass spectrometer type. Evaluations on benchmark data show that Antilope is competitive to the popular state-of-the-art programs PepNovo and NovoHMM both in terms of run time and accuracy. Furthermore, it offers increased flexibility in the number of considered ion types. Antilope will be freely available as part of the open source proteomics library OpenMS.
Geodesic stability for memoryless binary long-lived consensus
Venue: arXiv cs.DM 2011
Year: 2011

The determination of the stability of the long-lived consensus problem is a fundamental open problem in distributed systems. We concentrate on the memoryless binary case with geodesic paths. We offer a conjecture on the stability in this case, exhibit two classes of colourings which attain this conjectured bound, and improve the known lower bounds for all colourings. We also introduce a related parameter, which measures the stability only for certain geodesics, and for which we also prove lower bounds.
Experimental Aspects of Synthesis
Venue: arXiv cs.LO 2011
Year: 2011

We discuss the problem of experimentally evaluating linear-time temporal logic (LTL) synthesis tools for reactive systems. We first survey previous such work for the currently publicly available synthesis tools, and then draw conclusions by deriving useful schemes for future such evaluations. In particular, we explain why previous tools have incompatible scopes and semantics and provide a framework that reduces the impact of this problem for future experimental comparisons of such tools. Furthermore, we discuss which difficulties the complex workflows that begin to appear in modern synthesis tools induce on experimental evaluations and give answers to the question how convincing such evaluations can still be performed in such a setting.
Model-checking ATL under Imperfect Information and Perfect Recall Semantics is Undecidable
Venue: arXiv cs.LO 2011
Year: 2011

We propose a formal proof of the undecidability of the model checking problem for alternating- time temporal logic under imperfect information and perfect recall semantics. This problem was announced to be undecidable according to a personal communication on multi-player games with imperfect information, but no formal proof was ever published. Our proof is based on a direct reduction from the non-halting problem for Turing machines.
Improved RIP Analysis of Orthogonal Matching Pursuit
Venue: arXiv cs.DS 2011
Year: 2011

Orthogonal Matching Pursuit (OMP) has long been considered a powerful heuristic for attacking compressive sensing problems; however, its theoretical development is, unfortunately, somewhat lacking. This paper presents an improved Restricted Isometry Property (RIP) based performance guarantee for T-sparse signal reconstruction that asymptotically approaches the conjectured lower bound given in Davenport et al. We also further extend the state-of-the-art by deriving reconstruction error bounds for the case of general non-sparse signals subjected to measurement noise. We then generalize our results to the case of K-fold Orthogonal Matching Pursuit (KOMP). We finish by presenting an empirical analysis suggesting that OMP and KOMP outperform other compressive sensing algorithms in average case scenarios. This turns out to be quite surprising since RIP analysis (i.e. worst case scenario) suggests that these matching pursuits should perform roughly T^0.5 times worse than convex optimization, CoSAMP, and Iterative Thresholding.
LGM: Mining Frequent Subgraphs from Linear Graphs
Venue: arXiv cs.DS 2011
Year: 2011

A linear graph is a graph whose vertices are totally ordered. Biological and linguistic sequences with interactions among symbols are naturally represented as linear graphs. Examples include protein contact maps, RNA secondary structures and predicate-argument structures. Our algorithm, linear graph miner (LGM), leverages the vertex order for efficient enumeration of frequent subgraphs. Based on the reverse search principle, the pattern space is systematically traversed without expensive duplication checking. Disconnected subgraph patterns are particularly important in linear graphs due to their sequential nature. Unlike conventional graph mining algorithms detecting connected patterns only, LGM can detect disconnected patterns as well. The utility and efficiency of LGM are demonstrated in experiments on protein contact maps.
BP Variability Case Studies Development using different Modeling Approaches
Venue: arXiv cs.SE 2011
Year: 2011

Variability in Business Process modeling has already been faced by different authors from the literature. Depending on the context in which each author faces the modeling problem, we find different approaches (C-EPC, C-YAWL, FEATURE-EPC, PESOA, PROVOP, or WORKLETS). In this report we present four of the most representative approaches (C-EPC, PESOA, PROVOP and WORKLETS) which are presented by means of the different case studies found in the literature.
The Algebra of Two Dimensional Patterns
Venue: arXiv cs.IT 2011
Year: 2011

The article presents an algebra to represent two dimensional patterns using reciprocals of polynomials. Such a representation will be useful in neural network training and it provides a method of training patterns that is much more efficient than a pixel-wise representation.
Privacy-Enhanced Reputation-Feedback Methods to Reduce Feedback Extortion in Online Auctions
Venue: arXiv cs.CR 2011
Year: 2011

In this paper, we study methods for improving the utility and privacy of reputation scores for online auctions, such as used in eBay, so as to reduce the effectiveness of feedback extortion. The main ideas behind our techniques are to use randomization and various schemes to escrow reputations scores until appropriate external events occur. Depending on the degree of utility and privacy needed, these external techniques could depend on the number and type of reputation scores collected. Moreover, if additional privacy protection is needed, then random sampling can be used with respect reputation scores in such a way that reputation aggregates remain useful, but individual reputation scores are probabilistically hidden from users. Finally, we show that if privacy is also desired with respect to the the reputation aggregator, then we can use zero-knowledge proofs for reputation comparisons.
Modal Calculus of Illocutionary Logic
Venue: arXiv cs.LO 2011
Year: 2011

The aim of illocutionary logic is to explain how context can affect the meaning of certain special kinds of performative utterances. Recall that performative utterances are understood as follows: a speaker performs the illocutionary act (e.g. act of assertion, of conjecture, of promise) with the illocutionary force (resp. assertion, conjecture, promise) named by an appropriate performative verb in the way of representing himself as performing that act. In the paper I proposed many-valued interpretation of illocutionary forces understood as modal operators. As a result, I built up a non-Archimedean valued logic for formalizing illocutionary acts. A formal many-valued approach to illocutionary logic was offered for the first time.
Non-Conservative Diffusion and its Application to Social Network Analysis
Venue: arXiv cs.SI 2011
Year: 2011

The random walk is fundamental to modeling dynamic processes on networks. Metrics based on the random walk have been used in many applications from image processing to Web page ranking. However, how appropriate are random walks to modeling and analyzing social networks? We argue that unlike a random walk, which conserves the quantity diffusing on a network, many interesting social phenomena, such as the spread of information or disease on a social network, are fundamentally non-conservative. When an individual infects her neighbor with a virus, the total amount of infection increases. We classify diffusion processes as conservative and non-conservative and show how these differences impact the choice of metrics used for network analysis, as well as our understanding of network structure and behavior. We show that Alpha-Centrality, which mathematically describes non-conservative diffusion, leads to new insights into the behavior of spreading processes on networks. We give a scalable approximate algorithm for computing the Alpha-Centrality in a massive graph. We validate our approach on real-world online social networks of Digg. We show that a non-conservative metric, such as Alpha-Centrality, produces better agreement with empirical measure of influence than conservative metrics, such as PageRank. We hope that our investigation will inspire further exploration into the realms of conservative and non-conservative metrics in social network analysis.
Turbo Codes Based on Time-Variant Memory-1 Convolutional Codes over Fq
Venue: arXiv cs.IT 2011
Year: 2011

Two classes of turbo codes over high-order finite fields are introduced. The codes are derived from a particular protograph sub-ensemble of the (dv=2,dc=3) low-density parity-check code ensemble. A first construction is derived as a parallel concatenation of two non-binary, time-variant accumulators. The second construction is based on the serial concatenation of a non-binary, time-variant differentiator and of a non-binary, time-variant accumulator, and provides a highly-structured flexible encoding scheme for (dv=2,dc=4) ensemble codes. A cycle graph representation is provided. The proposed codes can be decoded efficiently either as low-density parity-check codes (via belief propagation decoding over the codes bipartite graph) or as turbo codes (via the forward-backward algorithm applied to the component codes trellis). The forward-backward algorithm for symbol maximum a posteriori decoding of the component codes is illustrated and simplified by means of the fast Fourier transform. The proposed codes provide remarkable gains (~ 1 dB) over binary low-density parity-check and turbo codes in the moderate-short block regimes.
Polynomial evaluation over finite fields: new algorithms and complexity bounds
Venue: arXiv cs.IT 2011
Year: 2011

An efficient evaluation method is described for polynomials in finite fields. Its complexity is shown to be lower than that of standard techniques when the degree of the polynomial is large enough. Applications to the syndrome computation in the decoding of Reed-Solomon codes are highlighted.
Short-Message Quantize-Forward Network Coding
Venue: arXiv cs.IT 2011
Year: 2011

Recent work for single-relay channels shows that quantize-forward (QF) with long-message encoding achieves the same reliable rates as compress-forward (CF) with short-message encoding. It is shown that short-message QF with backward or pipelined (sliding-window) decoding also achieves the same rates. Similarly, for many relays and sources, short-message QF with backward decoding achieves the same rates as long-message QF. Several practical advantages of short-message encoding are pointed out, e.g., reduced delay and simpler modulation. Furthermore, short-message encoding lets relays use decode-forward (DF) if their channel quality is good, thereby enabling multiinput, multi-output (MIMO) gains that are not possible with long-message encoding. Finally, one may combine the advantages of long- and short-message encoding by hashing a long message to short messages.
Measurement Matrix Design for Compressive Sensing Based MIMO Radar
Venue: arXiv cs.IT 2011
Year: 2011

In colocated multiple-input multiple-output (MIMO) radar using compressive sensing (CS), a receive node compresses its received signal via a linear transformation, referred to as measurement matrix. The samples are subsequently forwarded to a fusion center, where an L1-optimization problem is formulated and solved for target information. CS-based MIMO radar exploits the target sparsity in the angle-Doppler-range space and thus achieves the high localization performance of traditional MIMO radar but with many fewer measurements. The measurement matrix is vital for CS recovery performance. This paper considers the design of measurement matrices that achieve an optimality criterion that depends on the coherence of the sensing matrix (CSM) and/or signal-to-interference ratio (SIR). The first approach minimizes a performance penalty that is a linear combination of CSM and the inverse SIR. The second one imposes a structure on the measurement matrix and determines the parameters involved so that the SIR is enhanced. Depending on the transmit waveforms, the second approach can significantly improve SIR, while maintaining CSM comparable to that of the Gaussian random measurement matrix (GRMM). Simulations indicate that the proposed measurement matrices can improve detection accuracy as compared to a GRMM.
Low-Complexity Near-Optimal Codes for Gaussian Relay Networks
Venue: arXiv cs.IT 2011
Year: 2011

We consider the problem of information flow over Gaussian relay networks. Similar to the recent work by Avestimehr \emph{et al.} [1], we propose network codes that achieve up to a constant gap from the capacity of such networks. However, our proposed codes are also computationally tractable. Our main technique is to use the codes of Avestimehr \emph{et al.} as inner codes in a concatenated coding scheme.
Universal Higher Order Grammar
Venue: arXiv cs.CL 2011
Year: 2011

We examine the class of languages that can be defined entirely in terms of provability in an extension of the sorted type theory (Ty_n) by embedding the logic of phonologies, without introduction of special types for syntactic entities. This class is proven to precisely coincide with the class of logically closed languages that may be thought of as functions from expressions to sets of logically equivalent Ty_n terms. For a specific sub-class of logically closed languages that are described by finite sets of rules or rule schemata, we find effective procedures for building a compact Ty_n representation, involving a finite number of axioms or axiom schemata. The proposed formalism is characterized by some useful features unavailable in a two-component architecture of a language model. A further specialization and extension of the formalism with a context type enable effective account of intensional and dynamic semantics.
Bilayer LDPC Convolutional Codes for Half-Duplex Relay Channels
Venue: arXiv cs.IT 2011
Year: 2011

In this paper we present regular bilayer LDPC convolutional codes for half-duplex relay channels. For the binary erasure relay channel, we prove that the proposed code construction achieves the capacities for the source-relay link and the source-destination link provided that the channel conditions are known when designing the code. Meanwhile, this code enables the highest transmission rate with decode-and-forward relaying. In addition, its regular degree distributions can easily be computed from the channel parameters, which significantly simplifies the code optimization. Numerical results are provided for both binary erasure channels (BEC) and AWGN channels. In BECs, we can observe that the gaps between the decoding thresholds and the Shannon limits are impressively small. In AWGN channels, the bilayer LDPC convolutional code clearly outperforms its block code counterpart in terms of bit error rate.