OpenRaiser/Intern-Atlas huggingface dataset:
Unifying Büchi Complementation Constructions
Venue: arXiv cs.FL 2013
Year: 2013

Complementation of Büchi automata, required for checking automata containment, is of major theoretical and practical interest in formal verification. We consider two recent approaches to complementation. The first is the rank-based approach of Kupferman and Vardi, which operates over a DAG that embodies all runs of the automaton. This approach is based on the observation that the vertices of this DAG can be ranked in a certain way, termed an odd ranking, iff all runs are rejecting. The second is the slice-based approach of Kähler and Wilke. This approach tracks levels of "split trees" - run trees in which only essential information about the history of each run is maintained. While the slice-based construction is conceptually simple, the complementing automata it generates are exponentially larger than those of the recent rank-based construction of Schewe, and it suffers from the difficulty of symbolically encoding levels of split trees. In this work we reformulate the slice-based approach in terms of run DAGs and preorders over states. In doing so, we begin to draw parallels between the rank-based and slice-based approaches. Through deeper analysis of the slice-based approach, we strongly restrict the nondeterminism it generates. We are then able to employ the slice-based approach to provide a new odd ranking, called a retrospective ranking, that is different from the one provided by Kupferman and Vardi. This new ranking allows us to construct a deterministic-in-the-limit rank-based automaton with a highly restricted transition function. Further, by phrasing the slice-based approach in terms of ranks, our approach affords a simple symbolic encoding and achieves the tight bound of Schewe's construction
Text Steganographic Approaches: A Comparison
Venue: arXiv cs.CR 2013
Year: 2013

This paper presents three novel approaches of text steganography. The first approach uses the theme of missing letter puzzle where each character of message is hidden by missing one or more letters in a word of cover. The average Jaro score was found to be 0.95 indicating closer similarity between cover and stego file. The second approach hides a message in a wordlist where ASCII value of embedded character determines length and starting letter of a word. The third approach conceals a message, without degrading cover, by using start and end letter of words of the cover. For enhancing the security of secret message, the message is scrambled using one-time pad scheme before being concealed and cipher text is then concealed in cover. We also present an empirical comparison of the proposed approaches with some of the popular text steganographic approaches and show that our approaches outperform the existing approaches.
Mixing Strategies in Data Compression
Venue: arXiv cs.IT 2013
Year: 2013

We propose geometric weighting as a novel method to combine multiple models in data compression. Our results reveal the rationale behind PAQ-weighting and generalize it to a non-binary alphabet. Based on a similar technique we present a new, generic linear mixture technique. All novel mixture techniques rely on given weight vectors. We consider the problem of finding optimal weights and show that the weight optimization leads to a strictly convex (and thus, good-natured) optimization problem. Finally, an experimental evaluation compares the two presented mixture techniques for a binary alphabet. The results indicate that geometric weighting is superior to linear weighting.
Hypergraph Automata: A Theoretical Model for Patterned Self-assembly
Venue: arXiv cs.DM 2013
Year: 2013

Patterned self-assembly is a process whereby coloured tiles self-assemble to build a rectangular coloured pattern. We propose self-assembly (SA) hypergraph automata as an automata-theoretic model for patterned self-assembly. We investigate the computational power of SA-hypergraph automata and show that for every recognizable picture language, there exists an SA-hypergraph automaton that accepts this language. Conversely, we prove that for any restricted SA-hypergraph automaton, there exists a Wang Tile System, a model for recognizable picture languages, that accepts the same language. The advantage of SA-hypergraph automata over Wang automata, acceptors for the class of recognizable picture languages, is that they do not rely on an a priori defined scanning strategy
The Family of MapReduce and Large Scale Data Processing Systems
Venue: arXiv cs.DB 2013
Year: 2013

