OpenRaiser/Intern-Atlas huggingface dataset:
PHA*: Finding the Shortest Path with A* in An Unknown Physical Environment
Venue: arXiv cs.AI 2011
Year: 2011

We address the problem of finding the shortest path between two points in an unknown real physical environment, where a traveling agent must move around in the environment to explore unknown territory. We introduce the Physical-A* algorithm (PHA*) for solving this problem. PHA* expands all the mandatory nodes that A* would expand and returns the shortest path between the two points. However, due to the physical nature of the problem, the complexity of the algorithm is measured by the traveling effort of the moving agent and not by the number of generated nodes, as in standard A*. PHA* is presented as a two-level algorithm, such that its high level, A*, chooses the next node to be expanded and its low level directs the agent to that node in order to explore it. We present a number of variations for both the high-level and low-level procedures and evaluate their performance theoretically and experimentally. We show that the travel cost of our best variation is fairly close to the optimal travel cost, assuming that the mandatory nodes of A* are known in advance. We then generalize our algorithm to the multi-agent case, where a number of cooperative agents are designed to solve the problem. Specifically, we provide an experimental implementation for such a system. It should be noted that the problem addressed here is not a navigation problem, but rather a problem of finding the shortest path between two points for future usage.
A Comprehensive Trainable Error Model for Sung Music Queries
Venue: arXiv cs.AI 2011
Year: 2011

We propose a model for errors in sung queries, a variant of the hidden Markov model (HMM). This is a solution to the problem of identifying the degree of similarity between a (typically error-laden) sung query and a potential target in a database of musical works, an important problem in the field of music information retrieval. Similarity metrics are a critical component of query-by-humming (QBH) applications which search audio and multimedia databases for strong matches to oral queries. Our model comprehensively expresses the types of error or variation between target and query: cumulative and non-cumulative local errors, transposition, tempo and tempo changes, insertions, deletions and modulation. The model is not only expressive, but automatically trainable, or able to learn and generalize from query examples. We present results of simulations, designed to assess the discriminatory potential of the model, and tests with real sung queries, to demonstrate relevance to real-world applications.
Tracing Properties of UML and OCL Models with Maude
Venue: arXiv cs.SE 2011
Year: 2011

The starting point of this paper is a system described in form of a UML class diagram where system states are characterized by OCL invariants and system transitions are defined by OCL pre- and postconditions. The aim of our approach is to assist the developer in learning about the consequences of the described system states and transitions and about the formal implications of the properties that are explicitly given. We propose to draw conclusions about the stated constraints by translating the UML and OCL model into the algebraic specification language and system Maude, which is based on rewrite logic. We will concentrate in this paper on employing Maude's capabilities for state search. Maude's state search offers the possibility to describe a start configuration of the system and then explore all configurations reachable by rewriting. The search can be adjusted by formulating requirements for the allowed states and the allowed transitions.
First-order finite satisfiability vs tree automata in safety verification
Venue: arXiv cs.LO 2011
Year: 2011

In this paper we deal with verification of safety properties of term-rewriting systems. The verification problem is translated to a purely logical problem of finding a finite countermodel for a first-order formula, which further resolved by a generic finite model finding procedure. A finite countermodel produced during successful verification provides with a concise description of the system invariant sufficient to demonstrate a specific safety property. We show the relative completeness of this approach with respect to the tree automata completion technique. On a set of examples taken from the literature we demonstrate the efficiency of finite model finding approach as well as its explanatory power.
Beamforming on the MISO interference channel with multi-user decoding capability
Venue: arXiv cs.IT 2011
Year: 2011

