JournalTOCs

ACM Transactions on Computational Logic (TOCL)
[SJR: 0.985] [H-I: 31] [4 followers] Follow

Hybrid journal (It can contain Open Access articles)
ISSN (Print) 1529-3785 - ISSN (Online) 1557-945X
Published by ACM

[45 journals]

ACM Transactions on Computational Logic (TOCL) Volume 18 Issue 4,
September 2017 (Issue-in-Progress)
- PubDate: Thu, 21 Sep 2017 00:00:00 GMT
Algorithmic Compression of Finite Tree Languages by Rigid Acyclic Grammars
- Abstract: Sebastian Eberhard, Gabriel Ebner, Stefan Hetzl
  
  We present an algorithm to optimally compress a finite set of terms using a vectorial totally rigid acyclic tree grammar. This class of grammars has a tight connection to proof theory, and the grammar compression problem considered in this article has applications in automated deduction. The algorithm is based on a polynomial-time reduction to the MaxSAT optimization problem. The crucial step necessary to justify this reduction consists of applying a term rewriting relation to vectorial totally rigid acyclic tree grammars. Our implementation of this algorithm performs well on a large real-world dataset.
  PubDate: Thu, 21 Sep 2017 00:00:00 GMT