In the last two decades, the continuous increase of computational power has produced an overwhelming flow of data which has called for a paradigm shift in the computing architecture and large scale data processing mechanisms. MapReduce is a simple and powerful programming model that enables easy development of scalable parallel applications to process vast amounts of data on large clusters of commodity machines. It isolates the application from the details of running a distributed program such as issues on data distribution, scheduling and fault tolerance. However, the original implementation of the MapReduce framework had some limitations that have been tackled by many research efforts in several followup works after its introduction. This article provides a comprehensive survey for a family of approaches and mechanisms of large scale data processing mechanisms that have been implemented based on the original idea of the MapReduce framework and are currently gaining a lot of momentum in both research and industrial communities. We also cover a set of introduced systems that have been implemented to provide declarative programming interfaces on top of the MapReduce framework. In addition, we review several large scale data processing systems that resemble some of the ideas of the MapReduce framework for different purposes and application scenarios. Finally, we discuss some of the future research directions for implementing the next generation of MapReduce-like solutions.
Fast Compressed Sensing SAR Imaging based on Approximated Observation
Venue: arXiv cs.IT 2013
Year: 2013

In recent years, compressed sensing (CS) has been applied in the field of synthetic aperture radar (SAR) imaging and shows great potential. The existing models are, however, based on application of the sensing matrix acquired by the exact observation functions. As a result, the corresponding reconstruction algorithms are much more time consuming than traditional matched filter (MF) based focusing methods, especially in high resolution and wide swath systems. In this paper, we formulate a new CS-SAR imaging model based on the use of the approximated SAR observation deducted from the inverse of focusing procedures. We incorporate CS and MF within an sparse regularization framework that is then solved by a fast iterative thresholding algorithm. The proposed model forms a new CS-SAR imaging method that can be applied to high-quality and high-resolution imaging under sub-Nyquist rate sampling, while saving the computational cost substantially both in time and memory. Simulations and real SAR data applications support that the proposed method can perform SAR imaging effectively and efficiently under Nyquist rate, especially for large scale applications.
Morphological Analusis Of The Left Ventricular Eendocardial Surface Using A Bag-Of-Features Descriptor
Venue: arXiv cs.CV 2013
Year: 2013

The limitations of conventional imaging techniques have hitherto precluded a thorough and formal investigation of the complex morphology of the left ventricular (LV) endocardial surface and its relation to the severity of Coronary Artery Disease (CAD). Recent developments in high-resolution Multirow-Detector Computed Tomography (MDCT) scanner technology have enabled the imaging of LV endocardial surface morphology in a single heart beat. Analysis of high-resolution Computed Tomography (CT) images from a 320-MDCT scanner allows the study of the relationship between percent Diameter Stenosis (DS) of the major coronary arteries and localization of the cardiac segments affected by coronary arterial stenosis. In this paper a novel approach for the analysis using a combination of rigid transformation-invariant shape descriptors and a more generalized isometry-invariant Bag-of-Features (BoF) descriptor, is proposed and implemented. The proposed approach is shown to be successful in identifying, localizing and quantifying the incidence and extent of CAD and thus, is seen to have a potentially significant clinical impact. Specifically, the association between the incidence and extent of CAD, determined via the percent DS measurements of the major coronary arteries, and the alterations in the endocardial surface morphology is formally quantified. A multivariate regression test performed on a strict leave-one-out basis are shown to exhibit a distinct pattern in terms of the correlation coefficient within the cardiac segments where the incidence of coronary arterial stenosis is localized.
A New Construction of Multi-receiver Authentication Codes from Pseudo-Symplectic Geometry over Finite Fields
Venue: arXiv cs.IT 2013
Year: 2013

Multi-receiver authentication codes allow one sender to construct an authenticated message for a group of receivers such that each receiver can verify authenticity of the received message. In this paper, we constructed one multi-receiver authentication codes from pseudo-symplectic geometry over finite fields. The parameters and the probabilities of deceptions of this codes are also computed.
CSI Sharing Strategies for Transmitter Cooperation in Wireless Networks
Venue: arXiv cs.IT 2013
Year: 2013

