Constructing Minimal Phylogenetic Networks from Softwired Clusters is Fixed Parameter Tractable

Here we show that, given a set of clusters ${\mathcal{C}}$ on a set of taxa ${\mathcal{X}}$ , where $|{\mathcal{X}}|=n$ , it is possible to determine in time f(k)?poly(n) whether there exists a level-≤k network (i.e. a network where each biconnected component has reticulation number at most k) that represents all the clusters in ${\mathcal{C}}$ in the softwired sense, and if so to construct such a network. This extends a result from Kelk et al. (in IEEE/ACM Trans. Comput. Biol. Bioinform. 9:517–534, 2012) which showed that the problem is polynomial-time solvable for fixed k. By defining “k-reticulation generators” analogous to “level-k generators”, we then extend this fixed parameter tractability result to the problem where k refers not to the level but to the reticulation number of the whole network.     

Delayed theory combination vs. Nelson-Oppen for satisfiability modulo theories: a comparative analysis

Most state-of-the-art approaches for Satisfiability Modulo Theories $(SMT(\mathcal{T}))$ rely on the integration between a SAT solver and a decision procedure for sets of literals in the background theory $\mathcal{T} (\mathcal{T}{\text {-}}solver)$ . Often $\mathcal{T}$ is the combination $\mathcal{T}_1 \cup \mathcal{T}_2$ of two (or more) simpler theories $(SMT(\mathcal{T}_1 \cup \mathcal{T}_2))$ , s.t. the specific ${\mathcal{T}_i}{\text {-}}solvers$ must be combined. Up to a few years ago, the standard approach to $SMT(\mathcal{T}_1 \cup \mathcal{T}_2)$ was to integrate the SAT solver with one combined $\mathcal{T}_1 \cup \mathcal{T}_2{\text {-}}solver$ , obtained from two distinct ${\mathcal{T}_i}{\text {-}}solvers$ by means of evolutions of Nelson and Oppen’s (NO) combination procedure, in which the ${\mathcal{T}_i}{\text {-}}solvers$ deduce and exchange interface equalities. Nowadays many state-of-the-art SMT solvers use evolutions of a more recent $SMT(\mathcal{T}_1 \cup \mathcal{T}_2)$ procedure called Delayed Theory Combination (DTC), in which each ${\mathcal{T}_i}{\text {-}}solver$ interacts directly and only with the SAT solver, in such a way that part or all of the (possibly very expensive) reasoning effort on interface equalities is delegated to the SAT solver itself. In this paper we present a comparative analysis of DTC vs. NO for $SMT(\mathcal{T}_1 \cup \mathcal{T}_2)$ . On the one hand, we explain the advantages of DTC in exploiting the power of modern SAT solvers to reduce the search. On the other hand, we show that the extra amount of Boolean search required to the SAT solver can be controlled. In fact, we prove two novel theoretical results, for both convex and non-convex theories and for different deduction capabilities of the ${\mathcal{T}_i}{\text {-}}solvers$ , which relate the amount of extra Boolean search required to the SAT solver by DTC with the number of deductions and case-splits required to the ${\mathcal{T}_i}{\text {-}}solvers$ by NO in order to perform the same tasks: (i) under the same hypotheses of deduction capabilities of the ${\mathcal{T}_i}{\text {-}}solvers$ required by NO, DTC causes no extra Boolean search; (ii) using ${\mathcal{T}_i}{\text {-}}solvers$ with limited or no deduction capabilities, the extra Boolean search required can be reduced down to a negligible amount by controlling the quality of the $\mathcal{T}$ -conflict sets returned by the ${\mathcal{T}_i}{\text {-}}solvers$ .     

On Projection Matrices $$\mathcal{P}^k \to \mathcal{P}^2 ,k = 3,...,6, $$ and their Applications in Computer Vision

Projection matrices from projective spaces have long been used in multiple-view geometry to model the perspective projection created by the pin-hole camera. In this work we introduce higher-dimensional mappings for the representation of various applications in which the world we view is no longer rigid. We also describe the multi-view constraints from these new projection matrices (where k > 3) and methods for extracting the (non-rigid) structure and motion for each application.     

