Release 0.96 of the Omega Library and Calculator

Version 0.96 of the Omega Calculator and Omega Library is now available for anonymous ftp from ftp://ftp.cs.umd.edu/pub/omega/omega_library.

The Omega library/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] ->[j,j'] : 1 <= i < j < j' <= n}; The conditions describing a set or tuple can be an formulas can described by an arbitrary Presburger formula. Relations and sets can be combined using functions such as composition, intersection, union and difference. It also provides routines to generate code to iterate over the points in an integer tuple set. The Omega library provides a high-level, C++ interface to our routines. The Omega calculator is a text-based interface to the Omega library.

We hope to get feedback from this release about our interface. If you have an interest in using the Omega library in your work, please look over the interface and give us feedback. We will be much more likely to listen to requests for changes in the interface now than after we release version 1.0.

The interface of this current version will hopefully change and improve for version 1.0 as a result of feedback from users and our continuing work. However, we are unlikely to make any changes that would require substantial changes for people writing code that interfaces with version 0.91. We intend to release version 1.0 sometime in the late spring.

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

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

To give you an idea of what the Omega calculator and library can do, I've enclosed below same output from the Omega calculator. The input is echoed on lines starting with #

# Omega Calculator [v0.96, Jun 95]:
# #
# # Some examples from the documentation for the Omega Calculator
# # This is the input for figures 2 and 3.
# #
# 
# R := { [i] -> [i'] : 1 <= i,i' <= 10 && i' = i+1 };
# 
# R;

{[i] -> [i+1] : 1 <= i <= 9}

# 
# inverse R;

{[i] -> [i-1] : 2 <= i <= 10}

# 
# domain R;

{[i] : 1 <= i <= 9}

# 
# range R;

{[i] : 2 <= i <= 10}

# 
# R compose R;

{[i] -> [i+2] : 1 <= i <= 8}

# 
# R+;

{[i] -> [i'] : 1 <= i < i' <= 10}

#              # closure of R = R union (R compose R) union (R compose R ...
# complement R;

{[i] -> [i'] : i <= 0} union
 {[i] -> [i'] : 10 <= i} union
 {[i] -> [i'] : 1 <= i <= 9, i'-2} union
 {[i] -> [i'] : 1, i' <= i <= 9}

# 
# S := {[i] : 5 <= i <= 25};
# 
# S;

{[i] : 5 <= i <= 25}

# 
# R(S);

{[i] : 6 <= i <= 10}

#            # apply R to S
# R \ S;

{[i] -> [i+1] : 5 <= i <= 9}

#           # restrict domain of R to S
# R / S;

{[i] -> [i+1] : 4 <= i <= 9}

#           # restrict range of R to S
# (R\S) union (R/S);

{[i] -> [i+1] : 4 <= i <= 9}

# 
# (R\S) intersection (R/S);

{[i] -> [i+1] : 5 <= i <= 9}

# 
# (R/S) - (R\S);

{[4] -> [5] }

# 
# S*S;

{[i] -> [i'] : 5 <= i <= 25 && 5 <= i' <= 25}

#             # cross product 
# D := S - {[9:16:2]} - {[17:19]};
# 
# D;

{[i] : 5 <= i <= 8} union
 {[i] : Exists ( alpha : 2alpha = i && 10 <= i <= 16)} union
 {[i] : 20 <= i <= 25}

# 
# T :=  { [i] : 1 <= i <= 11 & exists (a : i = 2a) };
# 
# T;

{[i] : Exists ( alpha : 2alpha = i && 2 <= i <= 10)}

# 
# Hull T;

{[i] : 2 <= i <= 10}

# 
# Hull D;

{[i] : 5 <= i <= 25}

# 
# codegen D;
for(t1 = 5; t1 <= 8; t1++) {
  s1(t1);
  }
for(t1 = 10; t1 <= 16; t1 += 2) {
  s1(t1);
  }
for(t1 = 20; t1 <= 25; t1++) {
  s1(t1);
  }

# 
# codegen {[i,j] : 1 <= i+j,j <= 10};
for(t1 = -9; t1 <= 9; t1++) {
  for(t2 = max(-t1+1,1); t2 <= min(-t1+10,10); t2++) {
    s1(t1,t2);
    }
  }

#

Web Accessibility

omega@cs.umd.edu