Multiple-antenna "based" transmitter (TX) cooperation has been established as a promising tool towards avoiding, aligning, or shaping the interference resulting from aggressive spectral reuse. The price paid in the form of feedback and exchanging channel state information (CSI) between cooperating devices in most existing methods is often underestimated however. In reality, feedback and information overhead threatens the practicality and scalability of TX cooperation approaches in dense networks. Hereby we addresses a "Who needs to know what?" problem, when it comes to CSI at cooperating transmitters. A comprehensive answer to this question remains beyond our reach and the scope of this paper. Nevertheless, recent results in this area suggest that CSI overhead can be contained for even large networks provided the allocation of feedback to TXs is made non-uniform and to properly depend on the network's topology. This paper provides a few hints toward solving the problem.
Peeling the Grid
Venue: arXiv cs.DM 2013
Year: 2013

Consider the set of points formed by the integer $n \times n$ grid, and the process that in each iteration removes from the point set the vertices of its convex-hull. Here, we prove that the number of iterations of this process is O(n^{4/3}); that is, the number of convex layers of the $n\times n$ grid is Θ(n^{4/3}).
An Efficient Dual Approach to Distance Metric Learning
Venue: arXiv cs.LG 2013
Year: 2013

Distance metric learning is of fundamental interest in machine learning because the distance metric employed can significantly affect the performance of many learning methods. Quadratic Mahalanobis metric learning is a popular approach to the problem, but typically requires solving a semidefinite programming (SDP) problem, which is computationally expensive. Standard interior-point SDP solvers typically have a complexity of $O(D^{6.5})$ (with $D$ the dimension of input data), and can thus only practically solve problems exhibiting less than a few thousand variables. Since the number of variables is $D (D+1) / 2 $, this implies a limit upon the size of problem that can practically be solved of around a few hundred dimensions. The complexity of the popular quadratic Mahalanobis metric learning approach thus limits the size of problem to which metric learning can be applied. Here we propose a significantly more efficient approach to the metric learning problem based on the Lagrange dual formulation of the problem. The proposed formulation is much simpler to implement, and therefore allows much larger Mahalanobis metric learning problems to be solved. The time complexity of the proposed method is $O (D ^ 3) $, which is significantly lower than that of the SDP approach. Experiments on a variety of datasets demonstrate that the proposed method achieves an accuracy comparable to the state-of-the-art, but is applicable to significantly larger problems. We also show that the proposed method can be applied to solve more general Frobenius-norm regularized SDP problems approximately.
A Quasi-Polynomial Time Partition Oracle for Graphs with an Excluded Minor
Venue: arXiv cs.DS 2013
Year: 2013

Motivated by the problem of testing planarity and related properties, we study the problem of designing efficient {\em partition oracles}. A {\em partition oracle} is a procedure that, given access to the incidence lists representation of a bounded-degree graph $G= (V,E)$ and a parameter $\eps$, when queried on a vertex $v\in V$, returns the part (subset of vertices) which $v$ belongs to in a partition of all graph vertices. The partition should be such that all parts are small, each part is connected, and if the graph has certain properties, the total number of edges between parts is at most $\eps |V|$. In this work we give a partition oracle for graphs with excluded minors whose query complexity is quasi-polynomial in $1/\eps$, thus improving on the result of Hassidim et al. ({\em Proceedings of FOCS 2009}) who gave a partition oracle with query complexity exponential in $1/\eps$. This improvement implies corresponding improvements in the complexity of testing planarity and other properties that are characterized by excluded minors as well as sublinear-time approximation algorithms that work under the promise that the graph has an excluded minor.
Self Avoiding Paths Routing Algorithm in Scale-Free Networks
Venue: arXiv cs.NI 2013
Year: 2013

In this paper, we present a new routing algorithm called "the Self Avoiding Paths Routing Algorithm". Its application to traffic flow in scale-free networks shows a great improvement over the so called "efficient routing" protocol while at the same time maintaining a relatively low average packet travel time. It has the advantage of minimizing path overlapping throughout the network in a self consistent manner with a relatively small number of iterations by maintaining an equilibrated path distribution especially among the hubs. This results in a significant shifting of the critical packet generation rate over which traffic congestion occurs, thus permitting the network to sustain more information packets in the free flow state. The performance of the algorithm is discussed both on a Barábasi-Albert (BA) network and real autonomous system (AS) network data.
Bisimulations over DLTS in O(m.log n)-time
Venue: arXiv cs.FL 2013
Year: 2013

The well known Hopcroft's algorithm to minimize deterministic complete automata runs in $O(kn\log n)$-time, where $k$ is the size of the alphabet and $n$ the number of states. The main part of this algorithm corresponds to the computation of a coarsest bisimulation over a finite Deterministic Labelled Transition System (DLTS). By applying techniques we have developed in the case of simulations, we design a new algorithm which computes the coarsest bisimulation over a finite DLTS in $O(m\log n)$-time and $O(k+m+n)$-space, with $m$ the number of transitions. The underlying DLTS does not need to be complete and thus: $m\leq kn$. This new algorithm is much simpler than the two others found in the literature.
Constraining Influence Diagram Structure by Generative Planning: An Application to the Optimization of Oil Spill Response
Venue: arXiv cs.AI 2013
Year: 2013

This paper works through the optimization of a real world planning problem, with a combination of a generative planning tool and an influence diagram solver. The problem is taken from an existing application in the domain of oil spill emergency response. The planning agent manages constraints that order sets of feasible equipment employment actions. This is mapped at an intermediate level of abstraction onto an influence diagram. In addition, the planner can apply a surveillance operator that determines observability of the state---the unknown trajectory of the oil. The uncertain world state and the objective function properties are part of the influence diagram structure, but not represented in the planning agent domain. By exploiting this structure under the constraints generated by the planning agent, the influence diagram solution complexity simplifies considerably, and an optimum solution to the employment problem based on the objective function is found. Finding this optimum is equivalent to the simultaneous evaluation of a range of plans. This result is an example of bounded optimality, within the limitations of this hybrid generative planner and influence diagram architecture.
Some Experiments with Real-Time Decision Algorithms
Venue: arXiv cs.AI 2013
Year: 2013

