8 Search Results for "Hutchison, David"

Document
DOI: 10.4230/LIPIcs.ICDT.2025.11
Semantic Foundations of Equality Saturation

Authors: Dan Suciu, Yisu Remy Wang, and Yihong Zhang

Published in: LIPIcs, Volume 328, 28th International Conference on Database Theory (ICDT 2025)

Abstract
Equality saturation is an emerging technique for program and query optimization developed in the programming language community. It performs term rewriting over an E-graph, a data structure that compactly represents a program space. Despite its popularity, the theory of equality saturation lags behind the practice. In this paper, we define a fixpoint semantics of equality saturation based on tree automata and uncover deep connections between equality saturation and the chase. We characterize the class of chase sequences that correspond to equality saturation. We study the complexities of terminations of equality saturation in three cases: single-instance, all-term-instance, and all-E-graph-instance. Finally, we define a syntactic criterion based on acyclicity that implies equality saturation termination.
Cite as

Dan Suciu, Yisu Remy Wang, and Yihong Zhang. Semantic Foundations of Equality Saturation. In 28th International Conference on Database Theory (ICDT 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 328, pp. 11:1-11:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{suciu_et_al:LIPIcs.ICDT.2025.11,
  author =	{Suciu, Dan and Wang, Yisu Remy and Zhang, Yihong},
  title =	{{Semantic Foundations of Equality Saturation}},
  booktitle =	{28th International Conference on Database Theory (ICDT 2025)},
  pages =	{11:1--11:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-364-5},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{328},
  editor =	{Roy, Sudeepa and Kara, Ahmet},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2025.11},
  URN =		{urn:nbn:de:0030-drops-229523},
  doi =		{10.4230/LIPIcs.ICDT.2025.11},
  annote =	{Keywords: the chase, equality saturation, term rewriting, tree automata, query optimization}
}
Document
Database Theory in Action
DOI: 10.4230/LIPIcs.ICDT.2025.34
Database Theory in Action: Search-Based Program Optimization

Authors: Yihong Zhang, Dan Suciu, Yisu Remy Wang, and Max Willsey

Published in: LIPIcs, Volume 328, 28th International Conference on Database Theory (ICDT 2025)

Abstract
Recent work in programming languages developed an approach to term rewritings based on equality saturation (EqSat), which, instead of applying destructively the rewrite rules, maintains all equivalent expressions in a structure called an E-graph. This paper describes two surprising connections between EqSat and databases, going both ways. On one hand equality saturation can be viewed as a query evaluation problem, with great benefits. On the other hand, most sophisticated SQL query optimizers are based on the Volcano/Cascades framework which, we explain, is a variant of EqSat.
Cite as

Yihong Zhang, Dan Suciu, Yisu Remy Wang, and Max Willsey. Database Theory in Action: Search-Based Program Optimization. In 28th International Conference on Database Theory (ICDT 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 328, pp. 34:1-34:6, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{zhang_et_al:LIPIcs.ICDT.2025.34,
  author =	{Zhang, Yihong and Suciu, Dan and Wang, Yisu Remy and Willsey, Max},
  title =	{{Database Theory in Action: Search-Based Program Optimization}},
  booktitle =	{28th International Conference on Database Theory (ICDT 2025)},
  pages =	{34:1--34:6},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-364-5},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{328},
  editor =	{Roy, Sudeepa and Kara, Ahmet},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2025.34},
  URN =		{urn:nbn:de:0030-drops-229759},
  doi =		{10.4230/LIPIcs.ICDT.2025.34},
  annote =	{Keywords: Query optimization, program optimization, Cascades framework, equality saturation, Datalog}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2025.24
Sampling List Packings

Authors: Evan Camrud, Ewan Davies, Alex Karduna, and Holden Lee

Published in: LIPIcs, Volume 325, 16th Innovations in Theoretical Computer Science Conference (ITCS 2025)

Abstract
We initiate the study of approximately counting the number of list packings of a graph. The analogous problem for usual vertex coloring and list coloring has attracted substantial attention. For list packing the setup is similar, but we seek a full decomposition of the lists of colors into pairwise-disjoint proper list colorings. The existence of a list packing implies the existence of a list coloring, but the converse is false. Recent works on list packing have focused on existence or extremal results of on the number of list packings, but here we turn to the algorithmic aspects of counting and sampling. In graphs of maximum degree Δ and when the number of colors is at least Ω(Δ²), we give a fully polynomial-time randomized approximation scheme (FPRAS) based on rapid mixing of a natural Markov chain (the Glauber dynamics) which we analyze with the path coupling technique. Some motivation for our work is the investigation of an atypical spin system, one where the number of spins for each vertex is much larger than the graph degree.
Cite as

