Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Add infeasibility levels #45

Open
Whebon opened this issue May 4, 2024 · 0 comments
Open

Add infeasibility levels #45

Whebon opened this issue May 4, 2024 · 0 comments

Comments

@Whebon
Copy link
Contributor

Whebon commented May 4, 2024

The bottom up enumerator maintains a bank of subprograms to insert into a new larger program. Infeasible subprograms may become feasible when inserted in a larger program. Therefore, the program bank should also contain infeasible programs.

However, sometimes the inconsistency of a subprogram is within the subprogram itself. In that case, it will never yield a feasible program, even when inserted in a larger program. I would be great if states can be marked as 'always infeasible' in this case.

The following example demonstrates the three levels of (in)feasibility:

  • Feasible. The subprogram itself satisfies the constraints.
  • Infeasible The subprogram does not satisfy the constraints but could become feasible when part of a larger program.
  • Always infeasible The subprogram will never satisfy the constraints, even when it is a part of an arbitrary larger program.
grammar = @csgrammar begin
    Number = 1
    Number = 2
    Number = x
    Number = Number + Number
end    
addconstraint!(grammar, Forbidden(RuleNode(2))) #prevents rule 2 from ever occurring in the program
addconstraint!(grammar, Contains(3))            #enforces that rule 3 must be used in the program

#This subprogram is already a feasible program by itself
feasible_subprogram = RuleNode(4, [RuleNode(3), RuleNode(3)])

#This subprogram does not satisfy the Contains(3) constraint, so it is infeasible
#However, when inserted in a larger program that already contains rule 3, it might be feasible
infeasible_subprogram = RuleNode(4, [RuleNode(1), RuleNode(1)])

#This subprogram holds the forbidden subtree RuleNode(2), so it is infeasible
#Even when inserted in a larger program, it will still hold RuleNode(2)
always_infeasible_subprogram = RuleNode(4, [RuleNode(2), RuleNode(2)])

Why is this not here yet?

This is an optimization for different iterator types and won't affect the TopDownIterator at all.
Since my thesis does not concern bottom-up enumeration, I will focus on other issues instead.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

1 participant