OpenRaiser/Intern-Atlas huggingface dataset:
Reachability in Two-Clock Timed Automata is PSPACE-complete
Venue: arXiv cs.FL 2013
Year: 2013

A recent result of Haase et al. has shown that reachability in two-clock timed automata is log-space equivalent to reachability in bounded one-counter automata. We show that reachability in bounded one-counter automata is PSPACE-complete.
Comparision and analysis of photo image forgery detection techniques
Venue: arXiv cs.CV 2013
Year: 2013

Digital Photo images are everywhere, on the covers of magazines, in newspapers, in courtrooms, and all over the Internet. We are exposed to them throughout the day and most of the time. Ease with which images can be manipulated; we need to be aware that seeing does not always imply believing. We propose methodologies to identify such unbelievable photo images and succeeded to identify forged region by given only the forged image. Formats are additive tag for every file system and contents are relatively expressed with extension based on most popular digital camera uses JPEG and Other image formats like png, bmp etc. We have designed algorithm running behind with the concept of abnormal anomalies and identify the forgery regions.
An Analysis of Gene Expression Data using Penalized Fuzzy C-Means Approach
Venue: arXiv cs.CV 2013
Year: 2013

With the rapid advances of microarray technologies, large amounts of high-dimensional gene expression data are being generated, which poses significant computational challenges. A first step towards addressing this challenge is the use of clustering techniques, which is essential in the data mining process to reveal natural structures and identify interesting patterns in the underlying data. A robust gene expression clustering approach to minimize undesirable clustering is proposed. In this paper, Penalized Fuzzy C-Means (PFCM) Clustering algorithm is described and compared with the most representative off-line clustering techniques: K-Means Clustering, Rough K-Means Clustering and Fuzzy C-Means clustering. These techniques are implemented and tested for a Brain Tumor gene expression Dataset. Analysis of the performance of the proposed approach is presented through qualitative validation experiments. From experimental results, it can be observed that Penalized Fuzzy C-Means algorithm shows a much higher usability than the other projected clustering algorithms used in our comparison study. Significant and promising clustering results are presented using Brain Tumor Gene expression dataset. Thus patterns seen in genome-wide expression experiments can be interpreted as indications of the status of cellular processes. In these clustering results, we find that Penalized Fuzzy C-Means algorithm provides useful information as an aid to diagnosis in oncology.
Information Flow Analysis for a Dynamically Typed Functional Language with Staged Metaprogramming
Venue: arXiv cs.PL 2013
Year: 2013

Web applications written in JavaScript are regularly used for dealing with sensitive or personal data. Consequently, reasoning about their security properties has become an important problem, which is made very difficult by the highly dynamic nature of the language, particularly its support for runtime code generation. As a first step towards dealing with this, we propose to investigate security analyses for languages with more principled forms of dynamic code generation. To this end, we present a static information flow analysis for a dynamically typed functional language with prototype-based inheritance and staged metaprogramming. We prove its soundness, implement it and test it on various examples designed to show its relevance to proving security properties, such as noninterference, in JavaScript. To our knowledge, this is the first fully static information flow analysis for a language with staged metaprogramming, and the first formal soundness proof of a CFA-based information flow analysis for a functional programming language.
"Groupware for Groups": Problem-Driven Design in Deme
Venue: arXiv cs.HC 2013
Year: 2013

Design choices can be clarified when group interaction software is directed at solving the interaction needs of particular groups that pre-date the groupware. We describe an example: the Deme platform for online deliberation. Traditional threaded conversation systems are insufficient for solving the problem at which Deme is aimed, namely, that the democratic process in grassroots community groups is undermined both by the limited availability of group members for face-to-face meetings and by constraints on the use of information in real-time interactions. We describe and motivate design elements, either implemented or planned for Deme, that addresses this problem. We believe that "problem focused" design of software for preexisting groups provides a useful framework for evaluating the appropriateness of design elements in groupware generally.
On Consistency of Operational Transformation Approach
Venue: arXiv cs.DC 2013
Year: 2013

The Operational Transformation (OT) approach, used in many collaborative editors, allows a group of users to concurrently update replicas of a shared object and exchange their updates in any order. The basic idea of this approach is to transform any received update operation before its execution on a replica of the object. This transformation aims to ensure the convergence of the different replicas of the object, even though the operations are executed in different orders. However, designing transformation functions for achieving convergence is a critical and challenging issue. Indeed, the transformation functions proposed in the literature are all revealed incorrect. In this paper, we investigate the existence of transformation functions for a shared string altered by insert and delete operations. From the theoretical point of view, two properties - named TP1 and TP2 - are necessary and sufficient to ensure convergence. Using controller synthesis technique, we show that there are some transformation functions which satisfy only TP1 for the basic signatures of insert and delete operations. As a matter of fact, it is impossible to meet both properties TP1 and TP2 with these simple signatures.
Arithmetic Circuit Lower Bounds via MaxRank
Venue: arXiv cs.CC 2013
Year: 2013

