6 Search Results for "Chung, Benjamin"

Document
DOI: 10.4230/LIPIcs.STACS.2022.23
Blazing a Trail via Matrix Multiplications: A Faster Algorithm for Non-Shortest Induced Paths

Authors: Yung-Chung Chiu and Hsueh-I Lu

Published in: LIPIcs, Volume 219, 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)

Abstract
For vertices u and v of an n-vertex graph G, a uv-trail of G is an induced uv-path of G that is not a shortest uv-path of G. Berger, Seymour, and Spirkl [Discrete Mathematics 2021] gave the previously only known polynomial-time algorithm, running in O(n^{18}) time, to either output a uv-trail of G or ensure that G admits no uv-trail. We reduce the complexity to the time required to perform a poly-logarithmic number of multiplications of n²× n² Boolean matrices, leading to a largely improved O(n^{4.75})-time algorithm.
Cite as

Yung-Chung Chiu and Hsueh-I Lu. Blazing a Trail via Matrix Multiplications: A Faster Algorithm for Non-Shortest Induced Paths. In 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 219, pp. 23:1-23:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{chiu_et_al:LIPIcs.STACS.2022.23,
  author =	{Chiu, Yung-Chung and Lu, Hsueh-I},
  title =	{{Blazing a Trail via Matrix Multiplications: A Faster Algorithm for Non-Shortest Induced Paths}},
  booktitle =	{39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)},
  pages =	{23:1--23:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-222-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{219},
  editor =	{Berenbrink, Petra and Monmege, Benjamin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2022.23},
  URN =		{urn:nbn:de:0030-drops-158333},
  doi =		{10.4230/LIPIcs.STACS.2022.23},
  annote =	{Keywords: Induced subgraph, induced path, non-shortest path, dynamic data structure}
}
Document
Artifact
DOI: 10.4230/DARTS.5.2.8
On Julia’s Efficient Algorithm for Subtyping Union Types and Covariant Tuples (Artifact)

Authors: Benjamin Chung, Francesco Zappa Nardelli, and Jan Vitek

Published in: DARTS, Volume 5, Issue 2, Special Issue of the 33rd European Conference on Object-Oriented Programming (ECOOP 2019)

Abstract
This is the artifact for the pearl paper "On Julia’s efficient algorithm for subtyping union types and covariant tuples."
Cite as

Benjamin Chung, Francesco Zappa Nardelli, and Jan Vitek. On Julia’s Efficient Algorithm for Subtyping Union Types and Covariant Tuples (Artifact). In Special Issue of the 33rd European Conference on Object-Oriented Programming (ECOOP 2019). Dagstuhl Artifacts Series (DARTS), Volume 5, Issue 2, pp. 8:1-8:2, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@Article{chung_et_al:DARTS.5.2.8,
  author =	{Chung, Benjamin and Nardelli, Francesco Zappa and Vitek, Jan},
  title =	{{On Julia’s Efficient Algorithm for Subtyping Union Types and Covariant Tuples}},
  pages =	{8:1--8:2},
  journal =	{Dagstuhl Artifacts Series},
  ISSN =	{2509-8195},
  year =	{2019},
  volume =	{5},
  number =	{2},
  editor =	{Chung, Benjamin and Nardelli, Francesco Zappa and Vitek, Jan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DARTS.5.2.8},
  URN =		{urn:nbn:de:0030-drops-107855},
  doi =		{10.4230/DARTS.5.2.8},
  annote =	{Keywords: Type systems, subtyping, algorithmic type systems, distributive unions}
}
Document
Pearl
DOI: 10.4230/LIPIcs.ECOOP.2019.24
Julia’s Efficient Algorithm for Subtyping Unions and Covariant Tuples (Pearl)

Authors: Benjamin Chung, Francesco Zappa Nardelli, and Jan Vitek

Published in: LIPIcs, Volume 134, 33rd European Conference on Object-Oriented Programming (ECOOP 2019)

