The Provenance of Elegance in Computation - Essays Dedicated to Val Tannen

<!DOCTYPE html> <html lang="en"> <head> <meta charset="utf-8" /> <meta http-equiv="X-UA-Compatible" content="IE=edge" /> <meta name="google" content="notranslate"> <meta http-equiv="Content-Language" content="en"> <meta name="viewport" content="width=device-width, initial-scale=1" /> <meta name="csrf-token" content="S52CZAhrcW2rIq23IfK43MFr8aBPZDRrFAQt9Wlh" /> <link rel="canonical" href="https://drops.dagstuhl.de/entities/volume/OASIcs-volume-119" /> <title>The Provenance of Elegance in Computation - Essays Dedicated to Val Tannen</title> <link rel="icon" href="https://drops.dagstuhl.de/favicon.ico" /> <link rel="stylesheet" href="https://drops.dagstuhl.de/css/app.css?drops-core-2024-10-22" /> </head> <body> <nav class="navbar main fixed-top navbar-expand-lg navbar-light bg-light"> <div class="container-fluid"> <a class="navbar-brand" href="https://www.dagstuhl.de"> <img class="lzi-logo" src="https://drops.dagstuhl.de/images/LZI-Logo.jpg" width="84" height=62" alt="Schloss Dagstuhl - LZI - Logo" /> </a> <button class="navbar-toggler" type="button" data-bs-toggle="collapse" data-bs-target="#navbarSupportedContent" aria-controls="navbarSupportedContent" aria-expanded="false" aria-label="Toggle navigation"> <span class="navbar-toggler-icon"></span> </button> <div class="collapse navbar-collapse" id="navbarSupportedContent"> <ul class="navbar-nav me-auto mb-2 mb-lg-0"> <li class="nav-item" style="white-space: nowrap"> <a class="nav-link" href="https://drops.dagstuhl.de"> <i class="bi bi-house large-icon"></i> DROPS </a> </li> <li class="nav-item dropdown"> <a class="nav-link dropdown-toggle" href="#" id="navbarDropdownSeries" role="button" data-bs-toggle="dropdown" aria-expanded="false"> <i class="bi bi-journals large-icon"></i> Series </a> <ul class="dropdown-menu" aria-labelledby="navbarDropdown"> <li><a class="dropdown-item" href="https://drops.dagstuhl.de/entities/series/LIPIcs"> LIPIcs – Leibniz International Proceedings in Informatics </a> </li> <li><a class="dropdown-item" href="https://drops.dagstuhl.de/entities/series/OASIcs"> OASIcs – Open Access Series in Informatics </a> </li> <li><a class="dropdown-item" href="https://drops.dagstuhl.de/entities/series/DFU"> Dagstuhl Follow-Ups </a> </li> <li><a class="dropdown-item" href="https://drops.dagstuhl.de/entities/series/DagAnnRep"> Schloss Dagstuhl Jahresbericht </a> </li> <li class="dropdown-divider"></li> <li> <a class="dropdown-item" href="/#discontinued-series">Discontinued Series</a> </li> </ul> </li> <li class="nav-item dropdown"> <a class="nav-link dropdown-toggle" href="#" id="navbarDropdownJournals" role="button" data-bs-toggle="dropdown" aria-expanded="false"> <i class="bi bi-journal large-icon"></i> Journals </a> <ul class="dropdown-menu" aria-labelledby="navbarDropdown"> <li><a class="dropdown-item" href="https://drops.dagstuhl.de/entities/journal/DARTS"> DARTS – Dagstuhl Artifacts Series </a> </li> <li><a class="dropdown-item" href="https://drops.dagstuhl.de/entities/journal/DagRep"> Dagstuhl Reports </a> </li> <li><a class="dropdown-item" href="https://drops.dagstuhl.de/entities/journal/DagMan"> Dagstuhl Manifestos </a> </li> <li><a class="dropdown-item" href="https://drops.dagstuhl.de/entities/journal/LITES"> LITES – Leibniz Transactions on Embedded Systems </a> </li> <li><a class="dropdown-item" href="https://drops.dagstuhl.de/entities/journal/TGDK"> TGDK – Transactions on Graph Data and Knowledge </a> </li> </ul> </li> <li class="nav-item dropdown"> <a class="nav-link dropdown-toggle" href="#" id="navbarDropdownConferences" role="button" data-bs-toggle="dropdown" aria-expanded="false"> <i class="bi bi-people large-icon"></i> Conferences </a> <ul class="dropdown-menu conference-dropdown" aria-labelledby="navbarDropdown"> <div class="row"> <div class="col-sm-4 nav-conference-col"> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/AFT"> AFT </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/AIB"> AIB </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/AofA"> AofA </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/APPROX"> APPROX </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/ATMOS"> ATMOS </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/CALCO"> CALCO </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/CCC"> CCC </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/CONCUR"> CONCUR </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/COSIT"> COSIT </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/CP"> CP </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/CPM"> CPM </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/CSL"> CSL </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/DISC"> DISC </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/DITAM"> DITAM </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/DNA"> DNA </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/ECOOP"> ECOOP </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/ECRTS"> ECRTS </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/ESA"> ESA </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/FAB"> FAB </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/FMBC"> FMBC </a> </li> </div> <div class="col-sm-4 nav-conference-col"> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/FORC"> FORC </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/FSCD"> FSCD </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/FSTTCS"> FSTTCS </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/FUN"> FUN </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/GD"> GD </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/GIScience"> GIScience </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/ICALP"> ICALP </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/ICDT"> ICDT </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/ICPEC"> ICPEC </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/IPEC"> IPEC </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/iPMVM"> iPMVM </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/ISAAC"> ISAAC </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/ITC"> ITC </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/ITCS"> ITCS </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/ITP"> ITP </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/LDK"> LDK </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/MFCS"> MFCS </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/Microservices"> Microservices </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/NG-RES"> NG-RES </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/OPODIS"> OPODIS </a> </li> </div> <div class="col-sm-4 nav-conference-col"> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/PARMA"> PARMA </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/RANDOM"> RANDOM </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/SAND"> SAND </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/SAT"> SAT </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/SEA"> SEA </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/SLATE"> SLATE </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/SNAPL"> SNAPL </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/SoCG"> SoCG </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/STACS"> STACS </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/SWAT"> SWAT </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/TIME"> TIME </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/Tokenomics"> Tokenomics </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/TQC"> TQC </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/TYPES"> TYPES </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/WABI"> WABI </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/WCET"> WCET </a> </li> </div> </div> </ul> </li> <li class="nav-item"> <a class="nav-link" href="https://drops.dagstuhl.de/docs/about" id="navbarAbout"> <i class="bi bi-info-circle large-icon"></i><span class="nav-text-about-drops"> About DROPS</span> </a> </li> </ul> <form class="navbar-search d-flex" action="https://drops.dagstuhl.de/search" method="post"> <input type="hidden" name="_token" value="S52CZAhrcW2rIq23IfK43MFr8aBPZDRrFAQt9Wlh" autocomplete="off"> <div class="input-group"> <input class="form-control" type="search" placeholder="Search" aria-label="Search" name="term" autocomplete="off" maxlength="600"> <button class="btn btn-outline-success" type="submit"> <i class="bi bi-search" style="color: #000"></i> </button> </div> </form> <ul class="navbar-nav nav-metadata"> <li class="nav-item dropdown"> <a class="nav-link dropdown-toggle" id="navbarDropdownMetadata" role="button" data-bs-toggle="dropdown" aria-expanded="false"> <i class="bi bi-database-down large-icon"></i><span class="nav-text-metadata">Metadata Export</span> </a> <ul class="dropdown-menu dropdown-metadata" aria-labelledby="navbarDropdownMetadata"> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/metadata">Metadata Export</a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/oai?verb=Identify" target="_blank">OAI Interface</a> </li> </ul> </li> </ul> </div> </div> </nav> <div id="app" data-release="drops-core-2024-10-22" class="container "> <div id="_top-of-page"></div> <div class="fixed-search-button"><i class="bi bi-search"></i></div> <div class="volume-portal"> <br> <div class="entity-type volume"> <div> <span class="entity-type-name"> <i class="bi bi-book-half"></i> Volume </span> <span class="sharing-section"> <span class="sharing-buttons"> <span class="dropdown"> <a class="btn sharing-btn metadata dropdown-toggle" href="#" role="button" data-bs-toggle="dropdown" aria-expanded="false"><i class="bi bi-download"></i></a> <ul class="dropdown-menu dropdown-menu-end"> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/volume/OASIcs-volume-119/metadata/xml"> Export XML </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/volume/OASIcs-volume-119/metadata/acm-xml"> Export ACM-XML </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/volume/OASIcs-volume-119/metadata/doaj-xml"> Export DOAJ-XML </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/volume/OASIcs-volume-119/metadata/schema-org"> Export Schema.org </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/volume/OASIcs-volume-119/metadata/bibtex"> Export BibTeX </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/volume/OASIcs-volume-119/metadata/html"> Export HTML </a> </li> </ul> </span> </span> </span> </div> </div> <hr> <div> <h4>OASIcs, Volume 119</h4> <h1>The Provenance of Elegance in Computation - Essays Dedicated to Val Tannen</h1> </div> <section class="volume-issue-header mb-4"> <hr/> <section class="is-part-of"> <ul> <li> <span>Part of:</span> <span style="white-space: nowrap"> <i class="bi bi-journals"></i> Series: </span> <a href="https://drops.dagstuhl.de/entities/series/OASIcs">Open Access Series in Informatics (OASIcs)</a> <br> <span style="visibility: hidden">Part of:</span> <span style="white-space: nowrap"> <i class="bi bi-people"></i> Conference: </span> <a href="https://drops.dagstuhl.de/entities/conference/Tannen">Festschrift Val Tannen </a> </li> </ul> </section> <hr/> <div class="mt-5 row"> <div class="col-lg-3 mb-3"> <section class="thumbnail"> <img src="https://drops.dagstuhl.de/storage/01oasics/oasics-vol119-tannens-festschrift/thumbnails/OASIcs.Tannen/OASIcs.Tannen.png" alt="Thumbnail PDF" /> </section> </div> <div class="col-lg-6"> <section class="mb-5"> <h4>Event</h4> <a href="https://www.cis.upenn.edu/~val/home.html"> Tannen's Festschrift, May 24-25, 2024, University of Pennsylvania, Philadelphia, PA, USA </a> </section> <section class="editors mb-5"> <h4>Editors</h4> <div class="author person-details"> <div> <span class="name"><b>Antoine Amarilli</b></span> <a href="https://orcid.org/0000-0002-7977-4441"><img class="orcid-logo" src="https://drops.dagstuhl.de/images/orcid.png" alt="ORCID-Logo"></a> <a href="mailto:a3nm@a3nm.net"><i class="bi bi-envelope"></i></a> <a href="https://drops.dagstuhl.de/search/documents?author=Amarilli, Antoine"><small><i class="bi bi-search"></i></small></a> </div> <ul> <li class="affiliation">Télécom Paris, France</li> </ul> </div> <div class="author person-details"> <div> <span class="name"><b>Alin Deutsch</b></span> <a href="mailto:abdeutsch@ucsd.edu"><i class="bi bi-envelope"></i></a> <a href="https://drops.dagstuhl.de/search/documents?author=Deutsch, Alin"><small><i class="bi bi-search"></i></small></a> </div> <ul> <li class="affiliation">University of California, San Diego, USA</li> </ul> </div> </section> </div> <div class="col-lg-3"> <section class="mb-5"> <h4>Publication Details</h4> <ul> <li>published at: 2024-06-07</li> <li>Publisher: Schloss Dagstuhl – Leibniz-Zentrum für Informatik</li> <li>ISBN: 978-3-95977-320-1</li> <li>DBLP: <a href="https://dblp.org/db/conf/birthday/tannen2024"> db/conf/birthday/tannen2024 </a> </li> </ul> </section> <br> <section> <h4>Access Numbers</h4> <ul> <li> <a href="#" class="btn-statistics" data-entity="volume/OASIcs-volume-119" data-title="The Provenance of Elegance in Computation - Essays Dedicated to Val Tannen"> <i class="bi bi-graph-up"></i> Detailed Access Statistics available here </a> </li> <li> Total Document Accesses (updated on a weekly basis): <div class="stats-total"> <div class="stats total-downloads"> <div class="circle"> <div class="number" data-number="0">0</div> </div> <div class="label">PDF Downloads</div> </div> <div class="stats total-metadata-views"> <div class="circle"> <div class="number" data-number="0">0</div> </div> <div class="label">Metadata Views</div> </div> </div>  </li> </ul> </section> </div> </div> <div id="end-of-header"></div> </section> <div class="row mt-2"> <div class="col-sm-9 mt-2"> <h2>Documents <span class="btn badge color-dark _filter-info"></span></h2> <div class="documents"> <div class="no-results alert alert-danger -hidden"> No documents found matching your filter selection. </div> <div class="entity-list-item document card m-3" data-show="1" data-permanent-id="document/10.4230/OASIcs.Tannen"> <div class="entity-type"><i class="bi bi-file-earmark"></i> Document</div> <div class="category">Complete Volume</div> <div class="doi"><a href="https://doi.org/10.4230/OASIcs.Tannen">DOI: 10.4230/OASIcs.Tannen</a></div> <aside> <a class="icon-btn" style="color: red" href="https://drops.dagstuhl.de/storage/01oasics/oasics-vol119-tannens-festschrift/OASIcs.Tannen/OASIcs.Tannen.pdf" data-bs-toggle="tooltip" title="View PDF"><i class="bi bi-file-earmark-pdf-fill"></i></a><a class="icon-btn" style="color: #0d6efd!important;" href="https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.Tannen" data-bs-toggle="tooltip" title="View Detailed Metadata"><i class="bi bi-info-circle"></i></a><br/> <a class="icon-btn investigation" href="#" data-bs-toggle="collapse" data-bs-target="#abstract-20187" aria-expanded="false" aria-controls="collapseAbstract" title="Show Abstract"><span class="tooltip-wrapper" data-bs-toggle="tooltip" title="Show Abstract"><i class="bi bi-card-text"></i></span></a><a class="icon-btn investigation" href="#" data-bs-toggle="collapse" data-bs-target="#bibtex-20187" aria-expanded="false" aria-controls="collapseBibtex" title="Show BibTex"><span class="tooltip-wrapper" data-bs-toggle="tooltip" title="Show BibTex"><i class="bi bi-chat-left-quote"></i></a><br/><a class="icon-btn btn-statistics" data-entity="document/10.4230/OASIcs.Tannen" data-bs-toggle="tooltip" data-title="OASIcs, Volume 119, Tannen's Festschrift, Complete Volume" href="#" title="Access Statistics"><i class="bi bi-graph-up"></i></a> </aside> <div class="selectors"> <span data-key="dagstuhl.contributor.author" data-value="Amarilli, Antoine"></span> <span data-key="dagstuhl.contributor.author" data-value="Deutsch, Alin"></span> <span data-key="dagstuhl.subject.classification" data-value="Information systems"></span> </div> <div class="card-body"> <h5 class="card-title"> <a href="https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.Tannen"> OASIcs, Volume 119, Tannen's Festschrift, Complete Volume </a> </h5> <p class="card-text small authors"> <b>Authors:</b> Antoine Amarilli and Alin Deutsch </p> <div class="row"> <div class="collapse" id="abstract-20187"> <hr/> <h5 data-bs-toggle="collapse" data-bs-target="#abstract-20187">Abstract <span style="float: right; cursor: pointer"><i class="bi bi-chevron-up"></i></span></h5> <div class="abstract monospace"> OASIcs, Volume 119, Tannen's Festschrift, Complete Volume </div> </div> </div> <div class="row"> <div class="collapse" id="bibtex-20187"> <hr/> <h5 data-bs-toggle="collapse" data-bs-target="#bibtex-20187">Cite as <span style="float: right; cursor: pointer"><i class="bi bi-chevron-up"></i></span></h5> <p class="small">The Provenance of Elegance in Computation - Essays Dedicated to Val Tannen. Open Access Series in Informatics (OASIcs), Volume 119, pp. 1-196, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)</p> <hr/> <a href="#" class="btn btn-primary btn-xs copy-to-clipboard" title="Copy to clipboard" data-selector="bibtex-20187-input"><i class="bi bi-clipboard"></i> Copy BibTex To Clipboard<span class="bi bi-check -hidden" style="padding-left: 1em; font-weight: bold"></span></a><br/><br/> <pre class="bibtex">@Proceedings{amarilli_et_al:OASIcs.Tannen, title = {{OASIcs, Volume 119, Tannen's Festschrift, Complete Volume}}, booktitle = {The Provenance of Elegance in Computation - Essays Dedicated to Val Tannen}, pages = {1--196}, series = {Open Access Series in Informatics (OASIcs)}, ISBN = {978-3-95977-320-1}, ISSN = {2190-6807}, year = {2024}, volume = {119}, editor = {Amarilli, Antoine and Deutsch, Alin}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.Tannen}, URN = {urn:nbn:de:0030-drops-200953}, doi = {10.4230/OASIcs.Tannen}, annote = {Keywords: OASIcs, Volume 119, Tannen's Festschrift, Complete Volume} }</pre> <textarea style="position: absolute; top: 200vh" id="bibtex-20187-input">@Proceedings{amarilli_et_al:OASIcs.Tannen, title = {{OASIcs, Volume 119, Tannen's Festschrift, Complete Volume}}, booktitle = {The Provenance of Elegance in Computation - Essays Dedicated to Val Tannen}, pages = {1--196}, series = {Open Access Series in Informatics (OASIcs)}, ISBN = {978-3-95977-320-1}, ISSN = {2190-6807}, year = {2024}, volume = {119}, editor = {Amarilli, Antoine and Deutsch, Alin}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.Tannen}, URN = {urn:nbn:de:0030-drops-200953}, doi = {10.4230/OASIcs.Tannen}, annote = {Keywords: OASIcs, Volume 119, Tannen's Festschrift, Complete Volume} }</textarea> </div> </div> </div> </div> <div class="entity-list-item document card m-3" data-show="1" data-permanent-id="document/10.4230/OASIcs.Tannen.0"> <div class="entity-type"><i class="bi bi-file-earmark"></i> Document</div> <div class="category">Front Matter</div> <div class="doi"><a href="https://doi.org/10.4230/OASIcs.Tannen.0">DOI: 10.4230/OASIcs.Tannen.0</a></div> <aside> <a class="icon-btn" style="color: red" href="https://drops.dagstuhl.de/storage/01oasics/oasics-vol119-tannens-festschrift/OASIcs.Tannen.0/OASIcs.Tannen.0.pdf" data-bs-toggle="tooltip" title="View PDF"><i class="bi bi-file-earmark-pdf-fill"></i></a><a class="icon-btn" style="color: #0d6efd!important;" href="https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.Tannen.0" data-bs-toggle="tooltip" title="View Detailed Metadata"><i class="bi bi-info-circle"></i></a><br/> <a class="icon-btn investigation" href="#" data-bs-toggle="collapse" data-bs-target="#abstract-20188" aria-expanded="false" aria-controls="collapseAbstract" title="Show Abstract"><span class="tooltip-wrapper" data-bs-toggle="tooltip" title="Show Abstract"><i class="bi bi-card-text"></i></span></a><a class="icon-btn investigation" href="#" data-bs-toggle="collapse" data-bs-target="#bibtex-20188" aria-expanded="false" aria-controls="collapseBibtex" title="Show BibTex"><span class="tooltip-wrapper" data-bs-toggle="tooltip" title="Show BibTex"><i class="bi bi-chat-left-quote"></i></a><br/><a class="icon-btn btn-statistics" data-entity="document/10.4230/OASIcs.Tannen.0" data-bs-toggle="tooltip" data-title="Front Matter, Table of Contents, Preface, Conference Organization" href="#" title="Access Statistics"><i class="bi bi-graph-up"></i></a> </aside> <div class="selectors"> <span data-key="dagstuhl.contributor.author" data-value="Amarilli, Antoine"></span> <span data-key="dagstuhl.contributor.author" data-value="Deutsch, Alin"></span> <span data-key="dagstuhl.subject.classification" data-value="Information systems"></span> </div> <div class="card-body"> <h5 class="card-title"> <a href="https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.Tannen.0"> Front Matter, Table of Contents, Preface, Conference Organization </a> </h5> <p class="card-text small authors"> <b>Authors:</b> Antoine Amarilli and Alin Deutsch </p> <div class="row"> <div class="collapse" id="abstract-20188"> <hr/> <h5 data-bs-toggle="collapse" data-bs-target="#abstract-20188">Abstract <span style="float: right; cursor: pointer"><i class="bi bi-chevron-up"></i></span></h5> <div class="abstract monospace"> Front Matter, Table of Contents, Preface, Conference Organization </div> </div> </div> <div class="row"> <div class="collapse" id="bibtex-20188"> <hr/> <h5 data-bs-toggle="collapse" data-bs-target="#bibtex-20188">Cite as <span style="float: right; cursor: pointer"><i class="bi bi-chevron-up"></i></span></h5> <p class="small">The Provenance of Elegance in Computation - Essays Dedicated to Val Tannen. Open Access Series in Informatics (OASIcs), Volume 119, pp. 0:i-0:xii, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)</p> <hr/> <a href="#" class="btn btn-primary btn-xs copy-to-clipboard" title="Copy to clipboard" data-selector="bibtex-20188-input"><i class="bi bi-clipboard"></i> Copy BibTex To Clipboard<span class="bi bi-check -hidden" style="padding-left: 1em; font-weight: bold"></span></a><br/><br/> <pre class="bibtex">@InProceedings{amarilli_et_al:OASIcs.Tannen.0, author = {Amarilli, Antoine and Deutsch, Alin}, title = {{Front Matter, Table of Contents, Preface, Conference Organization}}, booktitle = {The Provenance of Elegance in Computation - Essays Dedicated to Val Tannen}, pages = {0:i--0:xii}, series = {Open Access Series in Informatics (OASIcs)}, ISBN = {978-3-95977-320-1}, ISSN = {2190-6807}, year = {2024}, volume = {119}, editor = {Amarilli, Antoine and Deutsch, Alin}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.Tannen.0}, URN = {urn:nbn:de:0030-drops-200962}, doi = {10.4230/OASIcs.Tannen.0}, annote = {Keywords: Front Matter, Table of Contents, Preface, Conference Organization} }</pre> <textarea style="position: absolute; top: 200vh" id="bibtex-20188-input">@InProceedings{amarilli_et_al:OASIcs.Tannen.0, author = {Amarilli, Antoine and Deutsch, Alin}, title = {{Front Matter, Table of Contents, Preface, Conference Organization}}, booktitle = {The Provenance of Elegance in Computation - Essays Dedicated to Val Tannen}, pages = {0:i--0:xii}, series = {Open Access Series in Informatics (OASIcs)}, ISBN = {978-3-95977-320-1}, ISSN = {2190-6807}, year = {2024}, volume = {119}, editor = {Amarilli, Antoine and Deutsch, Alin}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.Tannen.0}, URN = {urn:nbn:de:0030-drops-200962}, doi = {10.4230/OASIcs.Tannen.0}, annote = {Keywords: Front Matter, Table of Contents, Preface, Conference Organization} }</textarea> </div> </div> </div> </div> <div class="entity-list-item document card m-3" data-show="1" data-permanent-id="document/10.4230/OASIcs.Tannen.1"> <div class="entity-type"><i class="bi bi-file-earmark"></i> Document</div> <div class="doi"><a href="https://doi.org/10.4230/OASIcs.Tannen.1">DOI: 10.4230/OASIcs.Tannen.1</a></div> <aside> <a class="icon-btn" style="color: red" href="https://drops.dagstuhl.de/storage/01oasics/oasics-vol119-tannens-festschrift/OASIcs.Tannen.1/OASIcs.Tannen.1.pdf" data-bs-toggle="tooltip" title="View PDF"><i class="bi bi-file-earmark-pdf-fill"></i></a><a class="icon-btn" style="color: #0d6efd!important;" href="https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.Tannen.1" data-bs-toggle="tooltip" title="View Detailed Metadata"><i class="bi bi-info-circle"></i></a><br/> <a class="icon-btn investigation" href="#" data-bs-toggle="collapse" data-bs-target="#abstract-20189" aria-expanded="false" aria-controls="collapseAbstract" title="Show Abstract"><span class="tooltip-wrapper" data-bs-toggle="tooltip" title="Show Abstract"><i class="bi bi-card-text"></i></span></a><a class="icon-btn investigation" href="#" data-bs-toggle="collapse" data-bs-target="#bibtex-20189" aria-expanded="false" aria-controls="collapseBibtex" title="Show BibTex"><span class="tooltip-wrapper" data-bs-toggle="tooltip" title="Show BibTex"><i class="bi bi-chat-left-quote"></i></a><br/><a class="icon-btn btn-statistics" data-entity="document/10.4230/OASIcs.Tannen.1" data-bs-toggle="tooltip" data-title="Explaining Enterprise Knowledge Graphs with Large Language Models and Ontological Reasoning" href="#" title="Access Statistics"><i class="bi bi-graph-up"></i></a> </aside> <div class="selectors"> <span data-key="dagstuhl.contributor.author" data-value="Baldazzi, Teodoro"></span> <span data-key="dagstuhl.contributor.author" data-value="Bellomarini, Luigi"></span> <span data-key="dagstuhl.contributor.author" data-value="Ceri, Stefano"></span> <span data-key="dagstuhl.contributor.author" data-value="Colombo, Andrea"></span> <span data-key="dagstuhl.contributor.author" data-value="Gentili, Andrea"></span> <span data-key="dagstuhl.contributor.author" data-value="Sallinger, Emanuel"></span> <span data-key="dagstuhl.contributor.author" data-value="Atzeni, Paolo"></span> <span data-key="dagstuhl.subject.classification" data-value="Computing methodologies → Knowledge representation and reasoning"></span> <span data-key="dagstuhl.subject.classification" data-value="Computing methodologies → Natural language processing"></span> <span data-key="dagstuhl.subject.classification" data-value="Theory of computation → Data provenance"></span> </div> <div class="card-body"> <h5 class="card-title"> <a href="https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.Tannen.1"> Explaining Enterprise Knowledge Graphs with Large Language Models and Ontological Reasoning </a> </h5> <p class="card-text small authors"> <b>Authors:</b> Teodoro Baldazzi, Luigi Bellomarini, Stefano Ceri, Andrea Colombo, Andrea Gentili, Emanuel Sallinger, and Paolo Atzeni </p> <div class="row"> <div class="collapse" id="abstract-20189"> <hr/> <h5 data-bs-toggle="collapse" data-bs-target="#abstract-20189">Abstract <span style="float: right; cursor: pointer"><i class="bi bi-chevron-up"></i></span></h5> <div class="abstract monospace"> In recent times, the demand for transparency and accountability in AI-driven decisions has intensified, particularly in high-stakes domains like finance and bio-medicine. This focus on the provenance of AI-generated conclusions underscores the need for decision-making processes that are not only transparent but also readily interpretable by humans, to built trust of both users and stakeholders. In this context, the integration of state-of-the-art Large Language Models (LLMs) with logic-oriented Enterprise Knowledge Graphs (EKGs) and the broader scope of Knowledge Representation and Reasoning (KRR) methodologies is currently at the cutting edge of industrial and academic research across numerous data-intensive areas. Indeed, such a synergy is paramount as LLMs bring a layer of adaptability and human-centric understanding that complements the structured insights of EKGs. Conversely, the central role of ontological reasoning is to capture the domain knowledge, accurately handling complex tasks over a given realm of interest, and to infuse the process with transparency and a clear provenance-based explanation of the conclusions drawn, addressing the fundamental challenge of LLMs' inherent opacity and fostering trust and accountability in AI applications. In this paper, we propose a novel neuro-symbolic framework that leverages the underpinnings of provenance in ontological reasoning to enhance state-of-the-art LLMs with domain awareness and explainability, enabling them to act as natural language interfaces to EKGs. </div> </div> </div> <div class="row"> <div class="collapse" id="bibtex-20189"> <hr/> <h5 data-bs-toggle="collapse" data-bs-target="#bibtex-20189">Cite as <span style="float: right; cursor: pointer"><i class="bi bi-chevron-up"></i></span></h5> <p class="small">Teodoro Baldazzi, Luigi Bellomarini, Stefano Ceri, Andrea Colombo, Andrea Gentili, Emanuel Sallinger, and Paolo Atzeni. Explaining Enterprise Knowledge Graphs with Large Language Models and Ontological Reasoning. In The Provenance of Elegance in Computation - Essays Dedicated to Val Tannen. Open Access Series in Informatics (OASIcs), Volume 119, pp. 1:1-1:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)</p> <hr/> <a href="#" class="btn btn-primary btn-xs copy-to-clipboard" title="Copy to clipboard" data-selector="bibtex-20189-input"><i class="bi bi-clipboard"></i> Copy BibTex To Clipboard<span class="bi bi-check -hidden" style="padding-left: 1em; font-weight: bold"></span></a><br/><br/> <pre class="bibtex">@InProceedings{baldazzi_et_al:OASIcs.Tannen.1, author = {Baldazzi, Teodoro and Bellomarini, Luigi and Ceri, Stefano and Colombo, Andrea and Gentili, Andrea and Sallinger, Emanuel and Atzeni, Paolo}, title = {{Explaining Enterprise Knowledge Graphs with Large Language Models and Ontological Reasoning}}, booktitle = {The Provenance of Elegance in Computation - Essays Dedicated to Val Tannen}, pages = {1:1--1:20}, series = {Open Access Series in Informatics (OASIcs)}, ISBN = {978-3-95977-320-1}, ISSN = {2190-6807}, year = {2024}, volume = {119}, editor = {Amarilli, Antoine and Deutsch, Alin}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.Tannen.1}, URN = {urn:nbn:de:0030-drops-200971}, doi = {10.4230/OASIcs.Tannen.1}, annote = {Keywords: provenance, ontological reasoning, language models, knowledge graphs} }</pre> <textarea style="position: absolute; top: 200vh" id="bibtex-20189-input">@InProceedings{baldazzi_et_al:OASIcs.Tannen.1, author = {Baldazzi, Teodoro and Bellomarini, Luigi and Ceri, Stefano and Colombo, Andrea and Gentili, Andrea and Sallinger, Emanuel and Atzeni, Paolo}, title = {{Explaining Enterprise Knowledge Graphs with Large Language Models and Ontological Reasoning}}, booktitle = {The Provenance of Elegance in Computation - Essays Dedicated to Val Tannen}, pages = {1:1--1:20}, series = {Open Access Series in Informatics (OASIcs)}, ISBN = {978-3-95977-320-1}, ISSN = {2190-6807}, year = {2024}, volume = {119}, editor = {Amarilli, Antoine and Deutsch, Alin}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.Tannen.1}, URN = {urn:nbn:de:0030-drops-200971}, doi = {10.4230/OASIcs.Tannen.1}, annote = {Keywords: provenance, ontological reasoning, language models, knowledge graphs} }</textarea> </div> </div> </div> </div> <div class="entity-list-item document card m-3" data-show="1" data-permanent-id="document/10.4230/OASIcs.Tannen.2"> <div class="entity-type"><i class="bi bi-file-earmark"></i> Document</div> <div class="doi"><a href="https://doi.org/10.4230/OASIcs.Tannen.2">DOI: 10.4230/OASIcs.Tannen.2</a></div> <aside> <a class="icon-btn" style="color: red" href="https://drops.dagstuhl.de/storage/01oasics/oasics-vol119-tannens-festschrift/OASIcs.Tannen.2/OASIcs.Tannen.2.pdf" data-bs-toggle="tooltip" title="View PDF"><i class="bi bi-file-earmark-pdf-fill"></i></a><a class="icon-btn" style="color: #0d6efd!important;" href="https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.Tannen.2" data-bs-toggle="tooltip" title="View Detailed Metadata"><i class="bi bi-info-circle"></i></a><br/> <a class="icon-btn investigation" href="#" data-bs-toggle="collapse" data-bs-target="#abstract-20190" aria-expanded="false" aria-controls="collapseAbstract" title="Show Abstract"><span class="tooltip-wrapper" data-bs-toggle="tooltip" title="Show Abstract"><i class="bi bi-card-text"></i></span></a><a class="icon-btn investigation" href="#" data-bs-toggle="collapse" data-bs-target="#bibtex-20190" aria-expanded="false" aria-controls="collapseBibtex" title="Show BibTex"><span class="tooltip-wrapper" data-bs-toggle="tooltip" title="Show BibTex"><i class="bi bi-chat-left-quote"></i></a><br/><a class="icon-btn btn-statistics" data-entity="document/10.4230/OASIcs.Tannen.2" data-bs-toggle="tooltip" data-title="Traversal-Invariant Characterizations of Logarithmic Space" href="#" title="Access Statistics"><i class="bi bi-graph-up"></i></a> </aside> <div class="selectors"> <span data-key="dagstuhl.contributor.author" data-value="Bhaskar, Siddharth"></span> <span data-key="dagstuhl.contributor.author" data-value="Lindell, Steven"></span> <span data-key="dagstuhl.contributor.author" data-value="Weinstein, Scott"></span> <span data-key="dagstuhl.subject.classification" data-value="Theory of computation → Finite Model Theory"></span> </div> <div class="card-body"> <h5 class="card-title"> <a href="https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.Tannen.2"> Traversal-Invariant Characterizations of Logarithmic Space </a> </h5> <p class="card-text small authors"> <b>Authors:</b> Siddharth Bhaskar, Steven Lindell, and Scott Weinstein </p> <div class="row"> <div class="collapse" id="abstract-20190"> <hr/> <h5 data-bs-toggle="collapse" data-bs-target="#abstract-20190">Abstract <span style="float: right; cursor: pointer"><i class="bi bi-chevron-up"></i></span></h5> <div class="abstract monospace"> We give a novel descriptive-complexity theoretic characterization of L and NL computable queries over finite structures using traversal invariance. We summarize this as (N)L = FO + (breadth-first) traversal-invariance. </div> </div> </div> <div class="row"> <div class="collapse" id="bibtex-20190"> <hr/> <h5 data-bs-toggle="collapse" data-bs-target="#bibtex-20190">Cite as <span style="float: right; cursor: pointer"><i class="bi bi-chevron-up"></i></span></h5> <p class="small">Siddharth Bhaskar, Steven Lindell, and Scott Weinstein. Traversal-Invariant Characterizations of Logarithmic Space. In The Provenance of Elegance in Computation - Essays Dedicated to Val Tannen. Open Access Series in Informatics (OASIcs), Volume 119, pp. 2:1-2:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)</p> <hr/> <a href="#" class="btn btn-primary btn-xs copy-to-clipboard" title="Copy to clipboard" data-selector="bibtex-20190-input"><i class="bi bi-clipboard"></i> Copy BibTex To Clipboard<span class="bi bi-check -hidden" style="padding-left: 1em; font-weight: bold"></span></a><br/><br/> <pre class="bibtex">@InProceedings{bhaskar_et_al:OASIcs.Tannen.2, author = {Bhaskar, Siddharth and Lindell, Steven and Weinstein, Scott}, title = {{Traversal-Invariant Characterizations of Logarithmic Space}}, booktitle = {The Provenance of Elegance in Computation - Essays Dedicated to Val Tannen}, pages = {2:1--2:17}, series = {Open Access Series in Informatics (OASIcs)}, ISBN = {978-3-95977-320-1}, ISSN = {2190-6807}, year = {2024}, volume = {119}, editor = {Amarilli, Antoine and Deutsch, Alin}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.Tannen.2}, URN = {urn:nbn:de:0030-drops-200984}, doi = {10.4230/OASIcs.Tannen.2}, annote = {Keywords: Model theory, finite model theory, descriptive complexity theory, logarithmic space, graph traversals} }</pre> <textarea style="position: absolute; top: 200vh" id="bibtex-20190-input">@InProceedings{bhaskar_et_al:OASIcs.Tannen.2, author = {Bhaskar, Siddharth and Lindell, Steven and Weinstein, Scott}, title = {{Traversal-Invariant Characterizations of Logarithmic Space}}, booktitle = {The Provenance of Elegance in Computation - Essays Dedicated to Val Tannen}, pages = {2:1--2:17}, series = {Open Access Series in Informatics (OASIcs)}, ISBN = {978-3-95977-320-1}, ISSN = {2190-6807}, year = {2024}, volume = {119}, editor = {Amarilli, Antoine and Deutsch, Alin}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.Tannen.2}, URN = {urn:nbn:de:0030-drops-200984}, doi = {10.4230/OASIcs.Tannen.2}, annote = {Keywords: Model theory, finite model theory, descriptive complexity theory, logarithmic space, graph traversals} }</textarea> </div> </div> </div> </div> <div class="entity-list-item document card m-3" data-show="1" data-permanent-id="document/10.4230/OASIcs.Tannen.3"> <div class="entity-type"><i class="bi bi-file-earmark"></i> Document</div> <div class="doi"><a href="https://doi.org/10.4230/OASIcs.Tannen.3">DOI: 10.4230/OASIcs.Tannen.3</a></div> <aside> <a class="icon-btn" style="color: red" href="https://drops.dagstuhl.de/storage/01oasics/oasics-vol119-tannens-festschrift/OASIcs.Tannen.3/OASIcs.Tannen.3.pdf" data-bs-toggle="tooltip" title="View PDF"><i class="bi bi-file-earmark-pdf-fill"></i></a><a class="icon-btn" style="color: #0d6efd!important;" href="https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.Tannen.3" data-bs-toggle="tooltip" title="View Detailed Metadata"><i class="bi bi-info-circle"></i></a><br/> <a class="icon-btn investigation" href="#" data-bs-toggle="collapse" data-bs-target="#abstract-20191" aria-expanded="false" aria-controls="collapseAbstract" title="Show Abstract"><span class="tooltip-wrapper" data-bs-toggle="tooltip" title="Show Abstract"><i class="bi bi-card-text"></i></span></a><a class="icon-btn investigation" href="#" data-bs-toggle="collapse" data-bs-target="#bibtex-20191" aria-expanded="false" aria-controls="collapseBibtex" title="Show BibTex"><span class="tooltip-wrapper" data-bs-toggle="tooltip" title="Show BibTex"><i class="bi bi-chat-left-quote"></i></a><br/><a class="icon-btn btn-statistics" data-entity="document/10.4230/OASIcs.Tannen.3" data-bs-toggle="tooltip" data-title="Semiring Provenance in the Infinite" href="#" title="Access Statistics"><i class="bi bi-graph-up"></i></a> </aside> <div class="selectors"> <span data-key="dagstuhl.contributor.author" data-value="Brinke, Sophie"></span> <span data-key="dagstuhl.contributor.author" data-value="Grädel, Erich"></span> <span data-key="dagstuhl.contributor.author" data-value="Mrkonjić, Lovro"></span> <span data-key="dagstuhl.contributor.author" data-value="Naaf, Matthias"></span> <span data-key="dagstuhl.subject.classification" data-value="Theory of computation → Finite Model Theory"></span> </div> <div class="card-body"> <h5 class="card-title"> <a href="https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.Tannen.3"> Semiring Provenance in the Infinite </a> </h5> <p class="card-text small authors"> <b>Authors:</b> Sophie Brinke, Erich Grädel, Lovro Mrkonjić, and Matthias Naaf </p> <div class="row"> <div class="collapse" id="abstract-20191"> <hr/> <h5 data-bs-toggle="collapse" data-bs-target="#abstract-20191">Abstract <span style="float: right; cursor: pointer"><i class="bi bi-chevron-up"></i></span></h5> <div class="abstract monospace"> Semiring provenance evaluates database queries or logical statements not just by true or false but by values in some commutative semiring. This permits to track which combinations of atomic facts are responsible for the truth of a statement, and to derive further information, for instance concerning costs, confidence scores, number of proof trees, or access levels to protected data. The focus of this approach, proposed and developed to a large extent by Val Tannen and his collaborators, has first been on (positive) database query languages, but has later been extended, again in collaboration with Val, to a systematic semiring semantics for first-order logic (and other logical systems), as well as to a method for the strategy analysis of games. So far, semiring provenance has been studied for finite structures. To extend the semiring provenance approach for first-order logic to infinite domains, the semirings need to be equipped with addition and multiplication operators over infinite collections of values. This needs solid algebraic foundations, and we study here the necessary and desirable properties of semirings with infinitary operations to provide a well-defined and informative provenance analysis over infinite domains. We show that, with suitable definitions for such infinitary semiring, large parts of the theory of semiring provenance can be succesfully generalised to infinite structures. </div> </div> </div> <div class="row"> <div class="collapse" id="bibtex-20191"> <hr/> <h5 data-bs-toggle="collapse" data-bs-target="#bibtex-20191">Cite as <span style="float: right; cursor: pointer"><i class="bi bi-chevron-up"></i></span></h5> <p class="small">Sophie Brinke, Erich Grädel, Lovro Mrkonjić, and Matthias Naaf. Semiring Provenance in the Infinite. In The Provenance of Elegance in Computation - Essays Dedicated to Val Tannen. Open Access Series in Informatics (OASIcs), Volume 119, pp. 3:1-3:26, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)</p> <hr/> <a href="#" class="btn btn-primary btn-xs copy-to-clipboard" title="Copy to clipboard" data-selector="bibtex-20191-input"><i class="bi bi-clipboard"></i> Copy BibTex To Clipboard<span class="bi bi-check -hidden" style="padding-left: 1em; font-weight: bold"></span></a><br/><br/> <pre class="bibtex">@InProceedings{brinke_et_al:OASIcs.Tannen.3, author = {Brinke, Sophie and Gr\"{a}del, Erich and Mrkonji\'{c}, Lovro and Naaf, Matthias}, title = {{Semiring Provenance in the Infinite}}, booktitle = {The Provenance of Elegance in Computation - Essays Dedicated to Val Tannen}, pages = {3:1--3:26}, series = {Open Access Series in Informatics (OASIcs)}, ISBN = {978-3-95977-320-1}, ISSN = {2190-6807}, year = {2024}, volume = {119}, editor = {Amarilli, Antoine and Deutsch, Alin}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.Tannen.3}, URN = {urn:nbn:de:0030-drops-200997}, doi = {10.4230/OASIcs.Tannen.3}, annote = {Keywords: Semiring semantics, first-order logic, semirings with infinitary operations} }</pre> <textarea style="position: absolute; top: 200vh" id="bibtex-20191-input">@InProceedings{brinke_et_al:OASIcs.Tannen.3, author = {Brinke, Sophie and Gr\"{a}del, Erich and Mrkonji\'{c}, Lovro and Naaf, Matthias}, title = {{Semiring Provenance in the Infinite}}, booktitle = {The Provenance of Elegance in Computation - Essays Dedicated to Val Tannen}, pages = {3:1--3:26}, series = {Open Access Series in Informatics (OASIcs)}, ISBN = {978-3-95977-320-1}, ISSN = {2190-6807}, year = {2024}, volume = {119}, editor = {Amarilli, Antoine and Deutsch, Alin}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.Tannen.3}, URN = {urn:nbn:de:0030-drops-200997}, doi = {10.4230/OASIcs.Tannen.3}, annote = {Keywords: Semiring semantics, first-order logic, semirings with infinitary operations} }</textarea> </div> </div> </div> </div> <div class="entity-list-item document card m-3" data-show="1" data-permanent-id="document/10.4230/OASIcs.Tannen.4"> <div class="entity-type"><i class="bi bi-file-earmark"></i> Document</div> <div class="doi"><a href="https://doi.org/10.4230/OASIcs.Tannen.4">DOI: 10.4230/OASIcs.Tannen.4</a></div> <aside> <a class="icon-btn" style="color: red" href="https://drops.dagstuhl.de/storage/01oasics/oasics-vol119-tannens-festschrift/OASIcs.Tannen.4/OASIcs.Tannen.4.pdf" data-bs-toggle="tooltip" title="View PDF"><i class="bi bi-file-earmark-pdf-fill"></i></a><a class="icon-btn" style="color: #0d6efd!important;" href="https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.Tannen.4" data-bs-toggle="tooltip" title="View Detailed Metadata"><i class="bi bi-info-circle"></i></a><br/> <a class="icon-btn investigation" href="#" data-bs-toggle="collapse" data-bs-target="#abstract-20192" aria-expanded="false" aria-controls="collapseAbstract" title="Show Abstract"><span class="tooltip-wrapper" data-bs-toggle="tooltip" title="Show Abstract"><i class="bi bi-card-text"></i></span></a><a class="icon-btn investigation" href="#" data-bs-toggle="collapse" data-bs-target="#bibtex-20192" aria-expanded="false" aria-controls="collapseBibtex" title="Show BibTex"><span class="tooltip-wrapper" data-bs-toggle="tooltip" title="Show BibTex"><i class="bi bi-chat-left-quote"></i></a><br/><a class="icon-btn btn-statistics" data-entity="document/10.4230/OASIcs.Tannen.4" data-bs-toggle="tooltip" data-title="Annotation and More Annotation: Some Problems Posed by (and to) Val Tannen" href="#" title="Access Statistics"><i class="bi bi-graph-up"></i></a> </aside> <div class="selectors"> <span data-key="dagstuhl.contributor.author" data-value="Buneman, Peter"></span> <span data-key="dagstuhl.contributor.author" data-value="Vansummeren, Stijn"></span> <span data-key="dagstuhl.subject.classification" data-value="Information systems → Database design and models"></span> <span data-key="dagstuhl.subject.classification" data-value="Theory of computation → Database theory"></span> <span data-key="dagstuhl.subject.classification" data-value="Theory of computation → Data provenance"></span> </div> <div class="card-body"> <h5 class="card-title"> <a href="https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.Tannen.4"> Annotation and More Annotation: Some Problems Posed by (and to) Val Tannen </a> </h5> <p class="card-text small authors"> <b>Authors:</b> Peter Buneman and Stijn Vansummeren </p> <div class="row"> <div class="collapse" id="abstract-20192"> <hr/> <h5 data-bs-toggle="collapse" data-bs-target="#abstract-20192">Abstract <span style="float: right; cursor: pointer"><i class="bi bi-chevron-up"></i></span></h5> <div class="abstract monospace"> Among the many research accomplishments of Val Tannen, his work on provenance and semirings is probably the most widely known. In this paper, we discuss questions that arise when applying this general framework to the setting of curated databases, and in particular the setting where we can have multiple annotations on the same data, as well as annotations on annotations. </div> </div> </div> <div class="row"> <div class="collapse" id="bibtex-20192"> <hr/> <h5 data-bs-toggle="collapse" data-bs-target="#bibtex-20192">Cite as <span style="float: right; cursor: pointer"><i class="bi bi-chevron-up"></i></span></h5> <p class="small">Peter Buneman and Stijn Vansummeren. Annotation and More Annotation: Some Problems Posed by (and to) Val Tannen. In The Provenance of Elegance in Computation - Essays Dedicated to Val Tannen. Open Access Series in Informatics (OASIcs), Volume 119, pp. 4:1-4:8, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)</p> <hr/> <a href="#" class="btn btn-primary btn-xs copy-to-clipboard" title="Copy to clipboard" data-selector="bibtex-20192-input"><i class="bi bi-clipboard"></i> Copy BibTex To Clipboard<span class="bi bi-check -hidden" style="padding-left: 1em; font-weight: bold"></span></a><br/><br/> <pre class="bibtex">@InProceedings{buneman_et_al:OASIcs.Tannen.4, author = {Buneman, Peter and Vansummeren, Stijn}, title = {{Annotation and More Annotation: Some Problems Posed by (and to) Val Tannen}}, booktitle = {The Provenance of Elegance in Computation - Essays Dedicated to Val Tannen}, pages = {4:1--4:8}, series = {Open Access Series in Informatics (OASIcs)}, ISBN = {978-3-95977-320-1}, ISSN = {2190-6807}, year = {2024}, volume = {119}, editor = {Amarilli, Antoine and Deutsch, Alin}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.Tannen.4}, URN = {urn:nbn:de:0030-drops-201007}, doi = {10.4230/OASIcs.Tannen.4}, annote = {Keywords: Annotation, provenance, semiring, curated data} }</pre> <textarea style="position: absolute; top: 200vh" id="bibtex-20192-input">@InProceedings{buneman_et_al:OASIcs.Tannen.4, author = {Buneman, Peter and Vansummeren, Stijn}, title = {{Annotation and More Annotation: Some Problems Posed by (and to) Val Tannen}}, booktitle = {The Provenance of Elegance in Computation - Essays Dedicated to Val Tannen}, pages = {4:1--4:8}, series = {Open Access Series in Informatics (OASIcs)}, ISBN = {978-3-95977-320-1}, ISSN = {2190-6807}, year = {2024}, volume = {119}, editor = {Amarilli, Antoine and Deutsch, Alin}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.Tannen.4}, URN = {urn:nbn:de:0030-drops-201007}, doi = {10.4230/OASIcs.Tannen.4}, annote = {Keywords: Annotation, provenance, semiring, curated data} }</textarea> </div> </div> </div> </div> <div class="entity-list-item document card m-3" data-show="1" data-permanent-id="document/10.4230/OASIcs.Tannen.5"> <div class="entity-type"><i class="bi bi-file-earmark"></i> Document</div> <div class="doi"><a href="https://doi.org/10.4230/OASIcs.Tannen.5">DOI: 10.4230/OASIcs.Tannen.5</a></div> <aside> <a class="icon-btn" style="color: red" href="https://drops.dagstuhl.de/storage/01oasics/oasics-vol119-tannens-festschrift/OASIcs.Tannen.5/OASIcs.Tannen.5.pdf" data-bs-toggle="tooltip" title="View PDF"><i class="bi bi-file-earmark-pdf-fill"></i></a><a class="icon-btn" style="color: #0d6efd!important;" href="https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.Tannen.5" data-bs-toggle="tooltip" title="View Detailed Metadata"><i class="bi bi-info-circle"></i></a><br/> <a class="icon-btn investigation" href="#" data-bs-toggle="collapse" data-bs-target="#abstract-20193" aria-expanded="false" aria-controls="collapseAbstract" title="Show Abstract"><span class="tooltip-wrapper" data-bs-toggle="tooltip" title="Show Abstract"><i class="bi bi-card-text"></i></span></a><a class="icon-btn investigation" href="#" data-bs-toggle="collapse" data-bs-target="#bibtex-20193" aria-expanded="false" aria-controls="collapseBibtex" title="Show BibTex"><span class="tooltip-wrapper" data-bs-toggle="tooltip" title="Show BibTex"><i class="bi bi-chat-left-quote"></i></a><br/><a class="icon-btn btn-statistics" data-entity="document/10.4230/OASIcs.Tannen.5" data-bs-toggle="tooltip" data-title="Chasing Parallelism in Aggregating Graph Queries" href="#" title="Access Statistics"><i class="bi bi-graph-up"></i></a> </aside> <div class="selectors"> <span data-key="dagstuhl.contributor.author" data-value="Deutsch, Alin"></span> <span data-key="dagstuhl.subject.classification" data-value="Information systems → Graph-based database models"></span> <span data-key="dagstuhl.subject.classification" data-value="Information systems → Query optimization"></span> </div> <div class="card-body"> <h5 class="card-title"> <a href="https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.Tannen.5"> Chasing Parallelism in Aggregating Graph Queries </a> </h5> <p class="card-text small authors"> <b>Authors:</b> Alin Deutsch </p> <div class="row"> <div class="collapse" id="abstract-20193"> <hr/> <h5 data-bs-toggle="collapse" data-bs-target="#abstract-20193">Abstract <span style="float: right; cursor: pointer"><i class="bi bi-chevron-up"></i></span></h5> <div class="abstract monospace"> In practice, one frequently encounters queries that extract tabular results from graph databases by employing grouping and aggregation. This paper introduces a technique for rewriting the group-by list of graph queries in order to increase aggregation parallelism in graph engines that conform to a modern instantiation of the Bulk-Synchronous-Parallel computation model. </div> </div> </div> <div class="row"> <div class="collapse" id="bibtex-20193"> <hr/> <h5 data-bs-toggle="collapse" data-bs-target="#bibtex-20193">Cite as <span style="float: right; cursor: pointer"><i class="bi bi-chevron-up"></i></span></h5> <p class="small">Alin Deutsch. Chasing Parallelism in Aggregating Graph Queries. In The Provenance of Elegance in Computation - Essays Dedicated to Val Tannen. Open Access Series in Informatics (OASIcs), Volume 119, pp. 5:1-5:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)</p> <hr/> <a href="#" class="btn btn-primary btn-xs copy-to-clipboard" title="Copy to clipboard" data-selector="bibtex-20193-input"><i class="bi bi-clipboard"></i> Copy BibTex To Clipboard<span class="bi bi-check -hidden" style="padding-left: 1em; font-weight: bold"></span></a><br/><br/> <pre class="bibtex">@InProceedings{deutsch:OASIcs.Tannen.5, author = {Deutsch, Alin}, title = {{Chasing Parallelism in Aggregating Graph Queries}}, booktitle = {The Provenance of Elegance in Computation - Essays Dedicated to Val Tannen}, pages = {5:1--5:14}, series = {Open Access Series in Informatics (OASIcs)}, ISBN = {978-3-95977-320-1}, ISSN = {2190-6807}, year = {2024}, volume = {119}, editor = {Amarilli, Antoine and Deutsch, Alin}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.Tannen.5}, URN = {urn:nbn:de:0030-drops-201011}, doi = {10.4230/OASIcs.Tannen.5}, annote = {Keywords: Graph Databases, Grouping and Aggregation, Parallel Graph Computation Models, Rewriting, Constraint-based Minimization} }</pre> <textarea style="position: absolute; top: 200vh" id="bibtex-20193-input">@InProceedings{deutsch:OASIcs.Tannen.5, author = {Deutsch, Alin}, title = {{Chasing Parallelism in Aggregating Graph Queries}}, booktitle = {The Provenance of Elegance in Computation - Essays Dedicated to Val Tannen}, pages = {5:1--5:14}, series = {Open Access Series in Informatics (OASIcs)}, ISBN = {978-3-95977-320-1}, ISSN = {2190-6807}, year = {2024}, volume = {119}, editor = {Amarilli, Antoine and Deutsch, Alin}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.Tannen.5}, URN = {urn:nbn:de:0030-drops-201011}, doi = {10.4230/OASIcs.Tannen.5}, annote = {Keywords: Graph Databases, Grouping and Aggregation, Parallel Graph Computation Models, Rewriting, Constraint-based Minimization} }</textarea> </div> </div> </div> </div> <div class="entity-list-item document card m-3" data-show="1" data-permanent-id="document/10.4230/OASIcs.Tannen.6"> <div class="entity-type"><i class="bi bi-file-earmark"></i> Document</div> <div class="doi"><a href="https://doi.org/10.4230/OASIcs.Tannen.6">DOI: 10.4230/OASIcs.Tannen.6</a></div> <aside> <a class="icon-btn" style="color: red" href="https://drops.dagstuhl.de/storage/01oasics/oasics-vol119-tannens-festschrift/OASIcs.Tannen.6/OASIcs.Tannen.6.pdf" data-bs-toggle="tooltip" title="View PDF"><i class="bi bi-file-earmark-pdf-fill"></i></a><a class="icon-btn" style="color: #0d6efd!important;" href="https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.Tannen.6" data-bs-toggle="tooltip" title="View Detailed Metadata"><i class="bi bi-info-circle"></i></a><br/> <a class="icon-btn investigation" href="#" data-bs-toggle="collapse" data-bs-target="#abstract-20194" aria-expanded="false" aria-controls="collapseAbstract" title="Show Abstract"><span class="tooltip-wrapper" data-bs-toggle="tooltip" title="Show Abstract"><i class="bi bi-card-text"></i></span></a><a class="icon-btn investigation" href="#" data-bs-toggle="collapse" data-bs-target="#bibtex-20194" aria-expanded="false" aria-controls="collapseBibtex" title="Show BibTex"><span class="tooltip-wrapper" data-bs-toggle="tooltip" title="Show BibTex"><i class="bi bi-chat-left-quote"></i></a><br/><a class="icon-btn btn-statistics" data-entity="document/10.4230/OASIcs.Tannen.6" data-bs-toggle="tooltip" data-title="Fishing Fort: A System for Graph Analytics with ML Prediction and Logic Deduction" href="#" title="Access Statistics"><i class="bi bi-graph-up"></i></a> </aside> <div class="selectors"> <span data-key="dagstuhl.contributor.author" data-value="Fan, Wenfei"></span> <span data-key="dagstuhl.contributor.author" data-value="Liu, Shuhao"></span> <span data-key="dagstuhl.subject.classification" data-value="Information systems → Data mining"></span> <span data-key="dagstuhl.subject.classification" data-value="Information systems → Data management systems"></span> <span data-key="dagstuhl.subject.classification" data-value="Information systems → Information integration"></span> </div> <div class="card-body"> <h5 class="card-title"> <a href="https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.Tannen.6"> Fishing Fort: A System for Graph Analytics with ML Prediction and Logic Deduction </a> </h5> <p class="card-text small authors"> <b>Authors:</b> Wenfei Fan and Shuhao Liu </p> <div class="row"> <div class="collapse" id="abstract-20194"> <hr/> <h5 data-bs-toggle="collapse" data-bs-target="#abstract-20194">Abstract <span style="float: right; cursor: pointer"><i class="bi bi-chevron-up"></i></span></h5> <div class="abstract monospace"> This paper reports Fishing Fort, a graph analytic system developed in response to the following questions. What practical value can we get out of graph analytics? How can we effectively deduce the value from a real-life graph? Where can we get clean graphs to make accurate analyses possible? To answer these questions, Fishing Fort advocates to unify logic deduction and ML prediction by proposing Graph Association Rules (GARs), a class of logic rules in which ML models can be embedded as predicates. It employs GARs to deduce graph associations, enrich graphs and clean graphs. It has been deployed in production lines and proven effective in online recommendation, drug discovery, credit risk assessment, battery manufacturing and cybersecurity, among other things. </div> </div> </div> <div class="row"> <div class="collapse" id="bibtex-20194"> <hr/> <h5 data-bs-toggle="collapse" data-bs-target="#bibtex-20194">Cite as <span style="float: right; cursor: pointer"><i class="bi bi-chevron-up"></i></span></h5> <p class="small">Wenfei Fan and Shuhao Liu. Fishing Fort: A System for Graph Analytics with ML Prediction and Logic Deduction. In The Provenance of Elegance in Computation - Essays Dedicated to Val Tannen. Open Access Series in Informatics (OASIcs), Volume 119, pp. 6:1-6:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)</p> <hr/> <a href="#" class="btn btn-primary btn-xs copy-to-clipboard" title="Copy to clipboard" data-selector="bibtex-20194-input"><i class="bi bi-clipboard"></i> Copy BibTex To Clipboard<span class="bi bi-check -hidden" style="padding-left: 1em; font-weight: bold"></span></a><br/><br/> <pre class="bibtex">@InProceedings{fan_et_al:OASIcs.Tannen.6, author = {Fan, Wenfei and Liu, Shuhao}, title = {{Fishing Fort: A System for Graph Analytics with ML Prediction and Logic Deduction}}, booktitle = {The Provenance of Elegance in Computation - Essays Dedicated to Val Tannen}, pages = {6:1--6:18}, series = {Open Access Series in Informatics (OASIcs)}, ISBN = {978-3-95977-320-1}, ISSN = {2190-6807}, year = {2024}, volume = {119}, editor = {Amarilli, Antoine and Deutsch, Alin}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.Tannen.6}, URN = {urn:nbn:de:0030-drops-201025}, doi = {10.4230/OASIcs.Tannen.6}, annote = {Keywords: graph analytics, data cleaning, association analysis} }</pre> <textarea style="position: absolute; top: 200vh" id="bibtex-20194-input">@InProceedings{fan_et_al:OASIcs.Tannen.6, author = {Fan, Wenfei and Liu, Shuhao}, title = {{Fishing Fort: A System for Graph Analytics with ML Prediction and Logic Deduction}}, booktitle = {The Provenance of Elegance in Computation - Essays Dedicated to Val Tannen}, pages = {6:1--6:18}, series = {Open Access Series in Informatics (OASIcs)}, ISBN = {978-3-95977-320-1}, ISSN = {2190-6807}, year = {2024}, volume = {119}, editor = {Amarilli, Antoine and Deutsch, Alin}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.Tannen.6}, URN = {urn:nbn:de:0030-drops-201025}, doi = {10.4230/OASIcs.Tannen.6}, annote = {Keywords: graph analytics, data cleaning, association analysis} }</textarea> </div> </div> </div> </div> <div class="entity-list-item document card m-3" data-show="1" data-permanent-id="document/10.4230/OASIcs.Tannen.7"> <div class="entity-type"><i class="bi bi-file-earmark"></i> Document</div> <div class="doi"><a href="https://doi.org/10.4230/OASIcs.Tannen.7">DOI: 10.4230/OASIcs.Tannen.7</a></div> <aside> <a class="icon-btn" style="color: red" href="https://drops.dagstuhl.de/storage/01oasics/oasics-vol119-tannens-festschrift/OASIcs.Tannen.7/OASIcs.Tannen.7.pdf" data-bs-toggle="tooltip" title="View PDF"><i class="bi bi-file-earmark-pdf-fill"></i></a><a class="icon-btn" style="color: #0d6efd!important;" href="https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.Tannen.7" data-bs-toggle="tooltip" title="View Detailed Metadata"><i class="bi bi-info-circle"></i></a><br/> <a class="icon-btn investigation" href="#" data-bs-toggle="collapse" data-bs-target="#abstract-20195" aria-expanded="false" aria-controls="collapseAbstract" title="Show Abstract"><span class="tooltip-wrapper" data-bs-toggle="tooltip" title="Show Abstract"><i class="bi bi-card-text"></i></span></a><a class="icon-btn investigation" href="#" data-bs-toggle="collapse" data-bs-target="#bibtex-20195" aria-expanded="false" aria-controls="collapseBibtex" title="Show BibTex"><span class="tooltip-wrapper" data-bs-toggle="tooltip" title="Show BibTex"><i class="bi bi-chat-left-quote"></i></a><br/><a class="icon-btn btn-statistics" data-entity="document/10.4230/OASIcs.Tannen.7" data-bs-toggle="tooltip" data-title="A Note on Logical PERs and Reducibility. Logical Relations Strike Again!" href="#" title="Access Statistics"><i class="bi bi-graph-up"></i></a> </aside> <div class="selectors"> <span data-key="dagstuhl.contributor.author" data-value="Gallier, Jean"></span> <span data-key="dagstuhl.subject.classification" data-value="Theory of computation → Models of computation"></span> <span data-key="dagstuhl.subject.classification" data-value="Theory of computation → Type theory"></span> <span data-key="dagstuhl.subject.classification" data-value="Theory of computation → Complexity theory and logic"></span> </div> <div class="card-body"> <h5 class="card-title"> <a href="https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.Tannen.7"> A Note on Logical PERs and Reducibility. Logical Relations Strike Again! </a> </h5> <p class="card-text small authors"> <b>Authors:</b> Jean Gallier </p> <div class="row"> <div class="collapse" id="abstract-20195"> <hr/> <h5 data-bs-toggle="collapse" data-bs-target="#abstract-20195">Abstract <span style="float: right; cursor: pointer"><i class="bi bi-chevron-up"></i></span></h5> <div class="abstract monospace"> We prove a general theorem for establishing properties expressed by binary relations on typed (first-order) λ-terms, using a variant of the reducibility method and logical PERs. As an application, we prove simultaneously that β-reduction in the simply-typed λ-calculus is strongly normalizing, and that the Church-Rosser property holds (and similarly for βη-reduction). </div> </div> </div> <div class="row"> <div class="collapse" id="bibtex-20195"> <hr/> <h5 data-bs-toggle="collapse" data-bs-target="#bibtex-20195">Cite as <span style="float: right; cursor: pointer"><i class="bi bi-chevron-up"></i></span></h5> <p class="small">Jean Gallier. A Note on Logical PERs and Reducibility. Logical Relations Strike Again!. In The Provenance of Elegance in Computation - Essays Dedicated to Val Tannen. Open Access Series in Informatics (OASIcs), Volume 119, pp. 7:1-7:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)</p> <hr/> <a href="#" class="btn btn-primary btn-xs copy-to-clipboard" title="Copy to clipboard" data-selector="bibtex-20195-input"><i class="bi bi-clipboard"></i> Copy BibTex To Clipboard<span class="bi bi-check -hidden" style="padding-left: 1em; font-weight: bold"></span></a><br/><br/> <pre class="bibtex">@InProceedings{gallier:OASIcs.Tannen.7, author = {Gallier, Jean}, title = {{A Note on Logical PERs and Reducibility. Logical Relations Strike Again!}}, booktitle = {The Provenance of Elegance in Computation - Essays Dedicated to Val Tannen}, pages = {7:1--7:12}, series = {Open Access Series in Informatics (OASIcs)}, ISBN = {978-3-95977-320-1}, ISSN = {2190-6807}, year = {2024}, volume = {119}, editor = {Amarilli, Antoine and Deutsch, Alin}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.Tannen.7}, URN = {urn:nbn:de:0030-drops-201033}, doi = {10.4230/OASIcs.Tannen.7}, annote = {Keywords: Typed lambda-calculus, reducibility, logical relations, per’s, strong normalization, Church-Rosser property} }</pre> <textarea style="position: absolute; top: 200vh" id="bibtex-20195-input">@InProceedings{gallier:OASIcs.Tannen.7, author = {Gallier, Jean}, title = {{A Note on Logical PERs and Reducibility. Logical Relations Strike Again!}}, booktitle = {The Provenance of Elegance in Computation - Essays Dedicated to Val Tannen}, pages = {7:1--7:12}, series = {Open Access Series in Informatics (OASIcs)}, ISBN = {978-3-95977-320-1}, ISSN = {2190-6807}, year = {2024}, volume = {119}, editor = {Amarilli, Antoine and Deutsch, Alin}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.Tannen.7}, URN = {urn:nbn:de:0030-drops-201033}, doi = {10.4230/OASIcs.Tannen.7}, annote = {Keywords: Typed lambda-calculus, reducibility, logical relations, per’s, strong normalization, Church-Rosser property} }</textarea> </div> </div> </div> </div> <div class="entity-list-item document card m-3" data-show="1" data-permanent-id="document/10.4230/OASIcs.Tannen.8"> <div class="entity-type"><i class="bi bi-file-earmark"></i> Document</div> <div class="doi"><a href="https://doi.org/10.4230/OASIcs.Tannen.8">DOI: 10.4230/OASIcs.Tannen.8</a></div> <aside> <a class="icon-btn" style="color: red" href="https://drops.dagstuhl.de/storage/01oasics/oasics-vol119-tannens-festschrift/OASIcs.Tannen.8/OASIcs.Tannen.8.pdf" data-bs-toggle="tooltip" title="View PDF"><i class="bi bi-file-earmark-pdf-fill"></i></a><a class="icon-btn" style="color: #0d6efd!important;" href="https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.Tannen.8" data-bs-toggle="tooltip" title="View Detailed Metadata"><i class="bi bi-info-circle"></i></a><br/> <a class="icon-btn investigation" href="#" data-bs-toggle="collapse" data-bs-target="#abstract-20196" aria-expanded="false" aria-controls="collapseAbstract" title="Show Abstract"><span class="tooltip-wrapper" data-bs-toggle="tooltip" title="Show Abstract"><i class="bi bi-card-text"></i></span></a><a class="icon-btn investigation" href="#" data-bs-toggle="collapse" data-bs-target="#bibtex-20196" aria-expanded="false" aria-controls="collapseBibtex" title="Show BibTex"><span class="tooltip-wrapper" data-bs-toggle="tooltip" title="Show BibTex"><i class="bi bi-chat-left-quote"></i></a><br/><a class="icon-btn btn-statistics" data-entity="document/10.4230/OASIcs.Tannen.8" data-bs-toggle="tooltip" data-title="AutoML for Explainable Anomaly Detection (XAD)" href="#" title="Access Statistics"><i class="bi bi-graph-up"></i></a> </aside> <div class="selectors"> <span data-key="dagstuhl.contributor.author" data-value="Myrtakis, Nikolaos"></span> <span data-key="dagstuhl.contributor.author" data-value="Tsamardinos, Ioannis"></span> <span data-key="dagstuhl.contributor.author" data-value="Christophides, Vassilis"></span> <span data-key="dagstuhl.subject.classification" data-value="Computing methodologies → Anomaly detection"></span> </div> <div class="card-body"> <h5 class="card-title"> <a href="https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.Tannen.8"> AutoML for Explainable Anomaly Detection (XAD) </a> </h5> <p class="card-text small authors"> <b>Authors:</b> Nikolaos Myrtakis, Ioannis Tsamardinos, and Vassilis Christophides </p> <div class="row"> <div class="collapse" id="abstract-20196"> <hr/> <h5 data-bs-toggle="collapse" data-bs-target="#abstract-20196">Abstract <span style="float: right; cursor: pointer"><i class="bi bi-chevron-up"></i></span></h5> <div class="abstract monospace"> Numerous algorithms have been proposed for detecting anomalies (outliers, novelties) in an unsupervised manner. Unfortunately, it is not trivial, in general, to understand why a given sample (record) is labelled as an anomaly and thus diagnose its root causes. We propose the following reduced-dimensionality, surrogate model approach to explain detector decisions: approximate the detection model with another one that employs only a small subset of features. Subsequently, samples can be visualized in this low-dimensionality space for human understanding. To this end, we develop PROTEUS, an AutoML pipeline to produce the surrogate model, specifically designed for feature selection on imbalanced datasets. The PROTEUS surrogate model can not only explain the training data, but also the out-of-sample (unseen) data. In other words, PROTEUS produces predictive explanations by approximating the decision surface of an unsupervised detector. PROTEUS is designed to return an accurate estimate of out-of-sample predictive performance to serve as a metric of the quality of the approximation. Computational experiments confirm the efficacy of PROTEUS to produce predictive explanations for different families of detectors and to reliably estimate their predictive performance in unseen data. Unlike several ad-hoc feature importance methods, PROTEUS is robust to high-dimensional data. </div> </div> </div> <div class="row"> <div class="collapse" id="bibtex-20196"> <hr/> <h5 data-bs-toggle="collapse" data-bs-target="#bibtex-20196">Cite as <span style="float: right; cursor: pointer"><i class="bi bi-chevron-up"></i></span></h5> <p class="small">Nikolaos Myrtakis, Ioannis Tsamardinos, and Vassilis Christophides. AutoML for Explainable Anomaly Detection (XAD). In The Provenance of Elegance in Computation - Essays Dedicated to Val Tannen. Open Access Series in Informatics (OASIcs), Volume 119, pp. 8:1-8:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)</p> <hr/> <a href="#" class="btn btn-primary btn-xs copy-to-clipboard" title="Copy to clipboard" data-selector="bibtex-20196-input"><i class="bi bi-clipboard"></i> Copy BibTex To Clipboard<span class="bi bi-check -hidden" style="padding-left: 1em; font-weight: bold"></span></a><br/><br/> <pre class="bibtex">@InProceedings{myrtakis_et_al:OASIcs.Tannen.8, author = {Myrtakis, Nikolaos and Tsamardinos, Ioannis and Christophides, Vassilis}, title = {{AutoML for Explainable Anomaly Detection (XAD)}}, booktitle = {The Provenance of Elegance in Computation - Essays Dedicated to Val Tannen}, pages = {8:1--8:23}, series = {Open Access Series in Informatics (OASIcs)}, ISBN = {978-3-95977-320-1}, ISSN = {2190-6807}, year = {2024}, volume = {119}, editor = {Amarilli, Antoine and Deutsch, Alin}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.Tannen.8}, URN = {urn:nbn:de:0030-drops-201049}, doi = {10.4230/OASIcs.Tannen.8}, annote = {Keywords: Anomaly Explanation, Predictive Explanation, Anomaly Interpretation, Explainable AI} }</pre> <textarea style="position: absolute; top: 200vh" id="bibtex-20196-input">@InProceedings{myrtakis_et_al:OASIcs.Tannen.8, author = {Myrtakis, Nikolaos and Tsamardinos, Ioannis and Christophides, Vassilis}, title = {{AutoML for Explainable Anomaly Detection (XAD)}}, booktitle = {The Provenance of Elegance in Computation - Essays Dedicated to Val Tannen}, pages = {8:1--8:23}, series = {Open Access Series in Informatics (OASIcs)}, ISBN = {978-3-95977-320-1}, ISSN = {2190-6807}, year = {2024}, volume = {119}, editor = {Amarilli, Antoine and Deutsch, Alin}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.Tannen.8}, URN = {urn:nbn:de:0030-drops-201049}, doi = {10.4230/OASIcs.Tannen.8}, annote = {Keywords: Anomaly Explanation, Predictive Explanation, Anomaly Interpretation, Explainable AI} }</textarea> </div> </div> </div> </div> <div class="entity-list-item document card m-3" data-show="1" data-permanent-id="document/10.4230/OASIcs.Tannen.9"> <div class="entity-type"><i class="bi bi-file-earmark"></i> Document</div> <div class="doi"><a href="https://doi.org/10.4230/OASIcs.Tannen.9">DOI: 10.4230/OASIcs.Tannen.9</a></div> <aside> <a class="icon-btn" style="color: red" href="https://drops.dagstuhl.de/storage/01oasics/oasics-vol119-tannens-festschrift/OASIcs.Tannen.9/OASIcs.Tannen.9.pdf" data-bs-toggle="tooltip" title="View PDF"><i class="bi bi-file-earmark-pdf-fill"></i></a><a class="icon-btn" style="color: #0d6efd!important;" href="https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.Tannen.9" data-bs-toggle="tooltip" title="View Detailed Metadata"><i class="bi bi-info-circle"></i></a><br/> <a class="icon-btn investigation" href="#" data-bs-toggle="collapse" data-bs-target="#abstract-20197" aria-expanded="false" aria-controls="collapseAbstract" title="Show Abstract"><span class="tooltip-wrapper" data-bs-toggle="tooltip" title="Show Abstract"><i class="bi bi-card-text"></i></span></a><a class="icon-btn investigation" href="#" data-bs-toggle="collapse" data-bs-target="#bibtex-20197" aria-expanded="false" aria-controls="collapseBibtex" title="Show BibTex"><span class="tooltip-wrapper" data-bs-toggle="tooltip" title="Show BibTex"><i class="bi bi-chat-left-quote"></i></a><br/><a class="icon-btn btn-statistics" data-entity="document/10.4230/OASIcs.Tannen.9" data-bs-toggle="tooltip" data-title="On the Impact of Provenance Semiring Theory on the Design of a Provenance-Aware Database System" href="#" title="Access Statistics"><i class="bi bi-graph-up"></i></a> </aside> <div class="selectors"> <span data-key="dagstuhl.contributor.author" data-value="Senellart, Pierre"></span> <span data-key="dagstuhl.subject.classification" data-value="Theory of computation → Data provenance"></span> <span data-key="dagstuhl.subject.classification" data-value="Information systems → Database management system engines"></span> </div> <div class="card-body"> <h5 class="card-title"> <a href="https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.Tannen.9"> On the Impact of Provenance Semiring Theory on the Design of a Provenance-Aware Database System </a> </h5> <p class="card-text small authors"> <b>Authors:</b> Pierre Senellart </p> <div class="row"> <div class="collapse" id="abstract-20197"> <hr/> <h5 data-bs-toggle="collapse" data-bs-target="#abstract-20197">Abstract <span style="float: right; cursor: pointer"><i class="bi bi-chevron-up"></i></span></h5> <div class="abstract monospace"> We report on the impact that the theory of provenance semirings, developed by Val Tannen and his collaborators, has had on the design on a practical system for maintaining the provenance of query results over a relational database, namely ProvSQL. </div> </div> </div> <div class="row"> <div class="collapse" id="bibtex-20197"> <hr/> <h5 data-bs-toggle="collapse" data-bs-target="#bibtex-20197">Cite as <span style="float: right; cursor: pointer"><i class="bi bi-chevron-up"></i></span></h5> <p class="small">Pierre Senellart. On the Impact of Provenance Semiring Theory on the Design of a Provenance-Aware Database System. In The Provenance of Elegance in Computation - Essays Dedicated to Val Tannen. Open Access Series in Informatics (OASIcs), Volume 119, pp. 9:1-9:10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)</p> <hr/> <a href="#" class="btn btn-primary btn-xs copy-to-clipboard" title="Copy to clipboard" data-selector="bibtex-20197-input"><i class="bi bi-clipboard"></i> Copy BibTex To Clipboard<span class="bi bi-check -hidden" style="padding-left: 1em; font-weight: bold"></span></a><br/><br/> <pre class="bibtex">@InProceedings{senellart:OASIcs.Tannen.9, author = {Senellart, Pierre}, title = {{On the Impact of Provenance Semiring Theory on the Design of a Provenance-Aware Database System}}, booktitle = {The Provenance of Elegance in Computation - Essays Dedicated to Val Tannen}, pages = {9:1--9:10}, series = {Open Access Series in Informatics (OASIcs)}, ISBN = {978-3-95977-320-1}, ISSN = {2190-6807}, year = {2024}, volume = {119}, editor = {Amarilli, Antoine and Deutsch, Alin}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.Tannen.9}, URN = {urn:nbn:de:0030-drops-201050}, doi = {10.4230/OASIcs.Tannen.9}, annote = {Keywords: provenance, provenance semiring, ProvSQL} }</pre> <textarea style="position: absolute; top: 200vh" id="bibtex-20197-input">@InProceedings{senellart:OASIcs.Tannen.9, author = {Senellart, Pierre}, title = {{On the Impact of Provenance Semiring Theory on the Design of a Provenance-Aware Database System}}, booktitle = {The Provenance of Elegance in Computation - Essays Dedicated to Val Tannen}, pages = {9:1--9:10}, series = {Open Access Series in Informatics (OASIcs)}, ISBN = {978-3-95977-320-1}, ISSN = {2190-6807}, year = {2024}, volume = {119}, editor = {Amarilli, Antoine and Deutsch, Alin}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.Tannen.9}, URN = {urn:nbn:de:0030-drops-201050}, doi = {10.4230/OASIcs.Tannen.9}, annote = {Keywords: provenance, provenance semiring, ProvSQL} }</textarea> </div> </div> </div> </div> <div class="entity-list-item document card m-3" data-show="1" data-permanent-id="document/10.4230/OASIcs.Tannen.10"> <div class="entity-type"><i class="bi bi-file-earmark"></i> Document</div> <div class="doi"><a href="https://doi.org/10.4230/OASIcs.Tannen.10">DOI: 10.4230/OASIcs.Tannen.10</a></div> <aside> <a class="icon-btn" style="color: red" href="https://drops.dagstuhl.de/storage/01oasics/oasics-vol119-tannens-festschrift/OASIcs.Tannen.10/OASIcs.Tannen.10.pdf" data-bs-toggle="tooltip" title="View PDF"><i class="bi bi-file-earmark-pdf-fill"></i></a><a class="icon-btn" style="color: #0d6efd!important;" href="https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.Tannen.10" data-bs-toggle="tooltip" title="View Detailed Metadata"><i class="bi bi-info-circle"></i></a><br/> <a class="icon-btn investigation" href="#" data-bs-toggle="collapse" data-bs-target="#abstract-20198" aria-expanded="false" aria-controls="collapseAbstract" title="Show Abstract"><span class="tooltip-wrapper" data-bs-toggle="tooltip" title="Show Abstract"><i class="bi bi-card-text"></i></span></a><a class="icon-btn investigation" href="#" data-bs-toggle="collapse" data-bs-target="#bibtex-20198" aria-expanded="false" aria-controls="collapseBibtex" title="Show BibTex"><span class="tooltip-wrapper" data-bs-toggle="tooltip" title="Show BibTex"><i class="bi bi-chat-left-quote"></i></a><br/><a class="icon-btn btn-statistics" data-entity="document/10.4230/OASIcs.Tannen.10" data-bs-toggle="tooltip" data-title="Different Differences in Semirings" href="#" title="Access Statistics"><i class="bi bi-graph-up"></i></a> </aside> <div class="selectors"> <span data-key="dagstuhl.contributor.author" data-value="Suciu, Dan"></span> <span data-key="dagstuhl.subject.classification" data-value="Information systems → Structured Query Language"></span> </div> <div class="card-body"> <h5 class="card-title"> <a href="https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.Tannen.10"> Different Differences in Semirings </a> </h5> <p class="card-text small authors"> <b>Authors:</b> Dan Suciu </p> <div class="row"> <div class="collapse" id="abstract-20198"> <hr/> <h5 data-bs-toggle="collapse" data-bs-target="#abstract-20198">Abstract <span style="float: right; cursor: pointer"><i class="bi bi-chevron-up"></i></span></h5> <div class="abstract monospace"> Relational algebra operates over relations under either set semantics or bag semantics. In 2007 Val Tannen extended the semantics of relational algebra to K-relations, where each tuple is annotated with a value from a semiring. However, only the positive fragment of the relational algebra can be interpreted over K-relations. The reason is that a semiring contains only the operations addition and multiplication, and does not have a difference operation. This paper explores three ways of adding a difference operator to a semiring: as a freely generated algebra, by using the natural order, or by an explicit construction using products and quotients. The paper consists of both a survey of results from the literature, and of some novel results. </div> </div> </div> <div class="row"> <div class="collapse" id="bibtex-20198"> <hr/> <h5 data-bs-toggle="collapse" data-bs-target="#bibtex-20198">Cite as <span style="float: right; cursor: pointer"><i class="bi bi-chevron-up"></i></span></h5> <p class="small">Dan Suciu. Different Differences in Semirings. In The Provenance of Elegance in Computation - Essays Dedicated to Val Tannen. Open Access Series in Informatics (OASIcs), Volume 119, pp. 10:1-10:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)</p> <hr/> <a href="#" class="btn btn-primary btn-xs copy-to-clipboard" title="Copy to clipboard" data-selector="bibtex-20198-input"><i class="bi bi-clipboard"></i> Copy BibTex To Clipboard<span class="bi bi-check -hidden" style="padding-left: 1em; font-weight: bold"></span></a><br/><br/> <pre class="bibtex">@InProceedings{suciu:OASIcs.Tannen.10, author = {Suciu, Dan}, title = {{Different Differences in Semirings}}, booktitle = {The Provenance of Elegance in Computation - Essays Dedicated to Val Tannen}, pages = {10:1--10:20}, series = {Open Access Series in Informatics (OASIcs)}, ISBN = {978-3-95977-320-1}, ISSN = {2190-6807}, year = {2024}, volume = {119}, editor = {Amarilli, Antoine and Deutsch, Alin}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.Tannen.10}, URN = {urn:nbn:de:0030-drops-201062}, doi = {10.4230/OASIcs.Tannen.10}, annote = {Keywords: Semirings, K-relations} }</pre> <textarea style="position: absolute; top: 200vh" id="bibtex-20198-input">@InProceedings{suciu:OASIcs.Tannen.10, author = {Suciu, Dan}, title = {{Different Differences in Semirings}}, booktitle = {The Provenance of Elegance in Computation - Essays Dedicated to Val Tannen}, pages = {10:1--10:20}, series = {Open Access Series in Informatics (OASIcs)}, ISBN = {978-3-95977-320-1}, ISSN = {2190-6807}, year = {2024}, volume = {119}, editor = {Amarilli, Antoine and Deutsch, Alin}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.Tannen.10}, URN = {urn:nbn:de:0030-drops-201062}, doi = {10.4230/OASIcs.Tannen.10}, annote = {Keywords: Semirings, K-relations} }</textarea> </div> </div> </div> </div> <div class="entity-list-item document card m-3" data-show="1" data-permanent-id="document/10.4230/OASIcs.Tannen.11"> <div class="entity-type"><i class="bi bi-file-earmark"></i> Document</div> <div class="doi"><a href="https://doi.org/10.4230/OASIcs.Tannen.11">DOI: 10.4230/OASIcs.Tannen.11</a></div> <aside> <a class="icon-btn" style="color: red" href="https://drops.dagstuhl.de/storage/01oasics/oasics-vol119-tannens-festschrift/OASIcs.Tannen.11/OASIcs.Tannen.11.pdf" data-bs-toggle="tooltip" title="View PDF"><i class="bi bi-file-earmark-pdf-fill"></i></a><a class="icon-btn" style="color: #0d6efd!important;" href="https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.Tannen.11" data-bs-toggle="tooltip" title="View Detailed Metadata"><i class="bi bi-info-circle"></i></a><br/> <a class="icon-btn investigation" href="#" data-bs-toggle="collapse" data-bs-target="#abstract-20199" aria-expanded="false" aria-controls="collapseAbstract" title="Show Abstract"><span class="tooltip-wrapper" data-bs-toggle="tooltip" title="Show Abstract"><i class="bi bi-card-text"></i></span></a><a class="icon-btn investigation" href="#" data-bs-toggle="collapse" data-bs-target="#bibtex-20199" aria-expanded="false" aria-controls="collapseBibtex" title="Show BibTex"><span class="tooltip-wrapper" data-bs-toggle="tooltip" title="Show BibTex"><i class="bi bi-chat-left-quote"></i></a><br/><a class="icon-btn btn-statistics" data-entity="document/10.4230/OASIcs.Tannen.11" data-bs-toggle="tooltip" data-title="An Intensional Expressiveness Gap of Comprehension Syntax" href="#" title="Access Statistics"><i class="bi bi-graph-up"></i></a> </aside> <div class="selectors"> <span data-key="dagstuhl.contributor.author" data-value="Wong, Limsoon"></span> <span data-key="dagstuhl.subject.classification" data-value="Information systems → Relational database query languages"></span> </div> <div class="card-body"> <h5 class="card-title"> <a href="https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.Tannen.11"> An Intensional Expressiveness Gap of Comprehension Syntax </a> </h5> <p class="card-text small authors"> <b>Authors:</b> Limsoon Wong </p> <div class="row"> <div class="collapse" id="abstract-20199"> <hr/> <h5 data-bs-toggle="collapse" data-bs-target="#abstract-20199">Abstract <span style="float: right; cursor: pointer"><i class="bi bi-chevron-up"></i></span></h5> <div class="abstract monospace"> Comprehension syntax is widely adopted in modern programming languages as a means for manipulating collection types. This paper proves that all subquadratic algorithms which are expressible in comprehension syntax, do not compute low-selectivity joins. As database systems support these joins efficiently, this confirms an intensional expressiveness gap between comprehension syntax and relational database systems. The proof of this intensional expressiveness gap relies on a "limited-mixing" lemma which states that subquadratic algorithms expressible using comprehension syntax have limited ability for mixing atomic objects in their inputs. </div> </div> </div> <div class="row"> <div class="collapse" id="bibtex-20199"> <hr/> <h5 data-bs-toggle="collapse" data-bs-target="#bibtex-20199">Cite as <span style="float: right; cursor: pointer"><i class="bi bi-chevron-up"></i></span></h5> <p class="small">Limsoon Wong. An Intensional Expressiveness Gap of Comprehension Syntax. In The Provenance of Elegance in Computation - Essays Dedicated to Val Tannen. Open Access Series in Informatics (OASIcs), Volume 119, pp. 11:1-11:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)</p> <hr/> <a href="#" class="btn btn-primary btn-xs copy-to-clipboard" title="Copy to clipboard" data-selector="bibtex-20199-input"><i class="bi bi-clipboard"></i> Copy BibTex To Clipboard<span class="bi bi-check -hidden" style="padding-left: 1em; font-weight: bold"></span></a><br/><br/> <pre class="bibtex">@InProceedings{wong:OASIcs.Tannen.11, author = {Wong, Limsoon}, title = {{An Intensional Expressiveness Gap of Comprehension Syntax}}, booktitle = {The Provenance of Elegance in Computation - Essays Dedicated to Val Tannen}, pages = {11:1--11:13}, series = {Open Access Series in Informatics (OASIcs)}, ISBN = {978-3-95977-320-1}, ISSN = {2190-6807}, year = {2024}, volume = {119}, editor = {Amarilli, Antoine and Deutsch, Alin}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.Tannen.11}, URN = {urn:nbn:de:0030-drops-201074}, doi = {10.4230/OASIcs.Tannen.11}, annote = {Keywords: Comprehension syntax, intensional expressive power, limited-mixing lemma} }</pre> <textarea style="position: absolute; top: 200vh" id="bibtex-20199-input">@InProceedings{wong:OASIcs.Tannen.11, author = {Wong, Limsoon}, title = {{An Intensional Expressiveness Gap of Comprehension Syntax}}, booktitle = {The Provenance of Elegance in Computation - Essays Dedicated to Val Tannen}, pages = {11:1--11:13}, series = {Open Access Series in Informatics (OASIcs)}, ISBN = {978-3-95977-320-1}, ISSN = {2190-6807}, year = {2024}, volume = {119}, editor = {Amarilli, Antoine and Deutsch, Alin}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.Tannen.11}, URN = {urn:nbn:de:0030-drops-201074}, doi = {10.4230/OASIcs.Tannen.11}, annote = {Keywords: Comprehension syntax, intensional expressive power, limited-mixing lemma} }</textarea> </div> </div> </div> </div> </div> </div> <div class="col-sm-3 mt-2"> <h2>Filters</h2> <div class="free-text-filter mb-4"> <div class="input-group"> <input class="form-control no-outline" type="search" placeholder="Free Text Filter" aria-label="Free Text Filter" id="free-text-filter" maxlength="300"> </div> </div> <div class="grouped-metadata-filter" data-filter-key="dagstuhl.contributor.author"> <ul class="list-group"> <li class="list-group-item filter-headline list-group-item-dark"> <b><span class="count"></span> Authors</b> <span style="float: right;"><i class="bi bi-chevron-down"></i><i class="bi bi-chevron-up"></i></span> </li> <li class="list-group-item filter-item pinned -hidden" data-value="" data-key=""> <i class="bi bi-pin-angle-fill"></i> <span class="value"></span> <span class="action"><i><i class="bi bi-x-circle"></i></i></span> </li> <li class="list-group-item details buttons"> <span class="btn-group" role="group" aria-label="Show-All/Collapse"> <button type="button" class="btn btn-primary">Show All</button> <button type="button" class="btn btn-secondary">Collapse</button> </span> </li> <li class="list-group-item details show-all -hidden"> <button type="button" class="btn btn-primary">Show All</button> </li> <li class="list-group-item details filter-group-headline -expanded " data-group-selector="dagstuhl.contributor.author.A"> <b>A</b> <span style="float: right;"><i class="bi bi-chevron-down"></i><i class="bi bi-chevron-up"></i></span> </li> <li class="list-group-item details filter-item value " data-key="dagstuhl.contributor.author" data-value="Amarilli, Antoine" data-group-selector="dagstuhl.contributor.author.A"> Amarilli, Antoine <span class="action"><i class="bi bi-plus-circle"></i></span> </li> <li class="list-group-item details filter-item value " data-key="dagstuhl.contributor.author" data-value="Atzeni, Paolo" data-group-selector="dagstuhl.contributor.author.A"> Atzeni, Paolo <span class="action"><i class="bi bi-plus-circle"></i></span> </li> <li class="list-group-item details filter-group-headline " data-group-selector="dagstuhl.contributor.author.B"> <b>B</b> <span style="float: right;"><i class="bi bi-chevron-down"></i><i class="bi bi-chevron-up"></i></span> </li> <li class="list-group-item details filter-item value -hidden " data-key="dagstuhl.contributor.author" data-value="Baldazzi, Teodoro" data-group-selector="dagstuhl.contributor.author.B"> Baldazzi, Teodoro <span class="action"><i class="bi bi-plus-circle"></i></span> </li> <li class="list-group-item details filter-item value -hidden " data-key="dagstuhl.contributor.author" data-value="Bellomarini, Luigi" data-group-selector="dagstuhl.contributor.author.B"> Bellomarini, Luigi <span class="action"><i class="bi bi-plus-circle"></i></span> </li> <li class="list-group-item details filter-item value -hidden " data-key="dagstuhl.contributor.author" data-value="Bhaskar, Siddharth" data-group-selector="dagstuhl.contributor.author.B"> Bhaskar, Siddharth <span class="action"><i class="bi bi-plus-circle"></i></span> </li> <li class="list-group-item details filter-item value -hidden " data-key="dagstuhl.contributor.author" data-value="Brinke, Sophie" data-group-selector="dagstuhl.contributor.author.B"> Brinke, Sophie <span class="action"><i class="bi bi-plus-circle"></i></span> </li> <li class="list-group-item details filter-item value -hidden " data-key="dagstuhl.contributor.author" data-value="Buneman, Peter" data-group-selector="dagstuhl.contributor.author.B"> Buneman, Peter <span class="action"><i class="bi bi-plus-circle"></i></span> </li> <li class="list-group-item details filter-group-headline " data-group-selector="dagstuhl.contributor.author.C"> <b>C</b> <span style="float: right;"><i class="bi bi-chevron-down"></i><i class="bi bi-chevron-up"></i></span> </li> <li class="list-group-item details filter-item value -hidden " data-key="dagstuhl.contributor.author" data-value="Ceri, Stefano" data-group-selector="dagstuhl.contributor.author.C"> Ceri, Stefano <span class="action"><i class="bi bi-plus-circle"></i></span> </li> <li class="list-group-item details filter-item value -hidden " data-key="dagstuhl.contributor.author" data-value="Christophides, Vassilis" data-group-selector="dagstuhl.contributor.author.C"> Christophides, Vassilis <span class="action"><i class="bi bi-plus-circle"></i></span> </li> <li class="list-group-item details filter-item value -hidden " data-key="dagstuhl.contributor.author" data-value="Colombo, Andrea" data-group-selector="dagstuhl.contributor.author.C"> Colombo, Andrea <span class="action"><i class="bi bi-plus-circle"></i></span> </li> <li class="list-group-item details filter-group-headline " data-group-selector="dagstuhl.contributor.author.D"> <b>D</b> <span style="float: right;"><i class="bi bi-chevron-down"></i><i class="bi bi-chevron-up"></i></span> </li> <li class="list-group-item details filter-item value -hidden " data-key="dagstuhl.contributor.author" data-value="Deutsch, Alin" data-group-selector="dagstuhl.contributor.author.D"> Deutsch, Alin <span class="action"><i class="bi bi-plus-circle"></i></span> </li> <li class="list-group-item details filter-group-headline " data-group-selector="dagstuhl.contributor.author.F"> <b>F</b> <span style="float: right;"><i class="bi bi-chevron-down"></i><i class="bi bi-chevron-up"></i></span> </li> <li class="list-group-item details filter-item value -hidden " data-key="dagstuhl.contributor.author" data-value="Fan, Wenfei" data-group-selector="dagstuhl.contributor.author.F"> Fan, Wenfei <span class="action"><i class="bi bi-plus-circle"></i></span> </li> <li class="list-group-item details filter-group-headline " data-group-selector="dagstuhl.contributor.author.G"> <b>G</b> <span style="float: right;"><i class="bi bi-chevron-down"></i><i class="bi bi-chevron-up"></i></span> </li> <li class="list-group-item details filter-item value -hidden " data-key="dagstuhl.contributor.author" data-value="Gallier, Jean" data-group-selector="dagstuhl.contributor.author.G"> Gallier, Jean <span class="action"><i class="bi bi-plus-circle"></i></span> </li> <li class="list-group-item details filter-item value -hidden " data-key="dagstuhl.contributor.author" data-value="Gentili, Andrea" data-group-selector="dagstuhl.contributor.author.G"> Gentili, Andrea <span class="action"><i class="bi bi-plus-circle"></i></span> </li> <li class="list-group-item details filter-item value -hidden " data-key="dagstuhl.contributor.author" data-value="Grädel, Erich" data-group-selector="dagstuhl.contributor.author.G"> Grädel, Erich <span class="action"><i class="bi bi-plus-circle"></i></span> </li> <li class="list-group-item details filter-group-headline " data-group-selector="dagstuhl.contributor.author.L"> <b>L</b> <span style="float: right;"><i class="bi bi-chevron-down"></i><i class="bi bi-chevron-up"></i></span> </li> <li class="list-group-item details filter-item value -hidden " data-key="dagstuhl.contributor.author" data-value="Lindell, Steven" data-group-selector="dagstuhl.contributor.author.L"> Lindell, Steven <span class="action"><i class="bi bi-plus-circle"></i></span> </li> <li class="list-group-item details filter-item value -hidden " data-key="dagstuhl.contributor.author" data-value="Liu, Shuhao" data-group-selector="dagstuhl.contributor.author.L"> Liu, Shuhao <span class="action"><i class="bi bi-plus-circle"></i></span> </li> <li class="list-group-item details filter-group-headline " data-group-selector="dagstuhl.contributor.author.M"> <b>M</b> <span style="float: right;"><i class="bi bi-chevron-down"></i><i class="bi bi-chevron-up"></i></span> </li> <li class="list-group-item details filter-item value -hidden " data-key="dagstuhl.contributor.author" data-value="Mrkonjić, Lovro" data-group-selector="dagstuhl.contributor.author.M"> Mrkonjić, Lovro <span class="action"><i class="bi bi-plus-circle"></i></span> </li> <li class="list-group-item details filter-item value -hidden " data-key="dagstuhl.contributor.author" data-value="Myrtakis, Nikolaos" data-group-selector="dagstuhl.contributor.author.M"> Myrtakis, Nikolaos <span class="action"><i class="bi bi-plus-circle"></i></span> </li> <li class="list-group-item details filter-group-headline " data-group-selector="dagstuhl.contributor.author.N"> <b>N</b> <span style="float: right;"><i class="bi bi-chevron-down"></i><i class="bi bi-chevron-up"></i></span> </li> <li class="list-group-item details filter-item value -hidden " data-key="dagstuhl.contributor.author" data-value="Naaf, Matthias" data-group-selector="dagstuhl.contributor.author.N"> Naaf, Matthias <span class="action"><i class="bi bi-plus-circle"></i></span> </li> <li class="list-group-item details filter-group-headline " data-group-selector="dagstuhl.contributor.author.S"> <b>S</b> <span style="float: right;"><i class="bi bi-chevron-down"></i><i class="bi bi-chevron-up"></i></span> </li> <li class="list-group-item details filter-item value -hidden " data-key="dagstuhl.contributor.author" data-value="Sallinger, Emanuel" data-group-selector="dagstuhl.contributor.author.S"> Sallinger, Emanuel <span class="action"><i class="bi bi-plus-circle"></i></span> </li> <li class="list-group-item details filter-item value -hidden " data-key="dagstuhl.contributor.author" data-value="Senellart, Pierre" data-group-selector="dagstuhl.contributor.author.S"> Senellart, Pierre <span class="action"><i class="bi bi-plus-circle"></i></span> </li> <li class="list-group-item details filter-item value -hidden " data-key="dagstuhl.contributor.author" data-value="Suciu, Dan" data-group-selector="dagstuhl.contributor.author.S"> Suciu, Dan <span class="action"><i class="bi bi-plus-circle"></i></span> </li> <li class="list-group-item details filter-group-headline " data-group-selector="dagstuhl.contributor.author.T"> <b>T</b> <span style="float: right;"><i class="bi bi-chevron-down"></i><i class="bi bi-chevron-up"></i></span> </li> <li class="list-group-item details filter-item value -hidden " data-key="dagstuhl.contributor.author" data-value="Tsamardinos, Ioannis" data-group-selector="dagstuhl.contributor.author.T"> Tsamardinos, Ioannis <span class="action"><i class="bi bi-plus-circle"></i></span> </li> <li class="list-group-item details filter-group-headline " data-group-selector="dagstuhl.contributor.author.V"> <b>V</b> <span style="float: right;"><i class="bi bi-chevron-down"></i><i class="bi bi-chevron-up"></i></span> </li> <li class="list-group-item details filter-item value -hidden " data-key="dagstuhl.contributor.author" data-value="Vansummeren, Stijn" data-group-selector="dagstuhl.contributor.author.V"> Vansummeren, Stijn <span class="action"><i class="bi bi-plus-circle"></i></span> </li> <li class="list-group-item details filter-group-headline " data-group-selector="dagstuhl.contributor.author.W"> <b>W</b> <span style="float: right;"><i class="bi bi-chevron-down"></i><i class="bi bi-chevron-up"></i></span> </li> <li class="list-group-item details filter-item value -hidden " data-key="dagstuhl.contributor.author" data-value="Weinstein, Scott" data-group-selector="dagstuhl.contributor.author.W"> Weinstein, Scott <span class="action"><i class="bi bi-plus-circle"></i></span> </li> <li class="list-group-item details filter-item value -hidden " data-key="dagstuhl.contributor.author" data-value="Wong, Limsoon" data-group-selector="dagstuhl.contributor.author.W"> Wong, Limsoon <span class="action"><i class="bi bi-plus-circle"></i></span> </li> </ul> </div> <br /> <div class="grouped-metadata-filter" data-filter-key="dagstuhl.subject.classification"> <ul class="list-group"> <li class="list-group-item filter-headline list-group-item-dark"> <b><span class="count"></span> Subjects</b> <span style="float: right;"><i class="bi bi-chevron-down"></i><i class="bi bi-chevron-up"></i></span> </li> <li class="list-group-item filter-item pinned -hidden" data-value="" data-key=""> <i class="bi bi-pin-angle-fill"></i> <span class="value"></span> <span class="action"><i><i class="bi bi-x-circle"></i></i></span> </li> <li class="list-group-item details buttons"> <span class="btn-group" role="group" aria-label="Show-All/Collapse"> <button type="button" class="btn btn-primary">Show All</button> <button type="button" class="btn btn-secondary">Collapse</button> </span> </li> <li class="list-group-item details show-all -hidden"> <button type="button" class="btn btn-primary">Show All</button> </li> <li class="list-group-item details filter-group-headline -expanded " data-group-selector="dagstuhl.subject.classification.Computing methodologies"> <b>Computing methodologies</b> <span style="float: right;"><i class="bi bi-chevron-down"></i><i class="bi bi-chevron-up"></i></span> </li> <li class="list-group-item details filter-item value " data-key="dagstuhl.subject.classification" data-value="Computing methodologies → Anomaly detection" data-group-selector="dagstuhl.subject.classification.Computing methodologies"> Computing methodologies → Anomaly detection <span class="action"><i class="bi bi-plus-circle"></i></span> </li> <li class="list-group-item details filter-item value " data-key="dagstuhl.subject.classification" data-value="Computing methodologies → Knowledge representation and reasoning" data-group-selector="dagstuhl.subject.classification.Computing methodologies"> Computing methodologies → Knowledge representation and reasoning <span class="action"><i class="bi bi-plus-circle"></i></span> </li> <li class="list-group-item details filter-item value " data-key="dagstuhl.subject.classification" data-value="Computing methodologies → Natural language processing" data-group-selector="dagstuhl.subject.classification.Computing methodologies"> Computing methodologies → Natural language processing <span class="action"><i class="bi bi-plus-circle"></i></span> </li> <li class="list-group-item details filter-group-headline " data-group-selector="dagstuhl.subject.classification.Information systems"> <b>Information systems</b> <span style="float: right;"><i class="bi bi-chevron-down"></i><i class="bi bi-chevron-up"></i></span> </li> <li class="list-group-item details filter-item value -hidden " data-key="dagstuhl.subject.classification" data-value="Information systems" data-group-selector="dagstuhl.subject.classification.Information systems"> Information systems <span class="action"><i class="bi bi-plus-circle"></i></span> </li> <li class="list-group-item details filter-item value -hidden " data-key="dagstuhl.subject.classification" data-value="Information systems → Data management systems" data-group-selector="dagstuhl.subject.classification.Information systems"> Information systems → Data management systems <span class="action"><i class="bi bi-plus-circle"></i></span> </li> <li class="list-group-item details filter-item value -hidden " data-key="dagstuhl.subject.classification" data-value="Information systems → Data mining" data-group-selector="dagstuhl.subject.classification.Information systems"> Information systems → Data mining <span class="action"><i class="bi bi-plus-circle"></i></span> </li> <li class="list-group-item details filter-item value -hidden " data-key="dagstuhl.subject.classification" data-value="Information systems → Database design and models" data-group-selector="dagstuhl.subject.classification.Information systems"> Information systems → Database design and models <span class="action"><i class="bi bi-plus-circle"></i></span> </li> <li class="list-group-item details filter-item value -hidden " data-key="dagstuhl.subject.classification" data-value="Information systems → Database management system engines" data-group-selector="dagstuhl.subject.classification.Information systems"> Information systems → Database management system engines <span class="action"><i class="bi bi-plus-circle"></i></span> </li> <li class="list-group-item details filter-item value -hidden " data-key="dagstuhl.subject.classification" data-value="Information systems → Graph-based database models" data-group-selector="dagstuhl.subject.classification.Information systems"> Information systems → Graph-based database models <span class="action"><i class="bi bi-plus-circle"></i></span> </li> <li class="list-group-item details filter-item value -hidden " data-key="dagstuhl.subject.classification" data-value="Information systems → Information integration" data-group-selector="dagstuhl.subject.classification.Information systems"> Information systems → Information integration <span class="action"><i class="bi bi-plus-circle"></i></span> </li> <li class="list-group-item details filter-item value -hidden " data-key="dagstuhl.subject.classification" data-value="Information systems → Query optimization" data-group-selector="dagstuhl.subject.classification.Information systems"> Information systems → Query optimization <span class="action"><i class="bi bi-plus-circle"></i></span> </li> <li class="list-group-item details filter-item value -hidden " data-key="dagstuhl.subject.classification" data-value="Information systems → Relational database query languages" data-group-selector="dagstuhl.subject.classification.Information systems"> Information systems → Relational database query languages <span class="action"><i class="bi bi-plus-circle"></i></span> </li> <li class="list-group-item details filter-item value -hidden " data-key="dagstuhl.subject.classification" data-value="Information systems → Structured Query Language" data-group-selector="dagstuhl.subject.classification.Information systems"> Information systems → Structured Query Language <span class="action"><i class="bi bi-plus-circle"></i></span> </li> <li class="list-group-item details filter-group-headline " data-group-selector="dagstuhl.subject.classification.Theory of computation"> <b>Theory of computation</b> <span style="float: right;"><i class="bi bi-chevron-down"></i><i class="bi bi-chevron-up"></i></span> </li> <li class="list-group-item details filter-item value -hidden " data-key="dagstuhl.subject.classification" data-value="Theory of computation → Complexity theory and logic" data-group-selector="dagstuhl.subject.classification.Theory of computation"> Theory of computation → Complexity theory and logic <span class="action"><i class="bi bi-plus-circle"></i></span> </li> <li class="list-group-item details filter-item value -hidden " data-key="dagstuhl.subject.classification" data-value="Theory of computation → Data provenance" data-group-selector="dagstuhl.subject.classification.Theory of computation"> Theory of computation → Data provenance <span class="action"><i class="bi bi-plus-circle"></i></span> </li> <li class="list-group-item details filter-item value -hidden " data-key="dagstuhl.subject.classification" data-value="Theory of computation → Database theory" data-group-selector="dagstuhl.subject.classification.Theory of computation"> Theory of computation → Database theory <span class="action"><i class="bi bi-plus-circle"></i></span> </li> <li class="list-group-item details filter-item value -hidden " data-key="dagstuhl.subject.classification" data-value="Theory of computation → Finite Model Theory" data-group-selector="dagstuhl.subject.classification.Theory of computation"> Theory of computation → Finite Model Theory <span class="action"><i class="bi bi-plus-circle"></i></span> </li> <li class="list-group-item details filter-item value -hidden " data-key="dagstuhl.subject.classification" data-value="Theory of computation → Models of computation" data-group-selector="dagstuhl.subject.classification.Theory of computation"> Theory of computation → Models of computation <span class="action"><i class="bi bi-plus-circle"></i></span> </li> <li class="list-group-item details filter-item value -hidden " data-key="dagstuhl.subject.classification" data-value="Theory of computation → Type theory" data-group-selector="dagstuhl.subject.classification.Theory of computation"> Theory of computation → Type theory <span class="action"><i class="bi bi-plus-circle"></i></span> </li> </ul> </div> </div> </div> <div class="offcanvas offcanvas-bottom" tabindex="-1" id="statistics-offcanvas" aria-labelledby="statistics-offcanvas"> <div class="offcanvas-header"> <h5 class="offcanvas-title"></h5> <button type="button" class="btn-close text-reset" data-bs-dismiss="offcanvas" aria-label="Close"></button> </div> <div class="offcanvas-body small" data-context="The Provenance of Elegance in Computation - Essays Dedicated to Val Tannen"> <div style="margin-top: 20vh" class="centered-loader"><div class="loader"></div></div> <iframe class="-hidden"></iframe> </div> </div> </div> </div> <span class="_feedback-button"> <i class="bi bi-question-circle"></i> <span class="text">Questions / Remarks / Feedback</span> </span> <div class="_feedback-form -hidden"> <span class="_feedback-close">X</span> <p>Feedback for Dagstuhl Publishing</p> <div> <textarea class="form-control" name="_feedback"></textarea> <input class="form-control" type="text" name="name" autocomplete="off" placeholder="Name (optional)" maxlength="60" /> <input class="form-control" type="email" name="email" autocomplete="off" placeholder="Email (optional)" maxlength="60" /> <br/> <button class="btn btn-sm btn-default">Send</button> </div> </div> <div class="alert alert-success _feedback-success -hidden"> <span class="glyphicon glyphicon-ok"></span> <h3>Thanks for your feedback!</h3> <div>Feedback submitted</div> <button class="btn btn-white _feedback-done">OK</button> </div> <div class="alert alert-danger _feedback-error -hidden"> <span class="glyphicon glyphicon-remove"></span> <h3>Could not send message</h3> <div>Please try again later or send an <a href="mailto:publishing@dagstuhl.de">E-mail</a></div> <button class="btn btn-white _feedback-done">OK</button> </div> <a class="scroll-up-button -hidden" href="#_top-of-page"> <i class="bi bi-arrow-up-circle"></i> </a> <footer class="page-footer dark"> <div class="container"> <h5>About DROPS</h5> <p>Schloss Dagstuhl - Leibniz Center for Informatics has been operating the Dagstuhl Research Online Publication Server (short: DROPS) since 2004. DROPS enables publication of the latest research findings in a fast, uncomplicated manner, in addition to providing unimpeded, open access to them. All the requisite metadata on each publication is administered in accordance with general guidelines pertaining to online publications (cf. Dublin Core). This enables the online publications to be authorized for citation and made accessible to a wide readership on a permanent basis. Access is free of charge for readers following the open access idea which fosters unimpeded access to scientific publications. </p> </div> <div class="container"> <div class="row"> <div class="col-lg-6"> <h5>Instructions for Authors</h5> <div class="row"> <div class="col-sm-6"> <b>Dagstuhl Series</b><br> <ul> <li><a href="https://submission.dagstuhl.de/series/details/lipics#author">LIPIcs</a></li> <li><a href="https://submission.dagstuhl.de/series/details/oasics#author">OASIcs</a></li> <li><a href="https://submission.dagstuhl.de/series/details/dfu#author">Dagstuhl Follow-Ups</a></li> </ul> </div> <div class="col-sm-6"> <b>Dagstuhl Journals</b><br> <ul> <li><a href="https://submission.dagstuhl.de/series/details/darts#author">DARTS – Dagstuhl Artifacts Series</a></li> <li><a href="https://submission.dagstuhl.de/series/details/dagrep#author">Dagstuhl Reports</a></li> <li><a href="https://submission.dagstuhl.de/series/details/dagman#author">Dagstuhl Manifestos</a></li> <li><a href="https://submission.dagstuhl.de/series/details/lites#author">LITES</a></li> <li><a href="https://submission.dagstuhl.de/series/details/tgdk#author">TGDK – Transactions on Graph Data and Knowledge</a></li> </ul> </div> </div> </div> <div class="col-lg-6"> <h5>Instructions for Editors</h5> <div class="row"> <div class="col-sm-6"> <b>Dagstuhl Series</b><br> <ul> <li><a href="https://submission.dagstuhl.de/series/details/lipics#editor">LIPIcs</a></li> <li><a href="https://submission.dagstuhl.de/series/details/oasics#editor">OASIcs</a></li> <li><a href="https://submission.dagstuhl.de/series/details/dfu#editor">Dagstuhl Follow-Ups</a></li> </ul> </div> <div class="col-sm-6"> <b>Dagstuhl Journals</b><br> <ul> <li><a href="https://submission.dagstuhl.de/series/details/darts#editor">DARTS – Dagstuhl Artifacts Series</a></li> <li><a href="https://submission.dagstuhl.de/series/details/dagrep#editor">Dagstuhl Reports</a></li> <li><a href="https://submission.dagstuhl.de/series/details/dagman#editor">Dagstuhl Manifestos</a></li> <li><a href="https://submission.dagstuhl.de/series/details/lites#editor">LITES</a></li> <li><a href="https://submission.dagstuhl.de/series/details/tgdk#editor">TGDK – Transactions on Graph Data and Knowledge</a></li> </ul> </div> </div> </div> </div> </div> </footer> <div class="copyright"> © 2023-2024 <a href="https://www.dagstuhl.de">Schloss Dagstuhl – LZI GmbH</a> <a href="https://drops.dagstuhl.de/docs/imprint">Imprint</a> <a href="https://drops.dagstuhl.de/docs/privacy">Privacy</a> <a href="https://www.dagstuhl.de/en/publishing/team">Contact</a> </div> <script type="text/javascript" src="https://drops.dagstuhl.de/js/jquery-3.6.0.min.js"></script> <script type="text/javascript" src="https://drops.dagstuhl.de/js/app.js?drops-core-2024-10-22"></script> <script type="text/javascript" src="https://drops.dagstuhl.de/js/popper.min.js"></script> <script type="text/javascript" src="https://drops.dagstuhl.de/js/circle-progress.js"></script> <script type="text/javascript"> $(document).ready(function() { const view = { statsServer: 'https://drops-stats.dagstuhl.de', animationStarted: false, isScrolledIntoView: function (elem) { const rect = elem.getBoundingClientRect(); const elemTop = rect.top; //const elemBottom = rect.bottom; // const elemHeight = rect.height; return (elemTop >= 0) && (elemTop <= window.innerHeight); }, progressCircle: function ($el) { $el.find('.circle').circleProgress({ value: 1, size: 80, fill: { color: '#555' }, animation: { duration: 1200 } }); }, countUp: function($el) { $el.find('.number').each(function() { const $this = $(this); const number = parseInt($this.attr('data-number')); let suffix = ''; if (number > 90000) { $this.text(Math.ceil(number/1000)+' k'); suffix = ' k'; } else if (number > 90000000) { $this.text(Math.ceil(number/1000000)+' m'); suffix = ' m'; } else { $this.text(Math.ceil(number)) } $({ Counter: 0 }).animate({ Counter: $this.text().replace(suffix, '').replace(',', '') }, { duration: 1000, easing: 'swing', step: function() { $this.text(Math.ceil(this.Counter).toString().replace(/\B(?=(\d{3})+(?!\d))/g, ",") + suffix); } }); }); }, checkVisibility: function() { const $container = $('.stats-total'); if (view.isScrolledIntoView($container[0])) { if (!view.animationStarted) { view.animationStarted = true; view.progressCircle($container); setTimeout(function() { view.countUp($container) }, 200); } } }, initialize: function() { $.ajax({ type: 'get', url: view.statsServer + '/api/external/drops2/volume/OASIcs-volume-119/-/stats', success: function (result) { $('.total-downloads .number').attr('data-number', result.total.downloads); $('.total-metadata-views .number').attr('data-number', result.total.clicks); window.addEventListener('scroll', view.checkVisibility); view.checkVisibility(); }, error: function () { $('.total-downloads .number').text(0); $('.total-metadata-views .number').text(0); window.addEventListener('scroll', view.checkVisibility); view.checkVisibility(); } }); } }; view.initialize(); }); </script> <script type="text/javascript"> $(document).ready(function() { const view = { trackInvestigation: function(e) { const $entity = $(e.currentTarget).parent().parent(); const permanentId = $entity.attr('data-permanent-id'); $.ajax({ url: '/entities/' + permanentId + '/_investigation', type: 'get', }); }, initialize: function() { $('a.investigation').on('click', view.trackInvestigation); } }; view.initialize(); }); </script> <script type="text/javascript"> $(document).ready(function() { const view = { $el: { root: $('.grouped-metadata-filter'), freeTextFilter: $('#free-text-filter') }, appliedFilters: { freeText: [] }, methods: { toggleDetails: function(e) { var $current = $(e.currentTarget); var $parent = $current.parent(); $parent.toggleClass('-expanded'); }, toggleGroup: function(e) { var $current = $(e.currentTarget); var selector = $current.attr('data-group-selector'); $current.toggleClass('-expanded'); $('.filter-item[data-group-selector="' + selector + '"]').toggleClass('-hidden'); }, toggleFilter: function(e) { var $current = $(e.currentTarget); var key = $current.attr('data-key'); var value = $current.attr('data-value'); if (view.appliedFilters[key] === undefined) { view.appliedFilters[key] = []; } var index = view.appliedFilters[key].indexOf(value); if (index !== -1) { view.appliedFilters[key].splice(index, 1); $('.grouped-metadata-filter[data-filter-key="'+key+'"]').find('.pinned[data-value="'+value+'"]').remove(); } else { view.appliedFilters[key].push(value); var $template = $('.grouped-metadata-filter[data-filter-key="'+key+'"]').find('.pinned.-hidden'); var $filter = $template.clone(); $filter.find('.value').html(value); $filter.attr('data-value', value) .attr('data-key', key) .removeClass('-hidden') .insertAfter($template) .on('click', view.methods.toggleFilter); } var event = (index !== -1) ? 'removeFilter' : 'addFilter'; var filterCount = 0; for(var filterKey in view.appliedFilters) { filterCount += view.appliedFilters[filterKey].length; } $(document).trigger('grouped-metadata-filter:' + event, { key: key, value: value, appliedFilters: view.appliedFilters, filterCount: filterCount }); }, setFreeTextFilter: function(e) { var $current = $(e.currentTarget); var value = $current.val().trim(); if (value === '') { view.appliedFilters.freeText = [] } else { view.appliedFilters.freeText = [ value ]; } var filterCount = 0; for(var filterKey in view.appliedFilters) { filterCount += view.appliedFilters[filterKey].length; } $(document).trigger('grouped-metadata-filter:addFilter', { key: 'free-text', value: value, appliedFilters: view.appliedFilters, filterCount: filterCount }); }, dropAllFilters: function() { $('.grouped-metadata-filter').find('.filter-item.pinned:not(.-hidden)').click(); $('#free-text-filter').val('').trigger('keyup'); }, expandAllGroups: function(e) { var $current = $(e.currentTarget); $current.parent().parent().parent().find('.filter-group-headline:not(.-expanded)').click(); }, collapseAllGroups: function(e) { var $current = $(e.currentTarget); var $filter = $current.parent().parent().parent(); $filter.find('.filter-group-headline.-expanded').click(); $filter.find('.filter-headline').click(); $filter.find('.filter-headline').click(); } }, initialize: function() { view.$el.root.each(function() { var count = $(this).find('.filter-item.value').length; $(this).find('.filter-headline .count').text(count); }); view.$el.root.find('.filter-group-headline').on('click', view.methods.toggleGroup); view.$el.root.find('.filter-item').on('click', view.methods.toggleFilter); view.$el.root.find('.filter-headline').on('click', view.methods.toggleDetails); view.$el.root.find('.buttons .btn-primary').on('click', view.methods.expandAllGroups); view.$el.root.find('.buttons .btn-secondary').on('click', view.methods.collapseAllGroups); view.$el.freeTextFilter.on('keyup', view.methods.setFreeTextFilter); view.$el.freeTextFilter.on('search', view.methods.setFreeTextFilter); $(document).on('grouped-metadata-filter:dropAllFilters', view.methods.dropAllFilters); } }; view.initialize(); }); </script> <script type="text/javascript"> $(document).ready(function() { const view = { normalize: function(string) { return string.normalize('NFD').replace(/[\u0300-\u036f]/g, ""); }, applyFilters: function(e, data) { var $documents = $('.document'); var $noResults = $('.no-results'); $documents.each(function() { var $document = $(this); var matches = 0; for(var filterKey in data.appliedFilters) { var values = data.appliedFilters[filterKey]; if (filterKey === 'freeText' && values[0] !== undefined && values[0] !== '') { var regex = new RegExp(view.normalize(values[0].toLowerCase()), 'i'); matches += view.normalize($document.html()).match(regex) ? 1 : 0; } else { values.forEach(function (value) { matches += $document.find('.selectors').find('[data-key="' + filterKey + '"][data-value="' + value + '"]').length }); } } if (matches === data.filterCount) { $document.removeClass('-hidden'); } else { $document.addClass('-hidden') } }); if ($documents.parent().find('.document:not(.-hidden').length === 0) { $noResults.removeClass('-hidden'); } else { $noResults.addClass('-hidden'); } document.getElementById('end-of-header').scrollIntoView(); var filterInfo = ''; if (data.filterCount === 1) { filterInfo = '1 filter applied   ×'; } else if (data.filterCount > 1) { filterInfo = data.filterCount + ' filters applied   ×'; } $('._filter-info').html(filterInfo); if (data.appliedFilters.freeText[0] !== undefined && data.appliedFilters.freeText[0] !== '') { $('#free-text-filter').addClass('-active'); } else { $('#free-text-filter').removeClass('-active'); } }, initialize: function() { $(document).on('grouped-metadata-filter:addFilter', view.applyFilters); $(document).on('grouped-metadata-filter:removeFilter', view.applyFilters); } }; view.initialize(); }); </script> <script type="text/javascript"> function _enableFeedback() { var $feedbackButton = $('._feedback-button, .fixed-beta-button'); var $feedbackClose = $('._feedback-close'); var $feedbackForm = $('._feedback-form'); var $feedbackSubmit = $('._feedback-form button'); var $textarea = $feedbackForm.find('textarea'); var $feedbackSuccess = $('._feedback-success'); var $feedbackError = $('._feedback-error'); var $feedbackDoneButton = $('._feedback-done'); $feedbackButton.addClass('_show'); $feedbackButton.on('click', function () { $feedbackButton.addClass('-hidden'); $feedbackForm.removeClass('-hidden'); $textarea.focus(); }); $feedbackClose.on('click', function () { $feedbackSuccess.addClass('-hidden'); $feedbackForm.addClass('-hidden'); $feedbackButton.removeClass('-hidden'); }); $feedbackDoneButton.on('click', function () { $feedbackError.addClass('-hidden'); $feedbackSuccess.addClass('-hidden'); $feedbackForm.addClass('-hidden'); $feedbackButton.removeClass('-hidden'); }); $feedbackSubmit.on('click', function () { var message = $textarea.val(); if (message === undefined) { message = ''; } if (message.trim() !== '') { $.ajax({ url: '/api/v1/feedback', type: 'post', data: { content: message, context: window.location.href, name: $('input[name="name"]').val(), email: $('input[name="email"]').val(), }, success: function (result) { if (result === 'success') { $textarea.val(''); $feedbackSuccess.removeClass('-hidden'); } else { $feedbackError.removeClass('-hidden'); } }, error: function () { $feedbackError.removeClass('-hidden'); } }); } }); } var _defer_counter = 0; function _defer(method) { if (window.jQuery) { method(); } else { if (_defer_counter < 20) { setTimeout(function () { _defer(method); console.log(_defer_counter); _defer_counter++; }, 500); } } } setTimeout(function() { _defer(_enableFeedback); }, 1000); </script> <script type="text/javascript"> $(document).ready(function() { $('._filter-info').on('click', function() { $(document).trigger('grouped-metadata-filter:dropAllFilters'); }); }); </script> <script type="text/javascript"> $(document).ready(function() { const statistics = { statsServer: 'https://drops-stats.dagstuhl.de', showStatistics: function(e) { e.preventDefault(); const $offCanvas = $('#statistics-offcanvas'); const $iframe = $offCanvas.find('iframe'); const $loader = $offCanvas.find('.centered-loader'); $iframe.addClass('-hidden'); $loader.removeClass('-hidden'); $iframe[0].onload = function () { $iframe.removeClass('-hidden'); $loader.addClass('-hidden'); }.bind(this); const modeParameter = ''; const $target = $(e.currentTarget); const entityId = $target.attr('data-entity'); const title = $target.attr('data-title'); const embedUrl = statistics.statsServer + '/embed/external/drops2/' + entityId + modeParameter; let context = $offCanvas.find('.offcanvas-body').attr('data-context'); if (context === title) { context = ''; } if (context !== '') { context += '<br>'; } $offCanvas.find('.offcanvas-title').html(context + '<h2 style="font-weight: bold">' + title + '</h2>'); $offCanvas.offcanvas('show'); $offCanvas.find('iframe').attr('src', embedUrl); return false; }, initialize: function() { $('.btn-statistics').on('click', this.showStatistics); } }; statistics.initialize(); }); </script> <script type="text/javascript"> $(document).ready(function() { const app = { maxScrollPos: window.innerWidth < 500 ? 100 // mobile : 400, // desktop $el : { navbarSearch: $('nav .navbar-search'), fixedSearchButton: $('.fixed-search-button'), copyToClipboard: $('.copy-to-clipboard') }, methods: { hideMenuOnScroll: function(scrollPos) { const $menu = $('nav.navbar.main'); const $stickySearch = $('.search.sticky'); const $banner = $('#_banner'); const $fixedSearchButton = $('.fixed-search-button'); if (scrollPos > app.maxScrollPos) { $menu.addClass('-hide'); $banner.addClass('-hide'); $stickySearch.addClass('-top'); $fixedSearchButton.addClass('-show'); } else { app.methods.showMenu(null, false); } }, showMenu: function(e, focus) { const $menu = $('nav.navbar.main'); const $stickySearch = $('.search.sticky'); const $banner = $('#_banner'); const $fixedSearchButton = $('.fixed-search-button'); $menu.removeClass('-hide'); $banner.removeClass('-hide'); $stickySearch.removeClass('-top'); $fixedSearchButton.removeClass('-show'); if (focus !== false) { $('.navbar-search').find('input[name="term"]').focus(); } }, showUpLinkOnScroll: function(scrollPos) { const $upLink = $('.scroll-up-button'); if (scrollPos > app.maxScrollPos) { $upLink.removeClass('-hidden'); } else { $upLink.addClass('-hidden'); } }, scrollHandler: function() { const scrollPos = $(document).scrollTop(); app.methods.hideMenuOnScroll(scrollPos); app.methods.showUpLinkOnScroll(scrollPos); }, copyToClipboard: function(e) { e.preventDefault(); const $current = $(e.currentTarget); // console.log($current.attr('data-selector')); const element = $('#'+$current.attr('data-selector'))[0]; console.log(element); element.select(); document.execCommand("copy"); const $success = $current.find('.bi-check'); $success.removeClass('-hidden'); setTimeout(function() { $success.addClass('-hidden'); }, 1000); }, initTooltips: function() { const tooltipTriggerList = [].slice.call(document.querySelectorAll('[data-bs-toggle="tooltip"]')) const tooltipList = tooltipTriggerList.map(function (tooltipTriggerEl) { return new bootstrap.Tooltip(tooltipTriggerEl) }); }, expandSearch: function() { app.$el.navbarSearch.addClass('expanded'); }, collapseSearch: function(e) { if (!$(e.currentTarget).is('button.btn-outline-success')) { app.$el.navbarSearch.removeClass('expanded'); } }, initDeepLinksTabs: function() { const innerAnchors = [ 'resource-articles', 'cfp-si-resources', 'cfp-si-autonomous-systems-and-knowledge-graphs' ]; let anchors = []; $('a[role="tab"]').each(function() { anchors.push($(this).attr('aria-controls')); }); innerAnchors.forEach(function(anchor) { if ($('#'+anchor).length > 0) { anchors.push(anchor); } }); if (anchors.length === 0) { return; } let selectedAnchor = window.location.hash.substring(1); if (anchors.indexOf(selectedAnchor) === -1) { $('#publications-tab').tab('show'); window.scrollTo(0,0); return; } if (selectedAnchor !== 'publications') { const innerAnchorIndex = innerAnchors.indexOf(selectedAnchor); // anchor sits inside tab -> open the tab first, then scroll to anchor if (innerAnchorIndex > -1) { const $tab = $('#'+selectedAnchor).closest('.tab-pane'); console.log($tab); try { $('#'+$tab.attr('id')+'-tab').tab('show'); } catch (e) { } setTimeout(function () { $('#' + selectedAnchor)[0].scrollIntoView(); }, 800); } else { try { $('#' + selectedAnchor + '-tab').tab('show'); } catch (e) { } window.scrollTo(0, 0); } } $('[data-tab-link]').on('click', function(e) { const $target = $(e.currentTarget); let href = $target.attr('href'); let scrollLink = null; if (href === '#cfp-si-list') { scrollLink = href; href = '#cfp'; } try { console.log(href); $(href+'-tab').tab('show'); } catch(e) { } console.log(scrollLink); if (scrollLink !== null) { setTimeout(function() { $(scrollLink)[0].scrollIntoView(); }, 200); } else { setTimeout(function() { window.scrollTo(0,0); }, 200); } }); } }, initialize: function() { $(window).on('scroll', app.methods.scrollHandler); $(window).on('scroll-to-top', function() { window.scrollTo(0,0) }); $(document).trigger('scroll'); // set correct status for scroll-related parts (navbar/back-to-top) on page reload app.$el.copyToClipboard.on('click', app.methods.copyToClipboard); app.$el.fixedSearchButton.on('click', app.methods.showMenu); app.$el.navbarSearch.find('input').on('click', app.methods.expandSearch) app.$el.navbarSearch.find('input').on('blur', app.methods.collapseSearch); app.methods.initTooltips(); app.methods.initDeepLinksTabs(); } }; app.initialize(); }); </script> </body> </html>

CINXE.COM

The Provenance of Elegance in Computation - Essays Dedicated to Val Tannen