0.3. Queries

When an action domain is represented by a transition system, many computational problems involving that domain can be stated as questions about paths in this transition system. This idea is used in the approach to queries adopted in the input language of CCalc.

Consider, for instance, several identical objects, say coins, and a box in which these objects can be placed. There is enough room in the box for 10 coins. We are interested in the effect of the action a of putting a coin in the box on the number c of coins that are currently in the box. This domain can be represented by transition system TS2 (Section 0.1) with N=10.

Prediction. Currently there are 5 coins in the box. If I put one coin in the box twice in a row, how many coins will there be in the box at the end?

In terms of paths in the transition system: consider the path of length 2 that starts at the vertex c=5 and has both edges labeled a=t. Where does it end? (Answer: c=7.)

Postdiction. I just put one coin in the box twice in a row, and now there are 5 coins in it. How many coins were there in the box initially?

In terms of paths: consider the path of length 2 that ends at the vertex c=5 and has both edges labeled a=t. Where does it start? (Answer: c=3.)

Planning. Currently there are 4 coins in the box. Find the shortest sequence of events that will make the box full.

In terms of paths: find the shortest path from the vertex c=4 to the vertex c=10. (Answer: path of length 6 with every edge labeled a=t.)


Forward to Section 1.1: CCalc Input: Transition Systems
Back to Section 0.2: Describing Actions
Up to the Table of Contents