OpenRaiser/Intern-Atlas huggingface dataset:
BagPack: A general framework to represent semantic relations
Venue: arXiv cs.CL 2009
Year: 2009

We introduce a way to represent word pairs instantiating arbitrary semantic relations that keeps track of the contexts in which the words in the pair occur both together and independently. The resulting features are of sufficient generality to allow us, with the help of a standard supervised machine learning algorithm, to tackle a variety of unrelated semantic tasks with good results and almost no task-specific tailoring.
Network Coding with Two-Way Relaying: Achievable Rate Regions and Diversity-Multiplexing Tradeoffs
Venue: arXiv cs.IT 2009
Year: 2009

This paper addresses the fundamental characteristics of information exchange via multihop network coding over two-way relaying in a wireless ad hoc network. The end-to-end rate regions achieved by time-division multihop (TDMH), MAC-layer network coding (MLNC) and PHY-layer network coding (PLNC) are first characterized. It is shown that MLNC does not always achieve better rates than TDMH, time sharing between TDMH and MLNC is able to achieve a larger rate region, and PLNC dominates the rate regions achieved by TDMH and MLNC. An opportunistic scheduling algorithm for MLNC and PLNC is then proposed to stabilize the two-way relaying system for Poisson arrivals whenever the rate pair is within the Shannon rate regions of MLNC and PLNC. To understand the two-way transmission limits of multihop network coding, the sum-rate optimization with or without certain traffic pattern and the end-to-end diversity-multiplexing tradeoffs (DMTs) of two-way transmission over multiple relay nodes are also analyzed.
A Dichotomy Theorem for Polynomial Evaluation
Venue: arXiv cs.CC 2009
Year: 2009

A dichotomy theorem for counting problems due to Creignou and Hermann states that or any nite set S of logical relations, the counting problem #SAT(S) is either in FP, or #P-complete. In the present paper we show a dichotomy theorem for polynomial evaluation. That is, we show that for a given set S, either there exists a VNP-complete family of polynomials associated to S, or the associated families of polynomials are all in VP. We give a concise characterization of the sets S that give rise to "easy" and "hard" polynomials. We also prove that several problems which were known to be #P-complete under Turing reductions only are in fact #P-complete under many-one reductions.
On weak isometries of Preparata codes
Venue: arXiv cs.IT 2009
Year: 2009

Let C1 and C2 be codes with code distance d. Codes C1 and C2 are called weakly isometric, if there exists a mapping J:C1->C2, such that for any x,y from C1 the equality d(x,y)=d holds if and only if d(J(x),J(y))=d. Obviously two codes are weakly isometric if and only if the minimal distance graphs of these codes are isomorphic. In this paper we prove that Preparata codes of length n>=2^12 are weakly isometric if and only if these codes are equivalent. The analogous result is obtained for punctured Preparata codes of length not less than 2^10-1.
Capacity of the Gaussian Two-way Relay Channel to within 1/2 Bit
Venue: arXiv cs.IT 2009
Year: 2009

In this paper, a Gaussian two-way relay channel, where two source nodes exchange messages with each other through a relay, is considered. We assume that all nodes operate in full-duplex mode and there is no direct channel between the source nodes. We propose an achievable scheme composed of nested lattice codes for the uplink and structured binning for the downlink. We show that the scheme achieves within 1/2 bit from the cut-set bound for all channel parameters and becomes asymptotically optimal as the signal to noise ratios increase.
Combining coded signals with arbitrary modulations in orthogonal relay channels
Venue: arXiv cs.IT 2009
Year: 2009

We consider a relay channel for which the following assumptions are made. (1) The source-destination and relay-destination channels are orthogonal (frequency division relay channel). (2) The relay implements the decode-and-forward protocol. (3) The source and relay implement the same channel encoder, namely, a onvolutional encoder. (4) They can use arbitrary and possibly different modulations. In this framework, we derive the best combiner in the sense of the maximum likelihood (ML) at the destination and the branch metrics of the trellis associated with its channel decoder for the ML combiner and also for the maximum ratio combiner (MRC), cooperative-MRC (C-MRC), and the minimum mean-square error (MMSE) combiner.
Parallel machine scheduling with precedence constraints and setup times
Venue: arXiv cs.DS 2009
Year: 2009

