University of Leicester

informatics

Definability Issues of Group Theoretic Notions

Source of Funding: British-Finnish Academic Research Collaboration (ARC) Programme
Amount: 800
Duration: July 1997 - June 1998
Principal Investigators: Dr. Kerkko Luosto (University of Helsinki, Finland), Prof. Iain Stewart
Other Investigators: Dr. Juha Nurmonen, Mr. Ari Koponen (University of Helsinki, Finland)

The project has two main objectives. The first is to examine the definability of group theoretical notions in different logics when the group is finite and is considered as a finite structure. For example, the notion of simplicity on finite groups can be defined in second-order logic and also in least-fixed point logic, but it is unknown whether simplicity can be defined in first-order logic. The second objective is to examine the generating group of a language definable in some logic. For example, the syntactic monoid of the language of words over 0 and 1 in which the number of 1s is even is a group of order 2. But this group is not aperiodic and hence this language is not definable in first-order logic.

University of Leicester 15th December 2000. Last modified: 8th January 2004, 14:32:38.
Informatics Web Maintainer. This document has been approved by the Head of Department.