OpenRaiser/Intern-Atlas huggingface dataset:
Communicate only when necessary: Cooperative tasking for multi-agent systems
Venue: arXiv cs.MA 2011
Year: 2011

New advances in large scale distributed systems have amazingly offered complex functionalities through parallelism of simple and rudimentary components. The key issue in cooperative control of multi-agent systems is the synthesis of local control and interaction rules among the agents such that the entire controlled system achieves a desired global behavior. For this purpose, three fundamental problems have to be addressed: (1) task decomposition for top-down design, such that the fulfillment of local tasks guarantees the satisfaction of the global task, by the team; (2) fault-tolerant top-down design, such that the global task remains decomposable and achievable, in spite of some failures, and (3) design of interactions among agents to make an undecomposable task decomposable and achievable in a top-down framework. The first two problems have been addressed in our previous works, by identifying necessary and sufficient conditions for task automaton decomposition, and fault-tolerant task decomposability. This paper deals with the third problem and proposes a procedure to redistribute the events among agents in order to enforce decomposability of an undecomposable task automaton. The decomposability conditions are used to identify the root causes of undecomposability which are found to be due to over-communications that have to be deleted, while respecting the fault-tolerant decomposability conditions; or because of the lack of communications that require new sharing of events, while considering new violations of decomposability conditions. This result provides a sufficient condition to make any undecomposable deterministic task automaton decomposable in order to facilitate cooperative tasking. Illustrative examples are presented to show the concept of task automaton decomposabilization.
A polyhedral approach for the Equitable Coloring Problem
Venue: arXiv cs.DM 2011
Year: 2011

In this work we study the polytope associated with a 0,1-integer programming formulation for the Equitable Coloring Problem. We find several families of valid inequalities and derive sufficient conditions in order to be facet-defining inequalities. We also present computational evidence that shows the efficacy of these inequalities used in a cutting-plane algorithm.
Polyhedral results for the Equitable Coloring Problem
Venue: arXiv cs.DM 2011
Year: 2011

In this work we study the polytope associated with a 0/1 integer programming formulation for the Equitable Coloring Problem. We find several families of valid inequalities and derive sufficient conditions in order to be facet-defining inequalities. We also present computational evidence of the effectiveness of including these inequalities as cuts in a Branch & Cut algorithm.
The Capacity Region of the Linear Shift Deterministic Y-Channel
Venue: arXiv cs.IT 2011
Year: 2011

The linear shift deterministic Y-channel is studied. That is, we have three users and one relay, where each user wishes to broadcast one message to each other user via the relay, resulting in a multi-way relaying setup. The cut-set bounds for this setup are shown to be not sufficient to characterize its capacity region. New upper bounds are derived, which when combined with the cut-set bounds provide an outer bound on the capacity region. It is shown that this outer bound is achievable, and as a result, the capacity region of the linear shift deterministic Y-channel is characterized.
Parameterized Complexity Results for General Factors in Bipartite Graphs with an Application to Constraint Programming
Venue: arXiv cs.DS 2011
Year: 2011

The NP-hard general factor problem asks, given a graph and for each vertex a list of integers, whether the graph has a spanning subgraph where each vertex has a degree that belongs to its assigned list. The problem remains NP-hard even if the given graph is bipartite with partition U+V, and each vertex in U is assigned the list {1}; this subproblem appears in the context of constraint programming as the consistency problem for the extended global cardinality constraint. We show that this subproblem is fixed-parameter tractable when parameterized by the size of the second partite set V. More generally, we show that the general factor problem for bipartite graphs, parameterized by |V|, is fixed-parameter tractable as long as all vertices in U are assigned lists of length 1, but becomes W[1]-hard if vertices in U are assigned lists of length at most 2. We establish fixed-parameter tractability by reducing the problem instance to a bounded number of acyclic instances, each of which can be solved in polynomial time by dynamic programming.
Decompositions of two player games: potential, zero-sum, and stable games
Venue: arXiv cs.GT 2011
Year: 2011

