Functional programs as compressed data

DOI10.1007/S10990-013-9093-ZMaRDI QIDQ526441zbMATH OpenOpenAlexFDO

Authors Naoki Kobayashi, Kazutaka Matsuda, Ayumi Shinohara, Kazuya Yaguchi

Publication date 15 May 2017

Published in Higher-Order and Symbolic Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s10990-013-9093-z

zbMATH Keywords

data compressionprogram transformationhigher-order model checkingfunctional programssemantics-based program manipulation

Mathematics Subject Classification ID

Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Specification and verification (program logics, model checking, etc.) (68Q60) Functional programming and lambda calculus (68N18)

Recommendations

• Compact bit encoding schemes for simply-typed lambda-terms
• Simple, Effective Code-Size Reduction for Functional Programs
• Toward an abstract theory of data compression
• TREE COMPRESSION AND OPTIMIZATION WITH APPLICATIONS
• scientific article; zbMATH DE number 2185706

Cites work

• scientific article; zbMATH DE number 1142293 (Why is no real title available?)
• scientific article; zbMATH DE number 1380900 (Why is no real title available?)
• scientific article; zbMATH DE number 2087432 (Why is no real title available?)
• A filter lambda model and the completeness of type assignment
• A fully linear-time approximation algorithm for grammar-based compression
• A practical linear time algorithm for trivial automata model checking of higher-order recursion schemes
• Application of Lempel-Ziv factorization to the approximation of grammar-based compression.
• Automata, Languages and Programming
• Binary lambda calculus and combinatory logic
• Bottom-up and top-down tree transformations— a comparison
• Collage system: A unifying framework for compressed pattern matching.
• Complete restrictions of the intersection type discipline
• Complexity of model checking recursion schemes for fragments of the modal mu-calculus
• Decidability of higher-order matching
• Efficient algorithms to compute compressed longest common substrings and compressed palindromes
• Foundations of Software Science and Computation Structures
• Functional pearl: every bit counts
• High level tree transducers and iterated pushdown tree transducers
• Intersection type assignment systems
• Jewels of Stringology
• Model checking higher-order programs
• Semantic evaluation; intersection types and complexity of simply typed lambda calculus
• The IO- and OI-hierarchies
• The Smallest Grammar Problem
• The typed lambda-calculus is not elementary recursive
• Tree transducers, L systems, and two-way machines
• Types and higher-order recursion schemes for verification of higher-order programs
• Untyped Recursion Schemes and Infinite Intersection Types
• XML Type Checking Using High-Level Tree Transducer

Cited in

(7)

• Compaction of Church numerals
• Grammar-Based Tree Compression
• Simple, Effective Code-Size Reduction for Functional Programs
• Functional pearl: every bit counts
• Compact bit encoding schemes for simply-typed lambda-terms
• Lambda calculus with algebraic simplification for reduction parallelisation: extended study
• scientific article; zbMATH DE number 2087558 (Why is no real title available?)

This page was built for publication: Functional programs as compressed data

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