This paper considers the multiple-input-single-output interference channel (MISO-IC) with interference decoding capability (IDC), so that the interference signal can be decoded and subtracted from the received signal. On the MISO-IC with single user decoding, transmit beamforming vectors are classically designed to reach a compromise between mitigating the generated interference (zero forcing of the interference) or maximizing the energy at the desired user. The particularly intriguing problem arising in the multi-antenna IC with IDC is that transmitters may now have the incentive to amplify the interference generated at the non-intended receivers, in the hope that Rxs have a better chance of decoding the interference and removing it. This notion completely changes the previous paradigm of balancing between maximizing the desired energy and reducing the generated interference, thus opening up a new dimension for the beamforming design strategy. Our contributions proceed by proving that the optimal rank of the transmit precoders, optimal in the sense of Pareto optimality and therefore sum rate optimality, is rank one. Then, we investigate suitable transmit beamforming strategies for different decoding structures and characterize the Pareto boundary. As an application of this characterization, we obtain a candidate set of the maximum sum rate point} which at least contains the set of sum rate optimal beamforming vectors. We derive the Maximum-Ratio-Transmission (MRT) optimality conditions. Inspired by the MRT optimality conditions, we propose a simple algorithm that achieves maximum sum rate in certain scenarios and suboptimal, in other scenarios comparing to the maximum sum rate.
The Nakamura numbers for computable simple games
Venue: arXiv cs.GT 2011
Year: 2011

The Nakamura number of a simple game plays a critical role in preference aggregation (or multi-criterion ranking): the number of alternatives that the players can always deal with rationally is less than this number. We comprehensively study the restrictions that various properties for a simple game impose on its Nakamura number. We find that a computable game has a finite Nakamura number greater than three only if it is proper, nonstrong, and nonweak, regardless of whether it is monotonic or whether it has a finite carrier. The lack of strongness often results in alternatives that cannot be strictly ranked.
A Novel Multicriteria Group Decision Making Approach With Intuitionistic Fuzzy SIR Method
Venue: arXiv cs.AI 2011
Year: 2011

The superiority and inferiority ranking (SIR) method is a generation of the well-known PROMETHEE method, which can be more efficient to deal with multi-criterion decision making (MCDM) problem. Intuitionistic fuzzy sets (IFSs), as an important extension of fuzzy sets (IFs), include both membership functions and non-membership functions and can be used to, more precisely describe uncertain information. In real world, decision situations are usually under uncertain environment and involve multiple individuals who have their own points of view on handing of decision problems. In order to solve uncertainty group MCDM problem, we propose a novel intuitionistic fuzzy SIR method in this paper. This approach uses intuitionistic fuzzy aggregation operators and SIR ranking methods to handle uncertain information; integrate individual opinions into group opinions; make decisions on multiple-criterion; and finally structure a specific decision map. The proposed approach is illustrated in a simulation of group decision making problem related to supply chain management.
Dynamic OFDMA Resource Allocation for QoS Guarantee and System Optimization of Best Effort and Non Real-time Traffic
Venue: arXiv cs.NI 2011
Year: 2011

To achieve the requirement of high data rate, low latency, user fairness for next generation wireless networks, proper designing of cross-layer optimized dynamic resource allocation algorithm is prerequisite. In this paper, we propose a dynamic resource allocation scheme in Orthogonal Frequency Division Multiple Access (OFDMA) systems to optimize the non real-time (NRT) traffic, which requires allocation of minimum quantum of data within a predefined time that does not incur packet loss. Most existing and proposed works on resource allocation schemes focused on traffic consisting of delay constraint real-time (RT) or delay-tolerant (NRT, Best-Effort (BE)) applications in a single scheme. In this work, we investigate the resource allocation problem in heterogeneous multiuser OFDMA system with the objective of optimizing the aggregate data delivery of NRT and BE traffic to maximize the overall system performance, by exploiting the inherent time-diversity gain in mobile wireless environment for delay-tolerant applications. Simulation results show that the proposed algorithm greatly enhances the system capacity, when compared to traditional proportional fair resource allocation algorithm.
The traveling salesman problem on cubic and subcubic graphs
Venue: arXiv cs.DS 2011
Year: 2011