We introduce several methods of decomposition for two player normal form games. Viewing the set of all games as a vector space, we exhibit explicit orthonormal bases for the subspaces of potential games, zero-sum games, and their orthogonal complements which we call anti-potential games and anti-zero-sum games, respectively. Perhaps surprisingly, every anti-potential game comes either from the Rock-Paper-Scissors type games (in the case of symmetric games) or from the Matching Pennies type games (in the case of asymmetric games). Using these decompositions, we prove old (and some new) cycle criteria for potential and zero-sum games (as orthogonality relations between subspaces). We illustrate the usefulness of our decomposition by (a) analyzing the generalized Rock-Paper-Scissors game, (b) completely characterizing the set of all null-stable games, (c) providing a large class of strict stable games, (d) relating the game decomposition to the decomposition of vector fields for the replicator equations, (e) constructing Lyapunov functions for some replicator dynamics, and (f) constructing Zeeman games -games with an interior asymptotically stable Nash equilibrium and a pure strategy ESS.
Pseudo-Ring Testing Schemes and Algorithms of RAM Built-In and Embedded Self-Testing
Venue: arXiv cs.AR 2011
Year: 2011

Scan and ring schemes of the pseudo-ring memory selftesting are investigated. Both schemes are based on emulation of the linear or nonlinear feedback shift register by memory itself. Peculiarities of the pseudo-ring schemes implementation for multi-port and embedded memories, and for register file are described. It is shown that only small additional logic is required and allows microcontrollers at-speed testing. Also, in this article,are given the a posteriori values of some type of memories faults coverage when pseudo-ring testing schemes are applied.
SoC Software Components Diagnosis Technology
Venue: arXiv cs.AR 2011
Year: 2011

A novel approach to evaluation of hardware and software testability, represented in the form of register transfer graph, is proposed. Instances of making of software graph models for their subsequent testing and diagnosis are shown.
Exploratory simulation of an Intelligent Iris Verifier Distributed System
Venue: arXiv cs.CV 2011
Year: 2011

This paper discusses some topics related to the latest trends in the field of evolutionary approaches to iris recognition. It presents the results of an exploratory experimental simulation whose goal was to analyze the possibility of establishing an Interchange Protocol for Digital Identities evolved in different geographic locations interconnected through and into an Intelligent Iris Verifier Distributed System (IIVDS) based on multi-enrollment. Finding a logically consistent model for the Interchange Protocol is the key factor in designing the future large-scale iris biometric networks. Therefore, the logical model of such a protocol is also investigated here. All tests are made on Bath Iris Database and prove that outstanding power of discrimination between the intra- and the inter-class comparisons can be achieved by an IIVDS, even when practicing 52.759.182 inter-class and 10.991.943 intra-class comparisons. Still, the test results confirm that inconsistent enrollment can change the logic of recognition from a fuzzified 2-valent consistent logic of biometric certitudes to a fuzzified 3-valent inconsistent possibilistic logic of biometric beliefs justified through experimentally determined probabilities, or to a fuzzified 8-valent logic which is almost consistent as a biometric theory - this quality being counterbalanced by an absolutely reasonable loss in the user comfort level.
The taming of recurrences in computability logic through cirquent calculus, Part II
Venue: arXiv cs.LO 2011
Year: 2011

