Changeset c0631ae in git

Timestamp:

Apr 16, 2018, 1:37:27 PM (5 years ago)

Author:

Karim Abou Zeid <karim23697@…>

Branches:

(u'spielwiese', '8e0ad00ce244dfd0756200662572aef8402f13d5')

Children:

fba1c3965fbbe8b7c8b52cb5e07338d93c09aab4

Parents:

3d9a641dcde94d8e4816289e70f2242501f5fd27

Message:

Weak Noetherian

File:

• Singular/LIB/fpaprops.lib (modified) (8 diffs)

Singular/LIB/fpaprops.lib

@@ -37 +37 @@
 @*      2 right Noetherian
 @*      3 Noetherian
-@*      4 weak Noetherian (TODO)
+@*      4 weak Noetherian
 PURPOSE: Check whether the monomial algebra A/<LM(G)> is (left/right) noetherian
 ASSUME: - basering is a Letterplace ring
@@ -98 +98 @@
   intvec visited;
   visited[ncols(UG)] = 0;
-  int inFlag, outFlag;
+  int inFlag, outFlag, inOutFlag;
   for (int v = 1; v <= ncols(UG) && (inFlag + outFlag) != 3; v++) {
-    int inOutFlags = inOrOutCommingEdgeInCycle(UG, v, visited, 0);
+    int inOutFlags = inOutCommingEdgesInCycles(UG, v, visited, 0);
     if (inOutFlags == 1) {
       inFlag = 1;
     }
     if (inOutFlags == 2) {
-      outFlag = 2;
+      outFlag = 1;
     }
     if (inOutFlags == 3) {
       inFlag = 1;
-      outFlag = 2;
+      outFlag = 1;
+    }
+    if (inOutFlags == 4) {
+      inOutFlag = 1;
+    }
+    if (inOutFlags == 5) {
+      inFlag = 1;
+      inOutFlag = 1;
+    }
+    if (inOutFlags == 6) {
+      outFlag = 1;
+      inOutFlag = 1;
+    }
+    if (inOutFlags == 7) {
+      inFlag = 1;
+      outFlag = 1;
+      inOutFlag = 1;
     }
     kill inOutFlags;
   } kill v;
-  return (3 - inFlag - outFlag);
+  int noetherian = 3 - 1*inFlag - 2*outFlag;
+  if (noetherian == 0) {
+    return (4 - 4*inOutFlag); // weak noetherian
+  }
+  return (noetherian);
 }
 example
@@ -125 +145 @@
 }
 
-static proc inOrOutCommingEdgeInCycle(intmat G, int v, intvec visited, intvec path) {
+static proc inOutCommingEdgesInCycles(intmat G, int v, intvec visited, intvec path) {
   // Mark the current vertex as visited
   visited[v] = 1;
@@ -136 +156 @@
   }
 
-  int inFlag, outFlag;
+  int inFlag, outFlag, inOutFlag;
 
   for (int w = 1; w <= ncols(G) && (inFlag + outFlag) != 3; w++) {
     if (G[v,w] == 1) {
-      if (visited[w] == 1) {
-        // new cycle
-        if (v == w) {
+      if (visited[w] == 1) { // new cycle
+        int tmpInFlag;
+        int tmpOutFlag;
+        if (v == w) { // cycle is a loop
           for (int u = 1; u <= ncols(G); u++) {
             if (G[v,u] && u != v) {
-              outFlag = 2;
+              outFlag = 1;
+              tmpOutFlag = 1;
             }
             if (G[u,v] && u != v) {
               inFlag = 1;
+              tmpInFlag = 1;
             }
           } kill u;
@@ -158 +181 @@
                 if (path[i] != v) {
                   if (u != path[i+1]) { // and u is not the next element in the cycle
-                    outFlag = 2;
+                    outFlag = 1;
+                    tmpOutFlag = 1;
                   }
                 } else {
                   if (u != w) {
-                    outFlag = 2;
+                    outFlag = 1;
+                    tmpOutFlag = 1;
                   }
                 }
@@ -170 +195 @@
                   if (u != path[i-1]) { // and u is not the previous element in the cylce
                     inFlag = 1;
+                    tmpInFlag = 1;
                   }
                 } else {
                   if (u != v) {
                     inFlag = 1;
+                    tmpInFlag = 1;
                   }
                 }
@@ -183 +210 @@
           } kill i;
         }
+        if (tmpInFlag > 0 && tmpOutFlag > 0) {
+          // there are both in and outcomming edges in this cycle
+          inOutFlag = 1;
+        }
+        kill tmpInFlag;
+        kill tmpOutFlag;
       } else {
-        int inOutFlags = inOrOutCommingEdgeInCycle(G, w, visited, path);
+        int inOutFlags = inOutCommingEdgesInCycles(G, w, visited, path);
         if (inOutFlags == 1) {
           inFlag = 1;
         }
         if (inOutFlags == 2) {
-          outFlag = 2;
+          outFlag = 1;
         }
         if (inOutFlags == 3) {
           inFlag = 1;
-          outFlag = 2;
+          outFlag = 1;
+        }
+        if (inOutFlags == 4) {
+          inOutFlag = 1;
+        }
+        if (inOutFlags == 5) {
+          inFlag = 1;
+          inOutFlag = 1;
+        }
+        if (inOutFlags == 6) {
+          outFlag = 1;
+          inOutFlag = 1;
+        }
+        if (inOutFlags == 7) {
+          inFlag = 1;
+          outFlag = 1;
+          inOutFlag = 1;
         }
         kill inOutFlags;
@@ -200 +249 @@
   } kill w;
 
-  return (inFlag + outFlag);
+  return (1*inFlag + 2*outFlag + 4*inOutFlag);
 }