You're most welcome to contribute to this file if you want to comment
on the points made in the paper, or if you find any errors, typos,
etc. Just send me en email to mju@brics.dk. 

Marcin Jurdzinski

---------------------------------------------------------------------

9/2/2000

Typos in the STACS 2000 proceedings version:

Page 6, line 5 from the top: 
replace "$\varrho_1$" by "$\varrho_2$". 

Page 9, line 2 of Theorem 12: 
replace "that" by "than".

[Marcin Jurdzinski, mju@brics.dk]

---------------------------------------------------------------------

25/7/2000

Jens Voege (voege@informatik.rwth-aachen.de) has observed that the
definition of $\mathrm{Lift}\big(\varrho,v\big)(v)$ is flawed in the
STACS 2000 Proceedings version of the paper. Even though the algorithm
given in the paper works correctly with this definition, the problem
is that Proposition 9 does not hold in general.

The way to correct this flaw is to use the following definition of the
$\mathrm{Lift}(\cdot,\cdot)$ operator:

\[
\mathrm{Lift}\big(\varrho, v\big) (u) =
\begin{cases}
  \varrho(u) & \text{if } u \not= v, 
  \\
  \max\big\{\varrho(v), \min_{(v, w) \in E} 
    \mathrm{Prog}(\varrho, v, w)\big\} & \text{if } u = v \in V_\Diamond, 
  \\ 
  \max\big\{\varrho(v), \max_{(v, w) \in E} 
    \mathrm{Prog}(\varrho, v, w)\big\} & \text{if } u = v \in V_\Box.
\end{cases}
\]

Thanks for pointing this out Jens!

[Marcin Jurdzinski, mju@brics.dk]

---------------------------------------------------------------------

26/7/2000

There is a flaw in the Remark on page 8 in the STACS Proceedings
version of the paper. The conclusion in the third sentence is not
correct. See a revised version of the paper available at:

  http://www.brics.dk/~mju/Papers/Jur00-STACS.ps

for a correction.

[Marcin Jurdzinski, mju@brics.dk]

---------------------------------------------------------------------