Generalising Unit-Refutation Completeness and SLUR via Nested Input Resolution

The class ${\mathcal{SLUR}}$ (Single Lookahead Unit Resolution) was introduced in Schlipf et al. (Inf Process Lett 54:133–137, 1995) as an umbrella class for efficient (poly-time) SAT solving, with linear-time SAT decision, while the recognition problem was not considered. ?epek et al. (2012) and Balyo et al. (2012) extended this class in various ways to hierarchies covering all of CNF (all clause-sets). We introduce a hierarchy ${\mathcal{SLUR}}_k$ which we argue is the natural “limit” of such approaches. The second source for our investigations is the class ${\mathcal{UC}}$ of unit-refutation complete clause-sets, introduced in del Val (1994) as a target class for knowledge compilation. Via the theory of “hardness” of clause-sets as developed in Kullmann (1999), Kullmann (Ann Math Artif Intell 40(3–4):303–352, 2004) and Ansótegui et al. (2008) we obtain a natural generalisation ${\mathcal{UC}}_k$ , containing those clause-sets which are “unit-refutation complete of level k”, which is the same as having hardness at most k. Utilising the strong connections to (tree-)resolution complexity and (nested) input resolution, we develop basic methods for the determination of hardness (the level k in ${\mathcal{UC}}_k$ ). A fundamental insight now is that ${\mathcal{SLUR}}_k = {\mathcal{UC}}_k$ holds for all k. We can thus exploit both streams of intuitions and methods for the investigations of these hierarchies. As an application we can easily show that the hierarchies from ?epek et al. (2012) and Balyo et al. (2012) are strongly subsumed by ${\mathcal{SLUR}}_k$ . Finally we consider the problem of “irredundant” clause-sets in ${\mathcal{UC}}_k$ . For 2-CNF we show that strong minimisations are possible in polynomial time, while already for (very special) Horn clause-sets minimisation is NP-complete. We conclude with an extensive discussion of open problems and future directions. We envisage the concepts investigated here to be the starting point for a theory of good SAT translations, which brings together the good SAT-solving aspects from ${\mathcal{SLUR}}$ together with the knowledge-representation aspects from ${\mathcal{UC}}$ , and expands this combination via notions of “hardness”.     

Sparse Representations for Image Decompositions

International Journal of Computer Vision - We are given an image I and a library of templates ${\mathcal{L}}$ , such that ${\mathcal{L}}$ is an overcomplete basis for I. The templates can...     

Branching Time Logics \mathcal {BTL}^{\mathrm {U,S}}_{\mathrm {N},\mathrm {N}^{-1}}(\mathcal {Z})_{\alpha } with Operations Until and Since Based on Bundles of Integer Numbers, Logical Consecutions, Deciding Algorithms

This paper is intended as an attempt to describe logical consequence in branching time logics. We study temporal branching time logics $\mathcal {BTL}^{\mathrm {U,S}}_{\mathrm {N},\mathrm {N}^{-1}}(\mathcal {Z})_{\alpha }$ which use the standard operations Until and Next and dual operations Since and Previous (LTL, as standard, uses only Until and Next). Temporal logics $\mathcal {BTL}^{\mathrm {U,S}}_{\mathrm {N},\mathrm {N}^{-1}}(\mathcal {Z})_{\alpha }$ are generated by semantics based on Kripke/Hinttikka structures with linear frames of integer numbers $\mathcal {Z}$ with a single node (glued zeros). For $\mathcal {BTL}^{\mathrm {U,S}}_{\mathrm {N},\mathrm {N}^{-1}}(\mathcal {Z})_{\alpha }$ , the permissible branching of the node is limited by α (where 1≤α≤ω). We prove that any logic $\mathcal {BTL}^{\mathrm {U,S}}_{\mathrm {N},\mathrm {N}^{-1}}(\mathcal {Z})_{\alpha }$ is decidable w.r.t. admissible consecutions (inference rules), i.e. we find an algorithm recognizing consecutions admissible in $\mathcal {BTL}^{\mathrm {U,S}}_{\mathrm {N},\mathrm {N}^{-1}}(\mathcal {Z})_{\alpha }$ . As a consequence, it implies that $\mathcal {BTL}^{\mathrm {U,S}}_{\mathrm {N},\mathrm {N}^{-1}}(\mathcal {Z})_{\alpha }$ itself is decidable and solves the satisfiability problem.     

