File: NEWS

package info (click to toggle)
ppl 1:1.2-1
  • links: PTS, VCS
  • area: main
  • in suites:
  • size: 43,952 kB
  • ctags: 19,973
  • sloc: cpp: 212,085; sh: 12,176; makefile: 7,289; perl: 6,333; java: 2,220; ansic: 1,842; ml: 1,132; sed: 80
file content (2082 lines) | stat: -rw-r--r-- 80,857 bytes parent folder | download | duplicates (3)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
1001
1002
1003
1004
1005
1006
1007
1008
1009
1010
1011
1012
1013
1014
1015
1016
1017
1018
1019
1020
1021
1022
1023
1024
1025
1026
1027
1028
1029
1030
1031
1032
1033
1034
1035
1036
1037
1038
1039
1040
1041
1042
1043
1044
1045
1046
1047
1048
1049
1050
1051
1052
1053
1054
1055
1056
1057
1058
1059
1060
1061
1062
1063
1064
1065
1066
1067
1068
1069
1070
1071
1072
1073
1074
1075
1076
1077
1078
1079
1080
1081
1082
1083
1084
1085
1086
1087
1088
1089
1090
1091
1092
1093
1094
1095
1096
1097
1098
1099
1100
1101
1102
1103
1104
1105
1106
1107
1108
1109
1110
1111
1112
1113
1114
1115
1116
1117
1118
1119
1120
1121
1122
1123
1124
1125
1126
1127
1128
1129
1130
1131
1132
1133
1134
1135
1136
1137
1138
1139
1140
1141
1142
1143
1144
1145
1146
1147
1148
1149
1150
1151
1152
1153
1154
1155
1156
1157
1158
1159
1160
1161
1162
1163
1164
1165
1166
1167
1168
1169
1170
1171
1172
1173
1174
1175
1176
1177
1178
1179
1180
1181
1182
1183
1184
1185
1186
1187
1188
1189
1190
1191
1192
1193
1194
1195
1196
1197
1198
1199
1200
1201
1202
1203
1204
1205
1206
1207
1208
1209
1210
1211
1212
1213
1214
1215
1216
1217
1218
1219
1220
1221
1222
1223
1224
1225
1226
1227
1228
1229
1230
1231
1232
1233
1234
1235
1236
1237
1238
1239
1240
1241
1242
1243
1244
1245
1246
1247
1248
1249
1250
1251
1252
1253
1254
1255
1256
1257
1258
1259
1260
1261
1262
1263
1264
1265
1266
1267
1268
1269
1270
1271
1272
1273
1274
1275
1276
1277
1278
1279
1280
1281
1282
1283
1284
1285
1286
1287
1288
1289
1290
1291
1292
1293
1294
1295
1296
1297
1298
1299
1300
1301
1302
1303
1304
1305
1306
1307
1308
1309
1310
1311
1312
1313
1314
1315
1316
1317
1318
1319
1320
1321
1322
1323
1324
1325
1326
1327
1328
1329
1330
1331
1332
1333
1334
1335
1336
1337
1338
1339
1340
1341
1342
1343
1344
1345
1346
1347
1348
1349
1350
1351
1352
1353
1354
1355
1356
1357
1358
1359
1360
1361
1362
1363
1364
1365
1366
1367
1368
1369
1370
1371
1372
1373
1374
1375
1376
1377
1378
1379
1380
1381
1382
1383
1384
1385
1386
1387
1388
1389
1390
1391
1392
1393
1394
1395
1396
1397
1398
1399
1400
1401
1402
1403
1404
1405
1406
1407
1408
1409
1410
1411
1412
1413
1414
1415
1416
1417
1418
1419
1420
1421
1422
1423
1424
1425
1426
1427
1428
1429
1430
1431
1432
1433
1434
1435
1436
1437
1438
1439
1440
1441
1442
1443
1444
1445
1446
1447
1448
1449
1450
1451
1452
1453
1454
1455
1456
1457
1458
1459
1460
1461
1462
1463
1464
1465
1466
1467
1468
1469
1470
1471
1472
1473
1474
1475
1476
1477
1478
1479
1480
1481
1482
1483
1484
1485
1486
1487
1488
1489
1490
1491
1492
1493
1494
1495
1496
1497
1498
1499
1500
1501
1502
1503
1504
1505
1506
1507
1508
1509
1510
1511
1512
1513
1514
1515
1516
1517
1518
1519
1520
1521
1522
1523
1524
1525
1526
1527
1528
1529
1530
1531
1532
1533
1534
1535
1536
1537
1538
1539
1540
1541
1542
1543
1544
1545
1546
1547
1548
1549
1550
1551
1552
1553
1554
1555
1556
1557
1558
1559
1560
1561
1562
1563
1564
1565
1566
1567
1568
1569
1570
1571
1572
1573
1574
1575
1576
1577
1578
1579
1580
1581
1582
1583
1584
1585
1586
1587
1588
1589
1590
1591
1592
1593
1594
1595
1596
1597
1598
1599
1600
1601
1602
1603
1604
1605
1606
1607
1608
1609
1610
1611
1612
1613
1614
1615
1616
1617
1618
1619
1620
1621
1622
1623
1624
1625
1626
1627
1628
1629
1630
1631
1632
1633
1634
1635
1636
1637
1638
1639
1640
1641
1642
1643
1644
1645
1646
1647
1648
1649
1650
1651
1652
1653
1654
1655
1656
1657
1658
1659
1660
1661
1662
1663
1664
1665
1666
1667
1668
1669
1670
1671
1672
1673
1674
1675
1676
1677
1678
1679
1680
1681
1682
1683
1684
1685
1686
1687
1688
1689
1690
1691
1692
1693
1694
1695
1696
1697
1698
1699
1700
1701
1702
1703
1704
1705
1706
1707
1708
1709
1710
1711
1712
1713
1714
1715
1716
1717
1718
1719
1720
1721
1722
1723
1724
1725
1726
1727
1728
1729
1730
1731
1732
1733
1734
1735
1736
1737
1738
1739
1740
1741
1742
1743
1744
1745
1746
1747
1748
1749
1750
1751
1752
1753
1754
1755
1756
1757
1758
1759
1760
1761
1762
1763
1764
1765
1766
1767
1768
1769
1770
1771
1772
1773
1774
1775
1776
1777
1778
1779
1780
1781
1782
1783
1784
1785
1786
1787
1788
1789
1790
1791
1792
1793
1794
1795
1796
1797
1798
1799
1800
1801
1802
1803
1804
1805
1806
1807
1808
1809
1810
1811
1812
1813
1814
1815
1816
1817
1818
1819
1820
1821
1822
1823
1824
1825
1826
1827
1828
1829
1830
1831
1832
1833
1834
1835
1836
1837
1838
1839
1840
1841
1842
1843
1844
1845
1846
1847
1848
1849
1850
1851
1852
1853
1854
1855
1856
1857
1858
1859
1860
1861
1862
1863
1864
1865
1866
1867
1868
1869
1870
1871
1872
1873
1874
1875
1876
1877
1878
1879
1880
1881
1882
1883
1884
1885
1886
1887
1888
1889
1890
1891
1892
1893
1894
1895
1896
1897
1898
1899
1900
1901
1902
1903
1904
1905
1906
1907
1908
1909
1910
1911
1912
1913
1914
1915
1916
1917
1918
1919
1920
1921
1922
1923
1924
1925
1926
1927
1928
1929
1930
1931
1932
1933
1934
1935
1936
1937
1938
1939
1940
1941
1942
1943
1944
1945
1946
1947
1948
1949
1950
1951
1952
1953
1954
1955
1956
1957
1958
1959
1960
1961
1962
1963
1964
1965
1966
1967
1968
1969
1970
1971
1972
1973
1974
1975
1976
1977
1978
1979
1980
1981
1982
1983
1984
1985
1986
1987
1988
1989
1990
1991
1992
1993
1994
1995
1996
1997
1998
1999
2000
2001
2002
2003
2004
2005
2006
2007
2008
2009
2010
2011
2012
2013
2014
2015
2016
2017
2018
2019
2020
2021
2022
2023
2024
2025
2026
2027
2028
2029
2030
2031
2032
2033
2034
2035
2036
2037
2038
2039
2040
2041
2042
2043
2044
2045
2046
2047
2048
2049
2050
2051
2052
2053
2054
2055
2056
2057
2058
2059
2060
2061
2062
2063
2064
2065
2066
2067
2068
2069
2070
2071
2072
2073
2074
2075
2076
2077
2078
2079
2080
2081
2082
Copyright (C) 2001-2010 Roberto Bagnara <bagnara@cs.unipr.it>
Copyright (C) 2010-2016 BUGSENG srl (http://bugseng.com)

Verbatim copying and distribution of this entire article is permitted
in any medium, provided this notice is preserved.


Parma Polyhedra Library NEWS -- history of user-visible changes
===============================================================

--------------------------------------------------------------------------
NEWS for version 1.2  (released on February 11, 2016)
--------------------------------------------------------------------------

New and Changed Features
========================

o  Improved the efficiency of the conversion procedure for polyhedra
   by adding a quick adjacency check.

o  In the Java language interface, throw an exception when trying
   to build a disequality Constraint.


Bugfixes
========

o  Fixed a bug in the implementation of methods
     Pointset_Powerset<PSET>::relation_with(const Constraint&) const;
   and
     Pointset_Powerset<PSET>::relation_with(const Congruence&) const;
   whereby the computed result for relations strictly_intersects()
   and saturates() could have been wrong.

o  Fixed a bug in the implementation of dense rows.

o  Portability improved.


--------------------------------------------------------------------------
NEWS for version 1.1  (released on October 28, 2013)
--------------------------------------------------------------------------

New and Changed Features
========================

o  Added a new operator on polyhedra: the positive time elapse.

o  In the Java language interface:

    - The constraint/generator/... system classes now extend the ArrayList
      generic container (rather than Vector);

    - Variable objects are now built from a long (rather than int) value,
      thereby matching the type used elsewhere for space dimensions;

    - added new static method to Variable class
          void setStringifier(Variable_Stringifier)
      where Variable_Stringifier is an interface allowing for
      customization of the output routine for variable's names
      (see example in interfaces/Java/tests/Variable_Output_test1.java);

    - added value NOT_EQUAL to enumeration Relation_Symbol.


Bugfixes
========

o  Portability improved.

o  Fixed a precision regression in Polyhedron method
     void drop_some_non_integer_points(const Variables_Set&,
                                       Complexity_Class);

o  In the Java language interface, fixed a C++/Java conversion error
   whereby the construction of a valid Variable object in JNI code
   was leading to an exception being thrown. The bug has only been
   observed on 32-bit builds.

o  In the Java interface, fixed declaration of methods
     void drop_some_non_integer_points(...);
   so as to accept a Complexity_Class enum value.

o  Fixed an issue in method MIP_Problem::OK() whereby the method
   was trying to enforce a non-invariant condition.


--------------------------------------------------------------------------
NEWS for version 1.0  (released on June 28, 2012)
--------------------------------------------------------------------------

New and Changed Features
========================

o  Significant improvements have been obtained in both time and space
   resource usage by the definition of data structures and algorithms
   for the case of "sparse rows", i.e., sequences of coefficients
   where most of the values are zero.

o  The library fully supports two different representations for rows:
   the "dense" representation is an array-like representation tailored
   to sequences having most of their coefficients different from zero;
   the "sparse" representation saves memory space (as well as CPU
   cycles) when most of the coefficients in the sequence are zero.

o  A generic interface allows for a seamless interaction between the
   dense and the sparse row representation. Most library entities
   (linear expressions, constraints, generators, congruences, and
   their systems) can be built using either representation, specified
   as a constructor's argument.

o  As a by-product of this sparse/dense refactoring work, efficiency
   improvements have been obtained even for those computations that
   are still based on the dense row representation.

o  Reasonable default values for the row representation are provided
   for each library entity, automatically leading to significant
   memory space savings even in old client/library code, e.g., when
   dealing with constraint systems describing weakly relational
   abstractions such as boxes and octagonal shapes.

o  If desired, these default values can be customized to user's needs
   by changing just a few lines of library code.  For instance, the
   constraint systems stored inside C_Polyhedron and NNC_Polyhedron
   objects can be made to use the sparse representation by just
   changing the following line in Polyhedron.defs.hh:

     static const Representation default_con_sys_repr = DENSE;

   to become

     static const Representation default_con_sys_repr = SPARSE;


Bugfixes
========

o  Fixed a bug affecting methods

     bool BD_Shape<T>::contains(const BD_Shape& y) const;
     bool Octagonal_Shape<T>::contains(const Octagonal_Shape& y) const;

   whereby the wrong result was obtained when *this is an empty
   weakly-relational shape and y is not empty.

o  Fixed a bug affecting the PIP solver whereby a wrong result could have
   been obtained if the input constraint system contained multiple linear
   equality constraints.


--------------------------------------------------------------------------
NEWS for version 0.12.1  (released on April 16, 2012)
--------------------------------------------------------------------------

New and Changed Features
========================

o  In the C, Java, OCaml and Prolog interfaces, modified the signature
   of the function/method/predicate for setting the deterministic timeout
   threshold. The new interfaces take two input values, named `unscaled'
   and `scale', that are used to compute the threshold value as
   `unscaled * 2^scale'.

o  Added new Box<ITV> methods

     bool has_upper_bound(Variable var,
                          Coefficient& n, Coefficient& d, bool& closed) const;
     bool has_lower_bound(Variable var,
                          Coefficient& n, Coefficient& d, bool& closed) const;

   to query a non-empty box for the existence and value of its upper/lower
   bound on variable `var'. The methods have been also added to all the
   available language interfaces.

o  Two BibTeX databases of papers related to the Parma Polyhedra Library
   have been added to the distribution (in the `doc' directory).


Bugfixes
========

o  Restored the support for deterministic timeouts in the PIP solver
   (it was removed by accident in PPL 0.12).

o  Minor documentation fixes.

o  Portability improved.


--------------------------------------------------------------------------
NEWS for version 0.12  (released on February 27, 2012)
--------------------------------------------------------------------------

New and Changed Features
========================

o  New configure options `--with-gmp=DIR', `--with-gmp-include=DIR' and
   `--with-gmp-lib=DIR' supersede the (now removed) option
   `--with-gmp-prefix'.  (The old option never really worked; hopefully
   this is the last change in this area.)

o  New configuration option `--disable-documentation'.  When specified
   no new documentation is built: only the documentation already present
   in the source tree is installed upon `make install'.

o  The resolution process for PIP_Problem now better exploits the
   integrality of parameters to simplify the newly generated tautological
   constraints, the splitting constraints of decision nodes, and the
   expressions defining artificial parameters.

o  The implementations of the MIP and PIP solvers are based on a new
   data structure leading to significant space and time savings when
   the tableau matrix is sparse; the benchmarks of the ppl_lpsol demo
   show an improvement on the average case, that grows when the toughest
   tests in the benchmark suite are considered.

o  When the `--check' option is used, the input data for demo ppl_lpsol
   is perturbed the same way as GLPK does, thereby allowing for a
   meaningful comparison of the results obtained.

o  The input routine for PPL numeric datatypes has been extended to
   accept the ISO9899 (C99) hexadecimal floating constant syntax.

o  The Parma Watchdog Library has been merged into the
   Parma Polyhedra Library.


Bugfixes
========

o  Corrected a precision bug in methods

     Box<ITV>::upper_bound_assign(const Box&)
     Box<ITV>::upper_bound_assign_if_exact(const Box&)

   whereby, provided any argument is an empty box and under other rather
   specific conditions, the computed result was correct but unnecessarily
   imprecise.

o  Corrected a bug in method

     Grid::relation_with(const Constraint&) const

   whereby, under specific conditions, the method was creating invalid
   Grid_Generator objects and providing an incorrect result.


--------------------------------------------------------------------------
NEWS for version 0.11.2  (released on February 27, 2011)
--------------------------------------------------------------------------

Bugfixes
========

o  Fixed the semantics of the `--disable-fpmath' configure option
   (which is equivalent to `--enable-fpmath=no').  It now disables all
   floating point computations and, consequently, all numerical
   abstractions based on floating point numbers.

o  The PPL no longer overwrites the SIGILL signal handler.

o  Minor documentation fixes.

o  Portability improved.


--------------------------------------------------------------------------
NEWS for version 0.11.1  (released on February 20, 2011)
--------------------------------------------------------------------------

Bugfixes
========

o  Corrected a problem in the simplification of PIP_Problem solution trees
   whereby, under specific conditions, the node merging process produced
   decision nodes that did not satisfy their class invariant.

o  Corrected a precision bug in method

     Octagonal_Shape<T>::affine_image()

   whereby in the case of an invertible affine transformation implementing
   a variable sign symmetry (and optional translation), the computed result
   was correct but unnecessarily imprecise.

o  Corrected a problem in the input method for checked integers whereby,
   under specific conditions, the input stream state bits were not updated.
   The bug was only affecting builds using checked integer coefficients.

o  Corrected a bug in the OCaml interface, which was affecting functions

     ppl_Pointset_Powerset_<INSTANCE>_get_disjunct.

o  Corrected a couple of resource (re-)allocation problems that, under
   specific conditions, could affect the correctness of Grid constructor

     Grid::Grid(const Box<Interval>& box)

   and NNC_Polyhedron method

     Polyhedron::generalized_affine_image().

o  Corrected an efficiency bug in the C language interface function

     ppl_Linear_Expression_add_to_coefficient().

o  Corrected an efficiency bug in method

     MIP_Problem::compute_generator().

o  Corrected a bug affecting the input routine of ppl_lpsol, whereby
   the inhomogeneous term of the objective function was disregarded.

o  Corrected a bug affecting methods

     Box::CC76_widening_assign(const T&, Iterator, Iterator)
     Interval::CC76_widening_assign(const From&, Iterator, Iterator)

   whereby a lower bound would not be computed correctly when the two
   iterators specify an empty list of stop points.

o  Fixed a bug affecting

     Interval::Interval(const char* s)

   whereby a wrong interval would be constructed if `s' denotes a number
   that can only be represented as an infinity.

o  Fixed a bug whereby the argument of all the methods

     unconstrain(Variable var)

   was not checked correctly for space dimension compatibility.

o  Portability improved.


--------------------------------------------------------------------------
NEWS for version 0.11  (released on August 2, 2010)
--------------------------------------------------------------------------

New and Changed Features
========================

o  New class PIP_Problem provides a Parametric Integer Programming
   (PIP) problem solver (mainly based on P. Feautrier's
   specification).  The implementation combines a parametric dual
   simplex algorithm using exact arithmetic with Gomory's cut
   generation.

o  New "deterministic" timeout computation facilities: it is now
   possible to set computational bounds (on the library calls taking
   exponential time) that do not depend on the actual elapsed time and
   hence are independent from the actual computation environment (CPU,
   operating system, etc.).

o  New support for termination analysis via the automatic synthesis of
   linear ranking functions.  Given a sound approximation of a loop,
   the PPL provides methods to decide whether that approximation
   admits a linear ranking function (possibly obtaining one as a
   witness for termination) and to compute the space of all such
   functions.  In addition, methods are provided to obtain the space
   of all linear quasi-ranking functions, for use in conditional
   termination analysis.

o  New support for approximating computations involving (bounded)
   machine integers.  A general wrapping operator is provided that is
   parametric with respect to the set of space dimensions (variables)
   to be wrapped, the width, representation and overflow behavior of
   all these variables.  An optional constraint system can, when
   given, improve the precision.

o  All the PPL semantic objects provide new methods

     void drop_some_non_integer_points(Complexity_Class)
     void drop_some_non_integer_points(const Variables_Set&,
                                       Complexity_Class)

   which possibly tighten the object by dropping some points with
   non-integer coordinates (for the space dimensions corresponding to
   `vars'), within a certain computational complexity bound.

o  New Linear_Expression methods

     bool is_zero() const
     bool all_homogeneous_terms_are_zero() const

   return true if and only if `*this' is 0, and if and only if all the
   homogeneous terms of `*this' are 0, respectively.

o  New Linear_Expression methods

     void add_mul_assign(Coefficient_traits::const_reference c, Variable v)
     void sub_mul_assign(Coefficient_traits::const_reference c, Variable v)

   assign linear expression *this + c * v (resp., *this - c * v) to *this,
   while avoiding the allocation of a temporary Linear_Expression.

o  For the PPL semantic objects, other than the Pointset_Powerset and
   Partially_Reduced Product, there is a new method:

     bool frequency(const Linear_Expression& expr,
                    Coefficient& freq_n, Coefficient& freq_d,
                    Coefficient& val_n, Coefficient& val_d)

   This operator computes both the "frequency" (f = freq_n/freq_d)
   and a value (v = val_n/val_d)  closest to zero so that every point
   in the object satisfies the congruence (expr %= v) / f.

o  New reduction operator "Shape_Preserving_Reduction" has been added
   to the Partially_Reduced_Product abstraction.  This operator is
   aimed at the product of a grid and a shape domain, allowing the
   bounds of the shape to shrink to touch the points of the grid,
   such that the new bounds are parallel to the old bounds.

o  The Java interface has to be explicitly initialized before use by
   calling static method Parma_Polyhedra_Library.initialize_library().
   Initialization makes more explicit the exact point where PPL
   floating point rounding mode is set; it also allows for the caching
   of Java classes and field/method IDs, thereby reducing the overhead
   of native method callbacks.

o  The C and Java interfaces now support timeout computation facilities.

o  Implementation of general (C and NNC) polyhedra speeded up.

o  Implementation of the MIP solver speeded up.

o  When the PPL has been configured with
   CPPFLAGS="-DPPL_ARM_CAN_CONTROL_FPU=1", the library initialization
   procedure checks that the FPU can indeed be controlled and fails if
   that is not the case.

o  New configure option `--with-gmp-prefix' supersedes the (now removed)
   options `--with-libgmp-prefix' and `--with-libgmpxx-prefix'.

o  New configuration option `--with-gmp-build=DIR' allows to use a
   non-installed build of GMP in DIR.


Deprecated and Removed Methods
==============================

o  All methods having a name ending in `_and_minimize' (e.g.,
   add_constraints_and_minimize, poly_hull_assign_and_minimize, ...)
   have been removed (they were deprecated in version 0.10).


Bugfixes
========

o  Corrected a bug in maximize and mininimize optimization methods of
   class template Pointset_Powerset, whereby the Boolean value true
   (indicating successful optimization) was returned for empty powersets.

o  Corrected a bug in method
     bool NNC_Polyhedron::poly_hull_assign_if_exact(const NNC_Polyhedron&);
   whereby some inexact NNC hulls were incorrectly flagged as exact.


--------------------------------------------------------------------------
NEWS for version 0.10.2  (released on April 18, 2009)
--------------------------------------------------------------------------

Bugfixes
========

o  Correctly detect GMP 4.3.0.

o  Fixed the C interface library version information.

o  Test program tests/Polyhedron/memory1 disabled on the zSeries s390x
   platform.

o  Makefiles fixed so as to avoid failure of `make -n check'.


--------------------------------------------------------------------------
NEWS for version 0.10.1  (released on April 14, 2009)
--------------------------------------------------------------------------

New and Changed Features
========================

o  Added support for cross compilation.

o  The configuration script now explicitly checks that a recent enough
   version of GNU M4 is available if at least one non-C++ interface is
   enabled (in previous versions this check was not performed and
   building the library could fail in a mysterious way).

o  Robustness improved.

o  Some packaging issues have been fixed.

o  New macro PPL_DIRTY_TEMP_COEFFICIENT allows users of the C++
   interface to decrease memory allocation overhead and to improve
   locality whenever they need a temporary variable of type
   `Coefficient'.

o  The C++, C, Java and OCaml interfaces now provide utility functions
   to format the textual representations of constraints, congruences
   and so on.  This makes it easy to code debugging prints with line
   indentation and wrapping.

o  The C interface now provides functions of the form

     int ppl_io_asprint_Polyhedron(char** strp, P x)

   where `P' is any opaque pointer to a const PPL object. These
   functions print `x' to a malloc-allocated string, a pointer to
   which is returned via `strp'.

o  The OCaml interface can now be compiled to native code using ocamlopt.

o  New configuration option `--with-mlgmp=DIR' allows to specify the
   installation directory of the ML GMP package.

o  The OCaml interface now supports timeout computation facilities
   through functions ppl_set_timeout and ppl_reset_timeout.  Moreover,
   new functions ppl_Coefficient_is_bounded, ppl_Coefficient_min,
   ppl_Coefficient_max and ppl_max_space_dimension have been added.

o  The Prolog interfaces are no longer enabled by default in the
   release tarballs (they are enabled by default in the Git versions).


Bugfixes
========

o  Fixed a bug whereby `make check' was failing when the library was
   configured with the `--disable-watchdog' option.

o  Fixed a bug in method

     bool Polyhedron::contains_integer_point() const;

   whereby, under very specific conditions, an empty polyhedron is
   incorrectly said to contain an integer point.

o  Fixed a bug in method

     Partially_Reduced_Product<D1, D2, R>::time_elase_assign(y)

  whereby, if the product y was not already reduced, the operation could
  lose precision.

o  Fixed a bug in the OCaml interface, which was affecting functions

     ppl_Grid_generalized_affine_image_with_congruence

   and

     ppl_Grid_generalized_affine_preimage_with_congruence.

o  Fixed a bug in the Grid class that affected the methods

     Grid::bounds_from_above(), Grid::bounds_from_below(),
     Grid::maximize() and Grid::minimize();

   causing all of them to wrongly return true in certain cases where
   the grid generators were not minimized.

o  Fixed a bug whereby big-endian architectures were not properly
   recognized by the configuration script.

o  Fixed a bug in the Java/OCaml/Prolog interfaces, whereby
   the method/function/predicate for dropping a disjunct from a
   Pointset_Powerset object were returning an invalid iterator.

o  Fixed a bug in method Octagonal_Shape<T>::affine_image(var, expr)
   whereby a wrong result was computed under specific conditions.

o  Fixed a bug in the OCaml interface, whereby functions of form

     ppl_..._widening_assign_with_tokens

   and

     ppl_..._extrapolation_assign_with_tokens

   could return a wrong number of tokens.

o  Fixed a bug in the OCaml interface, whereby functions that returned
   an OCaml 'unit' type were returning the wrong value.

o  Fixed several garbage collection related bugs in the OCaml interface.


--------------------------------------------------------------------------
NEWS for version 0.10  (released on November 4, 2008)
--------------------------------------------------------------------------

New and Changed Features
========================

The license
-----------

o  The Parma Polyhedra Library is now released under the terms of the
   version 3 (or later) of the GNU General Public License.

New and renamed classes
-----------------------

o  The new class Octagonal_Shape provides an implementation of the domain
   of octagonal shapes (including optimized algorithms and a provably
   correct widening) as proposed by Roberto Bagnara, Patricia Hill,
   Elena Mazzi and Enea Zaffanella in their SAS 2005 paper.

o  A new abstraction called Box has been added.  Geometrically
   speaking, a Box represents a not necessarily closed, iso-oriented
   hyperrectangle.  This can also be seen as the smash product of `n'
   not necessarily closed and possibly unbounded intervals, where `n'
   is the space dimension of the box.  The Box template class is
   parametric with respect to a class of intervals.

o  A generic implementation of intervals has been added.  The template
   class Interval is parametric on the type used to represent the
   interval boundaries (all native integer and floating point types
   are supported as well as unbounded integers and rational numbers
   provided by GMP).  Another class template type parameter allows for
   the control of a number of other features of the class (such as the
   ability to represent: open as well as closed boundaries, empty
   intervals in addition to nonempty ones, intervals of extended
   number families that contain positive and negative infinities,
   plain intervals of real numbers and intervals of integer numbers).
   The Interval class still needs a lot of work and both its
   implementation and its interface are likely to change significantly:
   it is released now because it is needed for the Box class and as a
   kind of technology preview.

o  The class LP_Problem has been renamed MIP_Problem and now supports
   the solution of Mixed Integer (Linear) Programming problems.
   Support has been added for the incremental solution of MIP
   problems: it is now possible to add new space dimensions or new
   constraints to the feasible region, as well as change the objective
   function and the optimization mode, while still exploiting some of
   the computational work done before these changes.  Support has also
   been added to change control parameters for the pricing method.
   This allows a choice between the steepest edge pricing method,
   either implemented with floating point numbers (default) or with
   integer coefficients, and the textbook pricing method.

o  The PPL semantic object Polyhedra_Powerset has been replaced by the
   templatic object template <typename PS> Pointset_Powerset that can
   take any (simple) PPL semantic object for the domain of its
   disjuncts. In addition to the methods common to all the PPL
   semantic objects, methods specific to this domain include:

     void add_disjunct(const PS&),
     void pairwise_reduce(),
     void omega_reduce() const,
     bool geometrically_covers(const Pointset_Powerset&) const,
     bool geometrically_equals(const Pointset_Powerset&) const, and
     bool simplify_using_context_assign(const Pointset_Powerset&).

o  A new abstraction called Partially_Reduced_Product (PRP) has been
   added. A PRP is a pair of two PPL semantic objects that is
   parametric on the component domains and on a reduction operator.
   The PPL currently provides three reduction operators and hence,
   three different kinds of products:

   - a Direct_Product where the reduction operator is the identity;

   - a Smash_Product where the reduction operator shares emptiness
      information between the components; and

   - a Constraints_Product where the reduction operator refines each
     component with the constraints satisfied by the other component.

   The PRP class still needs a lot of work and both its implementation
   and its interface are likely to change significantly: it is released
   now as a kind of technology preview and any feedback is welcome.

New and renamed methods
-----------------------

o  All PPL semantic objects can now be constructed from other simple
   PPL semantic objects. All these constructors have an optional complexity
   argument with default value allowing algorithms with any complexity to be
   used.

o   New methods

      void restore_pre_PPL_rounding() and
      void set_rounding_for_PPL()

    allow the FPU rounding mode to be set to what it was before the
    initialization of the PPL, and to set it (again) so that the PPL
    abstractions based on floating point numbers work correctly, respectively.

o  All PPL semantic objects now provide methods

     void refine_with_constraint(const Constraint&),
     void refine_with_congruence(const Congruence&),
     void refine_with_constraints(const Constraint_System&), and
     void refine_with_congruences(const Congruence_System&).

   These methods are similar to the corresponding `add_' methods.
   The difference is in the reaction policy when the argument
   constraint/congruence is not optimally supported by the semantic
   domain: while the `add_' methods will throw an exception, the
   `refine_with_' methods will apply an upward approximation semantics.

o  Default widening operators of the form:

     void widening_assign(const ABSTRACTION&, unsigned*)

   are now provided for all abstractions except for the Pointset_Powerset
   abstractions.

o  All PPL semantic objects now provide the method

     int32_t hash_code() const

   returning a 32-bit hash code for *this.  If x and y are such that
   x == y evaluates to true, so does x.hash_code() == y.hash_code().

o  All PPL semantic objects now provide the methods

     memory_size_type total_memory_in_bytes() const
     memory_size_type external_memory_in_bytes() const

   returning, respectively, the total size in bytes of the memory
   occupied by the PPL object and the size in bytes of the memory
   managed by the PPL object.

o  For all the PPL semantic objects there are new methods:

    static bool can_recycle_constraint_systems() and
    static bool can_recycle_congruence_systems()

   that indicate whether or not a PPL semantic object is able to recycle
   constraints and congruences, respectively.

o  For all PPL semantic objects there is a new method:

     bool contains_integer_point() const

   which checks if a PPL semantic object contains an integer point;
   Note that this is not currently provided for the Partially_Reduced_Product
   classes.

o  For all PPL semantic objects there is a new method:

     bool constrains(Variable) const

   which checks if a dimension is constrained by a PPL semantic object;

o  For all PPL semantic objects there are new methods:

     void unconstrain(Variable)
     void unconstrain(const Variables_Set&)

   which assign, to a PPL semantic object, the cylindrification
   of the object with respect to one (resp., a set) of its dimensions,
   as defined by L. Henkin, J. D. Monk, and A. Tarski in Cylindric Algebras:
   Part I (published by North-Holland in 1971).

o  Several methods

     bool is_topologically_closed() const
     void topological_closure_assign()

   that were provided for just some of the PPL semantic objects are now
   uniformly available for all the objects.

o  Methods using the Congruence and Congruence_System classes
   such as

     Congruence_System congruences() const,
     Congruence_System minimized_congruences() const,
     void add_congruence(const Congruence&),
     void add_congruences(const Congruence_System&),
     void add_recycled_congruences(const Congruence_System&), and
     Poly_Con_Relation relation_with(const Congruence&).

   that were just provided for the Grid domain are now provided for
   all the PPL semantic objects.

o  For the Grid class, as it is not always possible to obtain a
   Pointset_Powerset<Grid> object that is a finite linear partition of
   the difference of two grids, we have added the method:
     std::pair<Grid, Pointset_Powerset<Grid> >
       approximate_partition(const Grid&, const Grid&, bool&)
   where the third argument is set to false if there is no
   finite linear partition.

o  In the Congruence class, for consistency with the Constraint class,
   the methods is_trivial_true() and is_trivial_false() have been renamed
   as is_tautological() and is_inconsistent(), respectively.

o  The methods

     bool Constraint_System::empty() const,
     bool Generator_System::empty() const,
     bool Congruence_System::empty() const, and
     bool Grid_Generator_System::empty() const

   return true if and only if the system in question is empty
   (i.e., it has no constraints, generators, congruences or grid-generators,
   respectively).

Deprecated and Removed Methods
==============================

o  As all PPL semantic objects can now be constructed from boxes,
   the constructors

     template <typename Box> C_Polyhedron(const Box&, From_Bounding_Box),
     template <typename Box> NNC_Polyhedron(const Box&, From_Bounding_Box),
     template <typename Box> Grid(const Box&, From_Bounding_Box)

   have been removed. Similarly, as boxes can be constructed from other
   PPL semantic objects, the method

     template <typename Box>
       void shrink_bounding_box(Box&, Complexity_Class) const

   has been removed from all the classes.

o  The use of methods having a name ending in `_and_minimize' (e.g.,
   add_constraints_and_minimize, poly_hull_assign_and_minimize, ...)
   is now deprecated (see the core library documentation for an
   explanation); their complete removal is planned for version 0.11.

o  Class BD_Shape and Grid no longer provide methods such as
   bds_hull_*, join_*, bds_difference_* and grid_difference_*. The
   uniformly named methods upper_bound_* and difference_assign should
   be used instead.  For (C and NNC) polyhedra, the poly_hull_* and
   poly_difference_assign methods have been kept for backward
   compatibility (users should anyway prefer adopting the uniformly
   named variants).

o  For Grids, the PPL no longer supports covering boxes; hence the constructor

     template <typename Box> Grid(const Box&, From_Covering_Box)

   and also the method

     template <typename Box> void get_covering_box(Box&) const

   have been removed.

Other changes for the C++ interface
-----------------------------------

o  All identifiers containing the strings `less_than_or_equal' or
   `greater_than_or_equal', any case, have been renamed so as to contain
   `less_or_equal' or `greater_or_equal', respectively.
   A similar change also applies to the C interface (see below).

o  The `ppl.hh' header file no longer defines macros not prefixed
   by "PPL_".

o  Users of the C++ interface of the library can now decide to disable
   the automatic initialization mechanism of the PPL.  To do so, the
   preprocessor symbol PPL_NO_AUTOMATIC_INITIALIZATION should be
   defined before including the <ppl.hh> header file.  When automatic
   initialization is disabled it is imperative to explicitly call the
   new function

     void Parma_Polyhedra_Library::initialize()

   before using the library.  The new function

     void Parma_Polyhedra_Library::finalize() and

   should also be called (to release a small amount of memory) when
   done with the library.

Changes to the other language interfaces
----------------------------------------

o  Support for language interfaces has been expanded to include
   OCaml and Java.  Thus the PPL now supports interfaces to
   C++, C, Java, OCaml, Ciao Prolog, GNU Prolog, SICStus Prolog,
   SWI Prolog, XSB Prolog and YAP Prolog.

o  Most of the PPL semantic objects provided by the C++ interface
   are also supported by all the non-C++ language interfaces. A few
   domains (in particular, many of the possible Box instantiations)
   are only available via the C++ interface.

o  Almost all the public methods for the PPL semantic objects are
   provided as methods/functions/predicates in the non-C++ language
   interfaces with a uniform naming policy. In particular:

   * in the C interface, the methods named

       ppl_Polyhedron_{constraints,generators,congruences}
       ppl_Polyhedron_minimized_{constraints,generators,congruences}

     have been renamed

       ppl_Polyhedron_get_{constraints,generators,congruences}
       ppl_Polyhedron_get_minimized_{constraints,generators,congruences},

     respectively;

   * in the Prolog interfaces, the predicates

       ppl_Grid_generalized_image_lhs_rhs/5 and
       ppl_Grid_generalized_preimage_lhs_rhs/5
       ppl_Grid_generalized_image/6 and
       ppl_Grid_generalized_preimage/6

     have been renamed as

       ppl_Grid_generalized_image_lhs_rhs_with_congruence/5
       ppl_Grid_generalized_preimage_lhs_rhs_with_congruence/5
       ppl_Grid_generalized_image_with_congruence/6
       ppl_Grid_generalized_preimage_with_congruence/6

     respectively, so as to allow for /4 and /5, resp., versions.

o  As already reported for the C++ interface, in the C interface,
   all identifiers containing the strings `less_than_or_equal' or
   `greater_than_or_equal', any case, have been renamed so as to contain
   `less_or_equal' or `greater_or_equal', respectively.

o  In the C interface it is no longer an error to call ppl_initialize()
   or ppl_finalize() multiple times (this matches the behavior of the
   other non-C++ language interfaces).

Documentation changes
---------------------

o  The documentation for the library has been deeply reorganized and
   split into several documents: besides the user and developer manuals
   for the core library and its C++ interface, we now provide separate
   user and developer manuals for each one of the other available
   language interfaces (namely, C, Java, OCaml, and Prolog). It is
   also possible to produce "configuration dependent" variants of the
   non-C++ language interface manuals, where the contents of the
   manual take into account the value of configuration option
   `--enable-instantiations'.
   All the manuals are provided in HTML, PDF and PostScript formats.

o  New man pages libppl(3) and libppl_c(3) have been added.  These
   give short overviews on how to use the PPL in C++ and C programs,
   respectively, on Unix-like operating systems.

Configuration changes
---------------------

o  Several options have been added to the configuration script.  These
   allow to control the generated language interfaces, the floating
   point instruction set to be used, the use of Valgrind during `make
   check', the exclusion of some PPL-based programs from the build.
   The README.configure file has been updated consequently.


Bugfixes
========

o  Fixed bugs that prevented building the library on systems not supported
   by the Parma Watchdog Library or when the `--disable-watchdog' configure
   was used.

o  Fixed a bug in Grid::constraints() and Grid::minimized_constraints()
   that caused an internal assertion to fail when the grid had 0 space
   dimensions.

o  Fixed a bug in Linear_System::insert(const Linear_Row&) whereby a
   wrong result could have been obtained when inserting a not necessarily
   closed constraint/generator in an empty system having a higher space
   dimension.


--------------------------------------------------------------------------
NEWS for version 0.9  (released on March 12, 2006)
--------------------------------------------------------------------------

New and Changed Features
========================

o  The class Grid provides a complete implementation of the relational
   domain of rational grids.  This can represent all sets that can
   be expressed by the conjunction of a finite number of congruence
   equations.  Operations provided include everything that is needed
   in the field of static analysis and verification, including affine
   images, preimages and their generalizations, grid-difference and
   widening operators.  This is the first time such a complete domain
   is made freely available to the community.

o  Several important portability improvements.  Among other things,
   it is now possible to build only the static libraries or only
   the shared libraries.  (Notice that some interfaces depend on
   the availability of the shared libraries: these will not be built
   when shared libraries are disabled.)


Bugfixes
========

o  Fixed a bug whereby the SICStus Prolog interface could not be built
   on x86_64.

o  Fixed a bug in an internal method that, under some circumstances,
   could cause a wrong result to be computed.


--------------------------------------------------------------------------
NEWS for version 0.8  (released on January 20, 2006)
--------------------------------------------------------------------------

New and Changed Features
========================

o  The class template BD_Shape<T> provides an implementation of the
   abstract domain of bounded difference shapes. The template type
   parameter T specifies the basic type used for the inhomogeneous term
   of bounded difference constraints; it can be instantiated to either
   GMP's unbounded precision types (mpq_class, mpz_class), native
   floating point types (float, double), or native integer types
   (8, 16, 32 and 64 bits wide).

o  New class LP_Problem provides an implementation of the
   primal simplex algorithm using exact arithmetic.

o  The new program `ppl-config' returns information about the
   configuration and the installed components of the PPL.
   This greatly simplifies the task of writing makefiles and
   automatic configuration scripts.  A manual page for `ppl-config'
   has also been added.

o  New Autoconf function

     AM_PATH_PPL([MINIMUM-VERSION, [ACTION-IF-FOUND [, ACTION-IF-NOT-FOUND]]])

   allows to test the existence and usability of particular versions of the
   PPL, defining macros containing the required paths.  The simple addition
   of, e.g.,

     AM_PATH_PPL(0.8)

   to an application's configure.ac file is all that is needed in most
   cases.  Paths to the installed version of the PPL will be detected,
   the version number will be checked to be at least the one
   indicated, the variables PPL_CPPFLAGS and PPL_LDFLAGS will be set
   accordingly and a quick sanity check of the PPL installation will
   be performed.  For more complex tasks, the AM_PATH_PPL function
   defines the `--with-ppl-prefix' and `--with-ppl-exec-prefix'
   configure options (useful when the PPL is installed into a
   non-standard place or when multiple versions of the PPL are
   installed).  AM_PATH_PPL also defines the `--disable-ppltest'
   configure option to disable the quick sanity check.  When something
   fails, AM_PATH_PPL provides accurate indications about what went
   wrong and how to fix it.  See the sources in m4/ppl.m4 for more
   information.

o  The browse and print versions of the PS and PDF formats of the user
   manual have been merged into single documents: ppl-user-0.8.pdf and
   ppl-user-0.8.ps.gz.  The equivalent developer reference documents
   have also been merged.

o  One of the possible values for the configuration option
   `--enable-coefficients' has been renamed from `gmp' to `mpz'.

o  New configuration option `--enable-interfaces' allows some or all of
   the Prolog and C interfaces to be selectively enabled.

o  Portability has been further improved.

o  Added to C_Polyhedron (resp., NNC_Polyhedron) new method

     bool poly_hull_assign_if_exact(const C_Polyhedron&)

   (resp. bool poly_hull_assign_if_exact(const NNC_Polyhedron&))
   and its synonym

     bool upper_bound_assign_if_exact(const C_Polyhedron&)

   (resp. bool upper_bound_assign_if_exact(const NNC_Polyhedron&)).

o  Added new typedef `element_type' to template Polyhedra_Powerset,
   which corresponds to the type of the underlying numeric domain.

o  Output operators have been added for Generator::Type and
   Constraint::Type.

o  Class Bounding_Box has new method

     Constraint_System Bounding_Box::constraints() const,

   which returns the system of constraints.

o  Class Bounding_Box has new widening methods

     Bounding_Box::CC76_widening_assign(const Bounding_Box& y)

   and

     template <typename Iterator>
     Bounding_Box::CC76_widening_assign(const Bounding_Box& y,
                                        Iterator first,
                                        Iterator last).

o  All methods in class Determinate that are specific to the Polyhedra
   template parameter have been dropped.  If needed, they can still be
   invoked through element().

o  Method

     bool Constraint_System::has_strict_inequalities() const

   is now publicly accessible.

o  Added Polyhedron methods difference_assign() and join_assign(),
   behaving as poly_difference_assign() and poly_hull_assign(),
   so as to have more uniform interfaces.

o  The helper function widen_fun_ref() building a limited widening
   function is now templatic even on the second argument (i.e., the
   limiting constraint system). The template widening method

     Polyhedra_Powerset<PH>::BHZ03_widening_assign()

   no longer has a default value for the certificate parameter.

o  The signatures of Polyhedron methods maximize() and minimize()
   have been greatly simplified.

o  The function template

     template <typename PH>
     bool check_containment(const PH&, const Polyhedra_Powerset<PH>&)

   now works whenever there exists a lossless conversion mapping an
   object of type PH into an NNC_Polyhedron (e.g., when PH = BD_Shape).
   The same holds for methods

     bool Polyhedra_Powerset<PH>::geometrically_covers()

   and

     bool Polyhedra_Powerset<PH>::geometrically_equals().

o  Disjuncts can be added to an instance of Polyhedra_Powerset with
   the new method

     void add_disjunct(const PH& ph).

o  The two generalized_affine_image() methods of class Polyhedron
   are now matched by corresponding methods for computing preimages
   of affine relations.

o  Added to class Polyhedron the method

     void bounded_affine_image(Variable v,
                               const Linear_Expression& lb,
                               const Linear_Expression& ub,
                               Coefficient_traits::const_reference d
                                 = Coefficient_one())

   computing the image of the polyhedron according to the
   transfer relation lb/d <= v' <= ub/d.
   Also added the corresponding method for computing preimages.

o  The enumeration

     Polyhedron::Degenerate_Kind

   has been placed outside of class Polyhedron and renamed as

     Degenerate_Element.

o  New output operators in namespace IO_Operators:

     std::ostream& operator<<(std::ostream&, const Constraint::Type&)

   and

     std::ostream& operator<<(std::ostream&, const Generator::Type&).

o  Added to class Constraint the methods

     bool is_tautological() const

   and

     bool is_inconsistent() const

   returning true when the constraint is always or never satisfied,
   respectively.

o  Added to classes Constraint (resp., Generator) the method

     bool is_equivalent_to(const Constraint& y) const

   (resp., bool is_equivalent_to(const Generator& y) const)
   which check for semantic equivalence of corresponding class
   instances.  Also made available the (semantic) comparison operators
   `==' and `!='.

o  The swap() methods of classes Linear_Expression, Constraint, Generator,
   Constraint_System and Generator_System are now publicly accessible.

o  Added to classes Constraint and Generator the methods

     void ascii_dump(std::ostream& s) const

   and

     void ascii_load(std::istream& s) const.

o  In classes Poly_Con_Relation and Poly_Gen_Relation the methods

     void ascii_dump(std::ostream& s) const

   and

     void ascii_load(std::istream& s) const

   are now publicly accessible.

o  All classes which provide the method

     void ascii_dump(std::ostream& s) const

   now also provide the methods

     void ascii_dump() const

   and

     void print() const.

   These methods print to std::cerr the textual and user-level
   representation (resp.) of the given object.  This enables the
   output of such object representations in GDB.

o  New functions added to the C interface:

     int ppl_Coefficient_is_bounded(void),
     int ppl_Coefficient_min(mpz_t min),
     int ppl_Coefficient_max(mpz_t max)

   allow C applications to obtain information about the Coefficient
   integer numerical type.

   The new Prolog interface predicates ppl_Coefficient_is_bounded/0,
   ppl_Coefficient_max/1 and ppl_Coefficient_min/1 provide the same
   functionality.

o  All predicates in the Prolog interface that require an input list
   as an argument will now throw an exception if that argument is not
   a list.  Before, some predicates, such as
   ppl_Polyhedron_remove_space_dimensions/2, would fail.

o  In the Prolog interface, the names and arities of the "with_token"
   widening and extrapolation predicates have been revised to
   "with_tokens" with an extra argument and the functionality has been
   revised to match more closely the corresponding C++ interface
   operators.

o  In the Prolog interface, the names and arities of the predicates
   that create handles for new polyhedra have been revised to match
   more closely the corresponding C and C++ interface operators.  That
   is, instead of having "c" and/or "nnc" as arguments to indicate the
   topology of the polyhedron, the topologies are now part of the
   names of the predicates.

o  The SWI-Prolog interface allows now the exchange of unbounded numbers
   between the PPL and Prolog applications.  This requires SWI-Prolog
   version 5.6.0 or later version.  Previous versions of SWI-Prolog
   are no longer supported.

o  The YAP interface allows now the exchange of unbounded numbers
   between the PPL and Prolog applications.  This requires YAP
   version 5.1.0 or later version.  Previous versions of YAP
   are no longer supported.

o  The `ppl_lpsol' demo has now two more options: with `--enumerate' it
   solves the given linear programming problem by vertex/point
   enumeration; with `--simplex' (the default) it uses our simplex
   implementation with exact arithmetic.  The `ppl_lpsol' program,
   which is only built if a suitable version of GLPK is available, is
   installed into the directory (selectable at configuration time) for
   user executables.

o  Manual pages have been added for the ppl_lpsol and ppl_lcdd
   programs.

o  The new class BD_Shape<T> as well as the "checked" native
   coefficients selectable with the `--enable-coefficients' configure
   options, are based on a very general and powerful notion of "number
   family with a policy".  This is made available to the users of the
   PPL via the wrapper template class Checked_Number<T, P>, where T is
   the underlying numeric type (native integer or float of any width,
   unbounded integer or rational) and `P' is a policy specifying
   things such as whether to check for overflows and other
   "exceptional" conditions and what to do in such cases.  The policy
   also specifies whether T should be extended with representations
   for infinities or NAN (Not A Number) and default rounding modes.
   A complete set of arithmetic functions and operators are provided:
   they either use the default rounding mode or accept a rounding mode
   as an extra parameter and, depending on the policy, may return a result
   that indicates the relation that exists between the true mathematical
   result and the (possibly approximate) computed result. Input/output
   functions with the same properties (controlled rounding and indications
   of the approximations) are also provided.


Bugfixes
========

o  Fixed a bug in Polyhedra_Powerset<PH>::concatenate_assign() whereby
   a temporary Polyhedra_Powerset object was created with the wrong
   dimension.

o  Corrected a memory leak bug in the demo ppl_lpsol.

o  Corrected a bug in method

     NNC_Polyhedron::minimized_constraints()

   whereby an internal assertion might have been violated.

o  Fixed a bug whereby calling the methods

     Polyhedron::generalized_affine_image()

   on an empty polyhedron could have resulted in an exception thrown.

o  Fixed a bug whereby the occurrence of an `out of memory' error during
   the allocation of a row of integer coefficients could have resulted
   in a memory leak.

o  Fixed a bug affecting the specialized constructors

     Polyhedra_Powerset<NNC_Polyhedron>::
     Polyhedra_Powerset(const Polyhedra_Powerset<C_Polyhedron>& y)

   and

     Polyhedra_Powerset<C_Polyhedron>::
     Polyhedra_Powerset(const Polyhedra_Powerset<C_Polyhedron>& y)

   whereby the newly built Polyhedra_Powerset object could have been
   flagged as non-redundant even though it was containing redundant
   disjuncts. Fixed a similar bug in generic constructor

     Polyhedra_Powerset(const Constraint_System& cs)

   that manifests when `cs' is denoting an empty polyhedron.

--------------------------------------------------------------------------
NEWS for version 0.7  (released on December 24, 2004)
--------------------------------------------------------------------------

New and Changed Features
========================

o  The new configuration option `--enable-coefficients' allows for the
   use of alternative (integral) coefficient types.  Besides GMP
   integers, the user can now use checked native integers (8, 16, 32
   or 64 bits wide).  The use of such native coefficients is
   completely safe, since systematic (yet efficient) overflow
   detection is performed and, in case of overflow, an exception is
   raised.  GMP coefficients are used by default.

o  Significant efficiency improvements have been achieved everywhere.

o  We now require GMP 4.1.3 or higher.

o  The following classes have been renamed as indicated:

     AskTell            -> Ask_Tell
     BoundingBox        -> Bounding_Box
     ConSys             -> Constraint_System
     GenSys             -> Generator_System
     Integer            -> Coefficient
     LinExpression      -> Linear_Expression
     Polyhedra_PowerSet -> Polyhedra_Powerset
     PowerSet           -> Powerset
     SatMatrix          -> Saturation_Matrix
     SatRow             -> Saturation_Row

o  The helper function `widen_fun' has been renamed `widen_fun_ref'.

o  New assignment operators allowing to obtain an NNC_Polyhedron from a
   C_Polyhedron and the other way around.  In the latter case, the
   topological closure of the argument polyhedron is computed.

o  New explicit constructors and assignment operators allowing to obtain a
   Polyhedra_Powerset<NNC_Polyhedron> from a Polyhedra_Powerset<C_Polyhedron>
   and the other way around.  In the latter case, the topological closure
   of the element polyhedra is computed.

o  New explicit constructor Powerset<CS>::Powerset(const CS& d):  if `d'
   is not bottom, builds a powerset containing only `d';  builds the empty
   powerset otherwise.

o  New explicit constructor
   Polyhedra_Powerset<CS>::Polyhedra_Powerset(const PH& ph):  if `ph' is
   not empty, builds a powerset containing only `ph';  builds the empty
   powerset otherwise.

o  New method

     Polyhedra_Powerset::poly_difference_assign(const Polyhedra_Powerset& y)

   assigns to `*this' the poly-difference of `*this' and `y'.

o  All the public classes of the library have been endowed with methods

     memory_size_type total_memory_in_bytes() const

   and

     memory_size_type external_memory_in_bytes() const

   returning (lower bounds for) the total size in bytes of the memory
   occupied by *this and of the memory managed by *this, respectively.
   The type `memory_size_type' is a newly added unsigned integral type
   suitable to the representation of such information.

o  New method dimension_type Polyhedron::affine_dimension() returns
   the affine dimension of *this (not to be confused with the dimension
   of its enclosing vector space) or 0, if *this is empty.

o  All the methods changing (i.e., adding, removing, mapping, etc.)
   the dimensions of the vector space have been renamed so as to avoid
   any possible ambiguity with the affine dimension of the modified object.
   For instance,

     Polyhedron::add_dimensions_and_embed(dimension_type m);

   has been renamed as

     Polyhedron::add_space_dimensions_and_embed(dimension_type m);

o  The constructor C_Polyhedron(const NNC_Polyhedron& y) no longer
   throws an exception if `y' is not topologically closed.  Rather,
   it constructs a C_Polyhedron representing the topological closure
   of `y'.

o  The following constructors have been made explicit:

     Constraint_System::Constraint_System(const Constraint& c),
     Generator_System::Generator_System(const Generator& g),
     C_Polyhedron::C_Polyhedron(const Constraint_System& cs),
     C_Polyhedron::C_Polyhedron(const Generator_System& cs),
     C_Polyhedron::C_Polyhedron(Constraint_System& cs),
     C_Polyhedron::C_Polyhedron(Generator_System& cs),
     NNC_Polyhedron::NNC_Polyhedron(const Constraint_System& cs),
     NNC_Polyhedron::NNC_Polyhedron(const Generator_System& cs),
     NNC_Polyhedron::NNC_Polyhedron(Constraint_System& cs),
     NNC_Polyhedron::NNC_Polyhedron(Generator_System& cs).
     Polyhedra_Powerset<PH>::Polyhedra_Powerset(const Constraint_System& cs).

o  Functions in the C interface that compute (space) dimensions
   no longer return their result.  The caller is now required to pass,
   as an extra argument, a pointer to a memory area where the result
   will be written.  All the C interface functions now use the return
   value to signal the success or failure of the requested operation.

o  Now `make check' runs a number of tests with `ppl_lcdd', comparing
   the results to expected ones.

o  The `ppl_lcdd' demo is now able to parse problems produced by lrs,
   i.e., where the number of rows of the matrix is omitted and replaced
   by "*****" (five asterisks).

o  The enumeration values of enum Complexity_Class have been renamed
   POLYNOMIAL_COMPLEXITY, SIMPLEX_COMPLEXITY and ANY_COMPLEXITY.

o  In the Prolog interface, the predicates
   ppl_new_polyhedron_from_dimension/3 and
   ppl_new_polyhedron_empty_from_dimension/3 have been replaced by a
   single predicate ppl_new_polyhedron_from_space_dimension/4 where
   the (extra) third argument indicates whether the polyhedron to be
   created should be the universe or the empty polyhedron.

o  As the unary plus operator is not in standard Prolog, '+'/1 in linear
   expressions is no longer supported by the Prolog interface.


Bugfixes
========

o  Fixed a bug that was causing an unwanted exception to be thrown
   when adding to a C_Polyhedron some generators obtained from an
   NNC_Polyhedron (even though no closure point was being added).

o  Fixed a bug in the handling of empty generator systems having
   a strictly positive space dimension.

o  Fixed a bug that was affecting Polyhedra_PowerSet::geometrically_covers()
   and Polyhedra_PowerSet::geometrically_equals().

o  Method C_Polyhedron::H79_widening_assign() now widens the polyhedron
   itself instead of the homogenized polyhedral cone representing it.

o  Fixed a bug that was affecting Polyhedron::H79_widening_assign()
   as well as all the limited and bounded extrapolation operators.

o  Fixed a bug in Polyhedron::map_space_dimensions() that could manifest
   itself when used with a partial function encoding permutation.

o  Fixed a bug in the C interface function
   ppl_new_Linear_Expression_with_dimension().

o  Fixed a bug in the `ppl_lpsol' demo.

o  Fixed a bug in Polyhedron::is_universe() that could manifest itself
   when the polyhedron is described by a generator system that is
   not in minimal form.


--------------------------------------------------------------------------
NEWS for version 0.6.1  (released on August 20, 2004)
--------------------------------------------------------------------------

New and Changed Features
========================

o  Some packaging issues have been fixed.

o  The documentation has been completed and improved.

o  The methods

     Polyhedra_PowerSet::semantically_contains(const Polyhedra_PowerSet&) and
     Polyhedra_PowerSet::semantically_equals(const Polyhedra_PowerSet&)

   have been renamed

     Polyhedra_PowerSet::geometrically_covers(const Polyhedra_PowerSet&) and
     Polyhedra_PowerSet::geometrically_equals(const Polyhedra_PowerSet& y),

   respectively.


--------------------------------------------------------------------------
NEWS for version 0.6  (released on August 18, 2004)
--------------------------------------------------------------------------

New and Changed Features
========================

o  New template classes Determinate, PowerSet, and Polyhedra_PowerSet.
   The first two classes realize, in a completely generic way, the
   determinate and powerset constructions described by Roberto Bagnara
   in his 1998, Science of Computer Programming paper.  The third class
   is a specialization of the powerset construction on polyhedra.
   The powerset construction comes with the generic widening technique
   proposed by Roberto Bagnara, Patricia Hill and Enea Zaffanella
   in their VMCAI 2004 paper.  Actually, the Polyhedra_PowerSet class
   provides the first genuine, non-trivial widening ever proposed
   (let alone made available) on a domain of sets of convex polyhedra.

o  New methods

     void Polyhedron::expand_dimension(Variable, dimension_type) and
     void Polyhedron::fold_dimensions(const Variables_Set&, Variable)

   allow the easy realization of summary dimensions as proposed
   by Denis Gopan and colleagues in their TACAS 2004 paper.

o  A new `demos' directory has been added.  In the `ppl_lcdd'
   subdirectory, this contains a sort of clone of the cddlib test
   program `lcdd', written using the PPL's C++ interface, together
   with several example polyhedra in the formats that the program can
   handle.  The `ppl_lpsol' subdirectory contains another demo program
   that solves linear programming problems by vertex/point
   enumeration.  This is written using the PPL's C interface and comes
   with several example problems in the Mathematical Programming
   System (MPS) format.  In order to read MPS files, `ppl_lpsol' uses
   the GNU Linear Programming Kit (GLPK); thus `ppl_lpsol' is only compiled
   if a suitable version of GLPK is available.

o  New macro PPL_VERSION expands to the version string of the library.

o  New file README.configure provides additional information about
   the configuration and compilation of the library.

o  The documentation has been improved in various ways.

o  The documentation for users, in PostScript, PDF and HTML formats,
   is now installed in a standard place by `make install'.

o  The variable `abandon_exponential_computations' has been renamed
   `abandon_expensive_computations'.

o  The methods

     void Polyhedron::add_constraints(ConSys& cs),
     void Polyhedron::add_generators(GenSys& gs),
     bool Polyhedron::add_constraints_and_minimize(ConSys& cs), and
     bool Polyhedron::add_generators_and_minimize(GenSys& gs)

   have been renamed

     void Polyhedron::add_recycled_constraints(ConSys& cs),
     void Polyhedron::add_recycled_generators(GenSys& gs),
     bool Polyhedron::add_recycled_constraints_and_minimize(ConSys& cs), and
     bool Polyhedron::add_recycled_generators_and_minimize(GenSys& gs),

   respectively.  At the same time, the methods

     void Polyhedron::add_constraints(const ConSys& cs),
     void Polyhedron::add_generators(const GenSys& gs),
     bool Polyhedron::add_constraints_and_minimize(const ConSys& cs), and
     bool Polyhedron::add_generators_and_minimize(const GenSys& gs)

   have been added.  Corresponding changes have been made to the C and
   Prolog interfaces.

o  New methods Polyhedron::maximize() and Polyhedron::minimize()
   for maximizing and minimizing a linear expression subject to the
   polyhedron.

o  New output operator in namespace IO_Operators:
   std::ostream& operator<<(std::ostream&, const LinExpression&).

o  The method Polyhedron::map_dimensions(const PartialFunction& pfunc)
   has been significantly optimized for the case when `pfunc' is a
   permutation.  A simple "renaming" of the dimensions is now
   extremely cheap.

o  The function Parma_Polyhedra_Library::max_space_dimension() has been
   given a new semantics and destiny: it returns the maximum space
   dimension that _all_ the abstractions provided by the library can
   handle.  Each individual abstraction provides its versions of this
   function.  Thus, e.g., NNC_Polyhedron::max_space_dimension()
   gives the maximum space dimensions an NNC_Polyhedron can handle.

o  The type of output functions for the class Variable,
   `Variable::Output_Function_Type', has been renamed
   `Variable::output_function_type' and is now defined as
   void output_function_type(std::ostream& s, const Variable& v).
   In other words, `v' is now passed by const reference and not by value.

o  Thanks to Bruno Haible, it is now possible to use versions of the
   GMP library installed into nonstandard places.  The new configure
   options `--with-libgmp-prefix[=DIR]' and `--with-libgmpxx-prefix[=DIR]'
   substitute the old (and not really working) options
   `--with-gmp-includes=DIR' and `--with-gmp-dir=DIR'.


Bugfixes
========

o  Fixed a bug in the C interface function ppl_Polyhedron_map_dimensions()
   whereby a wrong result was computed.

o  Fixed a bug in Polyhedron::poly_difference_assign(const Polyhedron&)
   whereby a wrong result was computed.

o  Fixed a bug in the Prolog interface predicate
   ppl_Polyhedron_get_bounding_box/3 whereby a wrong result was
   sometimes computed in the case of an empty polyhedron.

o  Fixed a bug in the Prolog interface predicate
   ppl_new_Polyhedron_from_bounding_box/3 whereby the predicate was
   failing when given an empty bounding box.


--------------------------------------------------------------------------
NEWS for version 0.5  (released on April 28, 2003)
--------------------------------------------------------------------------

New and Changed Features
========================

o  New methods Polyhedron::BHRZ03_widening_assign() and
   Polyhedron::BHRZ03_limited_extrapolation_assign().  The BHRZ03 widening
   is a novel widening that is always more precise than the one, by now
   standard, we call H79.

o  The novel "widening with tokens" technique improves on the good old
   widening delay technique by refraining from widening only when
   necessary.  Precision is thus increased still guaranteeing
   convergence.  All widening operators can now be supplied with an
   optional argument, recording the number of available tokens, which
   is decremented when tokens are used.

o  Two new methods have been defined that compute the image of
   a polyhedron under an affine relation. The first method,
   Polyhedron::generalized_affine_image(var, relsym, expr, denom),
   generalizes the classical Polyhedron::affine_image() method by allowing
   `relsym' to denote any of the relations <, <=, =, >=, >.
   The second method, Polyhedron::generalized_affine_image(lhs, relsym, rhs),
   is a variant where an arbitrary linear expression `lhs' is allowed to
   occur on the left-hand side of the affine relation.

o  New constructors to build polyhedra from read-only constraint and
   generator systems: C_Polyhedron(const ConSys&),
   C_Polyhedron(const GenSys&), NNC_Polyhedron(const ConSys&), and
   NNC_Polyhedron(const GenSys&).  In the C interface the functions
   taking non-const arguments named ppl_new_<T>_from_<S> have been
   renamed ppl_new_<T>_recycle_<S>, where <T> is either "C" or "NNC",
   and <S> is either "ConSys" or "GenSys".  The old names have been
   given to the new const functions.

o  New function LinExpression& operator*=(LinExpression&, const Integer&)
   to multiply (in place) an expression by a scalar.

o  The methods Polyhedron::check_empty() and Polyhedron::check_universe()
   have been renamed is_empty() and is_universe(), respectively.

o  New method bool Polyhedron::is_disjoint_from(const Polyhedron& y)
   returning true if and only `*this' and `y' are disjoint.

o  New methods bool Polyhedron::add_constraint_and_minimize(const
   Constraint&) and bool Polyhedron::add_generator_and_minimize(const
   Generator&) to add a constraint or a generator and minimizing the
   result at the same time.

o  New method: template <typename PartialFunction>
   void Polyhedron::map_dimensions(const PartialFunction&).
   This allows to rename the dimensions of a polyhedron according
   to a partial function mapping dimensions to dimensions.

o  New function LinExpression operator+(const LinExpression&): previously
   an expressions like `+x2-x3-x4 <= 0' could not constitute valid syntax
   for a constraint.

o  New type `dimension_type': an unsigned integral type for representing
   space dimensions.

o  New function dimension_type max_space_dimension():
   returns the maximum space dimension this library can handle.

o  New function dimension_type not_a_dimension():
   returns a value that does not designate a valid dimension.

o  The method Polyhedron::add_dimensions_and_constraints(ConSys&)
   has gone.  A similar functionality is provided by the new method
   Polyhedron::concatenate_assign(const Polyhedron&).  The same change
   has, of course, been performed on all the PPL interfaces.

o  New macros PPL_VERSION_MAJOR, PPL_VERSION_MINOR, PPL_VERSION_REVISION,
   and PPL_VERSION_BETA allow the client application to adapt to different
   versions of the library.

o  New function const char* version() returns a character string
   containing the PPL version.

o  New function const char* banner() returns a character string
   containing information about the PPL version, the licensing,
   the lack of any warranty whatsoever, the C++ compiler used
   to build the library, where to report bugs and where to look
   for further information.

o  The Prolog interface now supports also Ciao Prolog and XSB.

o  The C and Prolog interfaces have been extended so as to make more of
   the library's functionality available to Prolog and C users.

o  Timeout computation facilities have been added to the Prolog interfaces:
   new predicates ppl_set_timeout_exception_atom/1,
   ppl_timeout_exception_atom/1, ppl_set_timeout/1, ppl_reset_timeout/0.

o  Many efficiency improvements have been achieved.  Part of these have
   been obtained by increasing the degree of "laziness" of the library.

o  Many portability and standard-conformance improvements: the library
   can now be compiled with GNU g++, Intel C++ Compiler 7.0 for Linux,
   and Comeau C/C++ 4.3.0.1 Compiler Front-End; the library has also
   been tested on a variety of platforms.

o  The functions

     Polyhedron::operator<=(const Polyhedron&, const Polyhedron&),
     Polyhedron::operator>=(const Polyhedron&, const Polyhedron&),
     Polyhedron::operator<(const Polyhedron&, const Polyhedron&), and
     Polyhedron::operator>(const Polyhedron&, const Polyhedron&)

   have been removed.  The methods

     Polyhedron::contains(const Polyhedron&) and
     Polyhedron::strictly_contains(const Polyhedron&)

   provide the same functionality.

o  The method Polyhedron::limited_H79_widening_assign() has been renamed
   Polyhedron::limited_H79_extrapolation_assign().  From now on, the name
   `widening' is reserved for operators that come with a convergence
   guarantee (i.e., with the ability of turning infinite chains to finite
   ones).  Upper bound operators without such a guarantee contain the word
   `extrapolation' in their name.

o  The renamed method Polyhedron::limited_H79_extrapolation_assign()
   takes the constraint system argument by const reference (in the
   old Polyhedron::limited_H79_widening_assign() that argument was
   passed by non-const reference).

o  We now require GMP 4.1.2 or higher.

o  In conformance with the C++ standard [17.4.3.1.2], in all the
   identifiers exported by the C interface, any occurrence
   of "__" (double underscore) has been replaced by "_" (underscore).

o  Added a parameter to Polyhedron::shrink_bounding_box(): this specifies
   the complexity class of the algorithm to be used.

o  All the input/output operators have been confined into namespace
   Parma_Polyhedra_Library::IO_Operators.  This way they do not conflict
   with the operators the user might want to define.

o  The operator Constraint operator>>(const Constraint&, unsigned int)
   has been removed.

o  The method
   Polyhedron::poly_difference_assign_and_minimize(const Polyhedron&)
   has been removed.


Bugfixes
========

o  Fixed a bug in operator-=(LinExpression&, const LinExpression&)
   whereby we computed a wrong result in some circumstances.

o  Fixed a bug in method Polyhedron::minimized_constraints() that,
   under some circumstances, could cause a wrong result or a program
   crash.


--------------------------------------------------------------------------
NEWS for version 0.4.2 (released on October 4, 2002)
--------------------------------------------------------------------------

Bugfixes
========

o  Fixed a bug in method Polyhedron::add_generator(const Generator&)
   whereby we were not adding the corresponding closure point when adding
   a point to an empty NNC polyhedron.

o  Fixed a bug in method GenSys::insert(const Generator&) whereby the
   insertion of a generator into an empty generator system might be
   mishandled.

o  Fixed a bug in method Polyhedron::operator<=(const Polyhedron&)
   whereby the lines of the polyhedron were handled improperly.

o  Fixed a bug in a private method used to implement public method
   Polyhedron::relation_with(const Generator& g),
   whereby a wrong result was obtained when `g' was a line.

o  Fixed a bug in methods Polyhedron::affine_image() and
   Polyhedron::affine_preimage(), whereby a wrong result could be
   obtained when using a negative denominator for the affine expression.

o  Fixed a bug in methods Polyhedron::minimized_constraints() and
   Polyhedron::minimized_generators(), whereby a library invariant
   was violated when calling these methods on a zero-dimensional space
   universe NNC polyhedron.


--------------------------------------------------------------------------
NEWS for version 0.4.1 (released on July 30, 2002)
--------------------------------------------------------------------------

Bugfixes
========

o  Fixed a bug in Polyhedron::poly_difference_assign(const Polyhedron& y)
   whereby the equality constraints of `y' were ignored (the bug was
   affecting both C and NNC computations).

o  Fixed a bug in Polyhedron::operator=(const Polyhedron& y).  This bug,
   which is triggered in some cases when `y' is empty, should only affect
   versions of the library obtained with the `--enable-assertions'
   configuration flag.

o  Fixed a bug in Polyhedron::check_universe(), which was returning
   the wrong result when called on a zero-dim universe polyhedron.

o  Fixed a bug in NNC_Polyhedron::NNC_Polyhedron(ConSys& cs) whereby
   an invariant was violated in case `cs' was empty.  This bug
   should only affect versions of the library obtained with the
   `--enable-assertions' configuration flag.


--------------------------------------------------------------------------
NEWS for version 0.4 (released on July 1, 2002)
--------------------------------------------------------------------------

New and Changed Features
========================

o  Added full support for Not Necessarily Closed (NNC) polyhedra:
   - creation of strict inequality constraints and mixed constraint
     systems;
   - creation of closure points and extended generator systems;
   - added classes C_Polyhedron (for the representation of Closed
     polyhedra) and NNC_Polyhedron (the user no longer can create
     Polyhedron objects);
   - added topology compatibility checks to avoid mixing objects of
     the two kinds;
   - added explicit constructors to create a polyhedron of a given
     topology kind starting from a polyhedron of the other kind;
   - added methods Polyhedron::is_topologically_closed() and
     Polyhedron::topological_closure_assign();
   - implemented methods Polyhedron::minimized_constraints() and
     Polyhedron::minimized_generators() to obtain minimal
     descriptions, both for closed and for NNC polyhedra.

