#!/usr/bin/env python """ file: coextensions.py version: 1.0.1 date: 2020-08-30 author: Milan Petrik e-mail: petrikm@tf.czu.cz web page: http://home.czu.cz/petrikm/ ----------------------------------------------------- Run this program by typing "python coextensions.py". See the bottom of this file for examples. ----------------------------------------------------- Description: ------------ This program serves to generate all one-element coextensions of a given finite, negative tomonoid (abbreviated by "f.n. tomonoid"). (Here, tomonoid stands for a totally ordered monoid.) A f.n. tomonoid is a structure (S; <=, *, 1) such that: S is a finite set <= is a total order on S with the top element 1 *: S x S -> S is a binary operation on S such that, for every x,y,z in S: (x*y)*z = x*(y*z), x*1 = 1*x = x, y <= z implies x*y <= x*z and y*x <= z*x. A f.n. tomonoid is "commutative" iff x*y = y*x for every x,y in S. A f.n. tomonoid is "Archimedean" iff for every x <= y there is a natural number n such that y^n <= x. Here, y^n = y * y * ... * y (n times). For a detailed description of the algorithm see the papers: * M. Petrik and Th. Vetterlein. Algorithm to generate finite negative totally ordered monoids. In: IPMU 2016: 16th International Conference on Information Processing and Management of Uncertainty in Knowledge-Based Systems. Eindhoven, Netherlands, June 20-24, 2016. DOI: 10.1109/IFSA-SCIS.2017.8023247. * M. Petrik and Th. Vetterlein. Algorithm to generate the Archimedean, finite, negative tomonoids. In: Joint 7th International Conference on Soft Computing and Intelligent Systems and 15th International Symposium on Advanced Intelligent Systems. Kitakyushu, Japan, Dec. 3-6, 2014. DOI: 10.1109/SCIS-ISIS.2014.7044822. For details on one-element coextensions of finite, negative, tomonoids see the papers: * M. Petrik and Th. Vetterlein. Rees coextensions of finite tomonoids and free pomonoids. Semigroup Forum 99 (2019) 345-367. DOI: 10.1007/s00233-018-9972-z. * M. Petrik and Th. Vetterlein. Rees coextensions of finite, negative tomonoids. Journal of Logic and Computation 27 (2017) 337-356. DOI: 10.1093/logcom/exv047. History: -------- 2015-02-02 (v1.0.0) The program has been written. It can generate all f.n.tomonoids of a given size. Uses can choose to generate only Archimedean or commutative tomonoids. 2020-08-30 (v1.0.1) Comments in the source code have been changed to reflect the correct terminology ("elementary extensions have been renamed to "one-element coextensions", etc.). """ import copy import timeit import datetime import cPickle as pickle class Error(Exception): """A general error. The only attribute is 'text' with a description of the error.""" def __init__(self, text): """Parameters: text ... the description of the error """ self.text = text def __str__(self): return self.text class ErrorMultipleValues(Error): """Error referring to the fact, that there are assigned multiple values to one level equivalence class of a tomonoid. Attribute 'values' is a list of the values that are assigned.""" def __init__(self, values, tomonoid): self.values = values self.tomonoid = tomonoid self.text = "Multiple values: " + str(self.values) + " on tomonoid of size " + str(self.tomonoid.size) + "\n" + self.tomonoid.exportTableToText() + "\n" + self.tomonoid.parent.exportTableToText() class Counter: """Gives the sequence of increasing natural numbers. This is used to give unique names to generated tomonoids.""" def __init__(self): self.number = 0 self.report = False self.period = 10000 self.time = timeit.default_timer() def getNew(self): """Returns a new number increased by 1.""" self.number = self.number + 1 if self.report and self.number % self.period == 0: newTime = timeit.default_timer() print datetime.datetime.today(), print "Counter has reached", self.number, "in", (newTime - self.time), "seconds." self.time = newTime return self.number def getCurrent(self): """Returns the last number in the sequence. No inner increasing done.""" return self.number class ElementNames: "List of names of the elements of the tomonoid" def __init__(self, size): """Creates the list of names of the elements of the tomonoid. E.g. '0', 'u', 'v', 'w', 'x', 'y', 'z', '1' for a tomonoid of the size 8.""" self.size = size letters = map(chr, range(97, 124)) letters.reverse() self.names = self.size * ['?'] for i in range(self.size): self.names[i] = letters[i] self.names[self.size-1] = '0' self.names[0] = '1' def extend(self): """Extends the list of names of the elements by one. E.g. if the current size is 8 and thus the list is '0', 'u', 'v', 'w', 'x', 'y', 'z', '1' then the new size will be 9 and the list will be '0', 't', 'u', 'v', 'w', 'x', 'y', 'z', '1'.""" letters = map(chr, range(97, 124)) letters.reverse() self.names.append('0') self.size += 1 if self.size > 2: try: self.names[self.size-2] = letters[self.size-2] except IndexError: print "len names:", len(self.names), "len letters:", len(letters), "size:", self.size def getChar(self, elem): """Translates the inner representation of a tomonoid element (..., 2, 1, 0) to its outer representation ('0', ..., 'y', 'z', '1').""" if elem >= 0: return self.names[elem] elif elem == -1: return "?" else: return "!" def getPairName(self, pair): """Returns the name of the pair. E.g. if the pair is (0,4) then the string "(1,x)" is returned.""" return "(%s,%s)" % (self.getChar(pair[0]), self.getChar(pair[1])) def getNum(self, char): """Translates the outer representation of a tomonoid element ('0', ..., 'y', 'z', '1') to its inner representation (..., 2, 1, 0).""" return self.names.index(char) def exportToText(self): """Returns the sequence of the elements as a string that is suitable to be written to a text file.""" text = "" for i in range(self.size): if i > 0: text += ", " text += "%d: '%s'" % (i, self.getChar(i)) text += "\n" return text def show(self): """Shows the values of this instance of the class. This is mainly for the debugging purposes.""" print self.exportToText() class TomonoidReport: """This class contains all the generated tomonoids together with the information about their numbers, time spent on their generation, etc. """ def __init__(self, upToSize, method, archimedean, commutative): """Parameters: upToSize ... size up to which the tomonoids are generated method ... can be 'levelset', 'brute', or 'superbrute' ('levelset' is our new introduced method; 'brute' is a "more intelligent" brute force method based on generating all the one-element coextensions of a given tomonoid and testing whether they meet the axioms of a f.n. tomonoid; 'superbrute' is a "stupid" brute force method when all the possible multiplication tables of f.n. tomonoids of the given size are generated and then it is tested whether they meet the axioms of a f.n. tomonoid) archimedean ... True if the tomonoids have been generated as Archimedean commutative ... True if the tomonoids have been generated as commutative """ self.method = method # can be 'levelset', 'brute', or 'superbrute' self.upToSize = upToSize # size up to which the tomonoids are generated self.time = 0 # overall time to generate all the tomonoids self.tomonoids = [] # generated tomonoids; this list contains lists of tomonoids of sizes 1, 2, ..., upToSize self.times = [] # list of times spent on generation of tomonoids of given size self.numbers = [] # list of numbers of generated tomonoids of given size self.archimedean = archimedean # indicates whether the tomonoids have been generated as Archimedean self.commutative = commutative # indicates whether the tomonoids have been generated as commutative self.counterReachedValue = -1 def getMethodDescription(self): "Returns a description of the specified method." if self.method == "levelset": return "Level set based method" elif self.method == "brute": return "Brute force method" elif self.method == "superbrute": return "Super-brute force method" elif self.method == "unspecified": return "Unspecified method" else: return "Unknown method" def getTotalNumberOfTomonoids(self): """Returns the total number (in the whole tree) of the tomonoids that have been generated.""" result = 0 for num in self.numbers: result += num return result def printStartMessage(self): """This is just to give an echo to the console to indicate that the program has started to run.""" msg = "Generating finite, negative" if self.archimedean: msg += ", archimedean" if self.commutative: msg += ", commutative" msg += " tomonoids up to size %d by %s..." % ((self.upToSize), self.getMethodDescription()) print msg def getTextHead(self): """Returns the head of the text file to which the generated tomonoids are written.""" head = "" head += "=====================================================\n" head += " Finite, negative" if self.archimedean: head += ", archimedean" if self.commutative: head += ", commutative" head += " tomonoids\n" head += " method: %s\n" % self.getMethodDescription() head += " up to size: %s\n" % self.upToSize head += " total time: %s\n" % self.time head += " total number of tomonoids: %d\n" % self.getTotalNumberOfTomonoids() if self.counterReachedValue >= 0: head += " reached value of counter: %d\n" % self.counterReachedValue head += "=====================================================\n" for i in range(self.upToSize): head += "size: %d, time: %f sec, tomonoids: %d\n" % ((i+1), self.times[i], self.numbers[i]) head += "=====================================================\n" return head def writeToTextFile(self, fileName): """Writes the whole report (including all the generated tomonoids) to a text file; fileName specifies the name of the file without extension; extension '.txt' is added automatically.""" txtFileName = fileName + ".txt" out = open(txtFileName, "w") print "Writing file", txtFileName, "..." out.write(self.getTextHead()) # write the head of the file textFail = "" for i in range(self.upToSize): # write the info about all the generated tomonoids of the current size print "Writing tomonoids of size", (i+1) tomHead = "" tomHead += "-----------------------------------------------------\n" tomHead += " Finite, negative" if self.archimedean: tomHead += ", archimedean" if self.commutative: tomHead += ", commutative" tomHead += " tomonoids of size %d\n" % (i+1) tomHead += "-----------------------------------------------------\n" tomHead += " size: %d\n" % (i+1) tomHead += " number: %d\n" % self.numbers[i] tomHead += " time: %f\n" % self.times[i] tomHead += "-----------------------------------------------------\n\n" out.write(tomHead) failCounter = 0 # write the multiplication table of the generated tomonoids of the current size for t in self.tomonoids[i]: out.write(t.exportToText()) # write the coextensions of the tomonoid that is being written textExt = "CoExtensions (" + str(len(t.extensions)) + "):" for ext in t.extensions: textExt += " " + str(ext.serialNumber) textExt += "\n" out.write(textExt) # if for some pair of idempotents (here called "jumps") there # are no coextensions, it is written here if t.jumpsWithNoExtensions != []: textJumpsNoExt = "Jumps with no coextensions: " textJumpsNoExt += str(t.jumpsWithNoExtensions) textJumpsNoExt += " ..." for pair in t.jumpsWithNoExtensions: textJumpsNoExt += " " + t.elemNames.getPairName((pair[0],pair[1])) textJumpsNoExt += "\n" out.write(textJumpsNoExt) # perform a test whether the tomonoid that is being written to # the file meets the axioms of a f.n. tomonoid testReports = t.performAllTests() out.write(testReports.exportToText()) out.write("\n") # if this tomonoid does not meet the axioms, it is written here if not testReports.isSuccessfull(): failCounter += 1 textFail += "Algebraic tests failed on tomonoid %d (size %d).\n" % (t.serialNumber, t.size) # number of the tomonoids that does not meet the axioms textFail = "Algebraic tests on size %d failed in %d cases.\n" % ((i+1), failCounter) if failCounter > 0: print textFail, out.write(textFail) out.close() print "File", txtFileName, "written." def pickle(self, fileName): """This is to pickle the whole resulting data structure containing the generated tomonoids.""" pFileName = fileName + ".p" out = open(pFileName, "wb") print "Writing file", pFileName, "..." pickle.dump(self, out) out.close() print "File", pFileName, "written." def exportIdenticalTomonoidsInfoToText(self, identicalTomonoids): """Exports to the text file the info whether there are identical tomonoids generated. This should not happen, though.""" text = "" text += "Number of identical tomonoids: %d\n" % len(identicalTomonoids) for idTom in identicalTomonoids: s = idTom[0] i = idTom[1] j = idTom[2] text += "%d: %d ~ %d: %d (size: %d)" % (i, self.tomonoids[s][i].serialNumber, j, self.tomonoids[s][j].serialNumber, s+1) if self.tomonoids[s][i] == self.tomonoids[s][j]: text += " ... identical pointers" text += "\n" return text def show(self): """Shows the values of this instance of the class. This is mainly for the debugging purposes.""" print self.getTextHead() class AssociativityReport: """Represents the output of the associativity test of a given tomonoid.""" def __init__(self, successfull, x = '?', y = '?', z = '?'): """Parameters: successfull ... True if the tested tomonoid was associative x, y, z ... if the test was not successfull then store here for which values the associativity test has failed """ self.successfull = successfull self.x = x self.y = y self.z = z def __str__(self): """Return a string representation of this instance of the class.""" if self.successfull: return "successfull" else: return "failed on (%s*%s)*%s != %s*(%s*%s)" % (self.x, self.y, self.z, self.x, self.y, self.z) def exportToText(self): "Returns the report of the test as a string that is suitable to be written to a text file." return "Associativity test %s.\n" % str(self) def show(self): """Shows the values of this instance of the class. This is mainly for the debugging purposes.""" print self.exportToText(), class MonotonicityReport: """Represents the output of the monotonicity test of a given tomonoid.""" def __init__(self, successfull, x = '?', y = '?'): """Parameters: successfull ... True if the tested tomonoid was monotone x, y ... if the test was not successfull then store here for which values the monotonicity test has failed """ self.successfull = successfull self.x = x self.y = y def __str__(self): """Return a string representation of this instance of the class.""" if self.successfull: return "successfull" else: return "failed at (%s,%s)" % (self.x, self.y) def exportToText(self): "Returns the report of the test as a string that is suitable to be written to a text file." return "Monotonicity test %s.\n" % str(self) def show(self): """Shows the values of this instance of the class. This is mainly for the debugging purposes.""" print self.exportToText(), class CommutativityReport: """Represents the output of the commutativity test of a given tomonoid.""" def __init__(self, successfull, x = '?', y = '?'): """Parameters: successfull ... True if the tested tomonoid was commutative x, y ... if the test was not successfull then store here for which values the commutativity test has failed """ self.successfull = successfull self.x = x self.y = y def __str__(self): """Return a string representation of this instance of the class.""" if self.successfull: return "successfull" else: return "failed on %s*%s != %s*%s" % (self.x, self.y, self.y, self.x) def exportToText(self): "Returns the report of the test as a string that is suitable to be written to a text file." return "Commutativity test %s.\n" % str(self) def show(self): """Shows the values of this instance of the class. This is mainly for the debugging purposes.""" print self.exportToText(), class ArchimedeanicityReport: """Represents the output of the archimedeanicity test of a given tomonoid.""" def __init__(self, successfull, x = '?'): """Parameters: successfull ... True if the tested tomonoid was Archimedean x ... if the test was not successfull then store here for which value the Archimedeanicity test has failed """ self.successfull = successfull self.x = x def __str__(self): """Return a string representation of this instance of the class.""" if self.successfull: return "successfull" else: return "failed on %s*%s == %s" % (self.x, self.x, self.x) def exportToText(self): "Returns the report of the test as a string that is suitable to be written to a text file." return "Archimedeanicity test %s.\n" % str(self) def show(self): """Shows the values of this instance of the class. This is mainly for the debugging purposes.""" print self.exportToText(), class TestReport: """Represents the output of a test of algebraic properties of a finite, negative tomonoid. In this case, output of associativity, monotonicity, archimedeanicity, and commutativity test is stored. """ def __init__(self, tomonoid): """Parameters: tomonoid ... on which tomonoid the test have been performed """ self.tomonoid = tomonoid self.associativity = None self.monotonicity = None self.archimedeanicity = None self.commutativity = None def __str__(self): """Return a string representation of this instance of the class.""" if self.isSuccessfull(): return "successfull" else: return "failed" def isPerformed(self): "Returns True if all the tests have been performed." return self.associativity != None and self.monotonicity != None and self.archimedeanicity != None and self.commutativity != None def isSuccessfull(self): "Returns True if all the tests have been performed and successfull." if self.associativity and not self.associativity.successfull: return False if self.monotonicity and not self.monotonicity.successfull: return False if self.archimedeanicity and not self.archimedeanicity.successfull: return False if self.commutativity and not self.commutativity.successfull: return False return True def exportToText(self): "Returns the report of the test as a string that is suitable to be written to a text file." text = "Tests on tomonoid %d %s:\n" % (self.tomonoid.serialNumber, str(self)) if self.associativity: text += self.associativity.exportToText() else: text += "Associativity test not performed.\n" if self.monotonicity: text += self.monotonicity.exportToText() else: text += "Monotonicity test not performed.\n" if self.archimedeanicity: text += self.archimedeanicity.exportToText() else: text += "Archimedeanicity test not performed.\n" if self.commutativity: text += self.commutativity.exportToText() else: text += "Commutativity test not performed.\n" return text def show(self): """Shows the values of this instance of the class. This is mainly for the debugging purposes.""" print self.exportToText() class LevelEquivalence: """Finite, negative tomonoid represented by its level set equivalence. """ def __init__(self, size = 1): """Parameters: size ... size of the finite tomonoid """ # size of the finite tomonoid self.size = size # level set equivalence classes self.eqClasses = None # notation of the elements of the tomonoid self.elemNames = ElementNames(self.size) # setting the attributes 'zero', 'unit', 'atom', and 'coatom' self.setDesignatedValues() # define the level set equivalence self.createAsUndefined() def setDesignatedValues(self): """According to the value of self.size, stores the important values of the tomonoid to: self.zero ... the bottom element of the tomonoid self.unit ... the unit element of the tomonoid which is also the top element self.atom ... the highest element smaller than the top e self.coatom ... the lowest element higher than the bottom element """ if self.size < 1: raise Error, "Invalid size %d." % self.size elif self.size == 1: self.zero = self.unit = self.atom = self.coatom = 0 else: self.zero = self.size-1 self.unit = 0 self.atom = self.size-2 self.coatom = 1 def createEmptyEqClasses(self): """Create empty equivalence classes.""" self.eqClasses = self.size * [None] for i in range(self.size): self.eqClasses[i] = set([]) def createUnitPairs(self): """Create pairs with unit coordinate.""" self.eqClasses[self.unit].update(set([(self.unit,self.unit)])) for i in range(self.coatom, self.size, 1): self.eqClasses[i].update(set([(i,self.unit), (self.unit,i)])) def createZeroPairs(self): """Create pairs with zero coordinate.""" self.eqClasses[self.zero].update(set([(self.zero,self.zero)])) for i in range(self.coatom, self.zero, 1): self.eqClasses[self.zero].update(set([(i,self.zero), (self.zero,i)])) def createAsDrastic(self): """Creates the level equivalence of the drastic tomonoid.""" # create empty equivalence classes self.createEmptyEqClasses() # create pairs with unit coordinate self.createUnitPairs() # add all the other pairs - all to the zero class for i in range(self.coatom, self.size, 1): for j in range(self.coatom, self.size, 1): self.eqClasses[self.zero].add((i,j)) def createAsUndefined(self): """Creates the level equivalence of an undefined negative tomonoid.""" # create empty equivalence classes self.createEmptyEqClasses() # create pairs with unit coordinate self.createUnitPairs() # create pairs with zero coordinate self.createZeroPairs() # add all the other pairs - each pair to its own equivalence class for i in range(self.coatom, self.zero, 1): for j in range(self.coatom, self.zero, 1): self.eqClasses.append(set([(i,j)])) def createAsCopy(self, orig): """Makes this object to be a (deep) copy of 'orig'.""" self.size = orig.size self.eqClasses = copy.deepcopy(orig.eqClasses) self.elemNames = orig.elemNames self.zero = orig.zero self.unit = orig.unit self.atom = orig.atom self.coatom = orig.coatom def getCopy(self): "Returns a (deep) copy of the object." new = LevelEquivalence() new.createAsCopy(self) return new def createFromCharTable(self, charTable): """Defines the level equivalence according to the values given by the parameter 'charTable'. Parameter 'charTable' is a list of n lists of n characters taking values from '0', ..., 'x', 'y', 'z', '1' and it represents the multiplication table of a tomonoid. """ self.size = len(charTable) self.setDesignatedValues() self.elemNames = ElementNames(self.size) self.createEmptyEqClasses() for x in range(self.size): for y in range(self.size): value = self.elemNames.getNum(charTable[y][self.size - 1 - x]) self.eqClasses[value].add((x,y)) def extend(self): """Turns the level equivalence of is tomonoid into the (undefined) level equivalence of its extension. Further, size is increased by one and the designated constants and element names are all recomputed. """ formerSize = self.size self.size += 1 self.setDesignatedValues() self.elemNames.extend() numEqClasses = len(self.eqClasses) if numEqClasses > formerSize: # move the last class behind former zero to the end of the list self.eqClasses.append(self.eqClasses[self.zero]) # add (1,0), (0,1), and (0,0) to the zero class self.eqClasses[self.zero] = set([(self.unit, self.zero), (self.zero, self.unit), (self.zero, self.zero)]) else: # add (1,0), (0,1), and (0,0) to the zero class self.eqClasses.append(set([(self.unit, self.zero), (self.zero, self.unit), (self.zero, self.zero)])) # add pairs of type (x,0) and (0,x) to the zero class for i in range(self.coatom, self.zero, 1): self.eqClasses[self.zero].add((self.zero,i)) self.eqClasses[self.zero].add((i,self.zero)) # atom class (former zero class) is used to determine all the single # pair undefined equivalence classes if self.size > 2: for pair in self.eqClasses[self.atom]: if self.isNotOnBorder(pair): self.eqClasses.append(set([pair])) # setting the atom class to (1,at)~(at,1) self.eqClasses[self.atom] = set([(self.unit, self.atom), (self.atom, self.unit)]) def getEqClassAndIndex(self, pair): """Returns a pair (class, index) where 'class' denotes the level set equivalence class that contains pair=(a,b), otherwise it is False, and 'index' is the index (value) of this class; it is equal to self.undefined if its value is not within self.zero and self.unit.""" numEqClasses = len(self.eqClasses) for i in range(numEqClasses): if pair in self.eqClasses[i]: return (self.eqClasses[i], i) raise Error, "Level equivalence class not found!" def getIndex(self, pair): """Returns the index (value) of the class that contains pair=(a,b); it is equal to self.undefined if the value is not within self.zero and self.unit.""" cla, ind = self.getEqClassAndIndex(pair) return ind def isPositive(self, value): """Returns True if the value belongs to the elements of the tomonoid and it is not the zero of the tomonoid.""" return self.unit <= value < self.zero def isDefined(self, value): """Returns True if the value belongs to the elements of the tomonoid.""" return self.unit <= value <= self.zero def isUndefined(self, value): """Returns True if the value does not belong to the elements of the tomonoid.""" return not self.isDefined(value) def isAtomOrUndefined(self, value): """Returns True if the value is the atom of the tomonoid or if it does not belong to the elements of the tomonoid.""" return value == self.atom or self.isUndefined(value) def isHigherThanAtom(self, value): """Returns True if the value belongs to the elements of the tomonoid and it is not the zero nor the atom of the tomonoid.""" return self.isDefined(value) and value < self.atom def isZeroOrAtomOrUndefined(self, value): """Returns True if the value is the zero of the tomonoid or the atom of the tomonoid or if it does not belong to the elements of the tomonoid.""" return value == self.zero or value == self.atom or self.isUndefined(value) def isInSupport(self, pair): """Returns True if the functional value of the pair is greater than zero.""" return self.isPositive(self.getIndex(pair)) def isNotOnUnitAxis(self, pair): """Returns True if the pair does not lie on the axis given by the unit (top) element.""" return self.zero >= pair[0] > self.unit and self.zero >= pair[1] > self.unit def isNotOnZeroAxis(self, pair): """Returns True if the pair does not lie on the axis given by the zero (bottom) element.""" return self.zero > pair[0] >= self.unit and self.zero > pair[1] >= self.unit def isNotOnBorder(self, pair): """Returns True if the pair does lie neither on the axis given by the zero (bottom) element nor on the axis given by the unit (top) element.""" return self.zero > pair[0] > self.unit and self.zero > pair[1] > self.unit def isInUpperTriangle(self, pair): """Returns True if the pait lies on the upper triangle of the multiplication table of the tomonoid.""" return pair[0] > pair[1] def setValue(self, pair, value): """Adds 'pair' to the equivalence class with the given 'value'. Level equivalence relations are checked.""" cla, ind = self.getEqClassAndIndex(pair) if ind != value: if self.isDefined(ind): raise ErrorMultipleValues, ([ind, value], self) else: self.eqClasses[value].update(cla) self.eqClasses.remove(cla) def getValue(self, pair): """Returns the value of the pair, i.e., the index of the level equivalence class to which it belongs.""" cla, ind = self.getEqClassAndIndex(pair) if self.isUndefined(ind): raise Error, "Getting value of undefined pair!" return ind def relateClasses(self, ind1, ind2): """Merge two level equivalence classes (given by their indices) into one.""" if ind1 != ind2: if self.isDefined(ind2): if self.isDefined(ind1): raise ErrorMultipleValues, ([ind1, ind2], self) else: self.eqClasses[ind2].update(self.eqClasses[ind1]) self.eqClasses.remove(self.eqClasses[ind1]) else: self.eqClasses[ind1].update(self.eqClasses[ind2]) self.eqClasses.remove(self.eqClasses[ind2]) def relatePairs(self, pair1, pair2): # !!! neni resen pripad, kdy pair1 nebo pair2 neni v zadne tride """Makes pair1 and pair2 equivalent. If the pairs belong to eqClasses with different values, an ErrorMultipleValues is raised.""" if pair1 != pair2: ind1 = self.getIndex(pair1) ind2 = self.getIndex(pair2) self.relateClasses(ind1, ind2) def relateSetOfPairs(self, setOfPairs): """Makes all the pairs in the set equivalent.""" if len(setOfPairs) > 1: first = None for pair in setOfPairs: if first == None: first = pair else: self.relatePairs(first, pair) def relateColumn(self, x, yFrom, yTo): """Makes the pairs in a bounded column equivalent. This involves the pairs (x,yFrom), ..., (x,yTo).""" if yFrom == yTo: return elif yFrom < yTo: rang = range(yFrom, yTo+1, 1) elif yFrom > yTo: rang = range(yTo, yFrom+1, 1) first = None for y in rang: if first == None: first = (x,y) else: self.relatePairs(first, (x,y)) def relateRow(self, xFrom, xTo, y): """Makes the pairs in a bounded row equivalent. This involves the pairs (xFrom,y), ..., (xTo,y).""" if xFrom == xTo: return elif xFrom < xTo: ran = range(xFrom, xTo+1, 1) elif xFrom > xTo: ran = range(xTo, xFrom+1, 1) first = None for x in ran: if first == None: first = (x,y) else: self.relatePairs(first, (x,y)) def setPairToZero(self, pair): """Sets the value of 'pair' to self.zero (including all the other pairs in the same level equivalence class) and takes monotonicity into account, i.e., all the pairs that are closer to (self.zero, self.zero) are set to self.zero, as well, by the same procedure. If detected that a level equivalence class has multiple values then ErrorMultipleValues is raised. """ if self.isNotOnBorder(pair): for i in range(pair[0], self.zero, 1): for j in range(pair[1], self.zero, 1): self.setEqClassToZero(self.getIndex((i,j))) def setEqClassToZero(self, ind): """Merge the level equivalence class given by its index (parameter ind) with the zero level equivalence class. Monotonicity is taken into account, i.e., all the pairs that are closer to (self.zero, self.zero) are set to self.zero, as well.""" if self.isUndefined(ind): cla = self.eqClasses[ind] self.eqClasses[self.zero].update(cla) self.eqClasses.remove(cla) for pair in cla: self.setPairToZero((pair[0]+1,pair[1])) self.setPairToZero((pair[0],pair[1]+1)) elif self.isPositive(ind): raise ErrorMultipleValues, ([self.zero, ind], self) def setPairToAtom(self, pair): """Sets the value of 'pair' to self.atom (including all the other pairs in the same level equivalence class) and takes monotonicity into account, i.e., all the pairs that are closer to (self.unit, self.unit) are set to self.atom, as well, by the same procedure. If detected that a level equivalence class has multiple values (typically when attempting to set a pair to self.atom while this pair has been already set to self.zero) then ErrorMultipleValues is raised. """ if self.isNotOnBorder(pair): for i in range(pair[0], self.unit, -1): for j in range(pair[1], self.unit, -1): self.setEqClassToAtom(self.getIndex((i,j))) def setEqClassToAtom(self, ind): """Merge the level equivalence class given by its index (parameter ind) with the atom level equivalence class. Monotonicity is taken into account, i.e., all the pairs that are closer to (self.unit, self.unit) (and are undefined but not zero) are set to self.atom, as well.""" if self.isUndefined(ind): cla = self.eqClasses[ind] self.eqClasses[self.atom].update(cla) self.eqClasses.remove(cla) for pair in cla: self.setPairToAtom((pair[0]-1,pair[1])) self.setPairToAtom((pair[0],pair[1]-1)) elif ind == self.zero: raise ErrorMultipleValues, ([self.zero, self.atom], self) def getTable(self): """Returns the multiplication table of the tomonoid; the table is computed from the level equivalence.""" table = [] for i in range(self.size): table.append(self.size * [-1]) numEqClasses = len(self.eqClasses) for ind in range(numEqClasses): for pair in self.eqClasses[ind]: table[pair[0]][pair[1]] = ind return table def performAssociativityTest(self): """Performs a test to find out whether the tomonoid is associative or not. If it is associative then True is returned; otherwise False is returned. The result of the test, including the triplet indicating the failure, is written to 'associativityReport'.""" table = self.getTable() for x in range(self.size): for y in range(self.size): for z in range(self.size): xy = table[x][y] yz = table[y][z] if table[xy][z] != table[x][yz]: return AssociativityReport(False, self.elemNames.getChar(x), self.elemNames.getChar(y), self.elemNames.getChar(z)) return AssociativityReport(True) def performMonotonicityTest(self): """Performs a test to find out whether the tomonoid is monotone or not. If it is monotone then True is returned; otherwise False is returned. The result of the test, including the triplet indicating the failure, is written to 'monotonicityReport'.""" table = self.getTable() for x in range(0, self.size-1, 1): for y in range(0, self.size-1, 1): if table[x+1][y] < table[x][y] or table[x][y+1] < table[x][y]: return MonotonicityReport(False, self.elemNames.getChar(x), self.elemNames.getChar(y)) return MonotonicityReport(True) def performArchimedeanicityTest(self): """Performs a test to find out whether the tomonoid is Archimedean or not. If it is Archimedean then True is returned; otherwise False is returned. The result of the test, including the triplet indicating the failure, is written to 'archimedeanicityReport'.""" table = self.getTable() for x in range(1, self.size-1, 1): if table[x][x] <= x: return ArchimedeanicityReport(False, self.elemNames.getChar(x)) return ArchimedeanicityReport(True) def performCommutativityTest(self): """Performs a test to find out whether the tomonoid is commutative or not. If it is commutative then True is returned; otherwise False is returned. The result of the test, including the triplet indicating the failure, is written to 'commutativityReport'.""" table = self.getTable() for x in range(self.size): for y in range(self.size): if table[x][y] != table[y][x]: return CommutativityReport(False, self.elemNames.getChar(x), self.elemNames.getChar(y)) return CommutativityReport(True) def performAllTests(self): """Performs tests to find out whether the tomonoid is associative, monotone, commutative, and Archimedean. Returns an instance of the class TestReport.""" testReport = TestReport(self) testReport.associativity = self.performAssociativityTest() testReport.monotonicity = self.performMonotonicityTest() testReport.archimedeanicity = self.performArchimedeanicityTest() testReport.commutativity = self.performCommutativityTest() return testReport def isAssociative(self): """Performs a test to find out whether the tomonoid is associative. If it is so, returns True, otherwise False.""" associativityReport = self.performAssociativityTest() return associativityReport.successfull def isMonotone(self): """Performs a test to find out whether the tomonoid is monotone. If it is so, returns True, otherwise False.""" monotonicityReport = self.performMonotonicityTest() return monotonicityReport.successfull def isArchimedean(self): """Performs a test to find out whether the tomonoid is Archimedean. If it is so, returns True, otherwise False.""" archimedeanicityReport = self.performArchimedeanicityTest() return archimedeanicityReport.successfull def isCommutative(self): """Performs a test to find out whether the tomonoid is commutative. If it is so, returns True, otherwise False.""" commutativityReport = self.performCommutativityTest() return commutativityReport.successfull def getName(self, value): """Translates an inner value (integer from self.size-1 down to 0) to its outer representation (character from '0', ..., 'y', 'z', '1').""" if self.isDefined(value): return self.elemNames.getChar(value) else: return str(value) def exportDesignatedValuesToText(self): """Returns an information about the values of the constants 'zero', 'unit', 'atom', and 'coatom' as a string. This is for debugging purposes.""" text = "Designated values: " text += "size: " + str(self.size) + " " text += "ze: " + str(self.zero) + " " text += "at: " + str(self.atom) + " " text += "co: " + str(self.coatom) + " " text += "un: " + str(self.unit) + "\n" return text def exportDualitiesToText(self): """Returns a string reporting dualities in level equivalence classes (which should not happen). The string is suitable be written to the resulting text file. """ l = len(self.eqClasses) cnt = 0 text = "" for i in range(l): for pairI in self.eqClasses[i]: for j in range(i+1, l, 1): for pairJ in self.eqClasses[j]: if pairI == pairJ and i != j: text += "%s in both %d and %d\n" % (self.elemNames.getPairName(pairI), i, j) cnt += 1 text += "... %d dualities\n" % cnt return text def exportClassesToText(self): """Returns a string representation of the level equivalence classes.""" text = "" numClasses = len(self.eqClasses) for i in range(numClasses): text += "%d('%s'): [ " % (i, self.getName(i)) for pair in self.eqClasses[i]: text += self.elemNames.getPairName(pair) + " " text += "]\n" return text def exportTableToText(self): """Returns a string describing the multiplication table of the tomonoid. The string is suitable be written to the resulting text file. """ table = self.getTable() text = "" for x in range(self.size-1,-1,-1): if x <= 9: text += " " text += str(x) + " " text += "\n" for x in range(self.size-1,-1,-1): text += " " + self.getName(x) + " " text += "\n" for x in range(self.size-1,-1,-1): text += " - " text += "\n" for y in range(self.size): if y > 0: text += "\n" for x in range(self.size-1,-1,-1): ind = table[x][y] #try: # ind = self.getIndex((x,y)) #except Error: # ind = -2 if ind <= self.zero or ind <= 9: text += " " text += self.getName(ind) + " " text += "| " + self.getName(y) + " " if y <= 9: text += " " text += str(y) text += "\n" return text def getNumElems(self): """Returns the number of pairs in all the equivalence classes.""" result = 0 for cla in self.eqClasses: result += len(cla) return result def exportHeadToText(self): """Returns a string with the head of this level equivalence class. The string is suitable be written to the resulting text file. """ return "Level equivalence of a tomonoid\n" def exportToText(self): """Returns a string representation of the tomonoid.""" text = "" text += self.exportHeadToText() text += self.exportTableToText() text += "Level equivalence classes (pairs: %d):\n" % self.getNumElems() text += self.exportClassesToText() text += "Dualities in level equivalence classes:\n" text += self.exportDualitiesToText() text += "Tracebacks: " + str(self.numTracebacks) + "\n" return text def show(self): """Shows the values of this instance of the class. This is mainly for the debugging purposes.""" print self.exportToText() def showShort(self): """Shows the values of this instance of the class in a short format. This is mainly for the debugging purposes.""" print self.exportHeadToText() print self.exportTableToText() report = self.performAllTests() report.show() class TomonoidFN(LevelEquivalence): """This class represents a finite, negative tomonoid by its level set equivalence. """ def __init__(self, serialNumber, size = 1): """Parameters: serialNumber ... unique number assigned to this tomonoid (obtaind from an instance of the class Counter) size ... size of the tomonoid """ LevelEquivalence.__init__(self, size) self.serialNumber = serialNumber self.extensions = [] self.idempotents = [ self.unit ] # non-zero idempotents self.parent = None self.orig = None self.numTracebacks = [0, 0, 0, 0, 0] self.jumpsWithNoExtensions = [] def createAsCopy(self, orig): """Makes this tomonoid to be a copy of the tomonoid given by the parameter "orig".""" LevelEquivalence.createAsCopy(self, orig) self.extensions = [] self.idempotents = copy.deepcopy(orig.idempotents) self.parent = orig.parent self.orig = orig def getCopy(self, serialNumber): "Returns a (deep) copy of the object." new = TomonoidFN(serialNumber) new.createAsCopy(self) return new def createAsExtension(self, parent): """Makes this tomonoid to be an one-element coextension of the tomonoid given by the parameter "parent".""" self.createAsCopy(parent) self.elemNames = ElementNames(self.size) self.extend() self.parent = parent self.orig = None def getExtension(self, serialNumber): """Returns an one-element coextension of this tomonoid.""" new = TomonoidFN(serialNumber) new.createAsExtension(self) return new def createFromCharTable(self, charTable): """Defines the level equivalence according to the values given by the parameter 'charTable'. Parameter 'charTable' is a list of n lists of n characters taking values from '0', ..., 'x', 'y', 'z', '1' and it represents the multiplication table of a tomonoid. """ LevelEquivalence.createFromCharTable(self, charTable) self.computeIdempotents() def computeIdempotents(self): """Find all the idempotents of this tomonoid and stores them to self.idempotents. Does not return anything. """ self.idempotents = [ self.unit ] for i in range(self.coatom, self.zero, 1): if self.getIndex((i,i)) == i: self.idempotents.append(i) def computeExtensionsBrute(self, counter): """Computes all the one-element coextensions of this tomonoid by the brute force method. The computed coextensions are stored to self.extensions. Parameters: counter ... instance of the class Counter """ ext = self.getExtension(counter.getNew()) self.extensions = ext.goThroughAllEvaluationsBrute(counter) def goThroughAllEvaluationsBrute(self, counter): """This method is called by the method self.computeExtensionsBrute(counter). It recursively generates all the potential one-element coextensions of this tomonoid and tests whether they meet the axioms of a finite, negative tomonoid. All the coextensions that meet the axioms are then returned as a list. Parameters: counter ... instance of the class Counter """ if len(self.eqClasses) > self.size: extZero = self extAtom = self.getCopy(counter.getNew()) extZeroValid = True extAtomValid = True try: extZero.setEqClassToZero(self.size) except ErrorMultipleValues, e: extZeroValid = False try: extAtom.setEqClassToAtom(self.size) except ErrorMultipleValues, e: extAtomValid = False if extZeroValid: extensionsZero = extZero.goThroughAllEvaluationsBrute(counter) else: extensionsZero = [] if extAtomValid: extensionsAtom = extAtom.goThroughAllEvaluationsBrute(counter) else: extensionsAtom = [] extensionsZero.extend(extensionsAtom) return extensionsZero else: report = self.performAllTests() if report.isSuccessfull(): return [self] else: return [] def computeExtensions(self, counter): """Computes all the one-element coextensions of this tomonoid by the introduced level set based method. The computed extensions are stored to self.extensions. Parameters: counter ... instance of the class Counter """ self.numTracebacks = [0, 0, 0, 0, 0] if self.size == 1: ext = self.getExtension(counter.getNew()) self.extensions = [ ext ] return else: self.extensions = [] ext = self.getExtension(counter.getNew()) ext.computeE2() # (E2) #ext.computeIdempotents() numIdempotents = len(ext.idempotents) idpIndices = range(numIdempotents) bndX = numIdempotents * [0] bndY = numIdempotents * [0] for i in idpIndices: jumpX = ext.idempotents[i] jumpY = ext.idempotents[i] bndX[i] = ext.getJumpBndX(jumpY) bndY[i] = ext.getJumpBndY(jumpX) for ix in idpIndices: for iy in idpIndices: jumpX = ext.idempotents[ix] jumpY = ext.idempotents[iy] if ext.isUsablePairOfIdempotents(jumpX, jumpY, bndX[iy], bndY[ix]): tom = ext.getCopy(counter.getNew()) tom.jumpX = jumpX tom.jumpY = jumpY tom.computeE3b() # (E3')-b tracingBack = False if not tracingBack: try: tom.computeE4() # (E4') except ErrorMultipleValues, e: self.numTracebacks[0] += 1 tracingBack = True if not tracingBack: try: tom.computeE3a() # (E3')-a except ErrorMultipleValues, e: self.numTracebacks[1] += 1 tracingBack = True if not tracingBack: try: extensions = tom.goThroughAllEvaluations(counter) self.extensions.extend(extensions) except ErrorMultipleValues, e: self.numTracebacks[2] += 1 tracingBack = True ext.setPairToAtom((ext.atom, ext.atom)) ext.idempotents.append(ext.atom) self.extensions.append(ext) def goThroughAllEvaluations(self, counter): """This method is called by the method self.computeExtensions(counter). Performing our introduced algorithm (described in the paper that is referenced at the beginning of this source file) all the valid one-element coextensions are recursively generated and returned as a list. Parameters: counter ... instance of the class Counter """ if len(self.eqClasses) > self.size: extZero = self extAtom = self.getCopy(counter.getNew()) try: extZero.setEqClassToZero(self.size) extensionsZero = extZero.goThroughAllEvaluations(counter) except ErrorMultipleValues, e: self.numTracebacks[3] += 1 extensionsZero = [] try: extAtom.setEqClassToAtom(self.size) extensionsAtom = extAtom.goThroughAllEvaluations(counter) except ErrorMultipleValues, e: self.numTracebacks[4] += 1 extensionsAtom = [] extensionsZero.extend(extensionsAtom) return extensionsZero else: return [self] def computeE2(self): """Property (E2). Relates (a,e)~(d,c) in Reidemeister figures where (a,b) and (b,c) are in the support (set P), i.e., values of (a,b) and (b,c) are strictly higher than the atom.""" # for all the pairs that are evaluated strictly higher than the atom: for ind in range(self.coatom, self.atom, 1): for pair in self.eqClasses[ind]: # discard the pairs that have unit coordinate if self.isNotOnBorder(pair): a = pair[0] b = pair[1] d = self.getIndex((a,b)) # find c such that (b,c) is evaluated strictly higher than # the atom and relate (a,e)~(d,c) for c in range(self.coatom, self.atom, 1): e = self.getIndex((b,c)) if self.isZeroOrAtomOrUndefined(e): break self.relatePairs((d,c), (a,e)) def computeE3a(self): """Part (a) of Property (E3'). According to the chosen idempotent jumps, sets the corresponding pairs to zero.""" for a in range(self.coatom, self.atom, 1): c = self.jumpY + 1 for b in range(self.coatom, self.atom, 1): ind = self.getIndex((a,b)) if self.isZeroOrAtomOrUndefined(ind): e = self.getIndex((b,c)) if self.isDefined(e): self.setPairToZero((a,e)) break c = self.jumpX + 1 for b in range(self.coatom, self.atom, 1): ind = self.getIndex((b,a)) if self.isZeroOrAtomOrUndefined(ind): e = self.getIndex((c,b)) if self.isDefined(e): self.setPairToZero((e,a)) break def computeE3b(self): """Part (b) of Property (E3'). According to the chosen idempotent jumps, relates pairs (a,b)~(a,e) and (b,a)~(e,a) in the complement of the support (set P).""" if self.jumpY > self.unit: c = self.jumpY finish = False for b in range(self.coatom, self.atom, 1): e = self.getIndex((b,c)) if b < e: if self.isUndefined(e): e = self.atom finish = True for a in range(self.atom-1, self.unit, -1): d = self.getIndex((a,b)) if self.isHigherThanAtom(d): break self.relateColumn(a, b, e) if finish: break if self.jumpX > self.unit: c = self.jumpX finish = False for b in range(self.coatom, self.atom, 1): e = self.getIndex((c,b)) if b < e: if self.isUndefined(e): e = self.atom finish = True for a in range(self.atom-1, self.unit, -1): d = self.getIndex((b,a)) if self.isHigherThanAtom(d): break self.relateRow(b, e, a) if finish: break def computeE4(self): """Property (E4'). Sets the corresponding pairs to zero or atom regarding the chosen idempotent jumps.""" self.setPairToZero((self.jumpX+1, self.atom)) self.setPairToZero((self.atom, self.jumpY+1)) if self.jumpX != self.unit: self.setPairToAtom((self.jumpX, self.atom)) if self.jumpY != self.unit: self.setPairToAtom((self.atom, self.jumpY)) def getJumpBndX(self, jumpY): """Returns the highest value "bndX" such that the pair (bndX, jumpY) belongs to the atom level equivalence class or to no level equivalence class.""" bndX = self.atom for i in range(self.coatom, self.zero, 1): value = self.getIndex((i, jumpY)) if self.isAtomOrUndefined(value): bndX = i break return bndX def getJumpBndY(self, jumpX): """Returns the highest value "bndY" such that the pair (jumpX, bndY) belongs to the atom level equivalence class or to no level equivalence class.""" bndY = self.atom for i in range(self.coatom, self.zero, 1): value = self.getIndex((jumpX, i)) if self.isAtomOrUndefined(value): bndY = i break return bndY def isUsablePairOfIdempotents(self, jumpX, jumpY, bndX, bndY): """Test whether the chosen pair of idempotent jumps meets the necessary requirements. It is, actually, not necessary to use this test, however, it speeds the algorithm up (there is a lower number of tracebacks). """ value = self.getIndex((jumpX+1, bndX)) #if self.isAtomOrHigher(value): if self.isPositive(value): return False value = self.getIndex((bndY, jumpY+1)) #if self.isAtomOrHigher(value): if self.isPositive(value): return False return True def performAllTests(self): """Performs tests to find out whether the tomonoid is associative and monotone. Returns an instance of the class TestReport.""" testReport = TestReport(self) testReport.associativity = self.performAssociativityTest() testReport.monotonicity = self.performMonotonicityTest() return testReport def exportIdempotentsToText(self): """Returns a string describing the idempotents of this tomonoid. The string is suitable be written to the resulting text file. """ text = "Idempotents:" for i in self.idempotents: text += " " + self.elemNames.getChar(i) text += "\n" return text def exportDescriptionToText(self): """Returns a describing of this tomonoid. The string is suitable be written to the resulting text file. """ return "Finite, negative tomonoid" def exportHeadToText(self): """Returns a string with the head describing of this tomonoid. The string is suitable be written to the resulting text file. """ if self.parent: strParent = str(self.parent.serialNumber) else: strParent = "None" if self.orig: strOrig = str(self.orig.serialNumber) else: strOrig = "None" return self.exportDescriptionToText() + " no. %d (size: %d, parent: %s, orig: %s)\n" % (self.serialNumber, self.size, strParent, strOrig) class TomonoidFNA(TomonoidFN): """This class represents an Archimedean, finite, negative tomonoid by its level set equivalence. """ def getCopy(self, serialNumber): "Returns a (deep) copy of the object." new = TomonoidFNA(serialNumber) new.createAsCopy(self) return new def getExtension(self, serialNumber): """Returns an one-element coextension of this tomonoid.""" new = TomonoidFNA(serialNumber) new.createAsExtension(self) return new def extend(self): """Turns the level equivalence of is tomonoid into the (undefined) level equivalence of its extension. Further, size is increased by one and the designated constants and element names are all recomputed. """ formerSize = self.size self.size += 1 self.setDesignatedValues() self.elemNames.extend() numEqClasses = len(self.eqClasses) if numEqClasses > formerSize: # move the last class behind former zero to the end of the list self.eqClasses.append(self.eqClasses[self.zero]) # add (1,0), (0,1), and (0,0) to the zero class self.eqClasses[self.zero] = set([(self.unit, self.zero), (self.zero, self.unit), (self.zero, self.zero)]) else: # add (1,0), (0,1), and (0,0) to the zero class self.eqClasses.append(set([(self.unit, self.zero), (self.zero, self.unit), (self.zero, self.zero)])) # add pairs of type (x,0) and (0,x) to the zero class for i in range(self.coatom, self.zero, 1): self.eqClasses[self.zero].add((self.zero,i)) self.eqClasses[self.zero].add((i,self.zero)) if i != self.atom: self.eqClasses[self.atom].remove((self.atom,i)) self.eqClasses[self.zero].add((self.atom,i)) self.eqClasses[self.atom].remove((i,self.atom)) self.eqClasses[self.zero].add((i,self.atom)) # atom class (former zero class) is used to determine all the single # pair undefined equivalence classes if self.size > 2: for pair in self.eqClasses[self.atom]: if self.atom > pair[0] > self.unit and self.atom > pair[1] > self.unit: self.eqClasses.append(set([pair])) # moving (at,at) to the zero class self.eqClasses[self.atom].remove((self.atom,self.atom)) self.eqClasses[self.zero].add((self.atom,self.atom)) # setting the atom class to (1,at)~(at,1) self.eqClasses[self.atom] = set([(self.unit, self.atom), (self.atom, self.unit)]) def computeExtensions(self, counter): """Computes all the one-element coextensions of this tomonoid by the introduced level set based method. The computed extensions are stored to self.extensions. Parameters: counter ... instance of the class Counter """ if self.size <= 2: ext = self.getExtension(counter.getNew()) self.extensions = [ ext ] return else: ext = self.getExtension(counter.getNew()) ext.computeE2() ext.computeE3() self.extensions = ext.goThroughAllEvaluations(counter) # !!! def computeE3(self): """Property (E3).""" for a in range(self.coatom, self.atom, 1): for b in range(self.coatom, self.atom, 1): d = self.getIndex((a,b)) if self.isZeroOrAtomOrUndefined(d): c = self.coatom e = self.getIndex((b,c)) if self.isHigherThanAtom(e): self.setPairToZero((a,e)) break for b in range(self.coatom, self.atom, 1): d = self.getIndex((b,a)) if self.isZeroOrAtomOrUndefined(d): c = self.coatom e = self.getIndex((c,b)) if self.isHigherThanAtom(e): self.setPairToZero((e,a)) break def performAllTests(self): """Performs tests to find out whether the tomonoid is associative, monotone, and Archimedean. Returns an instance of the class TestReport.""" testReport = TestReport(self) testReport.associativity = self.performAssociativityTest() testReport.monotonicity = self.performMonotonicityTest() testReport.archimedeanicity = self.performArchimedeanicityTest() return testReport def exportDescriptionToText(self): """Returns a describing of this tomonoid. The string is suitable be written to the resulting text file. """ return "Finite, negative, Archimedean tomonoid" class TomonoidFNC(TomonoidFN): """This class represents a commutative, finite, negative tomonoid by its level set equivalence. """ def getCopy(self, serialNumber): "Returns a (deep) copy of the object." new = TomonoidFNC(serialNumber) new.createAsCopy(self) return new def getExtension(self, serialNumber): """Returns an one-element coextension of this tomonoid.""" new = TomonoidFNC(serialNumber) new.createAsExtension(self) return new def extend(self): """Turns the level equivalence of is tomonoid into the (undefined) level equivalence of its extension. Further, size is increased by one and the designated constants and element names are all recomputed. """ formerSize = self.size self.size += 1 self.setDesignatedValues() self.elemNames.extend() numEqClasses = len(self.eqClasses) if numEqClasses > formerSize: # move the last class behind former zero to the end of the list self.eqClasses.append(self.eqClasses[self.zero]) # add (1,0), (0,1), and (0,0) to the zero class self.eqClasses[self.zero] = set([(self.unit, self.zero), (self.zero, self.unit), (self.zero, self.zero)]) else: # add (1,0), (0,1), and (0,0) to the zero class self.eqClasses.append(set([(self.unit, self.zero), (self.zero, self.unit), (self.zero, self.zero)])) # add pairs of type (x,0) and (0,x) to the zero class for i in range(self.coatom, self.zero, 1): self.eqClasses[self.zero].add((self.zero,i)) self.eqClasses[self.zero].add((i,self.zero)) # atom class (former zero class) is used to determine all the single # pair undefined equivalence classes if self.size > 2: for pair in self.eqClasses[self.atom]: if self.isNotOnBorder(pair) and self.isInUpperTriangle(pair): self.eqClasses.append(set([pair, (pair[1], pair[0])])) if pair[0] == pair[1]: self.eqClasses.append(set([pair])) # setting the atom class to (1,at)~(at,1) self.eqClasses[self.atom] = set([(self.unit, self.atom), (self.atom, self.unit)]) def computeExtensions(self, counter): """Computes all the one-element coextensions of this tomonoid by the introduced level set based method. The computed extensions are stored to self.extensions. Parameters: counter ... instance of the class Counter """ self.numTracebacks = [0, 0, 0, 0, 0] if self.size == 1: ext = self.getExtension(counter.getNew()) self.extensions = [ ext ] return else: self.extensions = [] ext = self.getExtension(counter.getNew()) ext.computeE2() # (E2) for i in range(len(ext.idempotents)): jump = ext.idempotents[i] bnd = ext.getJumpBndX(jump) someExtensionsAdded = False constraintPassed = False if ext.isUsablePairOfIdempotents(jump, jump, bnd, bnd): constraintPassed = True tom = ext.getCopy(counter.getNew()) tom.jumpX = jump tom.jumpY = jump tom.computeE3b() # (E3')-b tracingBack = False if not tracingBack: try: tom.computeE4() # (E4') except ErrorMultipleValues, e: self.numTracebacks[0] += 1 tracingBack = True if not tracingBack: try: tom.computeE3a() # (E3')-a except ErrorMultipleValues, e: self.numTracebacks[1] += 1 tracingBack = True if not tracingBack: try: extensions = tom.goThroughAllEvaluations(counter) if extensions != []: someExtensionsAdded = True self.extensions.extend(extensions) except ErrorMultipleValues, e: self.numTracebacks[2] += 1 tracingBack = True if not someExtensionsAdded: self.jumpsWithNoExtensions.append((jump, jump, constraintPassed)) ext.setPairToAtom((ext.atom, ext.atom)) ext.idempotents.append(ext.atom) self.extensions.append(ext) def computeE3a(self): """Part (a) of Property (E3'). According to the chosen idempotent jumps, sets the corresponding pairs to zero.""" for a in range(self.coatom, self.atom, 1): c = self.jumpY + 1 for b in range(self.coatom, self.atom, 1): ind = self.getIndex((a,b)) if self.isZeroOrAtomOrUndefined(ind): e = self.getIndex((b,c)) if self.isDefined(e): self.setPairToZero((a,e)) break def computeE3b(self): """Part (b) of Property (E3'). According to the chosen idempotent jumps, relates pairs (a,b)~(a,e) and (b,a)~(e,a) in the complement of the support (set P).""" if self.jumpY > self.unit: c = self.jumpY finish = False for b in range(self.coatom, self.atom, 1): e = self.getIndex((b,c)) if b < e: if self.isUndefined(e): e = self.atom finish = True for a in range(self.atom-1, self.unit, -1): d = self.getIndex((a,b)) if self.isHigherThanAtom(d): break self.relateColumn(a, b, e) #self.relateRow(b, e, a) if finish: break def computeE4(self): """Property (E4'). Sets the corresponding pairs to zero or atom regarding the chosen idempotent jumps.""" self.setPairToZero((self.jumpX+1, self.atom)) if self.jumpX != self.unit: self.setPairToAtom((self.jumpX, self.atom)) def isUsablePairOfIdempotents(self, jumpX, jumpY, bndX, bndY): """Test whether the chosen pair of idempotent jumps meets the necessary requirements. It is, actually, not necessary to use this test, however, it speeds the algorithm up (there is a lower number of tracebacks).""" value = self.getIndex((jumpX+1, bndX)) #if self.isAtomOrHigher(value): if self.isPositive(value): return False return True def performAllTests(self): """Performs tests to find out whether the tomonoid is associative, monotone, and commutative. Returns an instance of the class TestReport.""" testReport = TestReport(self) testReport.associativity = self.performAssociativityTest() testReport.monotonicity = self.performMonotonicityTest() testReport.commutativity = self.performCommutativityTest() return testReport def exportDescriptionToText(self): """Returns a describing of this tomonoid. The string is suitable be written to the resulting text file. """ return "Finite, negative, commutative tomonoid" class TomonoidFNAC(TomonoidFNA): """This class represents an Archimedean, commutative, finite, negative tomonoid by its level set equivalence. """ def getCopy(self, serialNumber): "Returns a (deep) copy of the object." new = TomonoidFNAC(serialNumber) new.createAsCopy(self) return new def getExtension(self, serialNumber): """Returns an one-element coextension of this tomonoid.""" new = TomonoidFNAC(serialNumber) new.createAsExtension(self) return new def extend(self): """Turns the level equivalence of is tomonoid into the (undefined) level equivalence of its extension. Further, size is increased by one and the designated constants and element names are all recomputed. """ formerSize = self.size self.size += 1 self.setDesignatedValues() self.elemNames.extend() numEqClasses = len(self.eqClasses) if numEqClasses > formerSize: # move the last class behind former zero to the end of the list self.eqClasses.append(self.eqClasses[self.zero]) # add (1,0), (0,1), and (0,0) to the zero class self.eqClasses[self.zero] = set([(self.unit, self.zero), (self.zero, self.unit), (self.zero, self.zero)]) else: # add (1,0), (0,1), and (0,0) to the zero class self.eqClasses.append(set([(self.unit, self.zero), (self.zero, self.unit), (self.zero, self.zero)])) # add pairs of type (x,0) and (0,x) to the zero class for i in range(self.coatom, self.zero, 1): self.eqClasses[self.zero].add((self.zero,i)) self.eqClasses[self.zero].add((i,self.zero)) if i != self.atom: self.eqClasses[self.atom].remove((self.atom,i)) self.eqClasses[self.zero].add((self.atom,i)) self.eqClasses[self.atom].remove((i,self.atom)) self.eqClasses[self.zero].add((i,self.atom)) # atom class (former zero class) is used to determine all the single # pair undefined equivalence classes if self.size > 2: for pair in self.eqClasses[self.atom]: if self.atom > pair[0] > self.unit and self.atom > pair[1] > self.unit: if self.isInUpperTriangle(pair): self.eqClasses.append(set([pair, (pair[1], pair[0])])) if pair[0] == pair[1]: self.eqClasses.append(set([pair])) # moving (at,at) to the zero class self.eqClasses[self.atom].remove((self.atom,self.atom)) self.eqClasses[self.zero].add((self.atom,self.atom)) # setting the atom class to (1,at)~(at,1) self.eqClasses[self.atom] = set([(self.unit, self.atom), (self.atom, self.unit)]) def computeExtensions(self, counter): """Computes all the one-element coextensions of this tomonoid by the introduced level set based method. The computed extensions are stored to self.extensions. Parameters: counter ... instance of the class Counter """ if self.size <= 2: ext = self.getExtension(counter.getNew()) self.extensions = [ ext ] return else: ext = self.getExtension(counter.getNew()) ext.computeE2() ext.computeE3() self.extensions = ext.goThroughAllEvaluations(counter) # !!! def computeE3(self): """Property (E3).""" for a in range(self.coatom, self.atom, 1): for b in range(self.coatom, self.atom, 1): d = self.getIndex((a,b)) if self.isZeroOrAtomOrUndefined(d): c = self.coatom e = self.getIndex((b,c)) if self.isHigherThanAtom(e): self.setPairToZero((a,e)) break def performAllTests(self): """Performs tests to find out whether the tomonoid is associative, monotone, commutative, and Archimedean. Returns an instance of the class TestReport.""" testReport = TestReport(self) testReport.associativity = self.performAssociativityTest() testReport.monotonicity = self.performMonotonicityTest() testReport.archimedeanicity = self.performArchimedeanicityTest() testReport.commutativity = self.performCommutativityTest() return testReport def exportDescriptionToText(self): """Returns a describing of this tomonoid. The string is suitable be written to the resulting text file. """ return "Finite, negative, Archimedean, commutative tomonoid" # ----------------------------------------------------------------------------- # # End of classes # # ----------------------------------------------------------------------------- def getNewTomonoid(archimedean, commutative, serialNumber, size = 1): """Creates a new tomonoid (an instance of one of the classes TomonoidFNAC, TomonoidFNA, TomonoidFNC, TomonoidFN). Parameters: archimedean ... set to True if the tomonoid is supposed to be Archimedean commutative ... set to True if the tomonoid is supposed to be commutative serialNumber ... unique number assigned to this tomonoid size ... size of the tomonoid """ if(archimedean): if(commutative): return TomonoidFNAC(serialNumber, size) else: return TomonoidFNA(serialNumber, size) else: if(commutative): return TomonoidFNC(serialNumber, size) else: return TomonoidFN(serialNumber, size) def computeTomonoidsSuperBrute(archimedean, commutative, counter, size): """Generates all the specified f.n. tomonoids of the given size. This function does not work at the moment as the method iterateTable() is not implemented. """ tomonoids = [] tom = getNewTomonoid(archimedean, commutative, -1, size) # The first iterated tomonoid, which is the trivial tomonoid, is supposedly correct tomNew = tom.getCopy(counter.getNew()) tomonoids.append(tomNew) while(tom.iterateTable()): report = tom.performAllTests() if report.isSuccessfull(): tomNew = tom.getCopy(counter.new()) tomonoids.append(tomNew) return tomonoids def generateTomonoids(upToSize, method, archimedean, commutative): """Generates all the specified f.n. tomonoids up to the given size. Parameters: upToSize ... size up to which the tomonoids are generated method ... can be 'levelset', 'brute', or 'superbrute' ('levelset' is our new introduced method; 'brute' is a "more intelligent" brute force method based on generating all the one-element coextensions of a given tomonoid and testing whether they meet the axioms of a f.n. tomonoid; 'superbrute' is a "stupid" brute force method when all the possible multiplication tables of f.n. tomonoids of the given size are generated and then it is tested whether they meet the axioms of a f.n. tomonoid) archimedean ... set to True if the generated tomonoids are supposed to be Archimedean commutative ... set to True if the generated tomonoids are supposed to be commutative Remark: The "super brute force" method has been removed (it was fucking slow, anyway) and not yet re-implemented. """ counter=Counter() counter.report = True # the sequence elements generated by the counter will be reported counter.period = 10000 # every 10000th sequence element generated by the counter will be reported # report is an instance of the class TomonoidReport and will contain all # the generated tomonoids with additional informations report = TomonoidReport(upToSize, method, archimedean, commutative) report.printStartMessage() # time measurement totalTimeStart = timeit.default_timer() for i in range(upToSize): # current size of the generated tomonoids size = i+1 # time measurement partTimeStart = timeit.default_timer() if i == 0: # t0 is the trivial one-element tomonoid to start with t0 = getNewTomonoid(archimedean, commutative, counter.getNew(), 1) report.tomonoids.append([t0]) report.numbers.append(1) else: tomonoids = [] # here the generated tomonoids of the current size will be stored if method == 'levelset': # generate all the one-element coextensions by our level set based method for tom in report.tomonoids[i-1]: tom.computeExtensions(counter) tomonoids.extend(tom.extensions) elif method == 'brute': # generate all the one-element coextensions by the "more intelligent" brute force method for tom in report.tomonoids[i-1]: tom.computeExtensionsBrute(counter) tomonoids.extend(tom.extensions) elif method == 'superbrute': # to be re-implemented pass else: print "Unknow method:", method # add the generated tomonoids to the report report.tomonoids.append(tomonoids) num = len(tomonoids) report.numbers.append(num) # time measurement partTimeStop = timeit.default_timer() partTime = partTimeStop - partTimeStart report.times.append(partTime) # showing the total number of the generated tomonoids of the current size if report.numbers[i] == 1: numTomStr = "1 tomonoid" else: numTomStr = "%d tomonoids" % report.numbers[i] print "Computed", numTomStr, "of size", size, "in", partTime, "seconds." # time measurement totalTimeStop = timeit.default_timer() totalTime = totalTimeStop - totalTimeStart print "Total time:", totalTime, "seconds" report.time = totalTime report.counterReachedValue = counter.getCurrent() return report def generateAndStore(upToSize, method, archimedean, commutative): """Generates all the specified f.n. tomonoids up to the given size and stores them to a text file named output_(size)_(method)_A_C.txt and to a Python pickle file named output_(size)_(method)_A_C.p. Here, size is the maximal size of the generated tomonoids, method is one of 'levelset', 'brute', or 'superbrute', and '_A' and '_C' indicate whether the generated tomonoids are Archimedean and/or commutative. Parameters: upToSize ... size up to which the tomonoids are generated method ... can be 'levelset', 'brute', or 'superbrute' ('levelset' is our new introduced method; 'brute' is a "more intelligent" brute force method based on generating all the one-element coextensions of a given tomonoid and testing whether they meet the axioms of a f.n. tomonoid; 'superbrute' is a "stupid" brute force method when all the possible multiplication tables of f.n. tomonoids of the given size are generated and then it is tested whether they meet the axioms of a f.n. tomonoid) archimedean ... set to True if the generated tomonoids are supposed to be Archimedean commutative ... set to True if the generated tomonoids are supposed to be commutative Remark: The "super brute force" method has been removed (it was fucking slow, anyway) and not yet re-implemented. """ print "" print "------------------------------------------" print "Let us start!" print "------------------------------------------" print "" report = generateTomonoids(upToSize, method, archimedean, commutative) report.show() fileName = "output_" + str(upToSize) + "_" + method if archimedean: fileName += "_A" if commutative: fileName += "_C" report.writeToTextFile(fileName) report.pickle(fileName) print "Open this source file and see the examples at the bottom." # ----------------------------------------------------------------------------- # # Examples: # # ----------------------------------------------------------------------------- # Generate all the finite, negative tomonoids by the "brute force" method up to # size 5 and store the resulting report to the files: # output_5_brute.txt # output_5_brute.p # # generateAndStore(5, "brute", False, False) # Generate all the Archimedean, finite, negative tomonoids by the "level set # based" method up to size 6 and store the resulting report to the files: # output_6_levelset_A.txt # output_6_levelset_A.p # # generateAndStore(6, "levelset", True, False) # Generate all the commutative, finite, negative tomonoids by the "brute force" # method up to size 7 and store the resulting report to the files: # output_7_brute_C.txt # output_7_brute_C.p # # generateAndStore(7, "brute", False, True) # Generate all the Archimedean, commutative, finite, negative tomonoids by the # "level set based" method up to size 8 and store the resulting report to the # files: # output_8_levelset_A_C.txt # output_8_levelset_A_C.p # # generateAndStore(8, "levelset", True, True) # Generate all the commutative one-element coextensions of a commutative, finite, # negative tomonoid specified by its multiplication table. # The resulting one-element coextensions are then printed to console. # # table= [['0','t','u','v','w','x','y','z','1'], # ['0','0','u','u','w','x','x','z','z'], # ['0','0','0','t','u','u','u','x','y'], # ['0','0','0','0','u','u','u','x','x'], # ['0','0','0','0','0','u','u','w','w'], # ['0','0','0','0','0','0','t','u','v'], # ['0','0','0','0','0','0','0','u','u'], # ['0','0','0','0','0','0','0','0','t'], # ['0','0','0','0','0','0','0','0','0']] # counter = Counter() # tom = TomonoidFNC(counter.getNew()) # tom.createFromCharTable(table) # tom.showShort() # tom.computeExtensions(counter) # print "(There are", len(tom.extensions), "one-element coextensions of this f.n. tomonoid.)" # print # for ext in tom.extensions: # ext.showShort()