Constructing small tree grammars and small circuits for formulas

作者：

Highlights：

• A grammar-based tree compressor based on BISECTION is developed.

• The output grammar has size O(n/log⁡n), where n is the size of the input tree.

• A logspace as well as a linear time implementation is presented.

摘要

•A grammar-based tree compressor based on BISECTION is developed.•The output grammar has size O(n/log⁡n), where n is the size of the input tree.•A logspace as well as a linear time implementation is presented.

论文关键词：Grammar-based compression,Tree compression,Arithmetical circuits over semirings

论文评审过程：Received 24 August 2015, Revised 11 June 2016, Accepted 20 December 2016, Available online 29 December 2016, Version of Record 27 February 2017.

论文官网地址：https://doi.org/10.1016/j.jcss.2016.12.007