OpenRaiser/Intern-Atlas huggingface dataset:
Degrees of Lookahead in Regular Infinite Games
Venue: arXiv cs.FL 2012
Year: 2012

We study variants of regular infinite games where the strict alternation of moves between the two players is subject to modifications. The second player may postpone a move for a finite number of steps, or, in other words, exploit in his strategy some lookahead on the moves of the opponent. This captures situations in distributed systems, e.g. when buffers are present in communication or when signal transmission between components is deferred. We distinguish strategies with different degrees of lookahead, among them being the continuous and the bounded lookahead strategies. In the first case the lookahead is of finite possibly unbounded size, whereas in the second case it is of bounded size. We show that for regular infinite games the solvability by continuous strategies is decidable, and that a continuous strategy can always be reduced to one of bounded lookahead. Moreover, this lookahead is at most doubly exponential in the size of a given parity automaton recognizing the winning condition. We also show that the result fails for non-regular gamesxwhere the winning condition is given by a context-free omega-language.
Exponential synchronization rate of Kuramoto oscillators in the presence of a pacemaker
Venue: arXiv cs.SY 2012
Year: 2012

The exponential synchronization rate is addressed for Kuramoto oscillators in the presence of a pacemaker. When natural frequencies are identical, we prove that synchronization can be ensured even when the phases are not constrained in an open half-circle, which improves the existing results in the literature. We derive a lower bound on the exponential synchronization rate, which is proven to be an increasing function of pacemaker strength, but may be an increasing or decreasing function of local coupling strength. A similar conclusion is obtained for phase locking when the natural frequencies are non-identical. An approach to trapping phase differences in an arbitrary interval is also given, which ensures synchronization in the sense that synchronization error can be reduced to an arbitrary level.
Increasing sync rate of pulse-coupled oscillators via phase response function design: theory and application to wireless networks
Venue: arXiv cs.SY 2012
Year: 2012

This paper addresses the synchronization rate of weakly connected pulse-coupled oscillators (PCOs). We prove that besides coupling strength, the phase response function is also a determinant of synchronization rate. Inspired by the result, we propose to increase the synchronization rate of PCOs by designing the phase response function. This has important significance in PCO-based clock synchronization of wireless networks. By designing the phase response function, synchronization rate is increased even under a fixed transmission power. Given that energy consumption in synchronization is determined by the product of synchronization time and transformation power, the new strategy reduces energy consumption in clock synchronization. QualNet experiments confirm the theoretical results.
A new scheduling algorithm for server farms load balancing
Venue: arXiv cs.DC 2012
Year: 2012

This paper describes a new scheduling algorithm to distribute jobs in server farm systems. The proposed algorithm overcomes the starvation caused by SRPT (Shortest Remaining Processing Time). This algorithm is used in process scheduling in operating system approach. The algorithm was developed to be used in dispatcher scheduling. This algorithm is non-preemptive discipline, similar to SRPT, in which the priority of each job depends on its estimated run time, and also the amount of time it has spent on waiting. Tasks in the servers are served in order of priority to optimize the system response time. The experiments show that the mean round around time is reduced in the server farm system.
Characterizing Successful Formulas: the Multi-agent Case
Venue: arXiv cs.MA 2012
Year: 2012

Characterization of successful formulas in Public Announcement Logic (PAL) is a well known open problem in Dynamic Epistemic Logic. Recently, Holliday and ICard have given a complete characterization for the single agent case. However, the problem for the multi-agent case is open. This paper gives a partial solution to the problem, characterizing the subclass of the language consisting of unary operators, and discusses methods to give a complete solution.
Trivalent Graph isomorphism in polynomial time
Venue: arXiv cs.DM 2012
Year: 2012

It's important to design polynomial time algorithms to test if two graphs are isomorphic at least for some special classes of graphs. An approach to this was presented by Eugene M. Luks(1981) in the work \textit{Isomorphism of Graphs of Bounded Valence Can Be Tested in Polynomial Time}. Unfortunately, it was a theoretical algorithm and was very difficult to put into practice. On the other hand, there is no known implementation of the algorithm, although Galil, Hoffman and Luks(1983) shows an improvement of this algorithm running in $O(n^3 \log n)$. The two main goals of this master thesis are to explain more carefully the algorithm of Luks(1981), including a detailed study of the complexity and, then to provide an efficient implementation in SAGE system. It is divided into four chapters plus an appendix.
A New Algorithm for Data Compression Optimization
Venue: arXiv cs.DS 2012
Year: 2012

