TITLE: Inductive versus Fixpoint Definitions in Default Logic and Logic Programming

PRESENTER: David Makinson

DATE: Friday 2nd April 2004

TIME: 12:00noon-1:00pm

PLACE: Seminar Room K17

ABSTRACT:

In classical logic, the notion of a derivation is defined inductively, as also in most non-classical logics. But in default logic and nonmonotonic logic programming with the answer-set semantics, induction is abandoned in favour of extensions understood as fixpoints. The conventional wisdom is that there are kinds of extension that can be defined as fixpoints, but not inductively in any straightforward manner.

But how far is this true? Nobody has actually shown that it is, although two obstacles to an inductive definition are usually mentioned - the multiplicity of extensions and their possible non-existence. Nevertheless, Brewka (1994) showed that in Reiter default logic with normal rules we may replace fixpoint definitions by inductive ones; and the procedural presentation of non-normal Reiter default systems by Antoniou (1997) in effect implies the same for them too.

In this talk we show how this may in fact be done for any system satisfying certain general conditions. The general result applies both to Reiter default logic (and several of its variants) and to systems of default-based logic programming using the answer-set semantics. On the other hand, there are reasons to believe that an inductive definition cannot be given for the 'weak extensions' of Marek and Truszczynski, nor to the corresponding expansions of autoepistemic logic.

BIOGRAPHY OF SPEAKER:

Present position: Senior Research Fellow, Unit of Logic Language and Computation, Dept Computer Science, King's College London.

Associate position: Associate Member, Centre des Recherches en Epistemologie Applique (CREA) Paris.

Previous positions: 1980-2001: Programme Specialist, Division of Social Science Research and Policy (SHS/SRP), Sector of Social and Human Sciences, UNESCO, Paris. 1965-1980: Professor (Assistant, Associate, Full, Chairman of Department) American University of Beirut, Lebanon. Visiting Professor Buenos Aires and Bahia Blanca.

Research areas: Mathematical logic and its relations with other disciplines, particularly computer science and philosophy. Current research areas: nonmonotonic logics, input/output logics, logic of norms, logic of belief
change.

Research publications: Over fifty in number, and frequently cited. Appear in leading international journals of logic, computer science and philosophy including J. Artificial Intelligence, J. Logic and Computation, Logic Journal of the IGPL, J. Logic, Language and Information, J. Philosophical Logic, Studia Logica, J. Symbolic Logic, Zeitschrift Math. Logik, Theoria, and also as chapters in books published by Oxford University Press, Morgan Kaufmann, Springer-Verlag, IOS Press. Expository book Topics in Modern Logic in three languages.

Reviewing, editorial, refereeing in logic: Regular reviewer for Math. Reviews, Zentralblatt fr Math, occasionally for J. Symbolic Logic. On editorial boards of J. Applied Non-Classical Logics, J. Logic and Computation, J. Logic, Language and Information, Studia Logica, and also book series Trends in Logic. Referee for all these and several other journals, e.g. Artificial Intelligence, Erkenntnis, as well as for many international workshops in logic and computer science. Doctoral thesis examiner for universities in Argentina, Australia, France. Editorial in other fields: Formerly Editor-in-Chief of UNESCO.s International Social Science Journal. Co-Editor of its World Social Science Report 1999.

Professional Associations: Association of Symbolic Logic, British Logic Colloquium.

Host:

Thomas Meyer
National ICT, Australia, Sydney Node
Building K17, Computer Science and Engineering
The University of New South Wales, Sydney 2052, Australia
URL: http://www.cse.unsw.edu.au/~tmeyer/

Seminar Convenor:

Bernhard Hengst
Tel: +61-2-9385-3988,
E-mail: bernhardh@cse.unsw.edu.au
School of Computer Science & Engineering, UNSW.