Real-time Decision algorithms are a class of incremental resource-bounded [Horvitz, 89] or anytime [Dean, 93] algorithms for evaluating influence diagrams. We present a test domain for real-time decision algorithms, and the results of experiments with several Real-time Decision Algorithms in this domain. The results demonstrate high performance for two algorithms, a decision-evaluation variant of Incremental Probabilisitic Inference [D'Ambrosio 93] and a variant of an algorithm suggested by Goldszmidt, [Goldszmidt, 95], PK-reduced. We discuss the implications of these experimental results and explore the broader applicability of these algorithms.
Sound Abstraction of Probabilistic Actions in The Constraint Mass Assignment Framework
Venue: arXiv cs.AI 2013
Year: 2013

This paper provides a formal and practical framework for sound abstraction of probabilistic actions. We start by precisely defining the concept of sound abstraction within the context of finite-horizon planning (where each plan is a finite sequence of actions). Next we show that such abstraction cannot be performed within the traditional probabilistic action representation, which models a world with a single probability distribution over the state space. We then present the constraint mass assignment representation, which models the world with a set of probability distributions and is a generalization of mass assignment representations. Within this framework, we present sound abstraction procedures for three types of action abstraction. We end the paper with discussions and related work on sound and approximate abstraction. We give pointers to papers in which we discuss other sound abstraction-related issues, including applications, estimating loss due to abstraction, and automatically generating abstraction hierarchies.
An Evaluation of Structural Parameters for Probabilistic Reasoning: Results on Benchmark Circuits
Venue: arXiv cs.AI 2013
Year: 2013

Many algorithms for processing probabilistic networks are dependent on the topological properties of the problem's structure. Such algorithms (e.g., clustering, conditioning) are effective only if the problem has a sparse graph captured by parameters such as tree width and cycle-cut set size. In this paper we initiate a study to determine the potential of structure-based algorithms in real-life applications. We analyze empirically the structural properties of problems coming from the circuit diagnosis domain. Specifically, we locate those properties that capture the effectiveness of clustering and conditioning as well as of a family of conditioning+clustering algorithms designed to gradually trade space for time. We perform our analysis on 11 benchmark circuits widely used in the testing community. We also report on the effect of ordering heuristics on tree-clustering and show that, on our benchmarks, the well-known max-cardinality ordering is substantially inferior to an ordering called min-degree.
Efficient Search-Based Inference for Noisy-OR Belief Networks: TopEpsilon
Venue: arXiv cs.AI 2013
Year: 2013

Inference algorithms for arbitrary belief networks are impractical for large, complex belief networks. Inference algorithms for specialized classes of belief networks have been shown to be more efficient. In this paper, we present a search-based algorithm for approximate inference on arbitrary, noisy-OR belief networks, generalizing earlier work on search-based inference for two-level, noisy-OR belief networks. Initial experimental results appear promising.
Uncertain Inferences and Uncertain Conclusions
Venue: arXiv cs.AI 2013
Year: 2013

Uncertainty may be taken to characterize inferences, their conclusions, their premises or all three. Under some treatments of uncertainty, the inferences itself is never characterized by uncertainty. We explore both the significance of uncertainty in the premises and in the conclusion of an argument that involves uncertainty. We argue that for uncertainty to characterize the conclusion of an inference is natural, but that there is an interplay between uncertainty in the premises and uncertainty in the procedure of argument itself. We show that it is possible in principle to incorporate all uncertainty in the premises, rendering uncertainty arguments deductively valid. But we then argue (1) that this does not reflect human argument, (2) that it is computationally costly, and (3) that the gain in simplicity obtained by allowing uncertainty inference can sometimes outweigh the loss of flexibility it entails.
Geometric Implications of the Naive Bayes Assumption
Venue: arXiv cs.AI 2013
Year: 2013

A naive (or Idiot) Bayes network is a network with a single hypothesis node and several observations that are conditionally independent given the hypothesis. We recently surveyed a number of members of the UAI community and discovered a general lack of understanding of the implications of the Naive Bayes assumption on the kinds of problems that can be solved by these networks. It has long been recognized [Minsky 61] that if observations are binary, the decision surfaces in these networks are hyperplanes. We extend this result (hyperplane separability) to Naive Bayes networks with m-ary observations. In addition, we illustrate the effect of observation-observation dependencies on decision surfaces. Finally, we discuss the implications of these results on knowledge acquisition and research in learning.
Coherent Knowledge Processing at Maximum Entropy by SPIRIT
Venue: arXiv cs.AI 2013
Year: 2013

SPIRIT is an expert system shell for probabilistic knowledge bases. Knowledge acquisition is performed by processing facts and rules on discrete variables in a rich syntax. The shell generates a probability distribution which respects all acquired facts and rules and which maximizes entropy. The user-friendly devices of SPIRIT to define variables, formulate rules and create the knowledge base are revealed in detail. Inductive learning is possible. Medium sized applications show the power of the system.
Efficient Enumeration of Instantiations in Bayesian Networks
Venue: arXiv cs.AI 2013
Year: 2013

Over the past several years Bayesian networks have been applied to a wide variety of problems. A central problem in applying Bayesian networks is that of finding one or more of the most probable instantiations of a network. In this paper we develop an efficient algorithm that incrementally enumerates the instantiations of a Bayesian network in decreasing order of probability. Such enumeration algorithms are applicable in a variety of applications ranging from medical expert systems to model-based diagnosis. Fundamentally, our algorithm is simply performing a lazy enumeration of the sorted list of all instantiations of the network. This insight leads to a very concise algorithm statement which is both easily understood and implemented. We show that for singly connected networks, our algorithm generates the next instantiation in time polynomial in the size of the network. The algorithm extends to arbitrary Bayesian networks using standard conditioning techniques. We empirically evaluate the enumeration algorithm and demonstrate its practicality.