People tend to store a lot of files inside theirs storage. When the storage nears it limit, they then try to reduce those files size to minimum by using data compression software. In this paper we propose a new algorithm for data compression, called j-bit encoding (JBE). This algorithm will manipulates each bit of data inside file to minimize the size without losing any data after decoding which is classified to lossless compression. This basic algorithm is intended to be combining with other data compression algorithms to optimize the compression ratio. The performance of this algorithm is measured by comparing combination of different data compression algorithms.
Speed Tracking of a Linear Induction Motor - Enumerative Nonlinear Model Predictive Control
Venue: arXiv cs.SY 2012
Year: 2012

Direct torque control is considered as one of the most efficient techniques for speed and/or position tracking control of induction motor drives. However, this control scheme has several drawbacks: the switching frequency may exceed the maximum allowable switching frequency of the inverters, and the ripples in current and torque, especially at low speed tracking, may be too large. In this paper we propose a new approach that overcomes these problems. The suggested controller is a model predictive controller which directly controls the inverter switches. It is easy to implement in real time and it outperforms all previous approaches. Simulation results show that the new approach has as good tracking properties as any other scheme, and that it reduces the average inverter switching frequency about 95% as compared to classical direct torque control.
Wavelet Based Normal and Abnormal Heart Sound Identification using Spectrogram Analysis
Venue: arXiv cs.CV 2012
Year: 2012

The present work proposes a computer-aided normal and abnormal heart sound identification based on Discrete Wavelet Transform (DWT), it being useful for tele-diagnosis of heart diseases. Due to the presence of Cumulative Frequency components in the spectrogram, DWT is applied on the spectro-gram up to n level to extract the features from the individual approximation components. One dimensional feature vector is obtained by evaluating the Row Mean of the approximation components of these spectrograms. For this present approach, the set of spectrograms has been considered as the database, rather than raw sound samples. Minimum Euclidean distance is computed between feature vector of the test sample and the feature vectors of the stored samples to identify the heart sound. By applying this algorithm, almost 82% of accuracy was achieved.
Cross-Layer Design for Green Power Control
Venue: arXiv cs.NI 2012
Year: 2012

In this work, we propose a new energy efficiency metric which allows one to optimize the performance of a wireless system through a novel power control mechanism. The proposed metric possesses two important features. First, it considers the whole power of the terminal and not just the radiated power. Second, it can account for the limited buffer memory of transmitters which store arriving packets as a queue and transmit them with a success rate that is determined by the transmit power and channel conditions. Remarkably, this metric is shown to have attractive properties such as quasi-concavity with respect to the transmit power and a unique maximum, allowing to derive an optimal power control scheme. Based on analytical and numerical results, the influence of the packet arrival rate, the size of the queue, and the constraints in terms of quality of service are studied. Simulations show that the proposed cross-layer approach of power control may lead to significant gains in terms of transmit power compared to a physical layer approach of green communications.
Video Chat with Multiple Cameras
Venue: arXiv cs.MM 2012
Year: 2012

The dominant paradigm for video chat employs a single camera at each end of the conversation, but some conversations can be greatly enhanced by using multiple cameras at one or both ends. This paper provides the first rigorous investigation of multi-camera video chat, concentrating especially on the ability of users to switch between views at either end of the conversation. A user study of 23 individuals analyzes the advantages and disadvantages of permitting a user to switch between views at a remote location. Benchmark experiments employing up to four webcams simultaneously demonstrate that multi-camera video chat is feasible on consumer hardware. The paper also presents the design of MultiCam, a software package permitting multi-camera video chat. Some important trade-offs in the design of MultiCam are discussed, and typical usage scenarios are analyzed.
Bisimulation of Labeled State-to-Function Transition Systems of Stochastic Process Languages
Venue: arXiv cs.LO 2012
Year: 2012

Labeled state-to-function transition systems, FuTS for short, admit multiple transition schemes from states to functions of finite support over general semirings. As such they constitute a convenient modeling instrument to deal with stochastic process languages. In this paper, the notion of bisimulation induced by a FuTS is proposed and a correspondence result is proven stating that FuTS-bisimulation coincides with the behavioral equivalence of the associated functor. As generic examples, the concrete existing equivalences for the core of the process algebras ACP, PEPA and IMC are related to the bisimulation of specific FuTS, providing via the correspondence result coalgebraic justification of the equivalences of these calculi.
Category Theory and Model-Driven Engineering: From Formal Semantics to Design Patterns and Beyond
Venue: arXiv cs.SE 2012
Year: 2012

