Submitted by JÚLIO HEBER SILVA (julioheber@yahoo.com.br) on 2018-03-14T17:24:36Z No. of bitstreams: 2 Dissertação - Angie Tatiana Suárez Romero - 2018.pdf: 2209912 bytes, checksum: 0ad7489cc1457ed892d896b3aa2f4885 (MD5) license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) / Approved for entry into archive by Luciana Ferreira (lucgeral@gmail.com) on 2018-03-15T11:07:28Z (GMT) No. of bitstreams: 2 Dissertação - Angie Tatiana Suárez Romero - 2018.pdf: 2209912 bytes, checksum: 0ad7489cc1457ed892d896b3aa2f4885 (MD5) license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) / Made available in DSpace on 2018-03-15T11:07:28Z (GMT). No. of bitstreams: 2 Dissertação - Angie Tatiana Suárez Romero - 2018.pdf: 2209912 bytes, checksum: 0ad7489cc1457ed892d896b3aa2f4885 (MD5) license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) Previous issue date: 2018-03-05 / Conselho Nacional de Pesquisa e Desenvolvimento Científico e Tecnológico - CNPq / Cayley’s theorem allows us to represent a finite group as a permutations group of a finite set of points. In general, an action of a finite group G in a finite set, is described as an application of the group G in the symmetric group Sym(Ω). In this work we will describe some algorithms for permutation groups and implement them in the GAP system. We begin by describing a way of representing groups in computers, we calculate orbits, stabilizers in the basic form and by means of Schreier’s vectors. Later we make algorithms to work with primitive and transitive groups, thus arriving at the concept of BSGS, base and strong generator set, for permutation groups with the algorithm SCHREIERSIMS. In the end we work with group homomorphisms, we find the elements of a group through backtrack searches. / O Teorema de Cayley nos permite representar um grupo finito como grupo de permutações de um conjunto finito de pontos. De forma geral, uma ação de um grupo finito G em um conjunto finito Ω, é descrita como uma aplicação do grupo G no grupo simétrico Sym(Ω). Neste trabalho vamos descrever alguns algoritmos para grupos de permutação e implementa-los no sistema GAP. Começamos descrevendo uma maneira de representar grupos em computadores, calculamos órbitas, estabilizadores na forma básica e por meio de vetores de Schreier. Posteriormente fazemos algoritmos para trabalhar com grupos transitivos e primitivos, chegando assim ao conceito de, base e conjunto gerador forte (BSGS) para grupos de permutação finitos com o algoritmo SCHREIER-SIMS. No final trabalhamos com homomorfismos de grupos e encontramos os elementos de um grupo mediante pesquisas backtrack.

<p>A great variety of algebraic problems can be solved using Groebner bases, and computational commutative algebra is the branch of mathematics that focuses mainly on such problems. In this thesis we employ Buchberger's algorithm for finding Groebner bases by tailoring specialized instances of Buchberger's algorithm via code generation. We introduce a framework for meta programming and code generation in the F# programming language that removes the abstraction overhead of generic programs and produces type-safe and syntactically valid specialized instances of generic programs. Then, we discuss the concept of modularizing and decomposing the architecture of software products through a multistage design process and define what specialization of software means in the context of producing special instances. We provide a domain-specific language for the design of flexible, customizable, multistage programs. Finally, we utilize the aforementioned techniques and framework to produce a highly parametrized, abstract and generative program that finds Groebner bases based on Buchberger's original algorithm, which, given all the proper definitions and features of a specific problem in computational algebra, produces a specialized instance of a solver for this problem that can be shown to be correct and perform within the desired time complexity.</p> / Doctor of Philosophy (PhD)

We develop a public key cryptosystem whose security is based on the intractability of the ideal membership problem for a noncommutative algebra over a finite field. We show that this system, which is the noncommutative analogue of the Polly Cracker cryptosystem, is more secure than the commutative version. This is due to the fact that there are a number of ideals of noncommutative algebras (over finite fields) that have infinite reduced Groebner bases, and can be used to generate a public key. We present classes of such ideals and prove that they do not have a finite Groebner basis under any admissible order. We also examine various techniques to realize finite Groebner bases, in order to determine whether these ideals can be used effectively in the design of a public key cryptosystem. We then show how some of these classes of ideals, which have infinite reduced Groebner bases, can be used to design a public key cryptosystem. We also study various techniques of encryption. Finally, we study techniques of cryptanalysis that may be used to attack the cryptosystems that we present. We show how poorly constructed public keys can in fact, reveal the private key, and discuss techniques to design public keys that adequately conceal the private key. We also show how linear algebra can be used in ciphertext attacks and present a technique to overcome such attacks. This is different from the commutative version of the Polly Cracker cryptosystem, which is believed to be susceptible to "intelligent" linear algebra attacks. / Ph. D.

