Decidable fragments of simultaneous rigid reachability

Véronique Cortier Harald Ganzinger Florent Jacquemard 1 Margus Veanes
1 PROTHEO - Constraints, automatic deduction and software properties proofs
INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
Abstract : In this paper we prove decidability results of restricted fragments of simultaneous rigid reachability or SRR, that is the nonsymmetrical form of simultaneous rigid E-unification or SREU. The absence of symmetry forces us to use different methods, from the ones that have been successful in the context of SREU in the past (for example word equations). The methods that we use instead involve finite (tree) automata techniques, and the decidability proofs provide precise computational complexity bounds. The main results are 1) monadic SRR with ground rules is PSPACE-complete, and 2) balanced SRR with ground rules is EXPTIME-complete. The first result indicates the difference in computational power between fragments of SREU with ground rules and nonground rules, respectively, due to a straightforward encoding of word equations in monadic SREU (with nonground rules). The second result establishes the decidability and precise complexity of the largest known subfragment of nonmonadic SREU.
Keywords : accessibilite unification rigide reachability. rigid unification term rewriting reecriture de termes accessibilite.
Type de document :
Communication dans un congrès
Jiri Wiedermann, Peter van Emde Boas, Mogens Nielsen. International Colloquium on Automata, Languages, & Programming - ICALP'99, Jul 1999, Prague, Czech Republic, Springer-Verlag, 1644, pp.250-260, 1999, Lecture notes in computer science
Liste complète des métadonnées
https://hal.inria.fr/inria-00098806
Contributeur : Publications Loria <>
Soumis le : mardi 26 septembre 2006 - 08:38:45
Dernière modification le : jeudi 11 janvier 2018 - 06:19:58

Identifiants

  • HAL Id : inria-00098806, version 1

Collections

INRIA | LORIA | UNIV-LORRAINE

Citation

Véronique Cortier, Harald Ganzinger, Florent Jacquemard, Margus Veanes. Decidable fragments of simultaneous rigid reachability. Jiri Wiedermann, Peter van Emde Boas, Mogens Nielsen. International Colloquium on Automata, Languages, & Programming - ICALP'99, Jul 1999, Prague, Czech Republic, Springer-Verlag, 1644, pp.250-260, 1999, Lecture notes in computer science. 〈inria-00098806〉

Exporter

BibTeX TEI DC DCterms EndNote

Partager

Métriques

Consultations de la notice

159

Contact


archive-ouverte@inria.fr