On the complexity of linear and stratified context matching problems

Manfred Schmidt-Schauss Jürgen Stuber 1
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 complexity landscape of context matching with respect to the number of occurrences of variables (i.e. linearity vs. varity 2) and various restrictions of stratification. We show that stratified context matching (SCM) and varity 2 context matching are NP-complete, but that stratified simultaneous monadic context matching (SSMCM) is in P. SSMCM is equivalent to stratified simultaneous word matching (SSWM). We also show that the linear and the Comon-restricted case are in P and of time complexity O(n³). We give an algorithm for context matching and discuss how the performance of the general case can be improved through the use of information derived from polynomial approximations of the problem.
Type de document :
Communication dans un congrès
2nd International Workshop on Complexity in Automated Deduction - CiAD'02, Jul 2002, Copenhagen, Denmark. 18 p, 2002
Liste complète des métadonnées

https://hal.inria.fr/inria-00100988
Contributeur : Publications Loria <>
Soumis le : mardi 26 septembre 2006 - 14:53:20
Dernière modification le : jeudi 11 janvier 2018 - 06:19:57

Identifiants

  • HAL Id : inria-00100988, version 1

Collections

Citation

Manfred Schmidt-Schauss, Jürgen Stuber. On the complexity of linear and stratified context matching problems. 2nd International Workshop on Complexity in Automated Deduction - CiAD'02, Jul 2002, Copenhagen, Denmark. 18 p, 2002. 〈inria-00100988〉

Partager

Métriques

Consultations de la notice

48