We introduce the polynomial coefficient matrix and identify maximum rank of this matrix under variable substitution as a complexity measure for multivariate polynomials. We use our techniques to prove super-polynomial lower bounds against several classes of non-multilinear arithmetic circuits. In particular, we obtain the following results : As our main result, we prove that any homogeneous depth-3 circuit for computing the product of $d$ matrices of dimension $n \times n$ requires $Ω(n^{d-1}/2^d)$ size. This improves the lower bounds by Nisan and Wigderson(1995) when $d=ω(1)$. There is an explicit polynomial on $n$ variables and degree at most $\frac{n}{2}$ for which any depth-3 circuit $C$ of product dimension at most $\frac{n}{10}$ (dimension of the space of affine forms feeding into each product gate) requires size $2^{Ω(n)}$. This generalizes the lower bounds against diagonal circuits proved by Saxena(2007). Diagonal circuits are of product dimension 1. We prove a $n^{Ω(\log n)}$ lower bound on the size of product-sparse formulas. By definition, any multilinear formula is a product-sparse formula. Thus, our result extends the known super-polynomial lower bounds on the size of multilinear formulas by Raz(2006). We prove a $2^{Ω(n)}$ lower bound on the size of partitioned arithmetic branching programs. This result extends the known exponential lower bound on the size of ordered arithmetic branching programs given by Jansen(2008).
Socially Stable Matchings
Venue: arXiv cs.GT 2013
Year: 2013

In two-sided matching markets, the agents are partitioned into two sets. Each agent wishes to be matched to an agent in the other set and has a strict preference over these potential matches. A matching is stable if there are no blocking pairs, i.e., no pair of agents that prefer each other to their assigned matches. In this paper we study a variant of stable matching motivated by the fact that, in most centralized markets, many agents do not have direct communication with each other. Hence even if some blocking pairs exist, the agents involved in those pairs may not be able to coordinate a deviation. We model communication channels with a bipartite graph between the two sets of agents which we call the social graph, and we study socially stable matchings. A matching is socially stable if there are no blocking pairs that are connected by an edge in the social graph. Socially stable matchings vary in size and so we look for a maximum socially stable matching. We prove that this problem is NP-hard and, assuming the unique games conjecture, hard to approximate within a factor of 3/2-ε, for any constant ε>0. We complement the hardness results with a 3/2-approximation algorithm.
Modulated String Searching
Venue: arXiv cs.DS 2013
Year: 2013

