OpenRaiser/Intern-Atlas huggingface dataset:
Opacity Issues in Games with Imperfect Information
Venue: arXiv cs.GT 2011
Year: 2011

We study in depth the class of games with opacity condition, which are two-player games with imperfect information in which one of the players only has imperfect information, and where the winning condition relies on the information he has along the play. Those games are relevant for security aspects of computing systems: a play is opaque whenever the player who has imperfect information never "knows" for sure that the current position is one of the distinguished "secret" positions. We study the problems of deciding the existence of a winning strategy for each player, and we call them the opacity-violate problem and the opacity-guarantee problem. Focusing on the player with perfect information is new in the field of games with imperfect-information because when considering classical winning conditions it amounts to solving the underlying perfect-information game. We establish the EXPTIME-completeness of both above-mentioned problems, showing that our winning condition brings a gap of complexity for the player with perfect information, and we exhibit the relevant opacity-verify problem, which noticeably generalizes approaches considered in the literature for opacity analysis in discrete-event systems. In the case of blindfold games, this problem relates to the two initial ones, yielding the determinacy of blindfold games with opacity condition and the PSPACE-completeness of the three problems.
Connectivity Games over Dynamic Networks
Venue: arXiv cs.GT 2011
Year: 2011

A game-theoretic model for the study of dynamic networks is analyzed. The model is motivated by communication networks that are subject to failure of nodes and where the restoration needs resources. The corresponding two-player game is played between "Destructor" (who can delete nodes) and "Constructor" (who can restore or even create nodes under certain conditions). We also include the feature of information flow by allowing Constructor to change labels of adjacent nodes. As objective for Constructor the network property to be connected is considered, either as a safety condition or as a reachability condition (in the latter case starting from a non-connected network). We show under which conditions the solvability of the corresponding games for Constructor is decidable, and in this case obtain upper and lower complexity bounds, as well as algorithms derived from winning strategies. Due to the asymmetry between the players, safety and reachability objectives are not dual to each other and are treated separately.
An Optimal Decision Procedure for MPNL over the Integers
Venue: arXiv cs.LO 2011
Year: 2011

Interval temporal logics provide a natural framework for qualitative and quantitative temporal reason- ing over interval structures, where the truth of formulae is defined over intervals rather than points. In this paper, we study the complexity of the satisfiability problem for Metric Propositional Neigh- borhood Logic (MPNL). MPNL features two modalities to access intervals "to the left" and "to the right" of the current one, respectively, plus an infinite set of length constraints. MPNL, interpreted over the naturals, has been recently shown to be decidable by a doubly exponential procedure. We improve such a result by proving that MPNL is actually EXPSPACE-complete (even when length constraints are encoded in binary), when interpreted over finite structures, the naturals, and the in- tegers, by developing an EXPSPACE decision procedure for MPNL over the integers, which can be easily tailored to finite linear orders and the naturals (EXPSPACE-hardness was already known).
On P-transitive graphs and applications
Venue: arXiv cs.LO 2011
Year: 2011

We introduce a new class of graphs which we call P-transitive graphs, lying between transitive and 3-transitive graphs. First we show that the analogue of de Jongh-Sambin Theorem is false for wellfounded P-transitive graphs; then we show that the mu-calculus fixpoint hierarchy is infinite for P-transitive graphs. Both results contrast with the case of transitive graphs. We give also an undecidability result for an enriched mu-calculus on P-transitive graphs. Finally, we consider a polynomial time reduction from the model checking problem on arbitrary graphs to the model checking problem on P-transitive graphs. All these results carry over to 3-transitive graphs.
Deciding Reachability for 3-Dimensional Multi-Linear Systems
Venue: arXiv cs.LO 2011
Year: 2011

