Entropy conservation for comparison-based algorithms

DOI10.1016/J.TOPOL.2021.107913MaRDI QIDQ2077296zbMATH OpenOpenAlexFDO

Authors M. 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

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

Recommendations

• Comparing Notions of Computational Entropy
• Comparing notions of computational entropy
• scientific article; zbMATH DE number 3930881
• On Entropic Convergence of Algorithms
• scientific article; zbMATH DE number 4009819
• scientific article; zbMATH DE number 7113331
• Stochastic comparisons of cumulative entropies
• Computational analogues of entropy
• An algorithm for maximizing entropy subject to simple bounds

Cites work

• scientific article; zbMATH DE number 53952 (Why is no real title available?)
• scientific article; zbMATH DE number 1052006 (Why is no real title available?)
• scientific article; zbMATH DE number 6157240 (Why is no real title available?)
• A characterization of partial metrizability: Domains are quantifiable.
• Approximating SP-orders through total preorders: incomparability and transitivity through permutations
• Counting linear extensions
• Entropy and semivaluations on semilattices
• Modeling concurrency with partial orders
• Non-Hausdorff topology and domain theory. Selected topics in point-set topology
• Running time of the treapsort algorithm
• The Analysis of Heapsort
• The correspondence between partial metrics and semivaluations
• \(\mathcal{MOQA}\); unlocking the potential of compositional static average-case analysis

Cited in

(3)

• On Thurston’s core entropy algorithm
• scientific article; zbMATH DE number 4009819 (Why is no real title available?)
• scientific article; zbMATH DE number 7113331 (Why is no real title available?)

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2077296)