Evan Camrud, Ewan Davies, Alex Karduna, and Holden Lee. Sampling List Packings. In 16th Innovations in Theoretical Computer Science Conference (ITCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 325, pp. 24:1-24:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{camrud_et_al:LIPIcs.ITCS.2025.24,
  author =	{Camrud, Evan and Davies, Ewan and Karduna, Alex and Lee, Holden},
  title =	{{Sampling List Packings}},
  booktitle =	{16th Innovations in Theoretical Computer Science Conference (ITCS 2025)},
  pages =	{24:1--24:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-361-4},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{325},
  editor =	{Meka, Raghu},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2025.24},
  URN =		{urn:nbn:de:0030-drops-226528},
  doi =		{10.4230/LIPIcs.ITCS.2025.24},
  annote =	{Keywords: List packing, Graph colouring, Markov chains, Path coupling}
}
Document
Survey
DOI: 10.4230/TGDK.1.1.11
How Does Knowledge Evolve in Open Knowledge Graphs?

Authors: Axel Polleres, Romana Pernisch, Angela Bonifati, Daniele Dell'Aglio, Daniil Dobriy, Stefania Dumbrava, Lorena Etcheverry, Nicolas Ferranti, Katja Hose, Ernesto Jiménez-Ruiz, Matteo Lissandrini, Ansgar Scherp, Riccardo Tommasini, and Johannes Wachs

Published in: TGDK, Volume 1, Issue 1 (2023): Special Issue on Trends in Graph Data and Knowledge. Transactions on Graph Data and Knowledge, Volume 1, Issue 1

Abstract
Openly available, collaboratively edited Knowledge Graphs (KGs) are key platforms for the collective management of evolving knowledge. The present work aims t o provide an analysis of the obstacles related to investigating and processing specifically this central aspect of evolution in KGs. To this end, we discuss (i) the dimensions of evolution in KGs, (ii) the observability of evolution in existing, open, collaboratively constructed Knowledge Graphs over time, and (iii) possible metrics to analyse this evolution. We provide an overview of relevant state-of-the-art research, ranging from metrics developed for Knowledge Graphs specifically to potential methods from related fields such as network science. Additionally, we discuss technical approaches - and their current limitations - related to storing, analysing and processing large and evolving KGs in terms of handling typical KG downstream tasks.
Cite as

Axel Polleres, Romana Pernisch, Angela Bonifati, Daniele Dell'Aglio, Daniil Dobriy, Stefania Dumbrava, Lorena Etcheverry, Nicolas Ferranti, Katja Hose, Ernesto Jiménez-Ruiz, Matteo Lissandrini, Ansgar Scherp, Riccardo Tommasini, and Johannes Wachs. How Does Knowledge Evolve in Open Knowledge Graphs?. In Special Issue on Trends in Graph Data and Knowledge. Transactions on Graph Data and Knowledge (TGDK), Volume 1, Issue 1, pp. 11:1-11:59, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@Article{polleres_et_al:TGDK.1.1.11,
  author =	{Polleres, Axel and Pernisch, Romana and Bonifati, Angela and Dell'Aglio, Daniele and Dobriy, Daniil and Dumbrava, Stefania and Etcheverry, Lorena and Ferranti, Nicolas and Hose, Katja and Jim\'{e}nez-Ruiz, Ernesto and Lissandrini, Matteo and Scherp, Ansgar and Tommasini, Riccardo and Wachs, Johannes},
  title =	{{How Does Knowledge Evolve in Open Knowledge Graphs?}},
  journal =	{Transactions on Graph Data and Knowledge},
  pages =	{11:1--11:59},
  year =	{2023},
  volume =	{1},
  number =	{1},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/TGDK.1.1.11},
  URN =		{urn:nbn:de:0030-drops-194855},
  doi =		{10.4230/TGDK.1.1.11},
  annote =	{Keywords: KG evolution, temporal KG, versioned KG, dynamic KG}
}
Document
DOI: 10.4230/DagRep.5.4.1
Assuring Resilience, Security and Privacy for Flexible Networked Systems and Organisations (Dagstuhl Seminar 15151)

Authors: David Hutchison, Klara Nahrstedt, Marcus Schöller, Indra Spiecker gen. Döhmann, and Markus Tauber

