On the complexity of linear and stratified context matching problems
| Autor: | Schmidt-Schauss, Manfred, Stuber, Jürgen |
|---|---|
| Přispěvatelé: | Constraints, automatic deduction and software properties proofs (PROTHEO), INRIA Lorraine, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Centre National de la Recherche Scientifique (CNRS)-Institut National Polytechnique de Lorraine (INPL)-Université Nancy 2-Université Henri Poincaré - Nancy 1 (UHP)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Institut National Polytechnique de Lorraine (INPL)-Université Nancy 2-Université Henri Poincaré - Nancy 1 (UHP), Institut National de Recherche en Informatique et en Automatique (Inria)-Université Henri Poincaré - Nancy 1 (UHP)-Université Nancy 2-Institut National Polytechnique de Lorraine (INPL)-Centre National de la Recherche Scientifique (CNRS)-Université Henri Poincaré - Nancy 1 (UHP)-Université Nancy 2-Institut National Polytechnique de Lorraine (INPL)-Centre National de la Recherche Scientifique (CNRS), INRIA |
| Jazyk: | angličtina |
| Rok vydání: | 2002 |
| Předmět: | |
| Zdroj: | 2nd International Workshop on Complexity in Automated Deduction-CiAD'02 2nd International Workshop on Complexity in Automated Deduction-CiAD'02, Jul 2002, Copenhagen, Denmark. 18 p [Research Report] RR-4923, INRIA. 2003, pp.28 |
| Popis: | Colloque avec actes sans comité de lecture. internationale.; International audience; 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|