IMI Interdisciplinary Mathematics InstituteCollege of Arts and Sciences

Detecting Low Weight Circuits in Posemigroup Edge-Weighted Digraphs

  • March 26, 2018
  • 4 p.m.
  • LeConte 312


A question stemming from program termination analysis leads to following problem. Given a finite directed graph with edges taking labels from a partially ordered semi-group, does every circuit in the graph have weight above some specified ideal? As the number of circuits is (generally) infinite, the problem is first reduced to determining an upper bound on the length of cycles that must be examined, in the case the poset is finite. This suggests a (slow) algorithm for answering the question. A faster algorithm is proposed in the more general case of the poset satisfying the descending chain condition and having finite width. The algorithm determines if some circuit achieves a weight in the ideal.

Dr. Aaron Dutle is a Research Computer Scientist working in the Safety-Critical Avionics Systems Branch at NASA's Langley Research Center since 2014. He currently specializes in Formal Methods in Computer Science, and particularly their use in aerospace applications. He received his Ph.D in Mathematics from the University of South Carolina in 2012 under Dr. Joshua Cooper, and remained at the university for two years as a postdoctoral researcher under Drs. Eva Czabarka and Laszlo Szekely.

© Interdisciplinary Mathematics Institute | The University of South Carolina Board of Trustees | Webmaster