Strong Backdoors for Default Logic
In this paper, we introduce a notion of backdoors to Reiter's propositional default logic and study structural properties of it. Also we consider the problems of backdoor detection (parameterised by the solution size) as well as backdoor evaluation (parameterised by the size of the given backdoor), for various kinds of target classes (cnf, horn, krom, monotone, identity). We show that backdoor detection is fixed-parameter tractable for the considered target classes, and backdoor evaluation is either fixed-parameter tractable, in para-DP2 , or in para-NP, depending on the target class.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Evolution of default genetic control mechanisms
We present a model of the evolution of control systems in a genome under environmental constraints. The model conceptually follows the Jacob and Monod model of gene control. Genes contain control elements which respond t…
Learning Pseudo-Backdoors for Mixed Integer Programs
We propose a machine learning approach for quickly solving Mixed Integer Programs (MIP) by learning to prioritize a set of decision variables, which we call pseudo-backdoors, for branching that results in faster solution…
Combinatorial OptimizationOutlier detection in default logics: the tractability/intractability frontier
In default theories, outliers denote sets of literals featuring unexpected properties. In previous papers, we have defined outliers in default logics and investigated their formal properties. Specifically, we have looked…
LEMMAOutlier DetectionRethinking Backdoor Detection Evaluation for Language Models
Backdoor attacks, in which a model behaves maliciously when given an attacker-specified trigger, pose a major security risk for practitioners who depend on publicly released language models. Backdoor detection methods ai…
On Strong and Default Negation in Logic Program Updates (Extended Version)
Existing semantics for answer-set program updates fall into two categories: either they consider only strong negation in heads of rules, or they primarily rely on default negation in heads of rules and optionally provide…
Negation