Presenter José María Turull Torres, Dept. of Engineering Universidad Nacional de La Matanza, Argentina, and Massey University, New Zealand Bio 20 years of professional work in Informatics in Argentina and Mexico. A further 23 years of academic work with research in the areas of Database Theory, Finite Model Theory and Complexity, in Argentina and New Zealand. Currently appointed as a Professor in the Dept. of Engineering at Universidad Nacional de La Matanza, Argentina, and holding an Honorary Research Fellowship at Massey, N.Z. Member of the Program Committee in many international Conferences, and co-Chair in FoIKS 2004. Key-note Speaker in FMT in six int. Conferences. Many Refereed publications in journals like AMAI, APAL, J. of IGPL, JUCS, Acta Cybernetica, and TCS; chapters in books published by Springer, College Publications (London), Marcel Dekker, and AMS; editor in Springer and AMAI; articles in int. Conferences like FoIKS, CSL, IEEE Chilean SCCC, ETheCoM, EJC, ADC, and ADBIS. 2 Doctorate students and 4 Master students completed. Research visits and collaboration to U. of Helsinki, U. of Joensuu, U. of Tampere, U. of Warsaw, U. of Toronto, U. of Cantabria, Ecole Polytechnique de Paris, and Software Competence Centre Hagenberg. Abstract Relational machines (RM) were introduced in 1991 as abstract machines that compute queries to (finite) relational structures, or relational database instances (dbi's), that are generic (i.e., that preserve isomorphisms), and hence are more appropriate than Turing machines (TM) for query computation. RM's are TM's endowed with a relational store that holds the input dbi, as well as work relations, and can be queried and updated through first order logic (FO) formulas in their finite control. Consequently, k-ary RM's are incapable of computing the size of the input though, however, they can compute its size_{k}, i.e, the number of FO^{k} types of k-tuples in the dbi. Then, it was a natural consequence to define a new notion of complexity suitable for RM's. Relational Complexity was also introduced in 1991 as a complexity theory where the input dbi to a query is measured as its size_{k}, and complexity classes mirroring computational complexity classes were defined. Relational Complexity turned out to be a theoretical framework in which we can characterize exactly the expressive power of the well-known fixed point quantifiers of a wide range of sorts. In 1997, several equivalences between fixed point quantifiers (added to FO) and different relational complexity classes were proved, classifying them as either deterministic, non-deterministic, or alternating, and either inflationary or non-inflationary. Those characterizations are actually very interesting and meaningful, given that it was already known that if we restrict the input to only ordered dbi's, the same equivalences with computational complexity classes also hold. Regarding the characterization of relational complexity classes with other logics, it was proved that RM's have the same computation, or expressive power, as the (effective fragment of the) well known infinitary logic with finitely many variables. Besides, some fragments of second and third order logic, defined as semantic restrictions of the corresponding logic, have been proved to characterize several classes, and there is an ongoing work in that direction. One interesting consequence of it is that RM's are strong enough as to simulate the existence of third order relations in their relational store. An important application of the creation of new logics to Complexity Theory is the search for lower bounds of problems w.r.t. those logics, aiming to separate computational complexity classes. In this talk we will give a description of RM's and NRM's, will define the basic notions of Relational Complexity, and discuss its motivations and the tight relationship between the main classes and different fixed point logics and fragments of second and third order logics. |