Analytic variations on the common subexpression problem

DOI10.1007/BFB0032034MaRDI QIDQ4038694zbMATH OpenFDO

Authors P. Sipala, Jean-Marc Steyaert, Philippe Flajolet

Publication date 18 May 1993

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/BFB0032034

zbMATH Keywords

algebraic enumerationasymptotic analysisbranching modelscompaction problemgenerating functionsrandom uniform modeltree compaction

Mathematics Subject Classification ID

Data structures (68P05) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• scientific article; zbMATH DE number 3995070
• A program-algebraic approach to eliminating common subexpressions
• Compaction for two models of logarithmic‐depth trees: Analysis and experiments
• Minimizing space usage in evaluation of expression trees
• Compacted binary trees admit a stretched exponential

Cited in

(33)

• On finding common subtrees
• Encoding trees by linear recurrence sequences
• A bijection of plane increasing trees with relaxed binary trees of right height at most one
• Learning grammars for architecture-specific facade parsing
• Compacted binary trees admit a stretched exponential
• Partial derivative automaton by compressing regular expressions
• Distinct fringe subtrees in random trees
• Manipulation of regular expressions using derivatives: an overview
• Supertrees
• Asymptotic enumeration of compacted binary trees of bounded right height
• Counting and sampling gene family evolutionary histories in the duplication-loss and duplication-loss-transfer models
• Constructing small tree grammars and small circuits for formulas
• Noncontiguous pattern containment in binary trees
• XML compression via directed acyclic graphs
• A program-algebraic approach to eliminating common subexpressions
• Grammar-Based Tree Compression
• scientific article; zbMATH DE number 1273690 (Why is no real title available?)
• Expectation transfer between branching processes and random trees
• On the sub-permutations of pattern avoiding permutations
• scientific article; zbMATH DE number 3995070 (Why is no real title available?)
• On the Degeneracy of Random Expressions Specified by Systems of Combinatorial Equations
• Uniform random expressions lack expressivity
• Analytic analysis of algorithms
• Compaction for two models of logarithmic‐depth trees: Analysis and experiments
• Simplifications of Uniform Expressions Specified by Systems
• Investigations into proof structures
• Average-case analysis of unification algorithms
• Asymptotic analysis and efficient random sampling of directed ordered acyclic graphs
• Asymptotics of relaxed k-ary trees
• On the number of distinct fringe subtrees in binary search trees
• The likely maximum size of twin subtrees in a large random tree
• Compressed structures for partial derivative automata constructions
• Pattern avoidance in binary trees

This page was built for publication: Analytic variations on the common subexpression problem

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