Abstract
The Julia programming language supports multiple dispatch and provides a rich type annotation language to specify method applicability. When multiple methods are applicable for a given call, Julia relies on subtyping between method signatures to pick the correct method to invoke. Julia’s subtyping algorithm is surprisingly complex, and determining whether it is correct remains an open question. In this paper, we focus on one piece of this problem: the interaction between union types and covariant tuples. Previous work normalized unions inside tuples to disjunctive normal form. However, this strategy has two drawbacks: complex type signatures induce space explosion, and interference between normalization and other features of Julia’s type system. In this paper, we describe the algorithm that Julia uses to compute subtyping between tuples and unions - an algorithm that is immune to space explosion and plays well with other features of the language. We prove this algorithm correct and complete against a semantic-subtyping denotational model in Coq.
Cite as

Benjamin Chung, Francesco Zappa Nardelli, and Jan Vitek. Julia’s Efficient Algorithm for Subtyping Unions and Covariant Tuples (Pearl). In 33rd European Conference on Object-Oriented Programming (ECOOP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 134, pp. 24:1-24:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{chung_et_al:LIPIcs.ECOOP.2019.24,
  author =	{Chung, Benjamin and Zappa Nardelli, Francesco and Vitek, Jan},
  title =	{{Julia’s Efficient Algorithm for Subtyping Unions and Covariant Tuples}},
  booktitle =	{33rd European Conference on Object-Oriented Programming (ECOOP 2019)},
  pages =	{24:1--24:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-111-5},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{134},
  editor =	{Donaldson, Alastair F.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ECOOP.2019.24},
  URN =		{urn:nbn:de:0030-drops-108165},
  doi =		{10.4230/LIPIcs.ECOOP.2019.24},
  annote =	{Keywords: Type systems, Subtyping, Union types}
}
Document
DOI: 10.4230/LIPIcs.ECOOP.2018.12
KafKa: Gradual Typing for Objects

Authors: Benjamin Chung, Paley Li, Francesco Zappa Nardelli, and Jan Vitek

Published in: LIPIcs, Volume 109, 32nd European Conference on Object-Oriented Programming (ECOOP 2018)

Abstract
A wide range of gradual type systems have been proposed, providing many languages with the ability to mix typed and untyped code. However, hiding under language details, these gradual type systems embody fundamentally different ideas of what it means to be well-typed. In this paper, we show that four of the most common gradual type systems provide distinct guarantees, and we give a formal framework for comparing gradual type systems for object-oriented languages. First, we show that the different gradual type systems are practically distinguishable via a three-part litmus test. We present a formal framework for defining and comparing gradual type systems. Within this framework, different gradual type systems become translations between a common source and target language, allowing for direct comparison of semantics and guarantees.
Cite as

Benjamin Chung, Paley Li, Francesco Zappa Nardelli, and Jan Vitek. KafKa: Gradual Typing for Objects. In 32nd European Conference on Object-Oriented Programming (ECOOP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 109, pp. 12:1-12:25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{chung_et_al:LIPIcs.ECOOP.2018.12,
  author =	{Chung, Benjamin and Li, Paley and Zappa Nardelli, Francesco and Vitek, Jan},
  title =	{{KafKa: Gradual Typing for Objects}},
  booktitle =	{32nd European Conference on Object-Oriented Programming (ECOOP 2018)},
  pages =	{12:1--12:25},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-079-8},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{109},
  editor =	{Millstein, Todd},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ECOOP.2018.12},
  URN =		{urn:nbn:de:0030-drops-92170},
  doi =		{10.4230/LIPIcs.ECOOP.2018.12},
  annote =	{Keywords: Gradual typing, object-orientation, language design, type systems}
}
Document
DOI: 10.4230/DARTS.4.3.10
KafKa: Gradual Typing for Objects (Artifact)

Authors: Benjamin Chung, Paley Li, Francesco Zappa Nardelli, and Jan Vitek

Published in: DARTS, Volume 4, Issue 3, Special Issue of the 32nd European Conference on Object-Oriented Programming (ECOOP 2018)

Abstract
A wide range of gradual type systems have been proposed, providing many languages with the ability to mix typed and untyped code. However, hiding under language details, these gradual type systems have fundamentally different ideas of what it means to be typed. In this paper, we show that four of the most common gradual type systems provide distinct guarantees, and we give a formal framework for comparing gradual type systems for object-oriented languages. First, we show that the different gradual type systems are practically distinguishable via a three-part litmus test. Then, we present a formal framework for defining and comparing gradual type systems. Within this framework, different gradual type systems become translations between a common source and target language, allowing for direct comparison of semantics and guarantees.
Cite as

