Tristan State Resource Notes

Tristan's attempt to

I have divided this approach into two pieces:

1. Calculating profiles. They're not really profiles anymore, but it's similar, at least philosophically, to resource profile calculations.
2. Using profiles to calculate flaws and violations.

At Jeremy's suggestion, I have tried to get everything working without too much concern for efficiency. For example, the above separation may make it harder to do things efficiently, but the two pieces can be mixed without messing up the approach, I believe.

For notation, I use:

• SET(es) and SET(ls) for the earliest and latest starts for the SET transaction.
• REQ(es), REQ(ls), for the earliest and latest times for the REQ to begin.
• -REQ(es), and -REQ(ls) for the earliest and latest times for the REQ to end.

Calculating profiles

As we pass through time, we update 3 sets whenever we hit one of the above six classes of time points:

• A: The set of possible SET instances that could be valid at this time.
• B: The set of REQ tokens that might be underway at this time.
• C: The set of REQ tokens that must be underway at this time.

Building A

To build A, we start with the empty set.

for simplicity (having an initial state, or set of states is no different). Then:

• If we reach a SET(es), we add SET to A
• If we reach a SET(ls), we can remove any SET' for which SET'(ls) < SET(es) (Mike, this is equivalent to the bar we talked about)

If there is an initial state, or set of states, that can be represented with a SET where SET(es) = SET(ls) = 0 (or negative infinity?).

Building B

To build B, we start with the empty set. Then:

• If we reach REQ(es), we add REQ
• If we reach -REQ(ls), we remove REQ

Building C

To build C, we start with the empty set. Then:

• If we reach REQ(ls) and REQ(ls) < -REQ(es), we add REQ
• If we reach -REQ(es) and REQ(ls) < -REQ(es), we remove REQ

Note that C is a subset of B.

Detection flaws and violations

This can be broken into a number of cases:

1. FV detection just within A: For any pair SET and SET' in A:
2. It is a violation if they both must start at the same time and must set the state to different values (assuming for now that the state can be set to the same thing by multiple SETs at the same time).
3. The same thing with might and must is a flaw: It is a flaw if they both might start at the same time and must set the state to different values (assuming for now that the state can be set to the same thing by multiple SETs at the same time).
4. The same thing with must and might is a flaw.
5. The same things with might and might is a flaw.
6. FV detection within B and C:
7. If C contains REQ1 and REQ2, and their values must not intersect, it is a violation.
8. If B contains REQ1 and REQ2, and their values might not intersect, it is a flaw
9. FV detection between A and B,C:
10. If C contains REQ, and there is no SET in A whose value might match that of REQ, it is a violation.
11. If B contains REQ, and there is no SET in A whose value might match that of REQ, it is a flaw.
12. If B contains REQ, and there is any SET in A whose value might not match that of REQ, it is a flaw.

Adding temporal constraints

Most of the above ingores the fact that fewer flaws (and possibly more violations?) could be detecting by being aware of necessary (implicit or explicit) temporal constraints between SET, REQ, and -REQ.

Some of this could be handled when A,B,C are calculated. In fact, notice that we've used temporal information to decide when a SET is removed from A. However, it is not possible to handle all constraints during the construction of A,B,C, I think. For example, even if there is an SET->SET' temporal constraint, the domains for SET and SET' can overlap). Therefore, I propose:

• Timetable-style FV detection does the above.
• Flow-profile-style FV detection that augments the above with
• A precomputed all-pairs temporal constraint network (ie be able to quickly look up whether X is temporally constrained to be before Y)
• Update the above flaw/violation rules slightly.

Here is an updated of the above flaw/violation detection cases for using whatever temporal constraint information is pre-computed (new stuff in bold). Note that nothing changes within set A because we assume we use the extra information when building A.

1. FV detection just within A: For any pair SET and SET' in A:
2. It is a violation if they both must start at the same time and must set the state to different values (assuming for now that the state can be set to the same thing by multiple SETs at the same time) (no change).
3. The same thing with might and must is a flaw: It is a flaw if they both might start at the same time and must set the state to different values (assuming for now that the state can be set to the same thing by multiple SETs at the same time). (no change)
4. The same thing with must and might is a flaw. (no change)
5. The same things with might and might is a flaw. (no change)
6. FV detection within B and C:
7. If C contains REQ1 and REQ2, and their values must not intersect, it is a violation (no change here because if we're in C, there must not be a relevant temporal constraint between REQ1 and REQ2)
8. If B contains REQ1 and REQ2, and their values might not intersect and there is no precedence constraint between them, it is a flaw
9. FV detection between A and B,C:
10. If C contains REQ, and there is no SET in A **which might occur before REQ ends and ** whose value might match that of REQ, it is a violation.
11. If B contains REQ, and there is no SET in A **which might occur before REQ ends and ** whose value might match that of REQ, it is a flaw.
12. If B contains REQ, and there is any SET in A *which might occur before REQ ends and *whose value might not match that of REQ, it is a flaw.

This may not be quite right, but the basic idea is to avoid the cases that we know, based on extra temporal information, cannot occur.

Resolving flaws and violations

Haven't thought about this! :) However, it feels like there will be some pretty good heuristics that will tend to guide search in the right direction.