Published in: Dagstuhl Reports, Volume 5, Issue 4 (2015)

Abstract
Dagstuhl Seminar 15151 entitled “Assuring Resilience, Security and Privacy for Flexible Networked Systems and Organisations” brought together researchers from different disciplines in order to establish a research agenda for making future services in our increasingly connected world more resilient and secure, as well as addressing privacy. The participants came from a range of disciplines covering the techno-legal domain, resilience and systems security, and socio-technical concerns. The use case domains that were discussed during the Seminar covered the Internet of Things (IoT) as well as Cloud-based applications in which flexible service composition is a crucial element. From a starting point covering the “big picture”, the legal viewpoint, the technical viewpoint, and the organisational viewpoint, we derived initial research questions in small groups, and the questions and issues arising were then consolidated and refined. The groups discussed the issues in depth and have produced the report and the research agenda contained here.
Cite as

David Hutchison, Klara Nahrstedt, Marcus Schöller, Indra Spiecker gen. Döhmann, and Markus Tauber. Assuring Resilience, Security and Privacy for Flexible Networked Systems and Organisations (Dagstuhl Seminar 15151). In Dagstuhl Reports, Volume 5, Issue 4, pp. 1-17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@Article{hutchison_et_al:DagRep.5.4.1,
  author =	{Hutchison, David and Nahrstedt, Klara and Sch\"{o}ller, Marcus and Spiecker gen. D\"{o}hmann, Indra and Tauber, Markus},
  title =	{{Assuring Resilience, Security and Privacy for Flexible Networked Systems and Organisations (Dagstuhl Seminar 15151)}},
  pages =	{1--17},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2015},
  volume =	{5},
  number =	{4},
  editor =	{Hutchison, David and Nahrstedt, Klara and Sch\"{o}ller, Marcus and Spiecker gen. D\"{o}hmann, Indra and Tauber, Markus},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.5.4.1},
  URN =		{urn:nbn:de:0030-drops-52725},
  doi =		{10.4230/DagRep.5.4.1},
  annote =	{Keywords: Resilience, security, privacy, legal aspects, networked systems, organisations, society}
}
Document
DOI: 10.4230/DagSemProc.04411.1
04411 Abtracts Collection – Service Management and Self-Organization in IP-based Networks

Authors: Matthias Bossardt, Georg Carle, David Hutchison, Hermann de Meer, and Bernhard Plattner

Published in: Dagstuhl Seminar Proceedings, Volume 4411, Service Management and Self-Organization in IP-based Networks (2005)

Abstract
From 03.10.04 to 06.10.04, the Dagstuhl Seminar 04411 ``Service Management and Self-Organization in IP-based Networks'' was held in the International Conference and Research Center (IBFI), Schloss Dagstuhl. During the seminar, several participants presented their current research, and ongoing work and open problems were discussed. Abstracts of the presentations given during the seminar as well as abstracts of seminar results and ideas are put together in this paper. The first section describes the seminar topics and goals in general. Links to extended abstracts or full papers are provided, if available.
Cite as

Matthias Bossardt, Georg Carle, David Hutchison, Hermann de Meer, and Bernhard Plattner. 04411 Abtracts Collection – Service Management and Self-Organization in IP-based Networks. In Service Management and Self-Organization in IP-based Networks. Dagstuhl Seminar Proceedings, Volume 4411, pp. 1-18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2005)

Copy BibTex To Clipboard

@InProceedings{bossardt_et_al:DagSemProc.04411.1,
  author =	{Bossardt, Matthias and Carle, Georg and Hutchison, David and Meer, Hermann de and Plattner, Bernhard},
  title =	{{04411 Abtracts Collection – Service Management and Self-Organization in IP-based Networks}},
  booktitle =	{Service Management and Self-Organization in IP-based Networks},
  pages =	{1--18},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2005},
  volume =	{4411},
  editor =	{Matthias Bossardt and Georg Carle and D. Hutchison and Hermann de Meer and Bernhard Plattner},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.04411.1},
  URN =		{urn:nbn:de:0030-drops-1141},
  doi =		{10.4230/DagSemProc.04411.1},
  annote =	{Keywords: Service management , network service , self-organization , network management , programmable network , active network , peer-to-peer network ad-hoc network}
}
Document
DOI: 10.4230/DagSemProc.04411.2
04411 Preface – Service Management and Self-Organization in IP-based Networks

