Centrum voor Wiskunde en Informatica
Centrum voor Wiskunde en Informatica
Byrka J.,Centrum voor Wiskunde en Informatica |
Byrka J.,TU Eindhoven |
Gawrychowski P.,Wrocław University |
Huber K.T.,University of East Anglia |
Kelk S.,Centrum voor Wiskunde en Informatica
Journal of Discrete Algorithms | Year: 2010
The study of phylogenetic networks is of great interest to computational evolutionary biology and numerous different types of such structures are known. This article addresses the following question concerning rooted versions of phylogenetic networks. What is the maximum value of p ∈ [0, 1] such that for every input set T of rooted triplets, there exists some network N such that at least p | T | of the triplets are consistent with N? We call an algorithm that computes such a network (where p is maximum) worst-case optimal. Here we prove that the set containing all triplets (the full triplet set) in some sense defines p. Moreover, given a network N that obtains a fraction p′ for the full triplet set (for any p′), we show how to efficiently modify N to obtain a fraction ≥ p′ for any given triplet set T. We demonstrate the power of this insight by presenting a worst-case optimal result for level-1 phylogenetic networks improving considerably upon the 5/12 fraction obtained recently by Jansson, Nguyen and Sung. For level-2 phylogenetic networks we show that p ≥ 0.61. We emphasize that, because we are taking | T | as a (trivial) upper bound on the size of an optimal solution for each specific input T, the results in this article do not exclude the existence of approximation algorithms that achieve approximation ratio better than p. Finally, we note that all the results in this article also apply to weighted triplet sets. © 2009 Elsevier B.V. All rights reserved.
Petreczky M.,Maastricht University |
van Schuppen J.H.,Centrum voor Wiskunde en Informatica
Systems and Control Letters | Year: 2010
In this paper we introduce the novel concept of a hybrid generating series and show that continuous state and output trajectories of bilinear hybrid systems can be described in terms of these series. The results represent an extension of the Fliess-series expansion for bilinear systems to hybrid systems. © 2010 Elsevier B.V. All rights reserved.
Beveridge A.,Macalester College |
Dudek A.,Western Michigan University |
Frieze A.,Carnegie Mellon University |
Muller T.,Centrum voor Wiskunde en Informatica
Combinatorics Probability and Computing | Year: 2012
Cops and robbers is a turn-based pursuit game played on a graph G. One robber is pursued by a set of cops. In each round, these agents move between vertices along the edges of the graph. The cop number c(G) denotes the minimum number of cops required to catch the robber in finite time. We study the cop number of geometric graphs. For points x1,...,xn ε A. R2, and rε +, the vertex set of the geometric graph G(x1,..., xn r) is the graph on these n points, with xi, xj adjacent when ∥xi ' xj ∥≤ r. We prove that c(G) ≤ 9 for any connected geometric graph G in R2 and we give an example of a connected geometric graph with c(G) = 3. We improve on our upper bound for random geometric graphs that are sufficiently dense. Let (n,r) denote the probability space of geometric graphs with n vertices chosen uniformly and independently from [0,1]2. For Gε A. (n,r), we show that with high probability (w.h.p.), if r ≥ K 1 (log n/n)1/4 then c(G)≤ 2, and if r ≥ K 2(log n/n) 1/5 then c(G) = 1, where K 1, K 2 > 0 are absolute constants. Finally, we provide a lower bound near the connectivity regime of (n,r): if r ≤ K 3 log n/then c(G) > 1 w.h.p., where K 3 > 0 is an absolute constant. © 2012 Cambridge University Press.
Su R.,TU Eindhoven |
van Schuppen J.H.,Centrum voor Wiskunde en Informatica |
Rooda J.E.,TU Eindhoven |
Hofkamp A.T.,TU Eindhoven
Automatica | Year: 2010
In Ramadge-Wonham supervisory control theory we often need to check nonconflict of plants and corresponding synthesized supervisors. For a large system such a check imposes a great computational challenge because of the complexity incurred by the composition of plants and supervisors. In this paper we present a novel procedure based on automaton abstractions, which removes internal transitions of relevant automata at each step, allowing the nonconflict check to be performed on relatively small automata, even though the original product system can be fairly large. © 2010 Elsevier Ltd. All rights reserved.
Ordonez Camacho D.,Catholic University of Louvain |
Mens K.,Catholic University of Louvain |
Brand M.v.d.,TU Eindhoven |
Vinju J.,Centrum voor Wiskunde en Informatica
Science of Computer Programming | Year: 2010
Automatically generating program translators from source and target language specifications is a non-trivial problem. In this paper we focus on the problem of automating the process of building translators between operations languages, a family of DSLs used to program satellite operations procedures. We exploit their similarities to semi-automatically build transformation tools between these DSLs. The input to our method is a collection of annotated context-free grammars. To simplify the overall translation process even more, we also propose an intermediate representation common to all operations languages. Finally, we discuss how to enrich our annotated grammars model with more advanced semantic annotations to provide a verification system for the translation process. We validate our approach by semi-automatically deriving translators between some real world operations languages, using the prototype tool which we implemented for that purpose. © 2009 Elsevier B.V. All rights reserved.
Aardal K.,Centrum voor Wiskunde en Informatica |
Aardal K.,TU Eindhoven |
Wolsey L.A.,Catholic University of Louvain
Mathematical Programming | Year: 2010
We study different extended formulations for the coefficients of P are small compared to the coefficients of A and T. In such cases the new variables μ appear to be good branching directions, and in certain circumstances permit one to deduce rapidly that the instance is infeasible.We give a polynomial time algorithm for identifying such P, T if possible, and for the case that A has one row a we analyze the reformulation when s = 1, that is, one μ-variable is introduced. In particular,we determine the integer width of the extended formulations in the direction of theμ-variable, and derive a lower bound on the Frobenius number of a.We conclude with some preliminary tests to see if the reformulations are effective when the number s of additional constraints and variables is limited. © Springer-Verlag 2008.
Kiltz E.,Centrum voor Wiskunde en Informatica |
O'Neill A.,Georgia Institute of Technology |
Smith A.,Pennsylvania State University
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) | Year: 2010
We show that the widely deployed RSA-OAEP encryption scheme of Bellare and Rogaway (Eurocrypt 1994), which combines RSA with two rounds of an underlying Feistel network whose hash (i.e., round) functions are modeled as random oracles, meets indistinguishability under chosen-plaintext attack (IND-CPA) in the standard model based on simple, non-interactive, and non-interdependent assumptions on RSA and the hash functions. To prove this, we first give a result on a more general notion called "padding-based" encryption, saying that such a scheme is IND-CPA if (1) its underlying padding transform satisfies a "fooling" condition against small-range distinguishers on a class of high-entropy input distributions, and (2) its trapdoor permutation is sufficiently lossy as defined by Peikert and Waters (STOC 2008). We then show that the first round of OAEP satifies condition (1) if its hash function is t-wise independent for appopriate t and that RSA satisfies condition (2) under the Φ-Hiding Assumption of Cachin et al. (Eurocrypt 1999). This appears to be the first non-trivial positive result about the instantiability of RSA-OAEP. In particular, it increases our confidence that chosen-plaintext attacks are unlikely to be found against the scheme. In contrast, RSA-OAEP's predecessor in PKCS #1 v1.5 was shown to be vulnerable to such attacks by Coron et al. (Eurocrypt 2000). © 2010 Springer-Verlag Berlin Heidelberg.
Pake A.D.B.,ABB |
Schumacher J.M.,Centrum voor Wiskunde en Informatica
European Control Conference, ECC 1999 - Conference Proceedings | Year: 2015
In this paper a problem of industrial interest is presented: the control of an industrial gas compressor. The main feature of the problem is that the throughput of a gas compressor is limited both above and below. When the compressor should supply a lower flow rate, an additional valve must be opened. Thus the controller has a natural two-mode structure, making it particularly suited for hybrid control. A model of the gas compressor system and a hybrid controller are presented. Some simulations results are presented, showing that the proposed controller performs well, even under rapid changes in the boundary conditions. © 1999 EUCA.
Sella L.,Centrum voor Wiskunde en Informatica |
Collins P.,Centrum voor Wiskunde en Informatica
2007 European Control Conference, ECC 2007 | Year: 2015
In this paper we develop general techniques to study stability of hybrid systems with linear continuous dynamics. These techniques are based on matrix analysis and study of differentiable manifolds. These techniques operate on the space of switching times of the hybrid systems. Some special techniques for hybrid systems with three dimensional state space are also developed. © 2007 EUCA.
Hildebrand M.,Centrum Voor Wiskunde en Informatica |
Hardman L.,Centrum Voor Wiskunde en Informatica
WWW 2013 Companion - Proceedings of the 22nd International Conference on World Wide Web | Year: 2013
Video content analysis and named entity extraction are increasingly used to automatically generate content annotations for TV programs. A potential use of these annotations is to provide an entry point to background information that users can consume on a second screen. Automatic enrichments are, however, meaningless when it is unclear to the user what they can do with them and why they would. We propose to contextualize the annotations by an explicit representation of discourse in the form of scene templates. Through content rules these templates are populated with the relevant annotations. We illustrate this idea with an example video and annotations generated in the LinkedTV1 project.