2026-08-14T09:08:16Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:20107 2026-01-26T13:48:38Z ddc:004 open_access

An Intensional Expressiveness Gap of Comprehension Syntax Wong, Limsoon Comprehension syntax intensional expressive power limited-mixing lemma 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Limsoon Wong 2024 Is Part Of OASIcs, Volume 119, The Provenance of Elegance in Computation - Essays Dedicated to Val Tannen (2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/OASIcs.Tannen.11 urn:nbn:de:0030-drops-201074 https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.Tannen.11 eng https://creativecommons.org/licenses/by/4.0/legalcode