There is a hidden intrigue in the title. CT is one of the most abstract mathematical disciplines, sometimes nicknamed "abstract nonsense". MDE is a recent trend in software development, industrially supported by standards, tools, and the status of a new "silver bullet". Surprisingly, categorical patterns turn out to be directly applicable to mathematical modeling of structures appearing in everyday MDE practice. Model merging, transformation, synchronization, and other important model management scenarios can be seen as executions of categorical specifications. Moreover, the paper aims to elucidate a claim that relationships between CT and MDE are more complex and richer than is normally assumed for "applied mathematics". CT provides a toolbox of design patterns and structural principles of real practical value for MDE. We will present examples of how an elementary categorical arrangement of a model management scenario reveals deficiencies in the architecture of modern tools automating the scenario.
Decentralized Stochastic Control with Partial History Sharing: A Common Information Approach
Venue: arXiv cs.SY 2012
Year: 2012

A general model of decentralized stochastic control called partial history sharing information structure is presented. In this model, at each step the controllers share part of their observation and control history with each other. This general model subsumes several existing models of information sharing as special cases. Based on the information commonly known to all the controllers, the decentralized problem is reformulated as an equivalent centralized problem from the perspective of a coordinator. The coordinator knows the common information and select prescriptions that map each controller's local information to its control actions. The optimal control problem at the coordinator is shown to be a partially observable Markov decision process (POMDP) which is solved using techniques from Markov decision theory. This approach provides (a) structural results for optimal strategies, and (b) a dynamic program for obtaining optimal strategies for all controllers in the original decentralized problem. Thus, this approach unifies the various ad-hoc approaches taken in the literature. In addition, the structural results on optimal control strategies obtained by the proposed approach cannot be obtained by the existing generic approach (the person-by-person approach) for obtaining structural results in decentralized problems; and the dynamic program obtained by the proposed approach is simpler than that obtained by the existing generic approach (the designer's approach) for obtaining dynamic programs in decentralized problems.
Semi-metric networks for recommender systems
Venue: arXiv cs.IR 2012
Year: 2012

Weighted graphs obtained from co-occurrence in user-item relations lead to non-metric topologies. We use this semi-metric behavior to issue recommendations, and discuss its relationship to transitive closure on fuzzy graphs. Finally, we test the performance of this method against other item- and user-based recommender systems on the Movielens benchmark. We show that including highly semi-metric edges in our recommendation algorithms leads to better recommendations.
Design of Spectrum Sensing Policy for Multi-user Multi-band Cognitive Radio Network
Venue: arXiv cs.LG 2012
Year: 2012

Finding an optimal sensing policy for a particular access policy and sensing scheme is a laborious combinatorial problem that requires the system model parameters to be known. In practise the parameters or the model itself may not be completely known making reinforcement learning methods appealing. In this paper a non-parametric reinforcement learning-based method is developed for sensing and accessing multi-band radio spectrum in multi-user cognitive radio networks. A suboptimal sensing policy search algorithm is proposed for a particular multi-user multi-band access policy and the randomized Chair-Varshney rule. The randomized Chair-Varshney rule is used to reduce the probability of false alarms under a constraint on the probability of detection that protects the primary user. The simulation results show that the proposed method achieves a sum profit (e.g. data rate) close to the optimal sensing policy while achieving the desired probability of detection.
Improved Robust DWT-Watermarking in YCbCr Color Space
Venue: arXiv cs.CR 2012
Year: 2012

Digital watermarking is an effective way to protect copyright. In this paper, a robust watermarking algorithm based on wavelet transformation is proposed which can confirm the copyright without original image. The wavelet transformation technique is effective in image analyzing and processing. Thus the color-image watermark algorithm based on discrete wavelet transformation (DWT) begins to draw an increasing attention. In the proposed approach, the watermark Encrypt by Arnold transform and the host image is converted into the YCbCr color space. Then its Y channel decomposed into wavelet coefficients and the selected approximation coefficients are quantized and then their least significant bit of the quantized coefficients is replaced by the Encrypted watermark using LSB insertion technique. The experimental results show that watermark embedded by this algorithm is of better robustness and extra imperceptibility and robustness against wavelet compression compared to the traditional embedding methods in RGB color space.
On the Incentive to Deviate in Core Selecting Combinatorial Auctions
Venue: arXiv cs.GT 2012
Year: 2012

Recent spectrum auctions in the United Kingdom, and some proposals for future auctions of spectrum in the United States, are based on preliminary price discovery rounds, followed by calculation of final prices for the winning buyers. For example, the prices could be the projection of Vikrey prices onto the core of reported prices. The use of Vikrey prices should lead to more straightforward bidding, but the projection reverses some of the incentive for bidders to report truthfully. Still, we conjecture that the price paid by a winning buyer increases no faster than the bid, as in a first price auction. It would be rather disturbing if the conjecture is false. The conjecture is established for a buyer interacting with disjoint groups of other buyers in a star network setting. It is also shown that for any core-selecting payment rule and any integer w greater than or equal to two, there is a market setting with w winning buyers such that the price paid by some winning buyer increases at least (1-1/w) times as fast as the price bid.
Visualizations in Exploratory Search: A User Study with Stock Market Information
Venue: arXiv cs.HC 2012
Year: 2012

In this paper we present an approach that integrates interactive visualizations in the exploratory search process. In this model visualizations can act as hubs where large amounts of information are made accessible in easy user interfaces. Through interaction techniques this information can be combined with related information on the World Wide Web. We applied the new search concept to the domain of stock market information and conducted a user study. Participants could use this interface without instructions, could complete complex tasks like identifying related information items, link heterogeneous information types and use different interaction techniques to access related information more easily. In this way, users could quickly acquire knowledge in an unfamiliar domain.
On firm specific characteristics of pharmaceutical generics and incentives to permanence under fuzzy conditions
Venue: arXiv cs.AI 2012
Year: 2012

The aim of this paper is to develop a methodology that is useful for analysing from a microeconomic perspective the incentives to entry, permanence and exit in the market for pharmaceutical generics under fuzzy conditions. In an empirical application of our proposed methodology, the potential towards permanence of labs with different characteristics has been estimated. The case we deal with is set in an open market where global players diversify into different national markets of pharmaceutical generics. Risk issues are significantly important in deterring decision makers from expanding in the generic pharmaceutical business. However, not all players are affected in the same way and/or to the same extent. Small, non-diversified generics labs are in the worse position. We have highlighted that the expected NPV and the number of generics in the portfolio of a pharmaceutical lab are important variables, but that it is also important to consider the degree of diversification. Labs with a higher potential for diversification across markets have an advantage over smaller labs. We have described a fuzzy decision support system based on the Mamdani model in order to determine the incentives for a laboratory to remain in the market both when it is stable and when it is growing.
Raw Report on the Model Checking Contest at Petri Nets 2012
Venue: arXiv cs.SE 2012
Year: 2012

This article presents the results of the Model Checking Contest held at Petri Nets 2012 in Hambourg. This contest aimed at a fair and experimental evaluation of the performances of model checking techniques applied to Petri nets. This is the second edition after a successful one in 2011. The participating tools were compared on several examinations (state space generation and evaluation of several types of formulae - structural, reachability, LTL, CTL) run on a set of common models (Place/Transition and Symmetric Petri nets). After a short overview of the contest, this paper provides the raw results from the context, model per model and examination per examination.
Interleaving Command Sequences: a Threat to Secure Smartcard Interoperability
Venue: arXiv cs.CR 2012
Year: 2012

The increasingly widespread use of smartcards for a variety of sensitive applications, including digital signatures, creates the need to ensure and possibly certify the secure interoperability of these devices. Standard certification criteria, in particular the Common Criteria, define security requirements but do not sufficiently address the problem of interoperability. Here we consider the interoperability problem which arises when various applications interact with different smartcards through a middleware. In such a situation it is possible that a smartcard of type S receives commands that were supposed to be executed on a different smartcard of type S'. Such "external commands" can interleave with the commands that were supposed to be executed on S. We experimentally demonstrate this problem with a Common Criteria certified digital signature process on a commercially available smartcard. Importantly, in some of these cases the digital signature processes terminate without generating an error message or warning to the user.
Wavelet Based Image Coding Schemes : A Recent Survey
Venue: arXiv cs.CV 2012
Year: 2012

A variety of new and powerful algorithms have been developed for image compression over the years. Among them the wavelet-based image compression schemes have gained much popularity due to their overlapping nature which reduces the blocking artifacts that are common phenomena in JPEG compression and multiresolution character which leads to superior energy compaction with high quality reconstructed images. This paper provides a detailed survey on some of the popular wavelet coding techniques such as the Embedded Zerotree Wavelet (EZW) coding, Set Partitioning in Hierarchical Tree (SPIHT) coding, the Set Partitioned Embedded Block (SPECK) Coder, and the Embedded Block Coding with Optimized Truncation (EBCOT) algorithm. Other wavelet-based coding techniques like the Wavelet Difference Reduction (WDR) and the Adaptive Scanned Wavelet Difference Reduction (ASWDR) algorithms, the Space Frequency Quantization (SFQ) algorithm, the Embedded Predictive Wavelet Image Coder (EPWIC), Compression with Reversible Embedded Wavelet (CREW), the Stack-Run (SR) coding and the recent Geometric Wavelet (GW) coding are also discussed. Based on the review, recommendations and discussions are presented for algorithm development and implementation.