On the Word, Subsumption, and Complement Problem for Recurrent Term Schematizations

Miki Hermann 1 Gernot Salzer
1 PROTHEO - Constraints, automatic deduction and software properties proofs
INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
Abstract : We investigate the word and the subsumption problem for recurrent term schematizations, which are a special type of constraints based on iteration. By means of unification, we reduce these problems to a fragment of Presburger arithmetic. Our approach is applicable to all recurrent term schematizations having a finitary unification algorithm. Furthermore, we study a particular form of the complement problem. Given a finite set of terms, we ask whether its complement can be finitely represented by schematizations, using only the equality predicate without negation. The answer is negative as there are ground terms too complex to be represented by schematizations with limited resources.
Mots-clés : problème du mot recurrent set constraints word problem subsumption problem recurrent term schematization problème de la subsomption complément schématisation récurrente contraintes ensemblistes récurrentes
Type de document :
Communication dans un congrès
L. Brim and J. Gruska and J. Zlatuska. 23nd International Conference on Mathematical Foundations of Computer Science, 1998, Brno, République Tchèque, Springer, 1450, pp.257-266, 1998, Lecture Notes in Computer Science
Liste complète des métadonnées
https://hal.inria.fr/inria-00098687
Contributeur : Publications Loria <>
Soumis le : mardi 26 septembre 2006 - 08:16:32
Dernière modification le : jeudi 11 janvier 2018 - 06:19:58
Document(s) archivé(s) le : mercredi 29 mars 2017 - 12:37:30

Fichiers

98-R-020.pdf

Identifiants

  • HAL Id : inria-00098687, version 1

Collections

INRIA | LORIA | UNIV-LORRAINE

Citation

Miki Hermann, Gernot Salzer. On the Word, Subsumption, and Complement Problem for Recurrent Term Schematizations. L. Brim and J. Gruska and J. Zlatuska. 23nd International Conference on Mathematical Foundations of Computer Science, 1998, Brno, République Tchèque, Springer, 1450, pp.257-266, 1998, Lecture Notes in Computer Science. 〈inria-00098687〉

Exporter

BibTeX TEI DC DCterms EndNote

Partager

Métriques

Consultations de la notice

152

Téléchargements de fichiers

51

Contact


archive-ouverte@inria.fr