This paper deals with the problem of point-to-point reachability in multi-linear systems. These systems consist of a partition of the Euclidean space into a finite number of regions and a constant derivative assigned to each region in the partition, which governs the dynamical behavior of the system within it. The reachability problem for multi-linear systems has been proven to be decidable for the two-dimensional case and undecidable for the dimension three and higher. Multi-linear systems however exhibit certain properties that make them very suitable for topological analysis. We prove that reachability can be decided exactly in the 3-dimensional case when systems satisfy certain conditions. We show with experiments that our approach can be orders of magnitude more efficient than simulation.
Exploring Network Economics
Venue: arXiv cs.NI 2011
Year: 2011

In this paper, we explore what \emph{network economics} is all about, focusing on the interesting topics brought about by the Internet. Our intent is make this a brief survey, useful as an outline for a course on this topic, with an extended list of references. We try to make it as intuitive and readable as possible. We also deliberately try to be critical at times, and hope our interpretation of the topic will lead to interests for further discussions by those doing research in the same field.
Probabilistic Abstractions with Arbitrary Domains
Venue: arXiv cs.LO 2011
Year: 2011

Recent work by Hermanns et al. and Kattenbelt et al. has extended counterexample-guided abstraction refinement (CEGAR) to probabilistic programs. These approaches are limited to predicate abstraction. We present a novel technique, based on the abstract reachability tree recently introduced by Gulavani et al., that can use arbitrary abstract domains and widening operators (in the sense of abstract interpretation). We show how suitable widening operators can deduce loop invariants diffcult to find for predicate abstraction, and propose refinement techniques.
Fixed-delay Events in Generalized Semi-Markov Processes Revisited
Venue: arXiv cs.SY 2011
Year: 2011

We study long run average behavior of generalized semi-Markov processes with both fixed-delay events as well as variable-delay events. We show that allowing two fixed-delay events and one variable-delay event may cause an unstable behavior of a GSMP. In particular, we show that a frequency of a given state may not be defined for almost all runs (or more generally, an invariant measure may not exist). We use this observation to disprove several results from literature. Next we study GSMP with at most one fixed-delay event combined with an arbitrary number of variable-delay events. We prove that such a GSMP always possesses an invariant measure which means that the frequencies of states are always well defined and we provide algorithms for approximation of these frequencies. Additionally, we show that the positive results remain valid even if we allow an arbitrary number of reasonably restricted fixed-delay events.
Poplar: A Java Extension for Evolvable Component Integration
Venue: arXiv cs.PL 2011
Year: 2011

The Java programming language contains many features that aid component-based software development (CBSD), such as interfaces, visibility levels, and strong support for encapsulation. However, component evolution often causes so-called breaking changes, largely because of the rigidity of component interconnections in the form of explicit method calls and field accesses. We present a Java extension, Poplar, which we are currently developing. In Poplar, inter-component dependencies are expressed using declarative queries; concrete linking code, generated using a planning algorithm, replaces these at compile time. Poplar includes a minimal specification language based on typestate-like protocols and labels, and a lightweight effect system, which ensures the absence of unwanted interference between hand-written code and generated code. We give several examples of fully automatic component integration using Poplar, and demonstrate its potential to simplify object-oriented software development greatly through evolvable and statically checkable integration links.
Scheduling links for heavy traffic on interfering routes in wireless mesh networks
Venue: arXiv cs.NI 2011
Year: 2011

We consider wireless mesh networks and the problem of scheduling the links of a given set of routes under the assumption of a heavy-traffic pattern. We assume some TDMA protocol provides a background of synchronized time slots and seek to schedule the routes' links to maximize the number of packets that get delivered to their destinations per time slot. Our approach is to construct an undirected graph G and to heuristically obtain node multicolorings for G that can be turned into efficient link schedules. In G each node represents a link to be scheduled and the edges are set up to represent every possible interference for any given set of interference assumptions. We present two multicoloring-based heuristics and study their performance through extensive simulations. One of the two heuristics is based on relaxing the notion of a node multicoloring by dynamically exploiting the availability of communication opportunities that would otherwise be wasted. We have found that, as a consequence, its performance is significantly superior to the other's.
Max-Margin Stacking and Sparse Regularization for Linear Classifier Combination and Selection
Venue: arXiv cs.LG 2011
Year: 2011