This paper presents different methods for solving parallel machine scheduling problems with precedence constraints and setup times between the jobs. Limited discrepancy search methods mixed with local search principles, dominance conditions and specific lower bounds are proposed. The proposed methods are evaluated on a set of randomly generated instances and compared with previous results from the literature and those obtained with an efficient commercial solver. We conclude that our propositions are quite competitive and our results even outperform other approaches in most cases.
Generalised sequential crossover of words and languages
Venue: arXiv cs.DM 2009
Year: 2009

In this paper, we propose a new operation, Generalised Sequential Crossover (GSCO) of words, which in some sense an abstract model of crossing over of the chromosomes in the living organisms. We extend GSCO over language $L$ iteratively ($GSCO^*(L)$ as well as iterated GSCO over two languages $GSCO^*(L_1,L_2)$). Our study reveals that $GSCO^*(L)$ is subclass of regular languages for any $L$. We compare the different classes of GSCO languages with the prominent sub-regular classes.
Relational Lattice Foundation for Algebraic Logic
Venue: arXiv cs.DB 2009
Year: 2009

Relational Lattice is a succinct mathematical model for Relational Algebra. It reduces the set of six classic relational algebra operators to two: natural join and inner union. In this paper we push relational lattice theory in two directions. First, we uncover a pair of complementary lattice operators, and organize the model into a bilattice of four operations and four distinguished constants. We take a notice a peculiar way bilattice symmetry is broken. Then, we give axiomatic introduction of unary negation operation and prove several laws, including double negation and De Morgan. Next we reduce the model back to two basic binary operations and twelve axioms, and exhibit a convincing argument that the resulting system is complete in model-theoretic sense. The final parts of the paper casts relational lattice perspective onto database dependency theory and into cylindric algebras.
System approach to synthesis, modeling and control of complex dynamical systems
Venue: arXiv cs.CE 2009
Year: 2009

We consider the basic features of complex dynamical and control systems. Special attention is paid to the problems of synthesis of dynamical models of complex systems, construction of efficient control models, and to the development of simulation techniques. We propose an approach to the synthesis of dynamic models of complex systems that integrates expert knowledge with the process of modeling. A set-theoretic model of complex system is defined and briefly analyzed. A mathematical model of complex dynamical system with control, based on aggregate description, is also proposed. The structure of the model is described, and architecture of computer simulation system is presented, requirements to and components of computer simulation systems are analyzed.
Syntactic Confluence Criteria for Positive/Negative-Conditional Term Rewriting Systems
Venue: arXiv cs.AI 2009
Year: 2009

We study the combination of the following already known ideas for showing confluence of unconditional or conditional term rewriting systems into practically more useful confluence criteria for conditional systems: Our syntactical separation into constructor and non-constructor symbols, Huet's introduction and Toyama's generalization of parallel closedness for non-noetherian unconditional systems, the use of shallow confluence for proving confluence of noetherian and non-noetherian conditional systems, the idea that certain kinds of limited confluence can be assumed for checking the fulfilledness or infeasibility of the conditions of conditional critical pairs, and the idea that (when termination is given) only prime superpositions have to be considered and certain normalization restrictions can be applied for the substitutions fulfilling the conditions of conditional critical pairs. Besides combining and improving already known methods, we present the following new ideas and results: We strengthen the criterion for overlay joinable noetherian systems, and, by using the expressiveness of our syntactical separation into constructor and non-constructor symbols, we are able to present criteria for level confluence that are not criteria for shallow confluence actually and also able to weaken the severe requirement of normality (stiffened with left-linearity) in the criteria for shallow confluence of noetherian and non-noetherian conditional systems to the easily satisfied requirement of quasi-normality. Finally, the whole paper may also give a practically useful overview of the syntactical means for showing confluence of conditional term rewriting systems.
Algorithmic Meta-Theorems
Venue: arXiv cs.LO 2009
Year: 2009

