4 Search Results for "Martin, Russell"

Document
DOI: 10.4230/LIPIcs.TYPES.2016.13
On Subtyping in Type Theories with Canonical Objects

Authors: Georgiana Elena Lungu and Zhaohui Luo

Published in: LIPIcs, Volume 97, 22nd International Conference on Types for Proofs and Programs (TYPES 2016)

Abstract
How should one introduce subtyping into type theories with canonical objects such as Martin-Löf's type theory? It is known that the usual subsumptive subtyping is inadequate and it is understood, at least theoretically, that coercive subtyping should instead be employed. However, it has not been studied what the proper coercive subtyping mechanism is and how it should be used to capture intuitive notions of subtyping. In this paper, we introduce a type system with signatures where coercive subtyping relations can be specified, and argue that this provides a suitable subtyping mechanism for type theories with canonical objects. In particular, we show that the subtyping extension is well-behaved by relating it to the previous formulation of coercive subtyping. The paper then proceeds to study the connection with intuitive notions of subtyping. It first shows how a subsumptive subtyping system can be embedded faithfully. Then, it studies how Russell-style universe inclusions can be understood as coercions in our system. And finally, we study constructor subtyping as an example to illustrate that, sometimes, injectivity of coercions need be assumed in order to capture properly some notions of subtyping.
Cite as

Georgiana Elena Lungu and Zhaohui Luo. On Subtyping in Type Theories with Canonical Objects. In 22nd International Conference on Types for Proofs and Programs (TYPES 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 97, pp. 13:1-13:31, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{lungu_et_al:LIPIcs.TYPES.2016.13,
  author =	{Lungu, Georgiana Elena and Luo, Zhaohui},
  title =	{{On Subtyping in Type Theories with Canonical Objects}},
  booktitle =	{22nd International Conference on Types for Proofs and Programs (TYPES 2016)},
  pages =	{13:1--13:31},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-065-1},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{97},
  editor =	{Ghilezan, Silvia and Geuvers, Herman and Ivetic, Jelena},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.TYPES.2016.13},
  URN =		{urn:nbn:de:0030-drops-98496},
  doi =		{10.4230/LIPIcs.TYPES.2016.13},
  annote =	{Keywords: subtyping, type theory, conservative extension, canonical objects}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2018.25
Maximum Rooted Connected Expansion

Authors: Ioannis Lamprou, Russell Martin, Sven Schewe, Ioannis Sigalas, and Vassilis Zissimopoulos

Published in: LIPIcs, Volume 117, 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)

Abstract
Prefetching constitutes a valuable tool toward the goal of efficient Web surfing. As a result, estimating the amount of resources that need to be preloaded during a surfer's browsing becomes an important task. In this regard, prefetching can be modeled as a two-player combinatorial game [Fomin et al., Theoretical Computer Science 2014], where a surfer and a marker alternately play on a given graph (representing the Web graph). During its turn, the marker chooses a set of k nodes to mark (prefetch), whereas the surfer, represented as a token resting on graph nodes, moves to a neighboring node (Web resource). The surfer's objective is to reach an unmarked node before all nodes become marked and the marker wins. Intuitively, since the surfer is step-by-step traversing a subset of nodes in the Web graph, a satisfactory prefetching procedure would load in cache (without any delay) all resources lying in the neighborhood of this growing subset. Motivated by the above, we consider the following maximization problem to which we refer to as the Maximum Rooted Connected Expansion (MRCE) problem. Given a graph G and a root node v_0, we wish to find a subset of vertices S such that S is connected, S contains v_0 and the ratio |N[S]|/|S| is maximized, where N[S] denotes the closed neighborhood of S, that is, N[S] contains all nodes in S and all nodes with at least one neighbor in S. We prove that the problem is NP-hard even when the input graph G is restricted to be a split graph. On the positive side, we demonstrate a polynomial time approximation scheme for split graphs. Furthermore, we present a 1/6(1-1/e)-approximation algorithm for general graphs based on techniques for the Budgeted Connected Domination problem [Khuller et al., SODA 2014]. Finally, we provide a polynomial-time algorithm for the special case of interval graphs. Our algorithm returns an optimal solution for MRCE in O(n^3) time, where n is the number of nodes in G.
Cite as

Ioannis Lamprou, Russell Martin, Sven Schewe, Ioannis Sigalas, and Vassilis Zissimopoulos. Maximum Rooted Connected Expansion. In 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 117, pp. 25:1-25:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{lamprou_et_al:LIPIcs.MFCS.2018.25,
  author =	{Lamprou, Ioannis and Martin, Russell and Schewe, Sven and Sigalas, Ioannis and Zissimopoulos, Vassilis},
  title =	{{Maximum Rooted Connected Expansion}},
  booktitle =	{43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)},
  pages =	{25:1--25:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-086-6},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{117},
  editor =	{Potapov, Igor and Spirakis, Paul and Worrell, James},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2018.25},
  URN =		{urn:nbn:de:0030-drops-96076},
  doi =		{10.4230/LIPIcs.MFCS.2018.25},
  annote =	{Keywords: prefetching, domination, expansion, ratio}
}
Document
DOI: 10.4230/LIPIcs.WABI.2017.1
Disentangled Long-Read De Bruijn Graphs via Optical Maps