On set consensus numbers

It is conjectured that the only way a failure detector (FD) can help solving n-process tasks is by providing k-set consensus for some ${k\in\{1,\ldots,n\}}$ among all the processes. It was recently shown by Zieli??ski that any FD that allows for solving a given n-process task that is unsolvable read-write wait-free, also solves (n ? 1)-set consensus. In this paper, we provide a generalization of Zieli??ski??s result. We show that any FD that solves a colorless task that cannot be solved read-write k-resiliently, also solves k-set consensus. More generally, we show that every colorless task ${\mathcal{T}}$ can be characterized by its set consensus number: the largest ${k\in\{1,\ldots,n\}}$ such that ${\mathcal{T}}$ is solvable (k ? 1)-resiliently. A task ${\mathcal{T}}$ with set consensus number k is, in the failure detector sense, equivalent to k-set consensus, i.e., a FD solves ${\mathcal{T}}$ if and only if it solves k-set consensus. As a corollary, we determine the weakest FD for solving k-set consensus in every environment, i.e., for all assumptions on when and where failures might occur.     

Improving the lazy Krivine machine

Krivine presents the  machine, which produces weak head normal form results. Sestoft introduces several call-by-need variants of the  machine that implement result sharing via pushing update markers on the stack in a way similar to the TIM and the STG machine. When a sequence of consecutive markers appears on the stack, all but the first cause redundant updates. Improvements related to these sequences have dealt with either the consumption of the markers or the removal of the markers once they appear. Here we present an improvement that eliminates the production of marker sequences of length greater than one. This improvement results in the  machine, a more space and time efficient variant of . We then apply the classic optimization of short-circuiting operand variable dereferences to create the call-by-need  machine. Finally, we combine the two improvements in the  machine. On our benchmarks this machine uses half the stack space, performs one quarter as many updates, and executes between 27% faster and 17% slower than our ℒ variant of Sestoft’s lazy Krivine machine. More interesting is that on one benchmark ℒ, , and consume unbounded space, but consumes constant space. Our comparisons to Sestoft’s Mark 2 machine are not exact, however, since we restrict ourselves to unpreprocessed closed lambda terms. Our variant of his machine does no environment trimming, conversion to deBruijn-style variable access, and does not provide basic constants, data type constructors, or the recursive let. (The Y combinator is used instead.)     

Learning block-preserving graph patterns and its application to data mining

Recently, due to the rapid growth of electronic data having graph structures such as HTML and XML texts and chemical compounds, many researchers have been interested in data mining and machine learning techniques for finding useful patterns from graph-structured data (graph data). Since graph data contain a huge number of substructures and it tends to be computationally expensive to decide whether or not such data have given structural features, graph mining problems face computational difficulties. Let be a graph class which satisfies a connected hereditary property and contains infinitely many different biconnected graphs, and for which a special kind of the graph isomorphism problem can be computed in polynomial time. In this paper, we consider learning and mining problems for  . Firstly, we define a new graph pattern, which is called a block preserving graph pattern (bp-graph pattern) for  . Secondly, we present a polynomial time algorithm for deciding whether or not a given bp-graph pattern matches a given graph in  . Thirdly, by giving refinement operators over bp-graph patterns, we present a polynomial time algorithm for finding a minimally generalized bp-graph pattern for  . Outerplanar graphs are planar graphs which can be embedded in the plane in such a way that all of vertices lie on the outer boundary. Many pharmacologic chemical compounds are known to be represented by outerplanar graphs. The class of connected outerplanar graphs satisfies the above conditions for  . Next, we propose two incremental polynomial time algorithms for enumerating all frequent bp-graph patterns with respect to a given finite set of graphs in  . Finally, by reporting experimental results obtained by applying the two graph mining algorithms to a subset of the NCI dataset, we evaluate the performance of the two graph mining algorithms.     