Algorithmic meta-theorems are general algorithmic results applying to a whole range of problems, rather than just to a single problem alone. They often have a "logical" and a "structural" component, that is they are results of the form: every computational problem that can be formalised in a given logic L can be solved efficiently on every class C of structures satisfying certain conditions. This paper gives a survey of algorithmic meta-theorems obtained in recent years and the methods used to prove them. As many meta-theorems use results from graph minor theory, we give a brief introduction to the theory developed by Robertson and Seymour for their proof of the graph minor theorem and state the main algorithmic consequences of this theory as far as they are needed in the theory of algorithmic meta-theorems.
Dipole and Quadrupole Moments in Image Processing
Venue: arXiv cs.CV 2009
Year: 2009

This paper proposes an algorithm for image processing, obtained by adapting to image maps the definitions of two well-known physical quantities. These quantities are the dipole and quadrupole moments of a charge distribution. We will see how it is possible to define dipole and quadrupole moments for the gray-tone maps and apply them in the development of algorithms for edge detection.
Filter and nested-lattice code design for fading MIMO channels with side-information
Venue: arXiv cs.IT 2009
Year: 2009

Linear-assignment Gel'fand-Pinsker coding (LA-GPC) is a coding technique for channels with interference known only at the transmitter, where the known interference is treated as side-information (SI). As a special case of LA-GPC, dirty paper coding has been shown to be able to achieve the optimal interference-free rate for interference channels with perfect channel state information at the transmitter (CSIT). In the cases where only the channel distribution information at the transmitter (CDIT) is available, LA-GPC also has good (sometimes optimal) performance in a variety of fast and slow fading SI channels. In this paper, we design the filters in nested-lattice based coding to make it achieve the same rate performance as LA-GPC in multiple-input multiple-output (MIMO) channels. Compared with the random Gaussian codebooks used in previous works, our resultant coding schemes have an algebraic structure and can be implemented in practical systems. A simulation in a slow-fading channel is also provided, and near interference-free error performance is obtained. The proposed coding schemes can serve as the fundamental building blocks to achieve the promised rate performance of MIMO Gaussian broadcast channels with CDIT or perfect CSIT
Semantic Network Layering
Venue: arXiv cs.NI 2009
Year: 2009

The stack in various forms has been widely used as an architectural template for networking systems. Recently the stack has been subject to criticism for a lack of flexibility. However, when it comes right down to it nobody has offered a truly compelling alternative. Various cross-layer optimizations have been proposed, but these optimizations are frequently hacks to achieve a particular goal and offer no direct insight into why the existing network stack is inadequate. We propose that a fundamental problem with the existing network stack is that it attempts to layer functionality that is not well-suited to layering. In this work we use a "bottom up" model of information computation, storage, and transfer and the "top down" goals of networking systems to formulate a modular decomposition of networking systems. Based on this modular decomposition we propose a semantic layered structure for networking systems that eliminates many awkward cross-layer interactions that arise in the canonical layered stack.
Cyclic Codes and Sequences from a Class of Dembowski-Ostrom Functions
Venue: arXiv cs.IT 2009
Year: 2009

Let $q=p^n$ with $p$ be an odd prime. Let $0\leq k\leq n-1$ and $k\neq n/2$. In this paper we determine the value distribution of following exponential(character) sums \[\sum\limits_{x\in \bF_q}ζ_p^{\Tra_1^n(αx^{p^{3k}+1}+βx^{p^k+1})}\quad(α\in \bF_{p^m},β\in \bF_{q})\] and \[\sum\limits_{x\in \bF_q}ζ_p^{\Tra_1^n(αx^{p^{3k}+1}+βx^{p^k+1}+\ga x)}\quad(α\in \bF_{p^m},β,\ga\in \bF_{q})\] where $\Tra_1^n: \bF_q\ra \bF_p$ and $\Tra_1^m: \bF_{p^m}\ra\bF_p$ are the canonical trace mappings and $ζ_p=e^{\frac{2πi}{p}}$ is a primitive $p$-th root of unity. As applications: (1). We determine the weight distribution of the cyclic codes $\cC_1$ and $\cC_2$ over $\bF_{p^t}$ with parity-check polynomials $h_2(x)h_3(x)$ and $h_1(x)h_2(x)h_3(x)$ respectively where $t$ is a divisor of $d=\gcd(n,k)$, and $h_1(x)$, $h_2(x)$ and $h_3(x)$ are the minimal polynomials of $π^{-1}$, $π^{-(p^k+1)}$ and $π^{-(p^{3k}+1)}$ over $\bF_{p^t}$ respectively for a primitive element $π$ of $\bF_q$. (2). We determine the correlation distribution among a family of m-sequences.
Degrees of Undecidability in Rewriting
Venue: arXiv cs.LO 2009
Year: 2009

Undecidability of various properties of first order term rewriting systems is well-known. An undecidable property can be classified by the complexity of the formula defining it. This gives rise to a hierarchy of distinct levels of undecidability, starting from the arithmetical hierarchy classifying properties using first order arithmetical formulas and continuing into the analytic hierarchy, where also quantification over function variables is allowed. In this paper we consider properties of first order term rewriting systems and classify them in this hierarchy. Weak and strong normalization for single terms turn out to be Sigma-0-1-complete, while their uniform versions as well as dependency pair problems with minimality flag are Pi-0-2-complete. We find that confluence is Pi-0-2-complete both for single terms and uniform. Unexpectedly weak confluence for ground terms turns out to be harder than weak confluence for open terms. The former property is Pi-0-2-complete while the latter is Sigma-0-1-complete (and thereby recursively enumerable). The most surprising result is on dependency pair problems without minimality flag: we prove this to be Pi-1-1-complete, which means that this property exceeds the arithmetical hierarchy and is essentially analytic.
Implementation of Multipath and Multiple Description Coding in OLSR
Venue: arXiv cs.NI 2009
Year: 2009

In this paper we discussed the application and the implementation of multipath routing and multiple description coding (MDC) extension of OLSR, called MP-OLSR. It is based on the link state algorithm and employs periodic exchange of messages to maintain topology information of the networks. In the mean time, it updates the routing table in an on-demand scheme and forwards the packets in multiple paths which have been determined at the source. If a link failure is detected, the algorithm recovers the route automatically. Concerning the instability of the wireless networks, the multiple description coding is used to improve reliability of the network transmission, and several methods are proposed to allocate the redundancy in different paths. The simulation in NS2 shows that the new protocol can effectively improve the performance of the networks. The implementation of MP-OLSR is also proposed in the end.
Considerations on Resource Usage in Exceptions and Failures in Workflows
Venue: arXiv cs.SE 2009
Year: 2009

The paper presents a description of some point of view of different authors related to the failures and exceptions that appear in workflows, as a direct consequence of unavailability of resources involved in the workflow. Each of these interpretations is typical for a certain situation, depending on the authors' interpretation of failures and exceptions in workflows modeling real dynamical systems.
Separable Implementation of L2-Orthogonal STC CPM with Fast Decoding
Venue: arXiv cs.IT 2009
Year: 2009

In this paper we present an alternative separable implementation of L2-orthogonal space-time codes (STC) for continuous phase modulation (CPM). In this approach, we split the STC CPM transmitter into a single conventional CPM modulator and a correction filter bank. While the CPM modulator is common to all transmit antennas, the correction filter bank applies different correction units to each antenna. Thereby desirable code properties as orthogonality and full diversity are achievable with just a slightly larger bandwidth demand. This new representation has three main advantages. First, it allows to easily generalize the orthogonality condition to any arbitrary number of transmit antennas. Second, for a quite general set of correction functions that we detail, it can be proved that full diversity is achieved. Third, by separating the modulation and correction steps inside the receiver, a simpler receiver can be designed as a bank of data independent inverse correction filters followed by a single CPM demodulator. Therefore, in this implementation, only one correlation filter bank for the detection of all transmitted signals is necessary. The decoding effort grows only linearly with the number of transmit antennas.
A polynomial graph extension procedure for improving graph isomorphism algorithms
Venue: arXiv cs.DS 2009
Year: 2009

We present in this short note a polynomial graph extension procedure that can be used to improve any graph isomorphism algorithm. This construction propagates new constraints from the isomorphism constraints of the input graphs (denoted by $G(V,E)$ and $G'(V',E')$). Thus, information from the edge structures of $G$ and $G'$ is "hashed" into the weighted edges of the extended graphs. A bijective mapping is an isomorphism of the initial graphs if and only if it is an isomorphism of the extended graphs. As such, the construction enables the identification of pair of vertices $i\in V$ and $i'\in V'$ that can not be mapped by any isomorphism $h^*:V \to V'$ (e.g. if the extended edges of $i$ and $i'$ are different). A forbidding matrix $F$, that encodes all pairs of incompatible mappings $(i,i')$, is constructed in order to be used by a different algorithm. Moreover, tests on numerous graph classes show that the matrix $F$ might leave only one compatible element for each $i \in V$.
Accelerating and Evaluation of Syntactic Parsing in Natural Language Question Answering Systems
Venue: arXiv cs.AI 2009
Year: 2009

With the development of Natural Language Processing (NLP), more and more systems want to adopt NLP in User Interface Module to process user input, in order to communicate with user in a natural way. However, this raises a speed problem. That is, if NLP module can not process sentences in durable time delay, users will never use the system. As a result, systems which are strict with processing time, such as dialogue systems, web search systems, automatic customer service systems, especially real-time systems, have to abandon NLP module in order to get a faster system response. This paper aims to solve the speed problem. In this paper, at first, the construction of a syntactic parser which is based on corpus machine learning and statistics model is introduced, and then a speed problem analysis is performed on the parser and its algorithms. Based on the analysis, two accelerating methods, Compressed POS Set and Syntactic Patterns Pruning, are proposed, which can effectively improve the time efficiency of parsing in NLP module. To evaluate different parameters in the accelerating algorithms, two new factors, PT and RT, are introduced and explained in detail. Experiments are also completed to prove and test these methods, which will surely contribute to the application of NLP.
Polar Codes are Optimal for Lossy Source Coding
Venue: arXiv cs.IT 2009
Year: 2009

We consider lossy source compression of a binary symmetric source using polar codes and the low-complexity successive encoding algorithm. It was recently shown by Arikan that polar codes achieve the capacity of arbitrary symmetric binary-input discrete memoryless channels under a successive decoding strategy. We show the equivalent result for lossy source compression, i.e., we show that this combination achieves the rate-distortion bound for a binary symmetric source. We further show the optimality of polar codes for various problems including the binary Wyner-Ziv and the binary Gelfand-Pinsker problem
Design Guidelines for Training-based MIMO Systems with Feedback
Venue: arXiv cs.IT 2009
Year: 2009

In this paper, we study the optimal training and data transmission strategies for block fading multiple-input multiple-output (MIMO) systems with feedback. We consider both the channel gain feedback (CGF) system and the channel covariance feedback (CCF) system. Using an accurate capacity lower bound as a figure of merit, we investigate the optimization problems on the temporal power allocation to training and data transmission as well as the training length. For CGF systems without feedback delay, we prove that the optimal solutions coincide with those for non-feedback systems. Moreover, we show that these solutions stay nearly optimal even in the presence of feedback delay. This finding is important for practical MIMO training design. For CCF systems, the optimal training length can be less than the number of transmit antennas, which is verified through numerical analysis. Taking this fact into account, we propose a simple yet near optimal transmission strategy for CCF systems, and derive the optimal temporal power allocation over pilot and data transmission.
Decompositions of Grammar Constraints
Venue: arXiv cs.AI 2009
Year: 2009

A wide range of constraints can be compactly specified using automata or formal languages. In a sequence of recent papers, we have shown that an effective means to reason with such specifications is to decompose them into primitive constraints. We can then, for instance, use state of the art SAT solvers and profit from their advanced features like fast unit propagation, clause learning, and conflict-based search heuristics. This approach holds promise for solving combinatorial problems in scheduling, rostering, and configuration, as well as problems in more diverse areas like bioinformatics, software testing and natural language processing. In addition, decomposition may be an effective method to propagate other global constraints.
Combining Symmetry Breaking and Global Constraints
Venue: arXiv cs.AI 2009
Year: 2009

We propose a new family of constraints which combine together lexicographical ordering constraints for symmetry breaking with other common global constraints. We give a general purpose propagator for this family of constraints, and show how to improve its complexity by exploiting properties of the included global constraints.