In his 1987 paper entitled "Generalized String Matching", Abrahamson introduced {\em pattern matching with character classes} and provided the first efficient algorithm to solve it. The best known solution to date is due to Linhart and Shamir (2009). Another broad yet comparatively less studied class of string matching problems is that of numerical string searching, such as, e.g., the `less-than' or $L_1$-norm string searching. The best known solutions for problems in this class are based on FFT convolution after some suitable re-encoding. The present paper introduces {\em modulated string searching} as a unified framework for string matching problems where the numerical conditions can be combined with some Boolean/numerical decision conditions on the character classes. One example problem in this class is the {\em locally bounded $L_1$-norm} matching problem on character classes: here the "match" between a character at some position in the text and a set of characters at some position in the pattern is assessed based on the smallest $L_1$ distance between the text character and one of those pattern characters. The two positions "match" if the (absolute value of the) difference between the two characters does not exceed a predefined constant. The pattern has an occurrence in an alignment with the text if the sum of all such differences does not exceed a second predefined constant value. This problem requires a pointwise evaluation of the quality of each match and has no known solution based on the previously mentioned algorithms.
A Structurally and Temporally Extended Bayesian Belief Network Model: Definitions, Properties, and Modeling Techniques
Venue: arXiv cs.AI 2013
Year: 2013

We developed the language of Modifiable Temporal Belief Networks (MTBNs) as a structural and temporal extension of Bayesian Belief Networks (BNs) to facilitate normative temporal and causal modeling under uncertainty. In this paper we present definitions of the model, its components, and its fundamental properties. We also discuss how to represent various types of temporal knowledge, with an emphasis on hybrid temporal-explicit time modeling, dynamic structures, avoiding causal temporal inconsistencies, and dealing with models that involve simultaneously actions (decisions) and causal and non-causal associations. We examine the relationships among BNs, Modifiable Belief Networks, and MTBNs with a single temporal granularity, and suggest areas of application suitable to each one of them.
An Alternative Markov Property for Chain Graphs
Venue: arXiv cs.AI 2013
Year: 2013

Graphical Markov models use graphs, either undirected, directed, or mixed, to represent possible dependences among statistical variables. Applications of undirected graphs (UDGs) include models for spatial dependence and image analysis, while acyclic directed graphs (ADGs), which are especially convenient for statistical analysis, arise in such fields as genetics and psychometrics and as models for expert systems and Bayesian belief networks. Lauritzen, Wermuth and Frydenberg (LWF) introduced a Markov property for chain graphs, which are mixed graphs that can be used to represent simultaneously both causal and associative dependencies and which include both UDGs and ADGs as special cases. In this paper an alternative Markov property (AMP) for chain graphs is introduced, which in some ways is a more direct extension of the ADG Markov property than is the LWF property for chain graph.
A Sufficiently Fast Algorithm for Finding Close to Optimal Junction Trees
Venue: arXiv cs.DS 2013
Year: 2013

An algorithm is developed for finding a close to optimal junction tree of a given graph G. The algorithm has a worst case complexity O(c^k n^a) where a and c are constants, n is the number of vertices, and k is the size of the largest clique in a junction tree of G in which this size is minimized. The algorithm guarantees that the logarithm of the size of the state space of the heaviest clique in the junction tree produced is less than a constant factor off the optimal value. When k = O(log n), our algorithm yields a polynomial inference algorithm for Bayesian networks.
Decision-Analytic Approaches to Operational Decision Making: Application and Observation
Venue: arXiv cs.AI 2013
Year: 2013

Decision analysis (DA) and the rich set of tools developed by researchers in decision making under uncertainty show great potential to penetrate the technological content of the products and services delivered by firms in a variety of industries as well as the business processes used to deliver those products and services to market. In this paper I describe work in progress at Sun Microsystems in the application of decision-analytic methods to Operational Decision Making (ODM) in its World-Wide Operations (WWOPS) Business Management Group. Working with membersof product engineering, marketing, and sales, operations planners from WWOPS have begun to use a decision-analytic framework called SCRAM (Supply Communication/Risk Assessment and Management) to structure and solve problems in product planning, tracking, and transition. Concepts such as information value provide a powerful method of managing huge information sets and thereby enable managers to focus attention on factors that matter most for their business. Finally, our process-oriented introduction of decision-analytic methods to Sun managers has led to a focused effort to develop decision support software based on methods from decision making under uncertainty.
Belief Revision with Uncertain Inputs in the Possibilistic Setting
Venue: arXiv cs.AI 2013
Year: 2013

This paper discusses belief revision under uncertain inputs in the framework of possibility theory. Revision can be based on two possible definitions of the conditioning operation, one based on min operator which requires a purely ordinal scale only, and another based on product, for which a richer structure is needed, and which is a particular case of Dempster's rule of conditioning. Besides, revision under uncertain inputs can be understood in two different ways depending on whether the input is viewed, or not, as a constraint to enforce. Moreover, it is shown that M.A. Williams' transmutations, originally defined in the setting of Spohn's functions, can be captured in this framework, as well as Boutilier's natural revision.
Theoretical Foundations for Abstraction-Based Probabilistic Planning
Venue: arXiv cs.AI 2013
Year: 2013

Modeling worlds and actions under uncertainty is one of the central problems in the framework of decision-theoretic planning. The representation must be general enough to capture real-world problems but at the same time it must provide a basis upon which theoretical results can be derived. The central notion in the framework we propose here is that of the affine-operator, which serves as a tool for constructing (convex) sets of probability distributions, and which can be considered as a generalization of belief functions and interval mass assignments. Uncertainty in the state of the worlds is modeled with sets of probability distributions, represented by affine-trees while actions are defined as tree-manipulators. A small set of key properties of the affine-operator is presented, forming the basis for most existing operator-based definitions of probabilistic action projection and action abstraction. We derive and prove correct three projection rules, which vividly illustrate the precision-complexity tradeoff in plan projection. Finally, we show how the three types of action abstraction identified by Haddawy and Doan are manifested in the present framework.
Supply Restoration in Power Distribution Systems - A Case Study in Integrating Model-Based Diagnosis and Repair Planning
Venue: arXiv cs.AI 2013
Year: 2013

Integrating diagnosis and repair is particularly crucial when gaining sufficient information to discriminate between several candidate diagnoses requires carrying out some repair actions. A typical case is supply restoration in a faulty power distribution system. This problem, which is a major concern for electricity distributors, features partial observability, and stochastic repair actions which are more elaborate than simple replacement of components. This paper analyses the difficulties in applying existing work on integrating model-based diagnosis and repair and on planning in partially observable stochastic domains to this real-world problem, and describes the pragmatic approach we have retained so far.
How to evaluate individual researchers working in the natural and life sciences meaningfully? A proposal of methods based on percentiles of citations
Venue: arXiv cs.DL 2013
Year: 2013

Although bibliometrics has been a separate research field for many years, there is still no uniformity in the way bibliometric analyses are applied to individual researchers. Therefore, this study aims to set up proposals how to evaluate individual researchers working in the natural and life sciences. 2005 saw the introduction of the h index, which gives information about a researcher's productivity and the impact of his or her publications in a single number (h is the number of publications with at least h citations); however, it is not possible to cover the multidimensional complexity of research performance and to undertake inter-personal comparisons with this number. This study therefore includes recommendations for a set of indicators to be used for evaluating researchers. Our proposals relate to the selection of data on which an evaluation is based, the analysis of the data and the presentation of the results.
A Fresnelet-Based Encryption of Medical Images using Arnold Transform
Venue: arXiv cs.CR 2013
Year: 2013

Medical images are commonly stored in digital media and transmitted via Internet for certain uses. If a medical information image alters, this can lead to a wrong diagnosis which may create a serious health problem. Moreover, medical images in digital form can easily be modified by wiping off or adding small pieces of information intentionally for certain illegal purposes. Hence, the reliability of medical images is an important criterion in a hospital information system. In this paper, Fresnelet transform is employed along with appropriate handling of the Arnold transform and the discrete cosine transform to provide secure distribution of medical images. This method presents a new data hiding system in which steganography and cryptography are used to prevent unauthorized data access. The experimental results exhibit high imperceptibility for embedded images and significant encryption of information images.
Silent Transitions in Automata with Storage
Venue: arXiv cs.FL 2013
Year: 2013

We consider the computational power of silent transitions in one-way automata with storage. Specifically, we ask which storage mechanisms admit a transformation of a given automaton into one that accepts the same language and reads at least one input symbol in each step. We study this question using the model of valence automata. Here, a finite automaton is equipped with a storage mechanism that is given by a monoid. This work presents generalizations of known results on silent transitions. For two classes of monoids, it provides characterizations of those monoids that allow the removal of λ-transitions. Both classes are defined by graph products of copies of the bicyclic monoid and the group of integers. The first class contains pushdown storages as well as the blind counters while the second class contains the blind and the partially blind counters.
Technical Report: Cooperative Multi-Target Localization With Noisy Sensors
Venue: arXiv cs.RO 2013
Year: 2013

This technical report is an extended version of the paper 'Cooperative Multi-Target Localization With Noisy Sensors' accepted to the 2013 IEEE International Conference on Robotics and Automation (ICRA). This paper addresses the task of searching for an unknown number of static targets within a known obstacle map using a team of mobile robots equipped with noisy, limited field-of-view sensors. Such sensors may fail to detect a subset of the visible targets or return false positive detections. These measurement sets are used to localize the targets using the Probability Hypothesis Density, or PHD, filter. Robots communicate with each other on a local peer-to-peer basis and with a server or the cloud via access points, exchanging measurements and poses to update their belief about the targets and plan future actions. The server provides a mechanism to collect and synthesize information from all robots and to share the global, albeit time-delayed, belief state to robots near access points. We design a decentralized control scheme that exploits this communication architecture and the PHD representation of the belief state. Specifically, robots move to maximize mutual information between the target set and measurements, both self-collected and those available by accessing the server, balancing local exploration with sharing knowledge across the team. Furthermore, robots coordinate their actions with other robots exploring the same local region of the environment.
An Online Environment for Democratic Deliberation: Motivations, Principles, and Design
Venue: arXiv cs.HC 2013
Year: 2013

We have created a platform for online deliberation called Deme (which rhymes with 'team'). Deme is designed to allow groups of people to engage in collaborative drafting, focused discussion, and decision making using the Internet. The Deme project has evolved greatly from its beginning in 2003. This chapter outlines the thinking behind Deme's initial design: our motivations for creating it, the principles that guided its construction, and its most important design features. The version of Deme described here was written in PHP and was deployed in 2004 and used by several groups (including organizers of the 2005 Online Deliberation Conference). Other papers describe later developments in the Deme project (see Davies et al. 2005, 2008; Davies and Mintz 2009).