Item request has been placed! ×
Item request cannot be made. ×
loading  Processing Request

KBO Constraint Solving Revisited

Item request has been placed! ×
Item request cannot be made. ×
loading   Processing Request
اقرأ أكثر حفظ في قائمتي
  • معلومة اضافية
    • Contributors:
      Max-Planck-Institut für Informatik (MPII); Max-Planck-Gesellschaft; Modeling and Verification of Distributed Algorithms and Systems (VERIDIS); Max-Planck-Gesellschaft-Max-Planck-Gesellschaft-Inria Nancy - Grand Est; Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Department of Formal Methods (LORIA - FM); Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA); Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA); Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS); Max Planck Institute for Informatics Saarbrücken
    • بيانات النشر:
      HAL CCSD
      Springer Nature Switzerland
    • الموضوع:
      2023
    • Collection:
      Université de Lorraine: HAL
    • الموضوع:
      Prague (CZ); Czech Republic
    • نبذة مختصرة :
      International audience ; KBO constraint solving is very well-known to be an NPcomplete problem. Motivated by the needs of the family of SCL calculi, we consider the particular case where all terms occurring in a constraint are bound by a (single) ground term. We show that this problem and variants of this problem remain NP-complete even if the form of atoms in the constraint is further restricted. In addition, for a non-strict, partial term ordering solely based on symbol counting constraint solving remains NP-complete. Nevertheless, we provide a new simple algorithm testing KBO constraint solvability that performs well on benchmark examples.
    • Relation:
      hal-04313806; https://inria.hal.science/hal-04313806; https://inria.hal.science/hal-04313806/document; https://inria.hal.science/hal-04313806/file/978-3-031-43369-6_5.pdf
    • الرقم المعرف:
      10.1007/978-3-031-43369-6_5
    • Rights:
      http://creativecommons.org/licenses/by/ ; info:eu-repo/semantics/OpenAccess
    • الرقم المعرف:
      edsbas.B4E29541