We study the Travelling Salesman Problem (TSP) on the metric completion of cubic and subcubic graphs, which is known to be NP-hard. The problem is of interest because of its relation to the famous 4/3 conjecture for metric TSP, which says that the integrality gap, i.e., the worst case ratio between the optimal values of the TSP and its linear programming relaxation (the subtour elimination relaxation), is 4/3. We present the first algorithm for cubic graphs with approximation ratio 4/3. The proof uses polyhedral techniques in a surprising way, which is of independent interest. In fact we prove constructively that for any cubic graph on $n$ vertices a tour of length 4n/3-2 exists, which also implies the 4/3 conjecture, as an upper bound, for this class of graph-TSP. Recently, Mömke and Svensson presented a randomized algorithm that gives a 1.461-approximation for graph-TSP on general graphs and as a side result a 4/3-approximation algorithm for this problem on subcubic graphs, also settling the 4/3 conjecture for this class of graph-TSP. We will present a way to derandomize their algorithm which leads to a smaller running time than the obvious derandomization. All of the latter also works for multi-graphs.
The dimension of ergodic random sequences
Venue: arXiv cs.IT 2011
Year: 2011

Let μbe a computable ergodic shift-invariant measure over the Cantor space. Providing a constructive proof of Shannon-McMillan-Breiman theorem, V'yugin proved that if a sequence x is Martin-Löf random w.r.t. μthen the strong effective dimension Dim(x) of x equals the entropy of μ. Whether its effective dimension dim(x) also equals the entropy was left as an problem question. In this paper we settle this problem, providing a positive answer. A key step in the proof consists in extending recent results on Birkhoff's ergodic theorem for Martin-Löf random sequences.
A Stochastic Broadcast Pi-Calculus
Venue: arXiv cs.PF 2011
Year: 2011

In this paper we propose a stochastic broadcast PI-calculus which can be used to model server-client based systems where synchronization is always governed by only one participant. Therefore, there is no need to determine the joint synchronization rates. We also take immediate transitions into account which is useful to model behaviors with no impact on the temporal properties of a system. Since immediate transitions may introduce non-determinism, we will show how these non-determinism can be resolved, and as result a valid CTMC will be obtained finally. Also some practical examples are given to show the application of this calculus.
Lift-and-Project Integrality Gaps for the Traveling Salesperson Problem
Venue: arXiv cs.DS 2011
Year: 2011

We study the lift-and-project procedures of Lov{á}sz-Schrijver and Sherali-Adams applied to the standard linear programming relaxation of the traveling salesperson problem with triangle inequality. For the asymmetric TSP tour problem, Charikar, Goemans, and Karloff (FOCS 2004) proved that the integrality gap of the standard relaxation is at least 2. We prove that after one round of the Lov{á}sz-Schrijver or Sherali-Adams procedures, the integrality gap of the asymmetric TSP tour problem is at least 3/2, with a small caveat on which version of the standard relaxation is used. For the symmetric TSP tour problem, the integrality gap of the standard relaxation is known to be at least 4/3, and Cheung (SIOPT 2005) proved that it remains at least 4/3 after $o(n)$ rounds of the Lov{á}sz-Schrijver procedure, where $n$ is the number of nodes. For the symmetric TSP path problem, the integrality gap of the standard relaxation is known to be at least 3/2, and we prove that it remains at least 3/2 after $o(n)$ rounds of the Lov{á}sz-Schrijver procedure, by a simple reduction to Cheung's result.
Separator Theorems for Minor-Free and Shallow Minor-Free Graphs with Applications
Venue: arXiv cs.DM 2011
Year: 2011