Automata theory based on lattice-ordered semirings

In this paper, definitions of K{\mathcal{K}} automata, K{\mathcal{K}} regular languages, K{\mathcal{K}} regular expressions and K{\mathcal{K}} regular grammars based on lattice-ordered semirings are given. It is shown that K{\mathcal{K}}NFA is equivalent to K{\mathcal{K}}DFA under some finite condition, the Pump Lemma holds if K{\mathcal{K}} is finite, and Ke{{\mathcal{K}}}\epsilonNFA is equivalent to K{\mathcal{K}}NFA. Further, it is verified that the concatenation of K{\mathcal{K}} regular languages remains a K{\mathcal{K}} regular language. Similar to classical cases and automata theory based on lattice-ordered monoids, it is also found that K{\mathcal{K}}NFA, K{\mathcal{K}} regular expressions and K{\mathcal{K}} regular grammars are equivalent to each other when K{\mathcal{K}} is a complete lattice.     

Equiparadoxicality of Yablo’s Paradox and the Liar

It is proved that Yablo’s paradox and the Liar paradox are equiparadoxical, in the sense that their paradoxicality is based upon exactly the same circularity condition—for any frame ${\mathcal{K}}$ , the following are equivalent: (1) Yablo’s sequence leads to a paradox in ${\mathcal{K}}$ ; (2) the Liar sentence leads to a paradox in ${\mathcal{K}}$ ; (3) ${\mathcal{K}}$ contains odd cycles. This result does not conflict with Yablo’s claim that his sequence is non-self-referential. Rather, it gives Yablo’s paradox a new significance: his construction contributes a method by which we can eliminate the self-reference of a paradox without changing its circularity condition.     

Path Hitting in Acyclic Graphs

An instance of the path hitting problem consists of two families of paths, and ℋ, in a common undirected graph, where each path in ℋ is associated with a non-negative cost. We refer to and ℋ as the sets of demand and hitting paths, respectively. When p∈ℋ and share at least one mutual edge, we say that p hits q. The objective is to find a minimum cost subset of ℋ whose members collectively hit those of . In this paper we provide constant factor approximation algorithms for path hitting, confined to instances in which the underlying graph is a tree, a spider, or a star. Although such restricted settings may appear to be very simple, we demonstrate that they still capture some of the most basic covering problems in graphs. Our approach combines several novel ideas: We extend the algorithm of Garg, Vazirani and Yannakakis (Algorithmica, 18:3–20, 1997) for approximate multicuts and multicommodity flows in trees to prove new integrality properties; we present a reduction that involves multiple calls to this extended algorithm; and we introduce a polynomial-time solvable variant of the edge cover problem, which may be of independent interest. An extended abstract of this paper appeared in Proceedings of the 14th Annual European Symposium on Algorithms, 2006. This work is part of D. Segev’s Ph.D. thesis prepared at Tel-Aviv University under the supervision of Prof. Refael Hassin.     

Behavior of confined fluids in nanoslit pores: the normal pressure tensor

The aim of our research is to develop a theory, which can predict the behavior of confined fluids in nanoslit pores. The nanoslit pores studied in this work consist of two structureless and parallel walls in the xy plane located at z = 0 and z = H, in equilibrium with a bulk homogeneous fluid at the same temperature and at a given uniform bulk density. We have derived the following general equation for prediction of the normal pressure tensor P _zz of confined inhomogeneous fluids in nanoslit pores:

Exact Algorithms for Finding Longest Cycles in Claw-Free Graphs

