Computer Scientists’ Paper from 2006 Stands the Test of Time

A paper written in 2006 by UT Dallas computer science department head Dr. Gopal Gupta and three of his PhD students received a 10-year Test of Time Award from the Association for Logic Programming (ALP) at the 32nd International Conference on Logic Programming (ICLP) in New York.

Gupta, holder of the Erik Jonsson Chair in the Erik Jonsson School of Engineering and Computer Science, shares the honor with co-authors Dr. Luke Simon BS’01, PhD’06; Dr. Ajay Bansal PhD’07; and Dr. Ajay Mallya MS’02, PhD’06. Their paper, “Coinductive Logic Programming,” demonstrated a practical way of addressing circular, infinite patterned objects in a computational setting.

“Computations involving circular and infinite structures run forever, but they often have a pattern,” Gupta said. “If you recognize those patterns, you can reason about them using a concept called coinduction. While the concept was already used in mathematics, our work showed a practical way to introduce coinduction methods and logic into computation.”

The ALP's Test of Time awards recognize the most influential paper from the annual meeting of the ICLP held 10 years ago. The UT Dallas team’s work on coinduction within logic and computer science became the foundation for many efforts to address unsolved problems. Yet, theirs was an undertaking with humble beginnings.

“The original goal was for Simon to just write a short report and file it away,” Gupta said, explaining that his students’ interest in coinduction was sparked by the 1996 book Vicious Circles, written by Jon Barwise and Lawrence S. Moss. “They brought it to me, and I could see other problems that needed to be solved could potentially be solved with this. That’s how we got started.”

Simon, now a software engineering manager at Twitter, recalled the support he received from Gupta and Mallya as they brainstormed to develop the concept. "Coinductive Logic Programming" became the basis of Simon’s PhD thesis.

“Dr. Gupta was a great mentor who helped me bridge the gaps between theory and practical applications and between functional programming and logic programming,” Simon said. “Ajay Mallya encouraged me to see my wild thoughts through, enduring countless days in the research lab where I ranted and raved about the powers of coinduction. He was the only person awake through it all.”

Bansal is now an assistant professor at Arizona State University.

“Working with Dr. Gupta on coinductive logic programming led the successful development of goal-directed execution of answer set programs,” Bansal said. “This was at one time considered impossible to accomplish. Working on these projects laid a strong foundation for my current research in my academic career.”

Mallya joined Amazon after graduation and recently moved to work for KeyMe.

“I have fond memories of working with Dr. Gupta and others as we developed what has now become a highly successful research topic, producing several award-winning publications,” Mallya said. “The concepts and techniques I learned proved to be a great foundation for my career building large-scale software at Yahoo, Amazon and Expedia.”

Gupta highlighted the abilities of the students that happened to arrive at UT Dallas so close to each other.

“The team that came together in my PhD lab was very talented,” Gupta said. “Mallya had won the ICLP best student paper award in 2005, and the team’s work on web services was honored as the best paper at the European Conferences on Web Services that same year.”

Gupta emphasized that, just as their work placed building blocks for others, they had earlier work to guide them as well, noting that British mathematician Peter Aczel helped bring coinduction to mathematics in 1988.

“We didn’t invent coinduction — we showed how coinduction can be a basis for computation, just as induction is in standard programming,” Gupta said. “That’s why it got a lot of attention — and that work was conceived, realized and implemented wholly at UT Dallas.”