Authors: Bahar Alipanahi, Leena Salmela, Simon J. Puglisi, Martin Muggli, and Christina Boucher

Published in: LIPIcs, Volume 88, 17th International Workshop on Algorithms in Bioinformatics (WABI 2017)

Abstract
While long reads produced by third-generation sequencing technology from, e.g, Pacific Biosciences have been shown to increase the quality of draft genomes in repetitive regions, fundamental computational challenges remain in overcoming their high error rate and assembling them efficiently. In this paper we show that the de Bruijn graph built on the long reads can be efficiently and substantially disentangled using optical mapping data as auxiliary information. Fundamental to our approach is the use of the positional de Bruijn graph and a succinct data structure for constructing and traversing this graph. Our experimental results show that over 97.7% of directed cycles have been removed from the resulting positional de Bruijn graph as compared to its non-positional counterpart. Our results thus indicate that disentangling the de Bruijn graph using positional information is a promising direction for developing a simple and efficient assembly algorithm for long reads.
Cite as

Bahar Alipanahi, Leena Salmela, Simon J. Puglisi, Martin Muggli, and Christina Boucher. Disentangled Long-Read De Bruijn Graphs via Optical Maps. In 17th International Workshop on Algorithms in Bioinformatics (WABI 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 88, pp. 1:1-1:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{alipanahi_et_al:LIPIcs.WABI.2017.1,
  author =	{Alipanahi, Bahar and Salmela, Leena and Puglisi, Simon J. and Muggli, Martin and Boucher, Christina},
  title =	{{Disentangled Long-Read De Bruijn Graphs via Optical Maps}},
  booktitle =	{17th International Workshop on Algorithms in Bioinformatics (WABI 2017)},
  pages =	{1:1--1:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-050-7},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{88},
  editor =	{Schwartz, Russell and Reinert, Knut},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.WABI.2017.1},
  URN =		{urn:nbn:de:0030-drops-76614},
  doi =		{10.4230/LIPIcs.WABI.2017.1},
  annote =	{Keywords: Positional de Bruijn graph, Genome Assembly, Long Read Data, Optical maps}
}
Document
DOI: 10.4230/LIPIcs.OPODIS.2016.14
Deterministic Population Protocols for Exact Majority and Plurality

Authors: Leszek Gasieniec, David Hamilton, Russell Martin, Paul G. Spirakis, and Grzegorz Stachowiak

Published in: LIPIcs, Volume 70, 20th International Conference on Principles of Distributed Systems (OPODIS 2016)

Abstract
In this paper we study space-efficient deterministic population protocols for several variants of the majority problem including plurality consensus. We focus on space efficient majority protocols in populations with an arbitrary number of colours C represented by k-bit labels, where k = ceiling (log C). In particular, we present asymptotically space-optimal (with respect to the adopted k-bit representation of colours) protocols for (1) the absolute majority problem, i.e., a protocol which decides whether a single colour dominates all other colours considered together, and (2) the relative majority problem, also known in the literature as plurality consensus, in which colours declare their volume superiority versus other individual colours. The new population protocols proposed in this paper rely on a dynamic formulation of the majority problem in which the colours originally present in the population can be changed by an external force during the communication process. The considered dynamic formulation is based on the concepts studied by D. Angluin et al. and O. Michail et al. about stabilizing inputs and composition of population protocols. Also, the protocols presented in this paper use a composition of some known protocols for static and dynamic majority.
Cite as

Leszek Gasieniec, David Hamilton, Russell Martin, Paul G. Spirakis, and Grzegorz Stachowiak. Deterministic Population Protocols for Exact Majority and Plurality. In 20th International Conference on Principles of Distributed Systems (OPODIS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 70, pp. 14:1-14:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{gasieniec_et_al:LIPIcs.OPODIS.2016.14,
  author =	{Gasieniec, Leszek and Hamilton, David and Martin, Russell and Spirakis, Paul G. and Stachowiak, Grzegorz},
  title =	{{Deterministic Population Protocols for Exact Majority and Plurality}},
  booktitle =	{20th International Conference on Principles of Distributed Systems (OPODIS 2016)},
  pages =	{14:1--14:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-031-6},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{70},
  editor =	{Fatourou, Panagiota and Jim\'{e}nez, Ernesto and Pedone, Fernando},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2016.14},
  URN =		{urn:nbn:de:0030-drops-70837},
  doi =		{10.4230/LIPIcs.OPODIS.2016.14},
  annote =	{Keywords: Deterministic population protocols, majority, plurality consenus}
}
  • Refine by Author
  • 2 Martin, Russell
  • 1 Alipanahi, Bahar
  • 1 Boucher, Christina
  • 1 Gasieniec, Leszek
  • 1 Hamilton, David
  • Show More...

  • Refine by Classification
  • 1 Theory of computation → Approximation algorithms analysis

  • Refine by Keyword
  • 1 Deterministic population protocols
  • 1 Genome Assembly
  • 1 Long Read Data
  • 1 Optical maps
  • 1 Positional de Bruijn graph
  • Show More...

  • Refine by Type
  • 4 document

  • Refine by Publication Year
  • 2 2017
  • 2 2018

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact