OpenRaiser/Intern-Atlas huggingface dataset:
Reconstruction of complete interval tournaments
Venue: arXiv cs.DM 2010
Year: 2010

Let $a, b$ and $n$ be nonnegative integers $(b \geq a, \ b > 0, \ n \geq 1)$, $\mathcal{G}_n(a,b)$ be a multigraph on $n$ vertices in which any pair of vertices is connected with at least $a$ and at most $b$ edges and \textbf{v =} $(v_1, v_2, ..., v_n)$ be a vector containing $n$ nonnegative integers. We give a necessary and sufficient condition for the existence of such orientation of the edges of $\mathcal{G}_n(a,b)$, that the resulted out-degree vector equals to \textbf{v}. We describe a reconstruction algorithm. In worst case checking of \textbf{v} requires $Θ(n)$ time and the reconstruction algorithm works in $O(bn^3)$ time. Theorems of H. G. Landau (1953) and J. W. Moon (1963) on the score sequences of tournaments are special cases $b = a = 1$ resp. $b = a \geq 1$ of our result.
System-theoretic approach to image interest point detection
Venue: arXiv cs.CV 2010
Year: 2010

Interest point detection is a common task in various computer vision applications. Although a big variety of detector are developed so far computational efficiency of interest point based image analysis remains to be the problem. Current paper proposes a system-theoretic approach to interest point detection. Starting from the analysis of interdependency between detector and descriptor it is shown that given a descriptor it is possible to introduce to notion of detector redundancy. Furthermore for each detector it is possible to construct its irredundant and equivalent modification. Modified detector possesses lower computational complexity and is preferable. It is also shown that several known approaches to reduce computational complexity of image registration can be generalized in terms of proposed theory.
An Optimal Prefix Replication Strategy for VoD Services
Venue: arXiv cs.MM 2010
Year: 2010

In this paper we propose scalable proxy servers cluster architecture of interconnected proxy servers for high quality and high availability services. We also propose an optimal regional popularity based video prefix replication strategy and a scene change based replica caching algorithm that utilizes the zipf-like video popularity distribution to maximize the availability of videos closer to the client and request-servicing rate thereby reducing the client rejection ratio and the response time for the client. The simulation results of our proposed architecture and algorithm show the greater achievement in maximizing the availability of videos, client request-servicing rate and in reduction of initial start-up latency and client rejection ratio.
A Rank Based Replacement Policy for Multimedia Server Cache Using Zipf-Like Law
Venue: arXiv cs.PF 2010
Year: 2010

The cache replacement algorithm plays an important role in the overall performance of Proxy-Server system. In this paper we have proposed VoD cache memory replacement algorithm for a multimedia server system. We propose a Rank based cache replacement policy to manage the cache space in individual proxy server cache. Proposed replacement strategy incorporates in a simple way the most important characteristics of the video and its accesses such as its size, access frequency, recentness of the last access and the cost incurred while transferring the requested video from the server to the proxy. We compare our algorithm with some popular cache replacement algorithm using simulation. The video objects are ranked based on the access trend by considering the factors such as size, frequency and cost. Many studies have demonstrated that Zipf's-like law can govern many features of the VoD and is used to describe the popularity of the video. In this paper, we have designed a model, which ranks the video on the basis of its popularity using the Zipf-like law. The video with higher ranking is named "hot", while the video with lower ranking is named "cold". The result show that the proposed rank based algorithm improves cache hit ratio, cache byte ratio and average request latencies compared to other algorithms. Our experimental results indicate that Rank based cache replacement algorithm outperforms LRU, LFU and Greedy Dual.
A Distributed k-Secure Sum Protocol for Secure Multi-Party Computations
Venue: arXiv cs.CR 2010
Year: 2010

Secure sum computation of private data inputs is an interesting example of Secure Multiparty Computation (SMC) which has attracted many researchers to devise secure protocols with lower probability of data leakage. In this paper, we provide a novel protocol to compute the sum of individual data inputs with zero probability of data leakage when two neighbor parties collude to know the data of a middle party. We break the data block of each party into number of segments and redistribute the segments among parties before the computation. These entire steps create a scenario in which it becomes impossible for semi honest parties to know the private data of some other party.
Mapping The Best Practices of XP and Project Management: Well defined approach for Project Manager
Venue: arXiv cs.SE 2010
Year: 2010

Software engineering is one of the most recent additions in various disciplines of system engineering. It has emerged as a key obedience of system engineering in a quick succession of time. Various Software Engineering approaches are followed in order to produce comprehensive software solutions of affordable cost with reasonable delivery timeframe with less uncertainty. All these objectives are only satisfied when project's status is properly monitored and controlled; eXtreme Programming (XP) uses the best practices of AGILE methodology and helps in development of small size software very sharply. In this paper, authors proposed that via XP, high quality software with less uncertainty and under estimated cost can be developed due to proper monitoring and controlling of project. Moreover, authors give guidelines that how activities of project management can be embedded into development life cycle of XP to enhance the quality of software products and reduce the uncertainty.
Modeling and Reasoning over Distributed Systems using Aspect-Oriented Graph Grammars
Venue: arXiv cs.LO 2010
Year: 2010

Aspect-orientation is a relatively new paradigm that introduces abstractions to modularize the implementation of system-wide policies. It is based on a composition operation, called aspect weaving, that implicitly modifies a base system by performing related changes within the system modules. Aspect-oriented graph grammars (AOGG) extend the classic graph grammar formalism by defining aspects as sets of rule-based modifications over a base graph grammar. Despite the advantages of aspect-oriented concepts regarding modularity, the implicit nature of the aspect weaving operation may also introduce issues when reasoning about the system behavior. Since in AOGGs aspect weaving is characterized by means of rule-based rewriting, we can overcome these problems by using known analysis techniques from the graph transformation literature to study aspect composition. In this paper, we present a case study of a distributed client-server system with global policies, modeled as an aspect-oriented graph grammar, and discuss how to use the AGG tool to identify potential conflicts in aspect weaving.
A New Approach to Population Sizing for Memetic Algorithms: A Case Study for the Multidimensional Assignment Problem
Venue: arXiv cs.DS 2010
Year: 2010

Memetic Algorithms are known to be a powerful technique in solving hard optimization problems. To design a memetic algorithm one needs to make a host of decisions; selecting a population size is one of the most important among them. Most algorithms in the literature fix the population size to a certain constant value. This reduces the algorithm's quality since the optimal population size varies for different instances, local search procedures and running times. In this paper we propose an adjustable population size. It is calculated as a function of the running time of the whole algorithm and the average running time of the local search for the given instance. Note that in many applications the running time of a heuristic should be limited and therefore we use this limit as a parameter of the algorithm. The average running time of the local search procedure is obtained during the algorithm's run. Some coefficients which are independent with respect to the instance or the local search are to be tuned before the algorithm run; we provide a procedure to find these coefficients. The proposed approach was used to develop a memetic algorithm for the Multidimensional Assignment Problem (MAP or s-AP in the case of s dimensions) which is an extension of the well-known assignment problem. MAP is NP-hard and has a host of applications. We show that using adjustable population size makes the algorithm flexible to perform well for instances of very different sizes and types and for different running times and local searches. This allows us to select the most efficient local search for every instance type. The results of computational experiments for several instance families and sizes prove that the proposed algorithm performs efficiently for a wide range of the running times and clearly outperforms the state-of-the art 3-AP memetic algorithm being given the same time.
The Semantics of Graph Programs
Venue: arXiv cs.LO 2010
Year: 2010

GP (for Graph Programs) is a rule-based, nondeterministic programming language for solving graph problems at a high level of abstraction, freeing programmers from handling low-level data structures. The core of GP consists of four constructs: single-step application of a set of conditional graph-transformation rules, sequential composition, branching and iteration. We present a formal semantics for GP in the style of structural operational semantics. A special feature of our semantics is the use of finitely failing programs to define GP's powerful branching and iteration commands.
Adaptive Beamforming in Interference Networks via Bi-Directional Training
Venue: arXiv cs.IT 2010
Year: 2010

We study distributed algorithms for adjusting beamforming vectors and receiver filters in multiple-input multiple-output (MIMO) interference networks, with the assumption that each user uses a single beam and a linear filter at the receiver. In such a setting there have been several distributed algorithms studied for maximizing the sum-rate or sum-utility assuming perfect channel state information (CSI) at the transmitters and receivers. The focus of this paper is to study adaptive algorithms for time-varying channels, without assuming any CSI at the transmitters or receivers. Specifically, we consider an adaptive version of the recent Max-SINR algorithm for a time-division duplex system. This algorithm uses a period of bi-directional training followed by a block of data transmission. Training in the forward direction is sent using the current beam-formers and used to adapt the receive filters. Training in the reverse direction is sent using the current receive filters as beams and used to adapt the transmit beamformers. The adaptation of both receive filters and beamformers is done using a least-squares objective for the current block. In order to improve the performance when the training data is limited, we also consider using exponentially weighted data from previous blocks. Numerical results are presented that compare the performance of the algorithms in different settings.
Automatic Generation of Proof Tactics for Finite-Valued Logics
Venue: arXiv cs.LO 2010
Year: 2010

A number of flexible tactic-based logical frameworks are nowadays available that can implement a wide range of mathematical theories using a common higher-order metalanguage. Used as proof assistants, one of the advantages of such powerful systems resides in their responsiveness to extensibility of their reasoning capabilities, being designed over rule-based programming languages that allow the user to build her own `programs to construct proofs' - the so-called proof tactics. The present contribution discusses the implementation of an algorithm that generates sound and complete tableau systems for a very inclusive class of sufficiently expressive finite-valued propositional logics, and then illustrates some of the challenges and difficulties related to the algorithmic formation of automated theorem proving tactics for such logics. The procedure on whose implementation we will report is based on a generalized notion of analyticity of proof systems that is intended to guarantee termination of the corresponding automated tactics on what concerns theoremhood in our targeted logics.
Limits of Commutativity on Abstract Data Types
Venue: arXiv cs.DB 2010
Year: 2010

We present some formal properties of (symmetrical) commutativity, the major criterion used in transactional systems, which allow us to fully understand its advantages and disadvantages. The main result is that commutativity is subject to the same limitation as compatibility for arbitrary objects. However, commutativity has also a number of attracting properties, one of which is related to recovery and, to our knowledge, has not been exploited in the literature. Advantages and disadvantages are illustrated on abstract data types of interest. We also show how limits of commutativity have been circumvented, which gives guidelines for doing so (or not!).
La représentation formelle des concepts spatiaux dans la langue
Venue: arXiv cs.CL 2010
Year: 2010

In this chapter, we assume that systematically studying spatial markers semantics in language provides a means to reveal fundamental properties and concepts characterizing conceptual representations of space. We propose a formal system accounting for the properties highlighted by the linguistic analysis, and we use these tools for representing the semantic content of several spatial relations of French. The first part presents a semantic analysis of the expression of space in French aiming at describing the constraints that formal representations have to take into account. In the second part, after presenting the structure of our formal system, we set out its components. A commonsense geometry is sketched out and several functional and pragmatic spatial concepts are formalized. We take a special attention in showing that these concepts are well suited to representing the semantic content of several prepositions of French ('sur' (on), 'dans' (in), 'devant' (in front of), 'au-dessus' (above)), and in illustrating the inferential adequacy of these representations.
Feedback control logic synthesis for non safe Petri nets
Venue: arXiv cs.LO 2010
Year: 2010

This paper addresses the problem of forbidden states of non safe Petri Net (PN) modelling discrete events systems. To prevent the forbidden states, it is possible to use conditions or predicates associated with transitions. Generally, there are many forbidden states, thus many complex conditions are associated with the transitions. A new idea for computing predicates in non safe Petri nets will be presented. Using this method, we can construct a maximally permissive controller if it exists.
Towards increasing diversity for the relaying of LT Fountain Codes in Wireless Sensor Networks
Venue: arXiv cs.NI 2010
Year: 2010

Diversity is a powerful means to increase the transmission performance of wireless communications. For the case of fountain codes relaying, it has been shown previously that introducing diversity is also beneficial since it counteracts transmission losses on the channel. Instead of simply hop-by-hop forwarding information, each sensor node diversifies the information flow using XOR combinations of stored packets. This approach has been shown to be efficient for random linear fountain codes. However, random linear codes exhibit high decoding complexity. In this paper, we propose diversity increased relaying strategies for the more realistic Luby Transform code in order to maintain high transmission performance with low decoding computational complexity in a linear network. Results are provided herein for a linear network assuming uniform imperfect channel states.
wiki.openmath.org - how it works, how you can participate
Venue: arXiv cs.DL 2010
Year: 2010

At http://wiki.openmath.org, the OpenMath 2 and 3 Content Dictionaries are accessible via a semantic wiki interface, powered by the SWiM system. We shortly introduce the inner workings of the system, then describe how to use it, and conclude with first experiences gained from OpenMath society members working with the system and an outlook to further development plans.
Diversity-Multiplexing Tradeoff of Cooperative Communication with Linear Network Coded Relays
Venue: arXiv cs.IT 2010
Year: 2010

Network coding and cooperative communication have received considerable attention from the research community recently in order to mitigate the adverse effects of fading in wireless transmissions and at the same time to achieve high throughput and better spectral efficiency. In this work, we analyze a network coding scheme for a cooperative communication setup with multiple sources and destinations. The proposed protocol achieves the full diversity order at the expense of a slightly reduced multiplexing rate compared to existing schemes in the literature. We show that our scheme outperforms conventional cooperation in terms of the diversity-multiplexing tradeoff.
Stable Nash equilibria of medium access games under symmetric, socially altruistic behavior
Venue: arXiv cs.GT 2010
Year: 2010

We consider the effects of altruistic behavior on random medium access control (slotted ALOHA) for local area communication networks. For an idealized, synchronously iterative, two-player game with asymmetric player demands, we find a Hamiltonian governing the Jacobi dynamics under purely altruistic behavior. Though the positions of the interior Nash equilibrium points do not change in the presence of altruistic behavior, the nature of their local asymptotic stability does. There is a region of partially altruistic behavior for which neither interior Nash equilibrium point is locally asymptotically stable. Also, for a power control game with a single Nash equilibrium, we show how its stability changes as a function of the altruism parameter. Variations of these altruistic game frameworks are discussed considering power (instead of throughput) based costs and linear utility functions.
Learning Recursive Segments for Discourse Parsing
Venue: arXiv cs.CL 2010
Year: 2010

Automatically detecting discourse segments is an important preliminary step towards full discourse parsing. Previous research on discourse segmentation have relied on the assumption that elementary discourse units (EDUs) in a document always form a linear sequence (i.e., they can never be nested). Unfortunately, this assumption turns out to be too strong, for some theories of discourse like SDRT allows for nested discourse units. In this paper, we present a simple approach to discourse segmentation that is able to produce nested EDUs. Our approach builds on standard multi-class classification techniques combined with a simple repairing heuristic that enforces global coherence. Our system was developed and evaluated on the first round of annotations provided by the French Annodis project (an ongoing effort to create a discourse bank for French). Cross-validated on only 47 documents (1,445 EDUs), our system achieves encouraging performance results with an F-score of 73% for finding EDUs.
Preventing Distributed Denial-of-Service Attacks on the IMS Emergency Services Support through Adaptive Firewall Pinholing
Venue: arXiv cs.NI 2010
Year: 2010

Emergency services are vital services that Next Generation Networks (NGNs) have to provide. As the IP Multimedia Subsystem (IMS) is in the heart of NGNs, 3GPP has carried the burden of specifying a standardized IMS-based emergency services framework. Unfortunately, like any other IP-based standards, the IMS-based emergency service framework is prone to Distributed Denial of Service (DDoS) attacks. We propose in this work, a simple but efficient solution that can prevent certain types of such attacks by creating firewall pinholes that regular clients will surely be able to pass in contrast to the attackers clients. Our solution was implemented, tested in an appropriate testbed, and its efficiency was proven.
Securing Internet Protocol (IP) Storage: A Case Study
Venue: arXiv cs.NI 2010
Year: 2010

Storage networking technology has enjoyed strong growth in recent years, but security concerns and threats facing networked data have grown equally fast. Today, there are many potential threats that are targeted at storage networks, including data modification, destruction and theft, DoS attacks, malware, hardware theft and unauthorized access, among others. In order for a Storage Area Network (SAN) to be secure, each of these threats must be individually addressed. In this paper, we present a comparative study by implementing different security methods in IP Storage network.
QoS Based Capacity Enhancement for WCDMA Network with Coding Scheme
Venue: arXiv cs.NI 2010
Year: 2010

The wide-band code division multiple access (WCDMA) based 3G and beyond cellular mobile wireless networks are expected to provide a diverse range of multimedia services to mobile users with guaranteed quality of service (QoS). To serve diverse quality of service requirements of these networks it necessitates new radio resource management strategies for effective utilization of network resources with coding schemes. Call admission control (CAC) is a significant component in wireless networks to guarantee quality of service requirements and also to enhance the network resilience. In this paper capacity enhancement for WCDMA network with convolutional coding scheme is discussed and compared with block code and without coding scheme to achieve a better balance between resource utilization and quality of service provisioning. The model of this network is valid for the real-time (RT) and non-real-time (NRT) services having different data rate. Simulation results demonstrate the effectiveness of the network using convolutional code in terms of capacity enhancement and QoS of the voice and video services.
Relating Nominal and Higher-order Abstract Syntax Specifications
Venue: arXiv cs.LO 2010
Year: 2010

Nominal abstract syntax and higher-order abstract syntax provide a means for describing binding structure which is higher-level than traditional techniques. These approaches have spawned two different communities which have developed along similar lines but with subtle differences that make them difficult to relate. The nominal abstract syntax community has devices like names, freshness, name-abstractions with variable capture, and the new-quantifier, whereas the higher-order abstract syntax community has devices like lambda-binders, lambda-conversion, raising, and the nabla-quantifier. This paper aims to unify these communities and provide a concrete correspondence between their different devices. In particular, we develop a semantics-preserving translation from alpha-Prolog, a nominal abstract syntax based logic programming language, to G-, a higher-order abstract syntax based logic programming language. We also discuss higher-order judgments, a common and powerful tool for specifications with higher-order abstract syntax, and we show how these can be incorporated into G-. This establishes G- as a language with the power of higher-order abstract syntax, the fine-grained variable control of nominal specifications, and the desirable properties of higher-order judgments.