o  New method Polyhedron::time_elapse_assign(const Polyhedron&):
   it computes the time-elapse operation defined in

     N. Halbwachs, Y.-E. Proy, and P. Roumanoff.
     Verification of real-time systems using linear relation analysis.
     Formal Methods in System Design, 11(2):157-185, 1997.

o  New method Polyhedron::is_bounded(): it returns true if and only
   if the polyhedron is bounded, i.e., finite.

o  New methods Polyhedron::bounds_from_above(const LinExpression& e)
   and Polyhedron::bounds_from_below(const LinExpression& e): they
   return true if and only if the linear expression `e' is bounded
   from above/below in the polyhedron.

o  New, complete C interface.  As a demo, a toy solver for pure linear
   programming problems has been implemented using this interface.
   Notice that solving linear programming problems is completely
   outside the scope of the library.  As a consequence the toy provided
   as a demo is only a toy provided as a demo.

o  Revised and completed Prolog interface:
   - now supporting GNU Prolog, SICStus Prolog, SWI-Prolog and YAP.
   - all predicates have been renamed to match their intended
     semantics;
   - arguments have been reordered where necessary so as to follow the
     rule "input arguments before output arguments";
   - predicates added so that all the public methods for Polyhedra in
     the C++ library are available as Prolog predicates;
   - the interface has been extended to allow for closed and not
     necessarily closed polyhedra.

o  Added support for timeout-guarded operations.  It is now possible
   for client applications to safely interrupt any exponential
   computation paths in the library and get control back in a time
   that is a linear function of the space dimension of the object
   (polyhedron, system of constraints or generators) of highest
   dimension on which the library is operating upon.

o  The methods named convex_hull_* and convex_difference_*
   have been renamed poly_hull_* and poly_difference_*.

o  All methods named *_and_minimize() now return a Boolean
   flag that is false if the result is empty.

o  All method and variable names containing the word "vertex"
   have been replaced by names containing the word "point"
   (some previous uses of the word "vertex" were not formally correct).

o  The methods Polyhedron::includes(const Generator&) and
   Polyhedron::satisfies(const Constraint&) have been removed,
   as well as the enumeration GenSys_Con_Rel.
   They have been replaced by the new methods
   Polyhedron::relation_with(const Generator&) and
   Polyhedron::relation_with(const Constraint&),
   which return values of the new enumeration types
   Relation_Poly_Gen and Relation_Poly_Con, respectively.

o  The method Constraint::coefficient(void) has been renamed
   to Constraint::inhomogeneous_term(void).

o  The methods Polyhedron::widening_assign() and
   Polyhedron::limited_widening_assign() have been renamed
   Polyhedron::H79_widening_assign() and
   Polyhedron::limited_H79_widening_assign(), respectively.
   This emphasizes the fact that they implement extensions
   of the widenings introduced in

     N. Halbwachs.
     Determination Automatique de Relations Lineaires
     Verifiees par les Variables d'un Programme.
     These de 3eme cicle d'informatique,
     Universite scientifique et medicale de Grenoble,
     Grenoble, France, March 1979.

   and described in

     N. Halbwachs, Y.-E. Proy, and P. Roumanoff.
     Verification of real-time systems using linear relation analysis.
     Formal Methods in System Design, 11(2):157-185, 1997.

o  The library no longer calls abort(): appropriate exceptions
   are always thrown instead.


Bugfixes
========

o  Fixed a bug whereby creating a point with a negative denominator
   caused the library to misbehave.

o  Fixed a bug in Polyhedron::add_constraints(ConSys&) whereby
   we could have created constraint systems having rows with
   different capacities.

o  Several other bugs have been fixed.


--------------------------------------------------------------------------
NEWS for version 0.3 (released on February 26, 2002)
--------------------------------------------------------------------------

New Features
============

o  The library has been ported under Libtool: it is now possible
   to build dynamic libraries as well.

o  We now use the integer C++ class of GMP to represent the
   coefficients of constraints and generators, instead of our own
   (very much inferior) Integer class.  The drawback is that we
   now require GMP 4.0.1 or higher.

o  New methods Polyhedron::convex_difference_assign(const Polyhedron&) and
   Polyhedron::convex_difference_assign_and_minimize(const Polyhedron&).
   They assign to `*this' the convex hull of the set-theoretic difference
   of `*this' and the argument (possibly non minimized or minimized,
   respectively).

o  The method Polyhedron::add_generators(GenSys&) is now lazy,
   i.e., no minimization is performed.  Adding generators and
   minimizing at the same time is provided by the method
   Polyhedron::add_generators_and_minimize(GenSys&).
   These methods now throw an exception if the resulting
   polyhedron would be illegal.

o  Some performance improvements.

o  Added more test programs.


Bugfixes
========

o  Fixed Polyhedron::satisfies(const Constraint&) and
   Polyhedron::affine_image().

o  Polyhedron::limited_widening_assign(const Polyhedron&, ConSys&)
   was erroneously returning a (random) Boolean: it is now a void
   method.


--------------------------------------------------------------------------
NEWS for version 0.2 (released on November 14, 2001)
--------------------------------------------------------------------------

New Features
============

o  Massive API changes.  This would not normally be called "a feature",
   but the old API was very wrong in a number of ways.  More API changes
   are to be expected for the next few releases.

o  All user-accessible library methods are now guarded by suitable
   sanity checks.  Exception are thrown whenever the library is not
   called in the intended way.

o  A SICStus Prolog interface is now available.  It comes with a somewhat
   interesting demo: a toy CLP(Q) interpreter.

o  Greatly improved documentation.


Bugfixes
========

o  Many, many more than we would like to admit.


--------------------------------------------------------------------------
NEWS for version 0.1 (released on October 24, 2001)
--------------------------------------------------------------------------

New Features
============

o  The library has been released under the GNU General Public License.