Authors: Matthias Bossardt, Georg Carle, David Hutchison, Hermann de Meer, and Bernhard Plattner

Published in: Dagstuhl Seminar Proceedings, Volume 4411, Service Management and Self-Organization in IP-based Networks (2005)

Abstract
Preface to the online proceedings of Dagstuhl Seminar 04411
Cite as

Matthias Bossardt, Georg Carle, David Hutchison, Hermann de Meer, and Bernhard Plattner. 04411 Preface – Service Management and Self-Organization in IP-based Networks. In Service Management and Self-Organization in IP-based Networks. Dagstuhl Seminar Proceedings, Volume 4411, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2005)

Copy BibTex To Clipboard

@InProceedings{bossardt_et_al:DagSemProc.04411.2,
  author =	{Bossardt, Matthias and Carle, Georg and Hutchison, David and Meer, Hermann de and Plattner, Bernhard},
  title =	{{04411 Preface – Service Management and Self-Organization in IP-based Networks}},
  booktitle =	{Service Management and Self-Organization in IP-based Networks},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2005},
  volume =	{4411},
  editor =	{Matthias Bossardt and Georg Carle and D. Hutchison and Hermann de Meer and Bernhard Plattner},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.04411.2},
  URN =		{urn:nbn:de:0030-drops-827},
  doi =		{10.4230/DagSemProc.04411.2},
  annote =	{Keywords: Service management , self-organization , network management}
}
Document
DOI: 10.4230/DagSemProc.04411.12
From Active Networks to Cognitive Networks

Authors: Manolis Sifalakis and David Hutchison

Published in: Dagstuhl Seminar Proceedings, Volume 4411, Service Management and Self-Organization in IP-based Networks (2005)

Abstract
Future networks need to be autonomic self-managed and provide resilient servicing, even when the hardware fails. To achieve this goal, two fundamental requirements need to be satisfied: (i) the service management and provisioning must be independent and decoupled of the infrastructure management, and (ii) a certain degree of cognitive behaviour needs to be achieved at the service management level. In achieving the first goal, which in turn will enable the pursuing of the second goal, active and programmable networks will play an important role. A problem though arises when we try to build and use actual active networks, as most research so far has focused at the node level and has left us with a unbridged diversity of platforms and execution environments, which are largely uninteroperable with each other. We introduce a toolkit that provides a set of mechanisms aiming to bridge this diversity and provide a set of functionalities and abstractions for uniform installation and deployment of services over active and programmable networks.
Cite as

Manolis Sifalakis and David Hutchison. From Active Networks to Cognitive Networks. In Service Management and Self-Organization in IP-based Networks. Dagstuhl Seminar Proceedings, Volume 4411, pp. 1-4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2005)

Copy BibTex To Clipboard

@InProceedings{sifalakis_et_al:DagSemProc.04411.12,
  author =	{Sifalakis, Manolis and Hutchison, David},
  title =	{{From Active Networks to Cognitive Networks}},
  booktitle =	{Service Management and Self-Organization in IP-based Networks},
  pages =	{1--4},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2005},
  volume =	{4411},
  editor =	{Matthias Bossardt and Georg Carle and D. Hutchison and Hermann de Meer and Bernhard Plattner},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.04411.12},
  URN =		{urn:nbn:de:0030-drops-967},
  doi =		{10.4230/DagSemProc.04411.12},
  annote =	{Keywords: Active networks , self organisation , service mobility , dynamic service deployment}
}
  • Refine by Type
  • 8 Document/PDF
  • 4 Document/HTML

  • Refine by Publication Year
  • 3 2025
  • 1 2023
  • 1 2015
  • 3 2005

  • Refine by Author
  • 4 Hutchison, David
  • 2 Bossardt, Matthias
  • 2 Carle, Georg
  • 2 Meer, Hermann de
  • 2 Plattner, Bernhard
  • Show More...

  • Refine by Series/Journal
  • 3 LIPIcs
  • 1 TGDK
  • 1 DagRep
  • 3 DagSemProc

  • Refine by Classification
  • 2 Theory of computation → Equational logic and rewriting
  • 1 Information systems → Data streaming
  • 1 Information systems → Graph-based database models
  • 1 Information systems → Web data description languages
  • 1 Mathematics of computing → Approximation algorithms
  • Show More...

  • Refine by Keyword
  • 2 Service management
  • 2 equality saturation
  • 2 network management
  • 2 self-organization
  • 1 Active networks
  • Show More...

Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

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