This paper constructs a cirquent calculus system and proves its soundness and completeness with respect to the semantics of computability logic (see http://www.cis.upenn.edu/~giorgi/cl.html). The logical vocabulary of the system consists of negation, parallel conjunction, parallel disjunction, branching recurrence, and branching corecurrence. The article is published in two parts, with (the previous) Part I containing preliminaries and a soundness proof, and (the present) Part II containing a completeness proof.
Sidelobe Suppression for Capon Beamforming with Mainlobe to Sidelobe Power Ratio Maximization
Venue: arXiv cs.IT 2011
Year: 2011

High sidelobe level is a major disadvantage of the Capon beamforming. To suppress the sidelobe, this paper introduces a mainlobe to sidelobe power ratio constraint to the Capon beamforming. it minimizes the sidelobe power while keeping the mainlobe power constant. Simulations show that the obtained beamformer outperforms the Capon beamformer.
Fisher Information in Flow Size Distribution
Venue: arXiv cs.IT 2011
Year: 2011

The flow size distribution is a useful metric for traffic modeling and management. Its estimation based on sampled data, however, is problematic. Previous work has shown that flow sampling (FS) offers enormous statistical benefits over packet sampling but high resource requirements precludes its use in routers. We present Dual Sampling (DS), a two-parameter family, which, to a large extent, provide FS-like statistical performance by approaching FS continuously, with just packet-sampling-like computational cost. Our work utilizes a Fisher information based approach recently used to evaluate a number of sampling schemes, excluding FS, for TCP flows. We revise and extend the approach to make rigorous and fair comparisons between FS, DS and others. We show how DS significantly outperforms other packet based methods, including Sample and Hold, the closest packet sampling-based competitor to FS. We describe a packet sampling-based implementation of DS and analyze its key computational costs to show that router implementation is feasible. Our approach offers insights into numerous issues, including the notion of `flow quality' for understanding the relative performance of methods, and how and when employing sequence numbers is beneficial. Our work is theoretical with some simulation support and case studies on Internet data.
Bigraphical Refinement
Venue: arXiv cs.SE 2011
Year: 2011

We propose a mechanism for the vertical refinement of bigraphical reactive systems, based upon a mechanism for limiting observations and utilising the underlying categorical structure of bigraphs. We present a motivating example to demonstrate that the proposed notion of refinement is sensible with respect to the theory of bigraphical reactive systems; and we propose a sufficient condition for guaranteeing the existence of a safety-preserving vertical refinement. We postulate the existence of a complimentary notion of horizontal refinement for bigraphical agents, and finally we discuss the connection of this work to the general refinement of Reeves and Streader.
Refinement-based verification of sequential implementations of Stateflow charts
Venue: arXiv cs.LO 2011
Year: 2011

Simulink/Stateflow charts are widely used in industry for the specification of control systems, which are often safety-critical. This suggests a need for a formal treatment of such models. In previous work, we have proposed a technique for automatic generation of formal models of Stateflow blocks to support refinement-based reasoning. In this article, we present a refinement strategy that supports the verification of automatically generated sequential C implementations of Stateflow charts. In particular, we discuss how this strategy can be specialised to take advantage of architectural features in order to allow a higher level of automation.
Model exploration and analysis for quantitative safety refinement in probabilistic B
Venue: arXiv cs.LO 2011
Year: 2011

The role played by counterexamples in standard system analysis is well known; but less common is a notion of counterexample in probabilistic systems refinement. In this paper we extend previous work using counterexamples to inductive invariant properties of probabilistic systems, demonstrating how they can be used to extend the technique of bounded model checking-style analysis for the refinement of quantitative safety specifications in the probabilistic B language. In particular, we show how the method can be adapted to cope with refinements incorporating probabilistic loops. Finally, we demonstrate the technique on pB models summarising a one-step refinement of a randomised algorithm for finding the minimum cut of undirected graphs, and that for the dependability analysis of a controller design.
A CSP Account of Event-B Refinement
Venue: arXiv cs.LO 2011
Year: 2011

Event-B provides a flexible framework for stepwise system development via refinement. The framework supports steps for (a) refining events (one-by-one), (b) splitting events (one-by-many), and (c) introducing new events. In each of the steps events can moreover possibly be anticipated or convergent. All such steps are accompanied with precise proof obligations. Still, it remains unclear what the exact relationship - in terms of a behaviour-oriented semantics - between an Event-B machine and its refinement is. In this paper, we give a CSP account of Event-B refinement, with a treatment for the first time of splitting events and of anticipated events. To this end, we define a CSP semantics for Event-B and show how the different forms of Event-B refinement can be captured as CSP refinement.
Decidability of Existence and Construction of a Complement of a given Function
Venue: arXiv cs.LO 2011
Year: 2011

This article defines a complement of a function and conditions for existence of such a complement function and presents few algorithms to construct a complement.
Understanding opinions. A cognitive and formal account
Venue: arXiv cs.AI 2011
Year: 2011

The study of opinions, their formation and change, is one of the defining topics addressed by social psychology, but in recent years other disciplines, as computer science and complexity, have addressed this challenge. Despite the flourishing of different models and theories in both fields, several key questions still remain unanswered. The aim of this paper is to challenge the current theories on opinion by putting forward a cognitively grounded model where opinions are described as specific mental representations whose main properties are put forward. A comparison with reputation will be also presented.
Average-Consensus Algorithms in a Deterministic Framework
Venue: arXiv cs.DC 2011
Year: 2011

We consider the average-consensus problem in a multi-node network of finite size. Communication between nodes is modeled by a sequence of directed signals with arbitrary communication delays. Four distributed algorithms that achieve average-consensus are proposed. Necessary and sufficient communication conditions are given for each algorithm to achieve average-consensus. Resource costs for each algorithm are derived based on the number of scalar values that are required for communication and storage at each node. Numerical examples are provided to illustrate the empirical convergence rate of the four algorithms in comparison with a well-known "gossip" algorithm as well as a randomized information spreading algorithm when assuming a fully connected random graph with instantaneous communication.
Face Identification from Manipulated Facial Images using SIFT
Venue: arXiv cs.CV 2011
Year: 2011

Editing on digital images is ubiquitous. Identification of deliberately modified facial images is a new challenge for face identification system. In this paper, we address the problem of identification of a face or person from heavily altered facial images. In this face identification problem, the input to the system is a manipulated or transformed face image and the system reports back the determined identity from a database of known individuals. Such a system can be useful in mugshot identification in which mugshot database contains two views (frontal and profile) of each criminal. We considered only frontal view from the available database for face identification and the query image is a manipulated face generated by face transformation software tool available online. We propose SIFT features for efficient face identification in this scenario. Further comparative analysis has been given with well known eigenface approach. Experiments have been conducted with real case images to evaluate the performance of both methods.
MONARC Simulation Framework
Venue: arXiv cs.DC 2011
Year: 2011

This paper discusses the latest generation of the MONARC (MOdels of Networked Analysis at Regional Centers) simulation framework, as a design and modelling tool for large scale distributed systems applied to HEP experiments. A process-oriented approach for discrete event simulation is well-suited for describing concurrent running programs, as well as the stochastic arrival patterns that characterize how such systems are used. The simulation engine is based on Threaded Objects (or Active Objects), which offer great flexibility in simulating the complex behavior of distributed data processing programs. The engine provides an appropriate scheduling mechanism for the Active objects with support for interrupts. This approach offers a natural way of describing complex running programs that are data dependent and which concurrently compete for shared resources as well as large numbers of concurrent data transfers on shared resources. The framework provides a complete set of basic components (processing nodes, data servers, network components) together with dynamically loadable decision units (scheduling or data replication modules) for easily building complex Computing Model simulations. Examples of simulating complex data processing systems are presented, and the way the framework is used to compare different decision making algorithms or to optimize the overall Grid architecture and/or the policies that govern the Grid's use.
Avoiding Three Consecutive Blocks of the Same Size and Same Sum
Venue: arXiv cs.DM 2011
Year: 2011

We show that there exists an infinite word over the alphabet {0, 1, 3, 4} containing no three consecutive blocks of the same size and the same sum. This answers an open problem of Pirillo and Varricchio from 1994.
User Arrival in MIMO Interference Alignment Networks
Venue: arXiv cs.IT 2011
Year: 2011

In this paper we analyze a constant multiple-input multiple-output interference channel where a set of active users are cooperating through interference alignment while a set of secondary users desire access to the channel. We derive the minimum number of secondary transmit antennas required so that a secondary user can use the channel without affecting the sum rate of the active users, under a zero-forcing equalization assumption. When the secondary users have enough antennas, we derive several secondary user precoders that approximately maximize the secondary users' sum rate without changing the sum rate of the active users. When the secondary users do not have enough antennas, we perform numerical optimization to find secondary user precoders that cause minimum degradation to the sum rate of the active users. Through simulations, we confirm that i) with enough antennas at the secondary users, gains equivalent to the case of all the users cooperating through interference alignment is obtainable, and ii) when the secondary users do not have enough antennas, large rate losses at the active users can be avoided.
Answer Set Planning Under Action Costs
Venue: arXiv cs.AI 2011
Year: 2011

Recently, planning based on answer set programming has been proposed as an approach towards realizing declarative planning systems. In this paper, we present the language Kc, which extends the declarative planning language K by action costs. Kc provides the notion of admissible and optimal plans, which are plans whose overall action costs are within a given limit resp. minimum over all plans (i.e., cheapest plans). As we demonstrate, this novel language allows for expressing some nontrivial planning tasks in a declarative way. Furthermore, it can be utilized for representing planning problems under other optimality criteria, such as computing ``shortest'' plans (with the least number of steps), and refinement combinations of cheapest and fastest plans. We study complexity aspects of the language Kc and provide a transformation to logic programs, such that planning problems are solved via answer set programming. Furthermore, we report experimental results on selected problems. Our experience is encouraging that answer set planning may be a valuable approach to expressive planning systems in which intricate planning problems can be naturally specified and solved.
Temporal Decision Trees: Model-based Diagnosis of Dynamic Systems On-Board
Venue: arXiv cs.AI 2011
Year: 2011

The automatic generation of decision trees based on off-line reasoning on models of a domain is a reasonable compromise between the advantages of using a model-based approach in technical domains and the constraints imposed by embedded applications. In this paper we extend the approach to deal with temporal information. We introduce a notion of temporal decision tree, which is designed to make use of relevant information as long as it is acquired, and we present an algorithm for compiling such trees from a model-based reasoning system.
Advance Reservation of Resources for Task Execution in Grid Environments
Venue: arXiv cs.DC 2011
Year: 2011

The paper proposes a solution for the Grid scheduling problem, addressing in particular the requirement of high performance an efficient algorithm must fulfill. Advance Reservation engages a distributed, dynamic, fault-tolerant and efficient strategy which reserves resources for future task execution. The paper presents the main features of the strategy, the functioning mechanism the strategy is based on and the methods used for evaluating the algorithm.
Kolmogorov complexity and cryptography
Venue: arXiv cs.CR 2011
Year: 2011

This paper contains some results of An.A.Muchnik (1958-2007) reported in his talks at the Kolmogorov seminar (Moscow State Lomonosov University, Math. Department, Logic and Algorithms theory division, March 11, 2003 and April 8, 2003) but not published at that time. These results were stated (without proofs) in the joint talk of Andrej Muchnik and Alexei Semenov at Dagstuhl Seminar 03181, 27.04.2003-03.05.2003. This text was prepared by Alexey Chernov and Alexander Shen in 2008-2009. We consider (in the framework of algorithmic information theory) questions of the following type: construct a message that contains different amounts of information for recipients that have (or do not have) certain a priori information. Assume, for example, that the recipient knows some string $a$, and we want to send her some information that allows her to reconstruct some string $b$ (using $a$). On the other hand, this information alone should not allow the eavesdropper (who does not know $a$) to reconstruct $b$. It is indeed possible (if the strings $a$ and $b$ are not too simple). Then we consider more complicated versions of this question. What if the eavesdropper knows some string $c$? How long should be our message? We provide some conditions that guarantee the existence of a polynomial-size message; we show then that without these conditions this is not always possible.