Benjamin Chung, Paley Li, Francesco Zappa Nardelli, and Jan Vitek. KafKa: Gradual Typing for Objects (Artifact). In Special Issue of the 32nd European Conference on Object-Oriented Programming (ECOOP 2018). Dagstuhl Artifacts Series (DARTS), Volume 4, Issue 3, pp. 10:1-10:3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@Article{chung_et_al:DARTS.4.3.10,
  author =	{Chung, Benjamin and Li, Paley and Nardelli, Francesco Zappa and Vitek, Jan},
  title =	{{KafKa: Gradual Typing for Objects (Artifact)}},
  pages =	{10:1--10:3},
  journal =	{Dagstuhl Artifacts Series},
  ISSN =	{2509-8195},
  year =	{2018},
  volume =	{4},
  number =	{3},
  editor =	{Chung, Benjamin and Li, Paley and Nardelli, Francesco Zappa and Vitek, Jan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DARTS.4.3.10},
  URN =		{urn:nbn:de:0030-drops-92411},
  doi =		{10.4230/DARTS.4.3.10},
  annote =	{Keywords: Gradual typing, object-orientation, language design, type systems}
}
Document
DOI: 10.4230/DARTS.1.1.3
A Theory of Tagged Objects (Artifact)

Authors: Joseph Lee, Jonathan Aldrich, Troy Shaw, Alex Potanin, and Benjamin Chung

Published in: DARTS, Volume 1, Issue 1, Special Issue of the 29th European Conference on Object-Oriented Programming (ECOOP 2015)

Abstract
A compiler and interpreter for Wyvern programming language written in Java and hosted on http://github.com/wyvernlang/wyvern and some sample programs (.wyv) including the main example from the paper in borderedwindow.wyv. We also include an extract of all the unit tests of which a large number may be designed to fail -- therefore they are best run using JUnit which can be done by checking out the source tree from the GitHub project link above.
Cite as

Joseph Lee, Jonathan Aldrich, Troy Shaw, Alex Potanin, and Benjamin Chung. A Theory of Tagged Objects (Artifact). In Special Issue of the 29th European Conference on Object-Oriented Programming (ECOOP 2015). Dagstuhl Artifacts Series (DARTS), Volume 1, Issue 1, pp. 3:1-3:3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@Article{lee_et_al:DARTS.1.1.3,
  author =	{Lee, Joseph and Aldrich, Jonathan and Shaw, Troy and Potanin, Alex and Chung, Benjamin},
  title =	{{A Theory of Tagged Objects (Artifact)}},
  pages =	{3:1--3:3},
  journal =	{Dagstuhl Artifacts Series},
  ISSN =	{2509-8195},
  year =	{2015},
  volume =	{1},
  number =	{1},
  editor =	{Lee, Joseph and Aldrich, Jonathan and Shaw, Troy and Potanin, Alex and Chung, Benjamin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DARTS.1.1.3},
  URN =		{urn:nbn:de:0030-drops-55121},
  doi =		{10.4230/DARTS.1.1.3},
  annote =	{Keywords: objects, classes, tags, nominal and structural types}
}
  • Refine by Author
  • 5 Chung, Benjamin
  • 4 Vitek, Jan
  • 2 Li, Paley
  • 2 Nardelli, Francesco Zappa
  • 2 Zappa Nardelli, Francesco
  • Show More...

  • Refine by Classification
  • 2 Theory of computation → Type theory
  • 1 Mathematics of computing → Graph algorithms
  • 1 Software and its engineering → General programming languages
  • 1 Software and its engineering → Semantics

  • Refine by Keyword
  • 2 Gradual typing
  • 2 Type systems
  • 2 language design
  • 2 object-orientation
  • 2 type systems
  • Show More...

  • Refine by Type
  • 6 document

  • Refine by Publication Year
  • 2 2018
  • 2 2019
  • 1 2015
  • 1 2022

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