Seminars & Colloquia
Dept Comp Sci and EE, West Virginia University
"Modeling Reactive Systems through Mathematical Programs"
Monday November 24, 2014 10:30 AM
Location: 3211, EBII NCSU Centennial Campus
(Visitor parking instructions)
In this talk, I will discuss the modeling of reactive systems through a relatively new mathematical paradigm called Quantified Linear Programming. Quantified Linear Programs (QLPS) generalize traditional linear programs in that the program variables can be either existentially quantified or universally quantified. On account of quantifier alternations that appear in the specification, the problem of checking whether a QLP has a model is non-trivial. Indeed, even with a single alternation, a QLP variant is coNP-complete. The computational complexity of the general version of the problem is still open.
A related problem is the Quantified Linear Implication problem. Quantified Linear Implication (QLIs) generalize QLPS and are useful for modeling requirements in a number of domains. We will discuss the computational complexities of variants of the QLI problem.
K. Subramani graduated from U. Maryland, College Park with a Ph.D. in Computer Science in 2000. Since graduation, he has been with the Lane Department of Computer Science and Electrical Engineering at West Virginia University, where he is now a Full Professor. His primary research interests include computational logic, combinatorial optimization and network security. He is also interested in VLSI design problems, especially as they relate to FPGA partitioning and routing.
A complete list of his publications is available at: http://www.informatik.uni-trier.de/~ley/pers/hd/s/Subramani:K=
Host: Matthias (Matt) Stallmann, CSC