The main principle of stacked generalization (or Stacking) is using a second-level generalizer to combine the outputs of base classifiers in an ensemble. In this paper, we investigate different combination types under the stacking framework; namely weighted sum (WS), class-dependent weighted sum (CWS) and linear stacked generalization (LSG). For learning the weights, we propose using regularized empirical risk minimization with the hinge loss. In addition, we propose using group sparsity for regularization to facilitate classifier selection. We performed experiments using two different ensemble setups with differing diversities on 8 real-world datasets. Results show the power of regularized learning with the hinge loss function. Using sparse regularization, we are able to reduce the number of selected classifiers of the diverse ensemble without sacrificing accuracy. With the non-diverse ensembles, we even gain accuracy on average by using sparse regularization.
A Characterization of Entropy in Terms of Information Loss
Venue: arXiv cs.IT 2011
Year: 2011

There are numerous characterizations of Shannon entropy and Tsallis entropy as measures of information obeying certain properties. Using work by Faddeev and Furuichi, we derive a very simple characterization. Instead of focusing on the entropy of a probability measure on a finite set, this characterization focuses on the `information loss', or change in entropy, associated with a measure-preserving function. Information loss is a special case of conditional entropy: namely, it is the entropy of a random variable conditioned on some function of that variable. We show that Shannon entropy gives the only concept of information loss that is functorial, convex-linear and continuous. This characterization naturally generalizes to Tsallis entropy as well.
Extensions of Simple Conceptual Graphs: the Complexity of Rules and Constraints
Venue: arXiv cs.AI 2011
Year: 2011

Simple conceptual graphs are considered as the kernel of most knowledge representation formalisms built upon Sowa's model. Reasoning in this model can be expressed by a graph homomorphism called projection, whose semantics is usually given in terms of positive, conjunctive, existential FOL. We present here a family of extensions of this model, based on rules and constraints, keeping graph homomorphism as the basic operation. We focus on the formal definitions of the different models obtained, including their operational semantics and relationships with FOL, and we analyze the decidability and complexity of the associated problems (consistency and deduction). As soon as rules are involved in reasonings, these problems are not decidable, but we exhibit a condition under which they fall in the polynomial hierarchy. These results extend and complete the ones already published by the authors. Moreover we systematically study the complexity of some particular cases obtained by restricting the form of constraints and/or rules.
Improving the Efficiency of Inductive Logic Programming Through the Use of Query Packs
Venue: arXiv cs.AI 2011
Year: 2011

Inductive logic programming, or relational learning, is a powerful paradigm for machine learning or data mining. However, in order for ILP to become practically useful, the efficiency of ILP systems must improve substantially. To this end, the notion of a query pack is introduced: it structures sets of similar queries. Furthermore, a mechanism is described for executing such query packs. A complexity analysis shows that considerable efficiency improvements can be achieved through the use of this query pack execution mechanism. This claim is supported by empirical results obtained by incorporating support for query pack execution in two existing learning systems.
Automatically Training a Problematic Dialogue Predictor for a Spoken Dialogue System
Venue: arXiv cs.AI 2011
Year: 2011

Spoken dialogue systems promise efficient and natural access to a large variety of information sources and services from any phone. However, current spoken dialogue systems are deficient in their strategies for preventing, identifying and repairing problems that arise in the conversation. This paper reports results on automatically training a Problematic Dialogue Predictor to predict problematic human-computer dialogues using a corpus of 4692 dialogues collected with the 'How May I Help You' (SM) spoken dialogue system. The Problematic Dialogue Predictor can be immediately applied to the system's decision of whether to transfer the call to a human customer care agent, or be used as a cue to the system's dialogue manager to modify its behavior to repair problems, and even perhaps, to prevent them. We show that a Problematic Dialogue Predictor using automatically-obtainable features from the first two exchanges in the dialogue can predict problematic dialogues 13.2% more accurately than the baseline.
New Efficient Error-Free Multi-Valued Consensus with Byzantine Failures
Venue: arXiv cs.DC 2011
Year: 2011

In this report, we investigate the multi-valued Byzantine consensus problem. We introduce two algorithms: the first one achieves traditional validity requirement for consensus, and the second one achieves a stronger "q-validity" requirement. Both algorithms are more efficient than the ones introduces in our recent PODC 2011 paper titled "Error-Free Multi-Valued Consensus with Byzantine Failures".
A Comparative Study Between a Micromechanical Cantilever Resonator and MEMS-based Passives for Band-pass Filtering Application
Venue: arXiv cs.OH 2011
Year: 2011

Over the past few years, significant growth has been observed in using MEMS based passive components in the RF microelectronics domain, especially in transceiver components. This is due to some excellent properties of the MEMS devices like low loss, excellent isolation etc. in the microwave frequency domain where the on-chip passives normally tend to become leakier and degrades the transceiver performance. This paper presents a comparative analysis between MEMS-resonator based and MEMS-passives based band-pass filter configurations for RF applications, along with their design, simulation, fabrication and characterization. The filters were designed to have a center frequency of 455 kHz, meant for use as the intermediate frequency (IF) filter in superheterodyne receivers. The filter structures have been fabricated in PolyMUMPs process, a three-polysilicon layer surface micromachining process.
Operating LDPC Codes with Zero Shaping Gap
Venue: arXiv cs.IT 2011
Year: 2011

Unequal transition probabilities between input and output symbols, input power constraints, or input symbols of unequal durations can lead to non-uniform capacity achieving input distributions for communication channels. Using uniform input distributions reduces the achievable rate, which is called the shaping gap. Gallager's idea for reliable communication with zero shaping gap is to do encoding, matching, and jointly decoding and dematching. In this work, a scheme is proposed that consists in matching, encoding, decoding, and dematching. Only matching is channel specific whereas coding is not. Thus off-the-shelf LDPC codes can be applied. Analytical formulas for shaping and coding gap of the proposed scheme are derived and it is shown that the shaping gap can be made zero. Numerical results show that the proposed scheme allows to operate off-the-shelf LDPC codes with zero shaping gap and a coding gap that is unchanged compared to uniform transmission.
Multi-User Privacy: The Gray-Wyner System and Generalized Common Information
Venue: arXiv cs.IT 2011
Year: 2011

The problem of preserving privacy when a multivariate source is required to be revealed partially to multiple users is modeled as a Gray-Wyner source coding problem with K correlated sources at the encoder and K decoders in which the kth decoder, k = 1, 2, ...,K, losslessly reconstructs the kth source via a common link and a private link. The privacy requirement of keeping each decoder oblivious of all sources other than the one intended for it is introduced via an equivocation constraint at each decoder such that the total equivocation summed over all decoders is E. The set of achievable rates-equivocation tuples is completely characterized. Using this characterization, two different definitions of common information are presented and are shown to be equivalent.
Oblivious Collaboration
Venue: arXiv cs.DC 2011
Year: 2011

Communication is a crucial ingredient in every kind of collaborative work. But what is the least possible amount of communication required for a given task? We formalize this question by introducing a new framework for distributed computation, called {\em oblivious protocols}. We investigate the power of this model by considering two concrete examples, the {\em musical chairs} task $MC(n,m)$ and the well-known {\em Renaming} problem. The $MC(n,m)$ game is played by $n$ players (processors) with $m$ chairs. Players can {\em occupy} chairs, and the game terminates as soon as each player occupies a unique chair. Thus we say that player $P$ is {\em in conflict} if some other player $Q$ is occupying the same chair, i.e., termination means there are no conflicts. By known results from distributed computing, if $m \le 2n-2$, no strategy of the players can guarantee termination. However, there is a protocol with $m = 2n-1$ chairs that always terminates. Here we consider an oblivious protocol where in every time step the only communication is this: an adversarial {\em scheduler} chooses an arbitrary nonempty set of players, and for each of them provides only one bit of information, specifying whether the player is currently in conflict or not. A player notified not to be in conflict halts and never changes its chair, whereas a player notified to be in conflict changes its chair according to its deterministic program. Remarkably, even with this minimal communication termination can be guaranteed with only $m=2n-1$ chairs. Likewise, we obtain an oblivious protocol for the Renaming problem whose name-space is small as that of the optimal nonoblivious distributed protocol. Other aspects suggest themselves, such as the efficiency (program length) of our protocols. We make substantial progress here as well, though many interesting questions remain open.
Using Hopfield to Solve Resource-Leveling Problem
Venue: arXiv cs.NE 2011
Year: 2011

Although the traditional permute matrix coming along with Hopfield is able to describe many common problems, it seems to have limitation in solving more complicated problem with more constrains, like resource leveling which is actually a NP problem. This paper tries to find a better solution for it by using neural network. In order to give the neural network description of resource leveling problem, a new description method called Augmented permute matrix is proposed by expending the ability of the traditional one. An Embedded Hybrid Model combining Hopfield model and SA are put forward to improve the optimization in essence in which Hopfield servers as State Generator for the SA. The experiment results show that Augmented permute matrix is able to completely and appropriately describe the application. The energy function and hybrid model given in this study are also highly efficient in solving resource leveling problem.
MIS on the fly
Venue: arXiv cs.DC 2011
Year: 2011

Humans are very good at optimizing solutions for specific problems. Biological processes, on the other hand, have evolved to handle multiple constrained distributed environments and so they are robust and adaptable. Inspired by observations made in a biological system we have recently presented a simple new randomized distributed MIS algorithm \cite{ZScience}. Here we extend these results by removing a number of strong assumptions that we made, making the algorithms more practical. Specifically we present an $O(\log^2 n)$ rounds synchronous randomized MIS algorithm which uses only 1 bit unary messages (a beeping signal with collision detection), allows for asynchronous wake up, does not assume any knowledge of the network topology, and assumes only a loose bound on the network size. We also present an extension with no collision detection in which the round complexity increases to $(\log^3 n)$. Finally, we show that our algorithm is optimal under some restriction, by presenting a tight lower bound of $Ω(\log^2 n)$ on the number of rounds required to construct a MIS for a restricted model.
Comparing Haar-Hilbert and Log-Gabor Based Iris Encoders on Bath Iris Image Database
Venue: arXiv cs.CV 2011
Year: 2011

This papers introduces a new family of iris encoders which use 2-dimensional Haar Wavelet Transform for noise attenuation, and Hilbert Transform to encode the iris texture. In order to prove the usefulness of the newly proposed iris encoding approach, the recognition results obtained by using these new encoders are compared to those obtained using the classical Log- Gabor iris encoder. Twelve tests involving single/multienrollment and conducted on Bath Iris Image Database are presented here. One of these tests achieves an Equal Error Rate comparable to the lowest value reported so far for this database. New Matlab tools for iris image processing are also released together with this paper: a second version of the Circular Fuzzy Iris Segmentator (CFIS2), a fast Log-Gabor encoder and two Haar-Hilbert based encoders.
Some remarks on cops and drunk robbers
Venue: arXiv cs.DM 2011
Year: 2011

The cops and robbers game has been extensively studied under the assumption of optimal play by both the cops and the robbers. In this paper we study the problem in which cops are chasing a drunk robber (that is, a robber who performs a random walk) on a graph. Our main goal is to characterize the "cost of drunkenness." Specifically, we study the ratio of expected capture times for the optimal version and the drunk robber one. We also examine the algorithmic side of the problem; that is, how to compute near-optimal search schedules for the cops. Finally, we present a preliminary investigation of the invisible robber game and point out differences between this game and graph search.