| 
  
   the subword reachability problem in finitely presented commutative
   semigroups;
   | 
 
 
  
    
   | 
  
   the problem of computing the minimal elements of an equivalence
   class in a finitely presented commutative semigroup;
   | 
 
 
  
    
   | 
  
   the problem of computing the periods of an equivalence
   class in a finitely presented commutative semigroup;
   | 
 
 
  
    
   | 
  
   the equivalence problem for finitely presented commutative semigroups;
   | 
 
 
  
    
   | 
  
   the problem of computing the reduced Gröbner basis for a
   binomial ideal.
   | 
 
These bounds provide the first exact complexity bounds for Gröbner
basis computation and for the representation of the state set of
reversible Petri nets.