One goal of systems biology is to predict and modify the behavior of biological networks by accurately monitoring and modeling their responses to certain types of perturbations. The construction of mathematical models based on observation of these responses, referred to as reverse engineering, is an important step in elucidating the structure and dynamics of such networks. Continuous models, described by systems of differential equations, have been used to reverse engineer biochemical networks. Of increasing interest is the use of discrete models, which may provide a conceptual description of the network. In this dissertation we introduce a discrete modeling approach, rooted in computational algebra, to reverse-engineer networks from experimental time series data. The algebraic method uses algorithmic tools, including Groebner-basis techniques, to build the set of all discrete models that fit time series data and to select minimal models from this set. The models used in this work are discrete-time finite dynamical systems, which, when defined over a finite field, are described by systems of polynomial functions. We present novel reverse-engineering algorithms for discrete models, where each algorithm is suitable for different amounts and types of data. We demonstrate the effectiveness of the algorithms on simulated networks and conclude with a description of an ongoing project to reverse-engineer a real gene regulatory network in yeast. / Ph. D.

This thesis presents a unified framework for the analysis of instantaneous kinematics and statics of spatial manipulators. The proposed formulation covers the entire range of kinematic behavior, with kinematic singularity and isotropy appearing as special cases. An analogous treatment of statics is also presented. It is established that the formulations presented are capable of generating exact solutions in closed form for several interesting problems in manipulator analysis. Several such results have been obtained via extensive usage of symbolic computation tools developed for this purpose. The proposed approach is applicable to manipulators of different architectures. However, the focus is on the parallel and hybrid manipulators, as their analysis presents more challenges than their serial counterparts. The theory of screws has been adopted as the basis of the formulation. Instantaneous kinematics and statics are studied in terms of the principal bases of the space of twists, se(3), and the space of wrenches, se* (3), respectively. A dual number parameterisation of the motion space is adopted to make the formulation compact and dimensionally consistent. The properties of the dual combination obviate the need for an explicit scaling between the linear and angular velocities or the forces and moments. Hence the results obtained from the formulation are purely geometrical. The analysis of the twists is performed via the dual velocity Jacobian matrix. The principal basis of se(3) is obtained from the eigenproblem of a symmetrical dual matrix associated with the Jacobian. The notion of a dual eigenproblem is introduced in this context. Solutions are provided for the general case, as well as a few special cases. The computations involve the solution of at most a cubic equation for any arbitrary degree-of-freedom of rigid-body motion, and closed form results are therefore ensured. The results of the eigen-analysis lead to a decoupling of the rotational and the pure translational components of a rigid-body motion. This is termed as the partitioning of degrees-of-freedom. They also motivate an interesting classification of the manipulators based on the instantaneous partition of its degrees-of-freedom. This notion is further extended to analyse the effects of a singularity on the motion characteristics of a manipulator. Due to the duality of se(3) and se*(3), the formulation of statics is completely analogous, and involves, in essence, only the substitution of the dual wrench-transformation matrix for the dual Jacobian. A similar partitioning of the wrench system is introduced based on the eigen-decomposition in the context of statics. It is shown that the principal screws associated with either a system of twists or wrenches can be obtained from a generalised eigenproblem of two symmetric real matrices arising out of the symmetric dual matrix mentioned above. The general 2-and 3-screw systems are analysed in closed form via the generalised characteristic polynomial. Several special screw systems are described in terms of algebraic equations in terms of the coefficients of this polynomial. Principal bases for 4-and 5-systems are obtained in a novel fashion without deriving their reciprocal systems explicitly. Using the same approach based on the analysis of the characteristic polynomial, compact algebraic conditions for singularity and isotropy are derived as the special cases of a single formulation. The above formulations establish the existence of exact closed-form results. However, to implement them symbolically for a real application problem, capabilities in existing computer algebra systems do not suffice in general. Therefore simplification and computational algorithms are developed for dealing with large expressions with algebraic and trigonometric terms typically appearing in kinematics and statics. Three canonical forms of such expressions and the corresponding simplification schemes are presented. The theoretical developments are illustrated with examples of serial, parallel and hybrid manipulators throughout the thesis. However, the most important applications of these are in the kinematic and static analysis of a semi-regular Stewart platform manipulator (in which the top and bottom platforms are semi-regular hexagons). Using the degeneracy of the wrench transformation matrix as the singularity criterion, the singularity manifold of the manipulator is obtained via extensive application of the symbolic simplification algorithms. The constant-orientation singularity manifold is derived in a compact closed form, and a complete geometric characterisation and explicit parameterisation of the same are presented. The constant-position singularity manifold is also obtained in closed form. On the other hand, families of configurations of the manipulator for combined kinematic or static isotropy for a given architecture are derived in closed form. Also, architectural designs are obtained for the manipulator such that it exhibits combined kinematic or static isotropy at a given configuration.

Σε αυτήν την εργασία, προσεγγίζουμε την συνύπαρξη δύο βασικών αλγεβρικών δομών για τις ανάγκες επίλυσης πολλών προβλημάτων των σύγχρονων Μαθηματικών. Οι δομές αυτές είναι οι ομάδες και τα γραφήματα, που με την ταυτόχρονη χρήση τους μας οδήγησαν στην μελέτη των G-γραφημάτων. Ειδικότερα θα δούμε τον τρόπο με τον οποίο η θεωρία ομάδων βοηθά στην μελέτη των γραφημάτων και πως η θεωρία γραφημάτων ανταποδίδει τη βοήθεια αυτή. Όλα αυτά, προσδιορίζονται-μελετώνται και επεκτείνονται με την υποστήριξη που προσφέρει στις μέρες μας η Υπολογιστική Άλγεβρα. Ο κλάδος αυτός των μαθηματικών υποβοηθούμενος από αλγορίθμους και υπολογιστικά αλγεβρικά συστήματα καθοδήγησε και υποστήριξε την μελέτη «δύσκολων» προβλημάτων. Αναμένεται να επεκτείνει τη μελέτη και την επίλυση και άλλων ανοικτών προβλημάτων στο μέλλον. Αναδεικνύεται κατά αυτό τον τρόπο, η αξία και η σπουδαιότητα της χρήσης υπολογιστικών μεθόδων ως σημαντικού εργαλείου στην μελέτη γραφημάτων και ομάδων. Η εργασία έχει οργανωθεί σε εννέα κεφάλαια. Αρχικά γίνεται αναφορά στην Υπολογιστική Άλγεβρα. Υπολογιστική Άλγεβρα είναι ο κλάδος των Μαθηματικών ο οποίος ασχολείται με τις τεχνικές που εκτελούν τους αλγεβρικούς υπολογισμούς με την βοήθεια των υπολογιστών. Η λογική διαδικασία που χρησιμοποιεί φτιάχνεται από τις βασικές θεωρίες των μαθηματικών θεμάτων που επεξεργάζονται και επεκτείνονται από : 1) αλγορίθμους και δομές δεδομένων 2) γλώσσες προγραμματισμού και συστήματα λογισμικού 3) μέσα διασύνδεσης ανάμεσα στα αλγεβρικά υπολογιστικά συστήματα και τους χρησιμοποιούμενους αλγορίθμους. Οι «υπολογισμοί» πάνω σε διάφορα θέματα, είχαν απασχολήσει τον άνθρωπο από τα παλιά χρόνια γιατί πάντα ήθελε να δώσει λύσεις στα προβλήματά του. Στις μέρες μας, υπολογίζουμε περισσότερο για ερευνητικούς λόγους, για να επεκτείνουμε τους ήδη υπάρχοντες αλγορίθμους σε ευρύτερες περιοχές και για να επιλύσουμε σύγχρονα προβλήματα της επιστήμης. Πολλά από τα προβλήματα που σήμερα είναι “μη επιλύσιμα” στα Μαθηματικά, αφορούν στις Ομάδες. Στα Μαθηματικά Ομάδα (group) είναι ένα σύνολο, μαζί με μία διμελή πράξη (όπως ο πολλαπλασιασμός και η πρόσθεση) που ικανοποιούν βασικά αξιώματα που περιγράφονται λεπτομερώς στο κεφάλαιο 2 της εργασίας. Η σημασία των ομάδων στα Μαθηματικά είναι μεγάλη. Πολλά από τα αντικείμενα που ερευνώνται στα μαθηματικά είναι ομάδες. Γνωστά σύνολα αριθμών, όπως οι ακέραιοι, οι ρητοί, οι πραγματικοί και οι μιγαδικοί αριθμοί εφοδιασμένα με την πράξη της πρόσθεσης είναι ομάδες. Η θεωρία ομάδων θεμελιώνει τις ιδιότητες αυτών των συστημάτων και ανακαλύπτει πολλές άλλες. Τα αποτελέσματά της είναι ευρέως εφαρμόσιμα. Σημαντική αναφορά γίνεται στην ομάδα των μεταθέσεων n αντικειμένων (συμμετρική ομάδα) και την εναλλακτική ομάδα (είναι η ομάδα άρτιου αριθμού μεταθέσεων η αντικειμένων). Ενδιαφέρον θέμα είναι η δημιουργία νέων ομάδων από τις παλιές. Έτσι γίνεται σημαντικός ο ρόλος της υποομάδας, αλλά και των διαμερίσεων των ομάδων, πράγμα που επιτυγχάνεται ικανοποιητικά με την βοήθεια των «συνσυνόλων», της υποομάδας και των τροχιών (orbits). Ιδιαίτερο ρόλο στην θεωρία των ομάδων παίζουν οι μορφισμοί που μελετούν τις σχέσεις ανάμεσα στις ομάδες και ορίζονται με ειδικές συναρτήσεις οι οποίες παίρνουν αντικείμενα από μία ομάδα και τα αντιστοιχούν σε μία άλλη Εξετάζοντας τους μορφισμούς μας επιτρέπεται να κάνουμε σημαντική ανάλυση των σχέσεων ανάμεσα στις ομάδες. Επίσης οι μορφισμοί με τις αντιστοιχίσεις τους συνδέουν τις ομάδες με τα γραφήματα. Οι ομάδες υπογραμμίζουν πολλές άλλες αλγεβρικές δομές όπως τα πεδία και τα διανύσματα χώρου. Είναι επίσης σημαντικά εργαλεία για την μελέτη της συμμετρίας σε όλους τους τύπους. Η άποψη ότι η συμμετρία ενός αντικειμένου σχηματίζει μια ομάδα είναι θεμελιώδης για πολλά Μαθηματικά. Γι αυτές τις αιτίες η Θεωρία ομάδων είναι μια σημαντική περιοχή στα μοντέρνα μαθηματικά και με πολλές εφαρμογές σε άλλους κλάδους όπως η φυσική. Τα γραφήματα(graphs), τα κατευθυνόμενα γραφήματα (directed graphs) και τα δέντρα (trees) εμφανίζονται σε πολλές περιοχές των Μαθηματικών και της επιστήμης των Υπολογιστών. Το κεφάλαιο 3 καλύπτει αυτά τα θέματα. Το γράφημα πολλών προβλημάτων, που αναφέρονται σε διακριτά αντικείμενα και διμελείς σχέσεις, είναι μία πολύ βολική μορφή αναπαράστασης. Αυτό μας οδήγησε στην μελέτη της θεωρίας των γραφημάτων. Τα γραφήματα έπαιξαν και παίζουν σημαντικότατο ρόλο στην ανάπτυξη αλγορίθμων, καθώς είναι τα μόνα εργαλεία στα μαθηματικά που μπορούν να παραστήσουν μία αλληλουχία σκέψεων. Στη θεωρία των γραφημάτων ορίζονται οι “περίπατοι”(walks), οι “αποστάσεις” (distances), τα “υπογραφήματα” (subgraphs) και τέλος οι “μορφισμοί” (morphisms) που είναι ανάλογοι με εκείνους των ομάδων. Ιδιαίτερο ρόλο παίζει η συνδεσιμότητα (connectivity), κυρίαρχη δε για τους αλγορίθμους είναι η έννοια του “δέντρου” (tree). Δύο σημαντικά αλγοριθμικά προβλήματα που απασχολούν τους επιστήμονες είναι Α) ο έλεγχος δύο γραφημάτων ως προς τον ισομορφισμό Β) η εύρεση της ομάδας αυτομορφισμού ενός γραφήματος Τα παραπάνω προβλήματα δεν είναι πάντοτε επιλύσιμα. Εντούτοις σε μερικές περιπτώσεις μπορούν να επιλυθούν με τη βοήθεια αλγορίθμων που υποστηρίζονται από τα υπολογιστικά συστήματα GAP, NAUTY, και MAGMA Συνεχίζοντας στα κεφάλαια 4,5,6 κάνουμε μία μικρή περιγραφή στα κυριότερα για τους παραπάνω στόχους υπολογιστικά αλγεβρικά συστήματα. Η κύρια χρήση των υπολογιστικών αυτών συστημάτων είναι η σύνδεση των παραπάνω δομών (ομάδων και γραφημάτων). Εστιάζουν στους υπολογισμούς των μεταθέσεων n στοιχείων, τον υπολογισμό των μορφισμών των ομάδων, των συνσυνόλων, των τροχιών και των πυρήνων. Το αλγεβρικό Υπολογιστικό Σύστημα GAP, (Groups, Algorithms, Programming) περιέχει ένα «ανοικτό» λογισμικό στο χρήστη, πράγμα που σημαίνει ότι μπορεί κανείς να γράψει τα δικά του προγράμματα στη γλώσσα GAP και να τα χρησιμοποιήσει ακριβώς με τον ίδιο τρόπο όπως και τα προγράμματα τα οποία αποτελούν μέρος του συστήματος. Από την άλλη μεριά το ίδιο είναι εφοδιασμένο με μία μεγάλη βιβλιοθήκη συναρτήσεων η οποία υποστηρίζει αλγεβρικούς και άλλους αλγορίθμους. Αρχικά όλα τα προγράμματα της GAP βιβλιοθήκης ήταν γραμμένα στη γλώσσα προγραμματισμού C, τώρα όμως όλα τα προγράμματα έχουν γραφτεί στη γλώσσα GAP. Στο τέλος του κεφαλαίου 4, δίνονται παραδείγματα εφαρμογής προγραμμάτων του GAP πάνω στους ομοιομορφισμούς των ομάδων. To nauty (no automorphisms, yes?) είναι ένα σύνολο διαδικασιών για προσδιορισμό του αυτομορφισμού μιας ομάδας από ένα γράφημα χρωματισμένων κορυφών. Παρουσιάζει αυτήν την πληροφορία αφού του δοθεί ένα σύνολο γεννητόρων, το μέγεθος της ομάδας και ο αριθμός των τροχιών της ομάδας. Μπορεί επίσης να δώσει έναν ισομορφισμό του γραφήματος. Ο αλγόριθμος που χρησιμοποιεί το nauty είναι μία προς τα πίσω διαδρομή που μπορεί να περιγραφεί σε ομάδες ενός συνηθισμένου δέντρου αναζήτησης. Διάφορα μεγέθη και παράμετροι καθορίζουν την πορεία της διαδικασίας, της οποίας η έξοδος δίνεται σε επίπεδα. Το magma, είναι ένα υπολογιστικό αλγεβρικό σύστημα, σχεδιασμένο να επιλύει προβλήματα στην Άλγεβρα, στη Θεωρία Αριθμών, στη Γεωμετρία και σε συνδυασμούς των παραπάνω Μαθηματικών θεμάτων. Μπορεί να αναπτύξει «εκλεπτυσμένα Μαθηματικά», τα οποία είναι υπολογιστικά δύσκολα. Παρέχει ένα αυστηρό Μαθηματικό περιβάλλον, το οποίο δίνει έμφαση στον διαρθρωτικό υπολογισμό. Ένα χαρακτηριστικό κλειδί είναι η δυνατότητα να συναρμολογεί κανονικές αντιπροσωπεύσεις δομών. Τα κύρια χαρακτηριστικά του είναι: α) αλγεβρική φιλοσοφία σχεδιασμού, β) καθολικότητα, γ) ενοποίηση, δ) παρουσίαση. Το πρόγραμμα, παρέχει στο χρήστη μία συλλογή βιβλιοθηκών και αρχείων τεκμηρίωσης που βρίσκονται όλες σε έναν κατάλογο που το ίδιο περιέχει. Η μελέτη των G-graphs στο κεφάλαιο 7 έχει οργανωθεί ως εξής: Πρώτα δίνουμε τον ορισμό ενός G-graph. Έπειτα περιγράφουμε μερικούς βασικούς αλγορίθμους για συνδυασμούς ομάδων οι οποίοι χρησιμοποιούνται στην μελέτη των G-graphs. Μετά θα συζητήσουμε την αποτελεσματική αποθήκευση και δομή των G-graphs, και πώς να χρησιμοποιηθεί ένας μεταβαλλόμενος τύπος για να υπολογίζει αποτελεσματικά πολλές ιδιότητες ενός G-graph. Στη συνέχεια συγκεντρώνουμε τις μεθόδους που χρησιμοποιούνται, με τη χρήση του NAUTY. Στο κεφάλαιο 8 μας απασχολεί η ταξινόμηση των γραφημάτων που είναι μεταβατικά ως προς την απόσταση (distance transitive graphs). Αυτά είναι τα γραφήματα των οποίων οι ομάδες αυτομορφισμού είναι μεταβατικές πάνω σε κάθε σύνολο ζευγαριών κορυφών σε απόσταση i, για i=0,1,2,.. Παρουσιάζεται μία εισαγωγή σε αυτήν την κατηγορία γραφημάτων και θεωρήματα από τα οποία διέπονται. Με τη χρήση της κατηγορίας των πεπερασμένων απλών ομάδων, φαίνεται πιθανό να βρεθούν όλα τα γραφήματα που είναι μεταβατικά ως προς την απόσταση. Τέλος στο κεφάλαιο 9 μελετάται η έννοια της απαρίθμησης συνσυνόλων (coset enumeration) που τα παραπάνω υπολογιστικά συστήματα προσπαθούν επίσης να αντιμετωπίσουν. Απαρίθμηση συνσυνόλων είναι το πρόβλημα της μέτρησης των συνσυνόλων μιας υποομάδας Η μιας ομάδας G. Η απαρίθμηση συνσυνόλων είναι μια από τις παλαιότερες και πιο χρήσιμες μεθόδους της υπολογιστικής θεωρίας ομάδων. Το 1936 οι Τodd και Coxeter ανακάλυψαν μία διαδικασία για να απαριθμούν τα συνσύνολα μιας υποομάδας από μία ομάδα. Αυτό αποδείχτηκε ένα ισχυρό εργαλείο για τη μελέτη των πεπερασμένων “παρουσιαζόμενων” ομάδων (presented groups) στην υπολογιστική θεωρία τoυς. Παλιότερα το 1911, ο Dehm πρότεινε την επίλυση του “Προβλήματος των λέξεων”. Αυτό είναι η εύρεση ενός αλγορίθμου που να αποφασίζει αν σε μία ομάδα που ορίζεται από ένα πεπερασμένο σύνολο γεννητόρων (generators) και σχέσεων (relators), μία λέξη (word) στους γεννήτορες παριστάνει το ταυτοτικό στοιχείο (identical element). Το πρόβλημα που έθεσε ο Dehn προσπάθησαν πολλοί αργότερα να επιλύσουν με τοπολογικούς στοχασμούς. Σήμερα, η περιοχή αυτή της Υπολογιστικής Θεωρίας των ομάδων έχει αναπτυχθεί γρήγορα μέσω του σχεδιασμού , της ανάπτυξης και της εφαρμογής των Αλγορίθμων, καθώς και εξαιτίας του αυξανομένου αριθμού των Μαθηματικών επιστημόνων που έχουν εργαστεί πάνω σε αυτά τα θέματα. Στο κεφάλαιο 9 δίνουμε μία μικρή περιγραφή του αλγορίθμου των Todd-Coxeter. Αξίζει να σημειωθεί ότι το πρόβλημα των λέξεων σήμερα είναι επιλύσιμο για πολλές όχι όμως όλες τις ομάδες. / This subject is a descrription of the computer algebric systems GAP,NAUTY, MAGMA.

The theory of Grobner bases has garnered the interests of a large number of researchers in computational algebra due to its applications not only in mathematics but also in areas like control systems, robotics, cryptography to name a few. It is well known that the computation of Grobner bases takes time doubly exponential in the number of indeterminates rendering it impractical in all but a few places.The current known algorithms for Grobner bases depend on the term order over which Grobner bases is computed. In this thesis, we study computational complexity of some problems in computational ideal theory. We also study the algebraic formulation of combinatorial optimization problems. Gritzmann and Sturmfels (1993) posed the following question: Given a set of generators, decide whether it is a Gr¨obner bases with respect to some term order. This problem, termed as the Grobner Basis Detection(GBD)problem, was introduced as an application of Minkowski addition of polytopes. It was shown by Sturmfels and Wiegelmann (1997) that GBD is NP-hard. We study the problem for the case of zero-dimensional ideals and show that the problem is hard even in this special case. We study the detection problem in the case of border bases which are an alternative to Grobner bases in the case of zero dimensional ideals. We propose the Border Basis Detection(BBD) problem which is defined as follows: Given a set of generators of an ideal, decide whether that set of generators is a border basis of the ideal with respect to some order ideal. It is shown that BBD is NP-complete. We also formulate the rainbow connectivity problem as a system of polynomial equations such that solving the polynomial system yields a solution to it. We give an alternate formulation of the rainbow connectivity problem as a membership problem in polynomial ideals.

Systems biology is an emergent field focused on developing a system-level understanding of biological systems. In the last decade advances in genomics, transcriptomics and proteomics have gathered a remarkable amount data enabling the possibility of a system-level analysis to be grounded at a molecular level. The reverse-engineering of biochemical networks from experimental data has become a central focus in systems biology. A variety of methods have been proposed for the study and identification of the system's structure and/or dynamics. The objective of this dissertation is to introduce and propose solutions to some of the challenges inherent in reverse-engineering of biological systems. First, previously developed reverse engineering algorithms are studied and compared using data from a simulated network. This study draws attention to the necessity for a uniform benchmark that enables an ob jective comparison and performance evaluation of reverse engineering methods. Since several reverse-engineering algorithms require discrete data as input (e.g. dynamic Bayesian network methods, Boolean networks), discretization methods are being used for this purpose. Through a comparison of the performance of two network inference algorithms that use discrete data (from several different discretization methods) in this work, it has been shown that data discretization is an important step in applying network inference methods to experimental data. Next, a reverse-engineering algorithm is proposed within the framework of polynomial dynamical systems over finite fields. This algorithm is built for the identification of the underlying network structure and dynamics; it uses as input gene expression data and, when available, a priori knowledge of the system. An evolutionary algorithm is used as the heuristic search method for an exploration of the solution space. Computational algebra tools delimit the search space, enabling also a description of model complexity. The performance and robustness of the algorithm are explored via an artificial network of the segment polarity genes in the D. melanogaster. Once a mathematical model has been built, it can be used to run simulations of the biological system under study. Comparison of simulated dynamics with experimental measurements can help refine the model or provide insight into qualitative properties of the systems dynamical behavior. Within this work, we propose an efficient algorithm to describe the phase space, in particular to compute the number and length of all limit cycles of linear systems over a general finite field. This research has been partially supported by NIH Grant Nr. RO1GM068947-01. / Ph. D.

