Entropy conservation for comparison-based algorithms

DOI10.1016/j.topol.2021.107913OpenAlexW3213070776MaRDI QIDQ2077296

Michel Schellekens

Publication date: 25 February 2022

Published in: Topology and its Applications (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2011.07278

zbMATH Keywords

entropydata structurespartial orderslinear extensionssorting and searchingtopological sortscomparison-based algorithmsseries-parallel partial orders

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Analysis of algorithms (68W40) Partial orders, general (06A06) Searching and sorting (68P10) Semantics in the theory of computing (68Q55) Measures of information, entropy (94A17) Data structures (68P05)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Running time of the treapsort algorithm
• \(\mathcal{MOQA}\); unlocking the potential of compositional static average-case analysis
• Modeling concurrency with partial orders
• Counting linear extensions
• A characterization of partial metrizability: Domains are quantifiable.
• The correspondence between partial metrics and semivaluations
• The Analysis of Heapsort
• Non-Hausdorff Topology and Domain Theory
• Approximating SP-orders through total preorders: incomparability and transitivity through permutations
• Entropy and semivaluations on semilattices

This page was built for publication: Entropy conservation for comparison-based algorithms