Alon, Seymour, and Thomas generalized Lipton and Tarjan's planar separator theorem and showed that a $K_h$-minor free graph with $n$ vertices has a separator of size at most $h^{3/2}\sqrt n$. They gave an algorithm that, given a graph $G$ with $m$ edges and $n$ vertices and given an integer $h\geq 1$, outputs in $O(\sqrt{hn}m)$ time such a separator or a $K_h$-minor of $G$. Plotkin, Rao, and Smith gave an $O(hm\sqrt{n\log n})$ time algorithm to find a separator of size $O(h\sqrt{n\log n})$. Kawarabayashi and Reed improved the bound on the size of the separator to $h\sqrt n$ and gave an algorithm that finds such a separator in $O(n^{1 + ε})$ time for any constant $ε> 0$, assuming $h$ is constant. This algorithm has an extremely large dependency on $h$ in the running time (some power tower of $h$ whose height is itself a function of $h$), making it impractical even for small $h$. We are interested in a small polynomial time dependency on $h$ and we show how to find an $O(h\sqrt{n\log n})$-size separator or report that $G$ has a $K_h$-minor in $O(\poly(h)n^{5/4 + ε})$ time for any constant $ε> 0$. We also present the first $O(\poly(h)n)$ time algorithm to find a separator of size $O(n^c)$ for a constant $c < 1$. As corollaries of our results, we get improved algorithms for shortest paths and maximum matching. Furthermore, for integers $\ell$ and $h$, we give an $O(m + n^{2 + ε}/\ell)$ time algorithm that either produces a $K_h$-minor of depth $O(\ell\log n)$ or a separator of size at most $O(n/\ell + \ell h^2\log n)$. This improves the shallow minor algorithm of Plotkin, Rao, and Smith when $m = Ω(n^{1 + ε})$. We get a similar running time improvement for an approximation algorithm for the problem of finding a largest $K_h$-minor in a given graph.
Conway games, algebraically and coalgebraically
Venue: arXiv cs.LO 2011
Year: 2011

Using coalgebraic methods, we extend Conway's theory of games to possibly non-terminating, i.e. non-wellfounded games (hypergames). We take the view that a play which goes on forever is a draw, and hence rather than focussing on winning strategies, we focus on non-losing strategies. Hypergames are a fruitful metaphor for non-terminating processes, Conway's sum being similar to shuffling. We develop a theory of hypergames, which extends in a non-trivial way Conway's theory; in particular, we generalize Conway's results on game determinacy and characterization of strategies. Hypergames have a rather interesting theory, already in the case of impartial hypergames, for which we give a compositional semantics, in terms of a generalized Grundy-Sprague function and a system of generalized Nim games. Equivalences and congruences on games and hypergames are discussed. We indicate a number of intriguing directions for future work. We briefly compare hypergames with other notions of games used in computer science.
Efficient Loop Navigation for Symbolic Execution
Venue: arXiv cs.PL 2011
Year: 2011

Symbolic execution is a successful and very popular technique used in software verification and testing. A key limitation of symbolic execution is in dealing with code containing loops. The problem is that even a single loop can generate a huge number of different symbolic execution paths, corresponding to different number of loop iterations and taking various paths through the loop. We introduce a technique which, given a start location above some loops and a target location anywhere below these loops, returns a feasible path between these two locations, if such a path exists. The technique infers a collection of constraint systems from the program and uses them to steer the symbolic execution towards the target. On reaching a loop it iteratively solves the appropriate constraint system to find out which path through this loop to take, or, alternatively, whether to continue below the loop. To construct the constraint systems we express the values of variables modified in a loop as functions of the number of times a given path through the loop was executed. We have built a prototype implementation of our technique and compared it to state-of-the-art symbolic execution tools on simple programs with loops. The results show significant improvements in the running time. We found instances where our algorithm finished in seconds, whereas the other tools did not finish within an hour. Our approach also shows very good results in the case when the target location is not reachable by any feasible path.
Cooperative Jamming for Secure Communications in MIMO Relay Networks
Venue: arXiv cs.IT 2011
Year: 2011

