The scientific legacy of Marco Cadoli in Artificial Intelligence

It was in 1988 when Marco Cadoli asked me (Maurizio Lenzerini) if I could propose a master thesis work to him. I had just finished my first course as a professor. The course was about Software Engineering and Programming Languages, and during the lectures I had noticed Marco’s outstanding performance in the course, both in the part related to Software Design, and in the part devoted to object-oriented, functional and logic programming. I thought it was great that such a brilliant student was willing to work with me. So, we started discussing about possible topics, and I suggested Artificial Intelligence and in particular Knowledge Representation. More specifically, I talked to him about the research program I was pursuing, centered around the idea of understanding the exact computational complexity of various KR formalisms, in particular the formalisms for nonmonotonic reasoning. Although we now take it for granted that analyzing the computational complexity of a logical formalism is an essential tool for characterizing the properties of the formalism itself, at that time this kind of investigation was not so common. Only recently, people like Hector Levesque, Ron Brachman, Ray Reiter and others had started pointing out the importance of understanding the inherent complexity of reasoning tasks, and relating such complexity with the expressive power of the representation language. Marco had studied Theoretical Computer Science in