Grammatical compression: compressed equivalence and other problems

Abstract : In this work, we focus our attention to algorithmic solutions for problems where the instances are presented as straight-line programs on a given algebra. In our exposition, we try to survey general results by presenting some meaningful examples; moreover, where possible, we outline the proofs in order to give an insight of the methods and the techniques. We recall some recent results for the problem PosSLP, consisting of deciding if the integer defined by a straight-line program on the ring Z is greater than zero; we discuss some implications in the areas of numerical analysis and strategic games. Furthermore, we propose some methods for reducing Compressed Word Problem from an algebra to another; reductions from trace monoids to the semiring of nonnegative integers are exhibited and polynomial time algorithms for compressed equivalence in monoids related to Dyck reductions are shown. Finally, we consider inclusion problems for context-free languages, proving how in some cases efficient algorithms for these problems benefit from the ability to work with compressed data.
Type de document :
Article dans une revue
Discrete Mathematics and Theoretical Computer Science, DMTCS, 2010, 12 (4), pp.109-126
Liste complète des métadonnées

Littérature citée [40 références]  Voir  Masquer  Télécharger
Contributeur : Service Ist Inria Sophia Antipolis-Méditerranée / I3s <>
Soumis le : mardi 13 mai 2014 - 15:37:35
Dernière modification le : lundi 15 janvier 2018 - 17:06:09
Document(s) archivé(s) le : lundi 10 avril 2017 - 22:24:59


Fichiers produits par l'(les) auteur(s)


  • HAL Id : hal-00990458, version 1



Alberto Bertoni, Roberto Radicioni. Grammatical compression: compressed equivalence and other problems. Discrete Mathematics and Theoretical Computer Science, DMTCS, 2010, 12 (4), pp.109-126. 〈hal-00990458〉



Consultations de la notice


Téléchargements de fichiers