Department of Computer Science
University of Auckland
4pm Tuesday 19th November 2002
Room 2511, JCMB, King's Buildings
Basic components of a program consist of declarations of variables and their types, definitions of classes and their objects, methods, and their interactions. On an abstract level, the program defines an algebraic structure. In a programming terminology, this structure is the abstract data type implemented by the program. An algebraic specification of an abstract data type A is a specification S written in a formal language so that S defines A in a precise sense. In this talk we discuss some issues related to specifications of abstract data types. In particular, we address a long standing open problem of Bergtsra and Tucker about specifiability of absract data types by means of equations or conditional equations. The talk will include foundational aspects of the area, presents examples, and recent algebraic, logical, and computability-theoretic techniques developed towards the study of the problem.