url('https://fonts.googleapis.com/css2?family=Raleway:ital,wght@0,100..900;1,100..900&family=Source+Serif+4:ital,opsz,wght@0,8..60,200..900;1,8..60,200..900&display=swap');

(min-width: 768px) {
  .article.article-md h2 {
    font-size: 24px;
  }
}

(min-width: 1024px) {
  .article.article-md h2 {
    font-size: 28px;
  }
    .heading-button {
    width: 50px;
    height: 50px;
  }
  .heading-button-arrow {
    font-size: 28px;
    padding: 12px 8px
  }
}

(max-width: 768px) {
  [data-root-node="true"] {
    --margin-left: 0px !important;
    --margin-right: 0px !important;
  }
  .contained { 
    padding: 0px 16px;
  }

  [data-tid="h"] {
    margin-left: var(--margin-left);
    margin-right: var(--margin-right);
  }
  .auto-column-container {
    column-count: 1;
  }
  .pullquote, .pullquote.left, .pullquote.right{
    float: none;
    width: 100%;
    text-align: center;
    margin-left: 0;
    margin-right: 0;
  }

  .footer-content { 
    grid-template-columns: repeat(3, 1fr);
  }

  .footer-about {
    grid-column: 1 / span 3;
  }
}

ASP handles circular dependencies in rules through external support requirements. This approach mirrors real-world relationship modeling where cycles need external validation.

Look at the program below and think about what the result might be:

 contain the heads of the rules, there are four possibilities for the answer set:

An answer set is valid if it satisfies all rules of the program. Let's look at each possible answer set in turn and determine if it violates any rule and is therefore disqualified as a candidate.

The result of this program is the empty set (

(For the curious reader: Remember that answer sets must be 

 and the empty set is a subset of all other answer sets. Once it was determined that the empty set was an answer set, the other candidates did not need to be examined since they would not be 

, we defined an answer set as "all atoms that can be (

) derived from the rules of the program". The example above demonstrates why the notion of "

" is an important addition to that definition. Rules such as above which are 

contribute atoms to the answer set; they must be made 

. A good way to remember this is that cyclic rules must be 

— some rule external from the cycle must “support” the cycle.

If we add an additional fact to "prime the pump" (i.e. to make the rules 

. (The empty set can no longer be a candidate since facts must be present in all answer sets.)

Consider a scenario modeling mutual support relationships between family members:

supports(pete, mary) ← needs_help(mary), can_help(pete) .
supports(mary, pete) ← needs_help(pete), can_help(mary) .

needs_help(X) ← supports(Y, X) .
can_help(X) ← supports(X, Y) .

This creates a cycle: if Pete supports Mary, then Mary needs help, and if Mary needs help and Pete can help, Pete supports Mary. Without any external facts, we get the empty set (

) — the solver can't just assume support relationships exist.

supports(pete, mary) .  % Pete initially offers support to Mary

Then we get a fuller picture of mutual support: 

This mirrors real life — support relationships often need some initial action to get started. They can't just spring from nowhere, even if the potential for mutual support exists.

The example shows how ASP's handling of cycles prevents us from getting into unrealistic situations where support relationships magically appear without cause, while still allowing us to model the reciprocal nature of family support once it's initiated.

The handling of circular dependencies in ASP reveals some fundamental principles:

In the next sections, we'll build on these concepts to handle even more complex relationships and constraints. Understanding how ASP handles cycles is crucial for writing effective programs that accurately model real-world dependencies and relationships.

ASP-09 | Circular Dependencies

Cycles in Rules

Priming the Pump

Extending the Example

Real-World Example: Mutual Support

Takeaways

More from Building Blocks in Surface Tension

Recursive Rules

Conditional Literals

Join us on Discord

About Us

Info

Legal

Social