2023/11/30 by Shin-Cheng Mu, Mu, Shin-Cheng
Computer Science · #D.2.4 #F.3.1 #FOS: Computer and information sciences #Formal Methods in Verification #Logic, programming, and type systems #Parallel Computing and Optimization Techniques #Programming Languages (cs.PL)
paper · pdf · doi:10.48550/arxiv.2311.18528
openalex publication_date 2023/11/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Some top-down problem specifications, if executed directly, may compute sub-problems repeatedly. Instead, we may want a bottom-up algorithm that stores solutions of sub-problems in a table to be reused. It can be tricky, however, to figure out how the table can be represented and efficiently maintained. We study a special case: computing a function h taking lists as inputs such that h~xs is defined in terms of all immediate sublists of xs. Richard Bird studied this problem in 2008, and presented a concise but cryptic algorithm without much explanation. We give this algorithm a proper derivation, and discover a key property that allows it to work. The algorithm builds trees that have certain shapes -- the sizes along the left spine is a diagonal in Pascal's triangle. The crucial function we derive transforms one diagonal to the next.