# Rectangular Automata

have a question regarding rectangular automata and their derivatives.

In each location the derivates are defined by a interval, how are the derivates applied on the variables? Is one value chosen out of the interval and added to the value or do we reset the value to one value in the interval ?

Regards

• Have you taken a look at the thesis? – Yuval Filmus Jun 19 '18 at 14:45
• I have taken a look at this thesis right now, and i still don't understand how the derivatives work, may i am just not seeing the obvious. – Secr3t Jun 19 '18 at 16:18
• Can you edit the question to provide some background for people who aren't familiar with rectangular automata and their derivatives, summarize what you do understand, and give any references to what you've been reading to learn about this? – D.W. Jun 19 '18 at 21:00
• I am computersience student and i visit a lecture about hybrid systems, in this lecture we are working with hybrid automata, linear hybrid automata, rectangular automata,... A rectangular automata is defined by invariant conditions, guard conditions concerning the edges and derivatives for the different clocks in the automata In the other automatas the derivative for the clocks are all 1. In rectangular automata the derivatives of the clock are definde by an interval, now i am not sure how this works. To we add one value of the interval to the clock in each timeunit ? – Secr3t Jun 19 '18 at 21:30

The derivatives are applied over time in a continuous fashion.

Here is an example:

Assume that we want to find out whom of two runners wins a running tournament. They run for 100 meters each, and the one reaching a goal first wins.

We can model the position of the two runners using two variables $x$ and $y$. We do not quite know the exact speed of the runners, as it depends on how well they feel at the tournament day. But we know some boundaries on their speed, i.e., how $x$ evolves over time. Let's assume we know that $\dot x \in [9.8,9.9] \ \frac{m}{s}$ and that $\dot y \in [9.7,9.78] \ \frac{m}{s}$

So a rectangular hybrid automaton would have one "running" state in which the variables evolve like this, and then there are two states for the cases that runner $x$ has reached the goal and that runner $y$ has reached the goal. You can see from the numbers above that player $x$ will win, but let's assume that this is not obvious, and we want to use a rectangular hybrid automaton for this:

   | x:=0, y:=0
V
+- -------------------+    x >= 100       +---------------------+
| 0.98 <= x' <= 0.99  |------------------>| x' = 0              |
| 0.97 <= y' <= 0.978 |                   | 0.97 <= y' <= 0.978 |
| x < 10, y<10        |                   +---------------------+
+---------------------+
|                       y >= 100       +---------------------+
+------------------------------------->| 0.98 <= x' <= 0.99  |
| y' = 0              |
+---------------------+


If we always "reset the value to one value in the interval", then the two runners would never reach the 100 meter mark and hence one of the two goal states on the right is never right.

But it is also not the case that "one value chosen out of the interval and added to the value". Because adding is a discrete actions. You could, for example, add x' to x until one of the two conditions have been reached. But then, it takes exactly 11 steps for both runners to reach the goal, and hence, they both win at the same time. But that makes no sense, because time is continuous. Rather, if you plot the evolution of x over time, you would use x' as the steepness of the line, and the positions of the runners are really continously updated as time progresses, as in real life.

In rectangular hybrid automata, it doesn't really matter whether $\dot x$ can change at every moment of time to a different value in the interval or not. The reason is that we use these automata for checking the properties of model. In the example above, this would be whether the bottom-right location is ever reached (which is not the case). And for this analysis, whether the first derivatives has to stay constant (within their defined interval) or not does not matter.