A semigroup is simply a set with an associative binary operation; computational semigroup theory is the branch of mathematics concerned with developing techniques for computing with semigroups, as well as investigating semigroups with the help of computers. This thesis explores both sides of computational semigroup theory, across several topics, especially in the finite case. The central focus of this thesis is computing and describing maximal subsemigroups of finite semigroups. A maximal subsemigroup of a semigroup is a proper subsemigroup that is contained in no other proper subsemigroup. We present novel and useful algorithms for computing the maximal subsemigroups of an arbitrary finite semigroup, building on the paper of Graham, Graham, and Rhodes from 1968. In certain cases, the algorithms reduce to computing maximal subgroups of finite groups, and analysing graphs that capture information about the regular I-classes of a semigroup. We use the framework underpinning these algorithms to describe the maximal subsemigroups of many families of finite transformation and diagram monoids. This reproduces and greatly extends a large amount of existing work in the literature, and allows us to easily see the common features between these maximal subsemigroups. This thesis is also concerned with direct products of semigroups, and with a special class of semigroups known as Rees 0-matrix semigroups. We extend known results concerning the generating sets of direct products of semigroups; in doing so, we propose techniques for computing relatively small generating sets for certain kinds of direct products. Additionally, we characterise several features of Rees 0-matrix semigroups in terms of their underlying semigroups and matrices, such as their Green's relations and generating sets, and whether they are inverse. In doing so, we suggest new methods for computing Rees 0-matrix semigroups.