Skip to Main content Skip to Navigation
Conference papers

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.
Document type :
Conference papers
Complete list of metadata
Contributor : Publications Loria <>
Submitted on : Tuesday, September 26, 2006 - 2:53:20 PM
Last modification on : Friday, February 26, 2021 - 3:28:05 PM


  • HAL Id : inria-00100988, version 1



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. ⟨inria-00100988⟩



Record views