3 Search Results for "Hall, Tracy"

Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2019.34
Unlabeled Sample Compression Schemes and Corner Peelings for Ample and Maximum Classes

Authors: Jérémie Chalopin, Victor Chepoi, Shay Moran, and Manfred K. Warmuth

Published in: LIPIcs, Volume 132, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)

Abstract
We examine connections between combinatorial notions that arise in machine learning and topological notions in cubical/simplicial geometry. These connections enable to export results from geometry to machine learning. Our first main result is based on a geometric construction by H. Tracy Hall (2004) of a partial shelling of the cross-polytope which can not be extended. We use it to derive a maximum class of VC dimension 3 that has no corners. This refutes several previous works in machine learning from the past 11 years. In particular, it implies that the previous constructions of optimal unlabeled compression schemes for maximum classes are erroneous. On the positive side we present a new construction of an optimal unlabeled compression scheme for maximum classes. We leave as open whether our unlabeled compression scheme extends to ample (a.k.a. lopsided or extremal) classes, which represent a natural and far-reaching generalization of maximum classes. Towards resolving this question, we provide a geometric characterization in terms of unique sink orientations of the 1-skeletons of associated cubical complexes.
Cite as

Jérémie Chalopin, Victor Chepoi, Shay Moran, and Manfred K. Warmuth. Unlabeled Sample Compression Schemes and Corner Peelings for Ample and Maximum Classes. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 34:1-34:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{chalopin_et_al:LIPIcs.ICALP.2019.34,
  author =	{Chalopin, J\'{e}r\'{e}mie and Chepoi, Victor and Moran, Shay and Warmuth, Manfred K.},
  title =	{{Unlabeled Sample Compression Schemes and Corner Peelings for Ample and Maximum Classes}},
  booktitle =	{46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)},
  pages =	{34:1--34:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-109-2},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{132},
  editor =	{Baier, Christel and Chatzigiannakis, Ioannis and Flocchini, Paola and Leonardi, Stefano},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2019.34},
  URN =		{urn:nbn:de:0030-drops-106105},
  doi =		{10.4230/LIPIcs.ICALP.2019.34},
  annote =	{Keywords: VC-dimension, sample compression, Sauer-Shelah-Perles lemma, Sandwich lemma, maximum class, ample/extremal class, corner peeling, unique sink orientation}
}
Document
DOI: 10.4230/DagSemProc.05451.11
Using Program Slicing to Identify Faults in Software

Authors: Sue Black, Steve Counsell, Tracy Hall, and Paul Wernick

Published in: Dagstuhl Seminar Proceedings, Volume 5451, Beyond Program Slicing (2006)

Abstract
This study explores the relationship between program slices and faults. The aim is to investigate whether the characteristics of program slices can be used to identify fault-prone software components. Slicing metrics and dependence clusters are used to characterise the slicing profile of a software component, then the relationship between the slicing profile of the component and the faults in that component are then analysed. Faults can increase the likelihood of a system becoming unstable causing problems for the development and evolution of the system. Identifying faultprone components is difficult and reliable predictors of faultproneness not easily identifiable. Program slicing is an established software engineering technique for the detection and correction of specific faults. An investigation is carried out into whether the use of program slicing can be extended as a reliable tool to predict fault-prone software components. Preliminary results are promising suggesting that slicing may offer valuable insights into fault-proneness.
Cite as

Sue Black, Steve Counsell, Tracy Hall, and Paul Wernick. Using Program Slicing to Identify Faults in Software. In Beyond Program Slicing. Dagstuhl Seminar Proceedings, Volume 5451, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)

Copy BibTex To Clipboard

@InProceedings{black_et_al:DagSemProc.05451.11,
  author =	{Black, Sue and Counsell, Steve and Hall, Tracy and Wernick, Paul},
  title =	{{Using Program Slicing to Identify Faults in Software}},
  booktitle =	{Beyond Program Slicing},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2006},
  volume =	{5451},
  editor =	{David W. Binkley and Mark Harman and Jens Krinke},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.05451.11},
  URN =		{urn:nbn:de:0030-drops-5873},
  doi =		{10.4230/DagSemProc.05451.11},
  annote =	{Keywords: Program slicing, slicing metrics, fault proneness, software quality}
}
Document
DOI: 10.4230/DagSemProc.05451.7
Making Slicing Mainstream How can we be Weiser?

Authors: Karl Trygve Kalleberg, Tracy Hall, and Ran Ettinger

Published in: Dagstuhl Seminar Proceedings, Volume 5451, Beyond Program Slicing (2006)

Abstract
By now, the concept of program slicing has been known in the research community for around 25 years. As a research topic, it has enjoyed a fair share of popularity, evidenced by the number of articles published on the topic following Mark Weiser's seminal paper. However, outside research circles, program slicing appears to be virtually unknown. In this report, we take the premise that program slicing is both technically relevant, and has a sufficient theoretical foundation, to be applied in practice within the software industry. With this premise in mind, we ask ourselves, ``what are the mechanisms by which we as a community could make program slicing mainstream''?
Cite as

Karl Trygve Kalleberg, Tracy Hall, and Ran Ettinger. Making Slicing Mainstream How can we be Weiser?. In Beyond Program Slicing. Dagstuhl Seminar Proceedings, Volume 5451, pp. 1-11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)

Copy BibTex To Clipboard

@InProceedings{kalleberg_et_al:DagSemProc.05451.7,
  author =	{Kalleberg, Karl Trygve and Hall, Tracy and Ettinger, Ran},
  title =	{{Making Slicing Mainstream How can we be Weiser?}},
  booktitle =	{Beyond Program Slicing},
  pages =	{1--11},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2006},
  volume =	{5451},
  editor =	{David W. Binkley and Mark Harman and Jens Krinke},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.05451.7},
  URN =		{urn:nbn:de:0030-drops-4861},
  doi =		{10.4230/DagSemProc.05451.7},
  annote =	{Keywords: Program Slicing, Popularization}
}
  • Refine by Author
  • 2 Hall, Tracy
  • 1 Black, Sue
  • 1 Chalopin, Jérémie
  • 1 Chepoi, Victor
  • 1 Counsell, Steve
  • Show More...

  • Refine by Classification
  • 1 Mathematics of computing → Combinatorics
  • 1 Theory of computation → Computational geometry
  • 1 Theory of computation → Machine learning theory

  • Refine by Keyword
  • 1 Popularization
  • 1 Program Slicing
  • 1 Program slicing
  • 1 Sandwich lemma
  • 1 Sauer-Shelah-Perles lemma
  • Show More...

  • Refine by Type
  • 3 document

  • Refine by Publication Year
  • 2 2006
  • 1 2019

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