Secure communications can be impeded by eavesdroppers in conventional relay systems. This paper proposes cooperative jamming strategies for two-hop relay networks where the eavesdropper can wiretap the relay channels in both hops. In these approaches, the normally inactive nodes in the relay network can be used as cooperative jamming sources to confuse the eavesdropper. Linear precoding schemes are investigated for two scenarios where single or multiple data streams are transmitted via a decode-and-forward (DF) relay, under the assumption that global channel state information (CSI) is available. For the case of single data stream transmission, we derive closed-form jamming beamformers and the corresponding optimal power allocation. Generalized singular value decomposition (GSVD)-based secure relaying schemes are proposed for the transmission of multiple data streams. The optimal power allocation is found for the GSVD relaying scheme via geometric programming. Based on this result, a GSVD-based cooperative jamming scheme is proposed that shows significant improvement in terms of secrecy rate compared to the approach without jamming. Furthermore, the case involving an eavesdropper with unknown CSI is also investigated in this paper. Simulation results show that the secrecy rate is dramatically increased when inactive nodes in the relay network participate in cooperative jamming.
Indirect Channel Sensing for Cognitive Amplify-and-Forward Relay Networks
Venue: arXiv cs.IT 2011
Year: 2011

In cognitive radio network the primary channel information is beneficial. But it can not be obtained by direct channel estimation in cognitive system as pervious methods. And only one possible way is the primary receiver broadcasts the primary channel information to the cognitive users, but it would require the modification of the primary receiver and additional precious spectrum resource. Cooperative communication is also a promising technique. And this paper introduces an indirect channel sensing method for the primary channel in cognitive amplify-and-forward (AF) relay network. As the signal retransmitted from the primary AF relay node includes channel effects, the cognitive radio can receive retransmitted signal from AF node, and then extract the channel information from them. Afterwards, Least squares channel estimation and sparse channel estimation can be used to address the dense and sparse multipath channels respectively. Numerical experiment demonstrates that the proposed indirect channel sensing method has an acceptable performance.
Distributed SIR-Aware Scheduling in Large-Scale Wireless Networks
Venue: arXiv cs.IT 2011
Year: 2011

Opportunistic scheduling and routing can in principle greatly increase the throughput of decentralized wireless networks, but to be practical they must do so with small amounts of timely side information. In this paper, we propose three techniques for low-overhead distributed opportunistic scheduling (DOS) and precisely determine their affect on the overall network outage probability and transmission capacity (TC). The first is distributed channel-aware scheduling (DCAS), the second is distributed interferer-aware scheduling (DIAS), and the third generalizes and combines those two and is called distributed interferer-channel-aware scheduling (DICAS). One contribution is determining the optimum channel and interference thresholds that a given isolated transmitter should estimate and apply when scheduling their own transmissions. Using this threshold, the precise network-wide gain of each technique is quantified and compared. We conclude by considering interference cancellation at the receivers, and finding how much it improves the outage probability.
The entropy functional, the information path functional's essentials and their connections to Kolmogorov's entropy, complexity and physics
Venue: arXiv cs.IT 2011
Year: 2011

The paper introduces the recent results related to an entropy functional on trajectories of a controlled diffusion process, and the information path functional (IPF), analyzing their connections to the Kolmogorov's entropy, complexity and the Lyapunov's characteristics. Considering the IPF's essentials and specifics, the paper studies the singularities of the IPF extremal equations and the created invariant relations, which both are useful for the solution of important mathematical and applied problems. Keywords: Additive functional; Entropy; Singularities, Natural Border Problem; Invariant
Hamiltonian Paths in Two Classes of Grid Graphs
Venue: arXiv cs.DS 2011
Year: 2011

In this paper, we give the necessary and sufficient conditions for the existence of Hamiltonian paths in $L-$alphabet and $C-$alphabet grid graphs. We also present a linear-time algorithm for finding Hamiltonian paths in these graphs.