Omega Calculator version 0.7 available

The beta release of version 0.7 of the Omega Calculator is now
available for anonymous ftp from ftp.cs.umd.edu:pub/omega/OmegaCalc.
Version 0.7 is the first publicly released Omega Calculator version.


The implementation of the Omega Calculator has been done by a number
of people at the University of Maryland:


Wayne Kelly, Vadim Maslov, William Pugh,
Evan Rosser, Tatiana Shpeisman, Dave Wonnacott


Enclosed is README file from the distribution.




This is a beta release of version 0.7 of the Omega Calculator.
The Omega calculator is a text-based interface to the Omega library,
a set of routines developed for manipulating
    * Presburger formulas,
    * Integer tuple sets, and
    * Integer tuple relations


This beta release surely contains a number of undiscovered bugs
as well as known, undocumented bugs we haven't got around
to fixing yet. This release is being distributed to let people
see where we are going with our research, and learn whether
more robust and documented versions of our software might be
useful in their research. This version will expire on July 31st,
1994. By that point, a new, improved version should be available.
The ftp site for our software is ftp.cs.umd.edu/pub/omega. The
Omega calculator is in the subdirectory OmegaCalc. Information
about the Omega project is also available via www:
http://www.cs.umd.edu/projects/omega


At the moment, we are only making executables available via
anonymous ftp. Source code is available by request (so that
we to conform to g++-lib's distribution requirements), but not
via ftp. The current source is unsupported and guaranteed to change
without notice. We _highly_recommend_ that you wait for a supported
source release if you want to use our source - we plan to release this
soon, together with a description of the high level C++ interface. If
you really must have the source now, send a 1000 word essay on why
you can't wait, to omega@cs.umd.edu ;-). The Omega library will be
freely available for experimentation or incorporation in research
or commercial tools (and will be freed from g++-lib).




Presburger Formulas
===================


Presburger formulas are those formulas that can be built using
linear constraints over integer variables, the usual logical
connectives ("and", "or" and "not") and universal and existential
quantifiers ("there exists" and "forall").


Within the realm of Presburger formulas, the Omega calculator is
exact. The worst-case cost of determining the satisfablity of
Presburger formulas is suspected to be $2^{2^{2^{O(n)}}}$, and
our worst case performance is no better than this. For simple
cases arising in situations such as dependence analysis and
compiling High Performance Fortran, our performance is acceptable.


We have recently been focused on improving the functionality
of our library rather than the performance. It is currently
4-8 times slower than our previous implementation. Some of
this will improve in the near future, but our speed will
probably never match that of our previous implementation
due to the high-level, abstract interface provided by the
new library.




The Omega calculator
====================


The Omega calculator manipulates sets of integer tuples and
relations between integer tuples. Some examples include:


{ [i,j] : 1 <= i,j <= 10};


{ [i] ->[i,j] : 1 <= i < j <= 10};


{ [i,j] ->[i+1,j+1] : 1 <= i, j <= n};


The conditions describing a set or tuple can be an
formulas can described by an arbitrary Presburger formula.


The Omega calculator can also manipulate relations and sets
using standard operations such as union, intersection,
difference, inverse and composition.


In the following examples, input to the calculator is
prefixed with "#":


# R := { [i] -> [i+1] : 1 <= i <= 9 };
# S := {[i] : 5 <= i <= 15 };
# inverse R;
{[In_1] -> [In_1-1] : 2 <= In_1 <= 10}
# domain R;
{[i] : 1 <= i <= 9}
# range R;
{[In_1] : 2 <= In_1 <= 10}
# R compose R;
{[i] -> [i+2] : 1 <= i <= 8}
# S;
{[i] : 5 <= i <= 15}
# R(S);
{[Out_1] : 6 <= Out_1 <= 10}
# symbolic n;
# {[iw] -> [ir] :
# 1 <= iw, ir <= 2n and iw=ir
# and ! exists ( ik,jk : 1 <= ik <= 2n && 1 <= jk < n and
# iw <= ik = ir and 2jk = ir )
# and ! exists ( ik,jk : 1 <= ik <= 2n && 1 <= jk < n and
# iw <= ik = ir and 2jk+1 = ir )
# };
{[iw] -> [iw] : n = 1 && 1 <= iw <= 2}
union {[1] -> [1] : 1 <= n}
union {[2n] -> [2n] : 1 <= n}
# I := {[i,j]: 1 <= i <= 101 && exists (alpha : i = 2 alpha) &&
# 2n+i <= j <=401 && exists (alpha : j = 2 alpha)};
# iterations I;
if n <= 199 then
for i = 2 to min((-2n+400),100) step 2 do
    for j = (2n+i) to 400 step 2 do
        <element>
#


--

Return to the comp.compilers page.
Search the comp.compilers archives again.