The Hamiltonian Cycle problem is the problem of deciding whether an n-vertex graph G has a cycle passing through all vertices of G. This problem is a classic NP-complete problem. Finding an exact algorithm that solves it in ${\mathcal {O}}^{*}(\alpha^{n})$ time for some constant α<2 was a notorious open problem until very recently, when Björklund presented a randomized algorithm that uses ${\mathcal {O}}^{*}(1.657^{n})$ time and polynomial space. The Longest Cycle problem, in which the task is to find a cycle of maximum length, is a natural generalization of the Hamiltonian Cycle problem. For a claw-free graph G, finding a longest cycle is equivalent to finding a closed trail (i.e., a connected even subgraph, possibly consisting of a single vertex) that dominates the largest number of edges of some associated graph H. Using this translation we obtain two deterministic algorithms that solve the Longest Cycle problem, and consequently the Hamiltonian Cycle problem, for claw-free graphs: one algorithm that uses ${\mathcal {O}}^{*}(1.6818^{n})$ time and exponential space, and one algorithm that uses ${\mathcal {O}}^{*}(1.8878^{n})$ time and polynomial space.     

On the Relation between States and Maps in Infinite Dimensions

Relations between states and maps, which are known for quantum systems in finitedimensional Hilbert spaces, are formulated rigorously in geometrical terms with no use of coordinate (matrix) interpretation. In a tensor product realization they are represented simply by a permutation of factors. This leads to natural generalizations for infinite-dimensional Hilbert spaces and a simple proof of a generalized Choi Theorem. The natural framework is based on spaces of Hilbert-Schmidt operators and the corresponding tensor products of Hilbert spaces. It is proved that the corresponding isomorphisms cannot be naturally extended to compact (or bounded) operators, nor reduced to the trace-class operators. On the other hand, it is proven that there is a natural continuous map from trace-class operators on (with the nuclear norm) into compact operators mapping the space of all bounded operators on into trace class operators on (with the operator-norm). Also in the infinite-dimensional context, the Schmidt measure of entanglement and multipartite generalizations of state-maps relations are considered in the paper.     

Attractive energy contribution to nanoconfined fluids behavior: the normal pressure tensor

The aim of our research is to demonstrate the role of attractive intermolecular potential energy on normal pressure tensor of confined molecular fluids inside nanoslit pores of two structureless purely repulsive parallel walls in xy plane at z = 0 and z = H, in equilibrium with a bulk homogeneous fluid at the same temperature and at a uniform density. To achieve this we have derived the perturbation theory version of the normal pressure tensor of confined inhomogeneous fluids in nanoslit pores:

A Dynamic Logic of Agency II: Deterministic $${\mathcal{DLA}}$$ , Coalition Logic,and Game Theory

We continue the work initiated in Herzig and Lorini (J Logic Lang Inform, in press) whose aim is to provide a minimalistic logical framework combining the expressiveness of dynamic logic in which actions are first-class citizens in the object language, with the expressiveness of logics of agency such as STIT and logics of group capabilities such as CL and ATL. We present a logic called DDLA{\mathcal{DDLA}} (Deterministic Dynamic logic of Agency) which supports reasoning about actions and joint actions of agents and coalitions, and agentive and coalitional capabilities. In DDLA{\mathcal{DDLA}} it is supposed that, once all agents have selected a joint action, the effect of this joint action is deterministic. In order to assess DDLA{\mathcal{DDLA}} we prove that it embeds Coalition Logic. We then extend DDLA{\mathcal{DDLA}} with modal operators for agents’ preferences, and show that the resulting logic is sufficiently expressive to capture the game-theoretic concepts of best response and Nash equilibrium.     

A result on k-valent graphs and its application to a graph embedding problem

Summary It is proved that any n-vertex, k-valent undirected simple graph, G, contains a spanning tree with at least leaves. As a result of this it is shown that any such graph contains an independent set, of size at least n/5k, with the property that deleting the vertices in this set and their incident edges does not disconnect G. This latter result is applied by giving an improved upper bound on the area required to embed arbitrary graphs into grid graphs.