Deontic Constraint Satisfaction Problem (CSP)

The atomic units of the problem representing normative propositions or action states that must be assigned a truth value or compliance status. In a legal domain, a variable might represent complies_with_gdpr_art_17 (right to erasure) or data_retention_period_exceeded. Each variable has a finite domain of possible deontic statuses—typically {obligatory, permitted, prohibited, violated, fulfilled}—rather than simple Boolean values. The selection and granularity of these variables directly determines the expressiveness of the normative model and the computational complexity of the solving process.

Formal relations that restrict permissible combinations of variable assignments, encoding the normative force of legal rules. Constraints fall into three primary categories:

• Obligation constraints: If condition A holds, then action B must be assigned fulfilled
• Prohibition constraints: If condition C holds, then action D must not be assigned performed
• Permission constraints: Explicitly carve out exceptions where a generally prohibited action is allowed Constraints are typically expressed as deontic conditionals using operators from Standard Deontic Logic or Input/Output Logic, and may include defeasibility markers indicating which constraints can be overridden by higher-priority norms.

The conflict resolution engine that applies meta-constraints to determine precedence when two applicable norms demand incompatible assignments. It implements the classical legal principles:

• Lex superior: Higher authority norms override lower ones (constitution > statute > regulation)
• Lex specialis: More specific rules override general ones
• Lex posterior: Later-enacted norms override earlier ones In a Deontic CSP, the resolver dynamically weights constraints or partitions the constraint graph into ordered layers, ensuring the solver explores compliant assignments in the correct priority sequence before considering defeasible norms.

A specialized sub-component that manages secondary obligations triggered when a primary duty is violated. CTD structures address Chisholm's Paradox—the classical failure of Standard Deontic Logic to consistently represent remedial norms. The handler maintains a violation state register that tracks which primary obligations have been breached and activates the corresponding compensatory constraint set. For example, if a contract requires delivery by March 1 (primary obligation) and the deadline is missed, the CTD handler activates the penalty clause constraint (secondary obligation to pay liquidated damages). This ensures the CSP remains logically consistent even when modeling non-ideal compliance scenarios.

The verification module that checks whether a candidate assignment constitutes a valid deontic model—a complete, consistent mapping of all variables that satisfies every non-defeated constraint. The validator performs three critical checks:

• Consistency: No variable is simultaneously assigned obligatory and prohibited
• Completeness: Every triggered obligation has a corresponding fulfillment or violation status
• Closure: All CTD chains are fully resolved with no dangling remedial obligations If the solution space is empty—meaning no assignment satisfies all constraints—the validator identifies the minimal unsatisfiable core, pinpointing the specific conflicting norms that require human legal review or legislative reconciliation.

The inference mechanism that derives implicit normative consequences from explicitly encoded constraints before the solver begins its search. Using techniques adapted from arc consistency algorithms (such as AC-3) and forward chaining, the engine propagates the effects of known assignments through the constraint graph. For instance, if a statute prohibits data processing without consent, and the variable user_consent_obtained is assigned false, the engine propagates prohibited to all processing action variables. This prunes the search space dramatically, reducing the computational complexity of solving large-scale regulatory compliance problems with thousands of interdependent norms.

The fundamental state that a Deontic CSP is designed to resolve. A normative conflict occurs when two or more applicable rules prescribe incompatible actions for the same agent in the same context. For example, a data retention regulation requiring 7-year storage conflicting with a privacy regulation mandating deletion after 2 years. Resolution strategies include lex superior (higher authority prevails), lex specialis (specific rule overrides general), and lex posterior (later rule overrides earlier). In a CSP framework, these resolution strategies are encoded as meta-constraints that dynamically reorder or disable conflicting variables.

A conditional obligation that activates precisely when a primary duty has been violated, representing the normative system's fallback rules. CTD structures are the primary source of complexity in Deontic CSPs because they introduce non-monotonic dependencies—constraints that only become active when other constraints are unsatisfied. For instance: 'You ought not park here; but if you do park here, you ought to pay the meter.' The CSP must model this as a conditional constraint activation where the payment obligation variable is gated on the violation of the parking prohibition variable.

A non-monotonic logical framework that allows normative conclusions to be retracted in the presence of new information, directly modeling how legal rules admit exceptions. In a Deontic CSP, defeasibility is implemented through constraint priority hierarchies where lower-priority constraints are automatically relaxed when they conflict with higher-priority ones. This avoids the rigid brittleness of classical constraint solvers. Key mechanisms include:

• Defeaters: Rules that block a conclusion without establishing the opposite
• Undercutting: Attacking the applicability condition of a norm
• Rebuttal: Directly contradicting the normative conclusion

The structured ordering of legal norms by authority that provides the conflict resolution backbone for a Deontic CSP. The hierarchy is typically encoded as a partial order over constraint sets using three classical principles:

• Lex superior: Constitutional norms override statutory norms override regulatory norms
• Lex specialis: Specific provisions override general provisions within the same authority level
• Lex posterior: Later-enacted norms override earlier ones when authority and specificity are equal In CSP implementation, this hierarchy is translated into integer weights assigned to each constraint, with the solver maximizing the sum of satisfied constraint weights.

The Kantian axiom that an agent can only be obligated to perform an action if it is actually possible for them to do so. In a Deontic CSP, this functions as a domain-pruning constraint that removes impossible actions from the variable domains before the solver runs. For example, if a regulation requires filing a report within 24 hours but the agent lacks system access during that window, the obligation is invalidated. This principle prevents the CSP from generating unsatisfiable obligation sets that would otherwise require the solver to fail or produce irrational outputs.