BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY:Definability of linear equation systems over groups and rings - Pa
 kusa\, W (RWTH Aachen University)
DTSTART:20120329T140000Z
DTEND:20120329T143000Z
UID:TALK37160@talks.cam.ac.uk
CONTACT:Mustapha Amrani
DESCRIPTION:joint work with A. Dawar\, E. Grädel\, B. Holm\, E. Kopczynsk
 i) \n\nOne of the major open question in finite model theory is whether th
 ere is a logic for PTIME. As one promising candidate\, fixed-point logic w
 ith counting\, FPC\, has been studied extensively\, and indeed\, FPC has b
 een shown to capture PTIME on important classes of structures.\n \nAlthoug
 h Cai\, Fürer and Immerman ruled out FPC for the general case already in 
 1992\, it was only in 2007 that Atserias et. al [1] found a class of natur
 al problems explaining the major shortcoming of FPC. Specifically\, they p
 roved that the important problem of solving linear equation systems (SLES)
  over finite Abelian groups cannot be expressed in FPC\; moreover\, all ot
 her known queries separating FPC from PTIME turned out to be reducible to 
 SLES via simple logical reductions. Hence\, problems from algebra provide 
 a new source of operators which have polynomial-time data complexity and w
 hich might be used to strictly extend the expressive power of FPC (cf. the
  notion of rank logics [2]).\n \nMotivated by these insights\, we study SL
 ES over various classes of finite groups and rings from the viewpoint of l
 ogical (inter-)definability. All problems that we consider are decidable i
 n polynomial time\, but not expressible in FPC. Based on the structure the
 ory of finite rings\, we prove that on important classes of rings\, SLES c
 an be reduced to SLES over cyclic groups\, which constitute the most basic
  class of tractable domains for SLES. Furthermore\, we prove closure prope
 rties for classes of queries that reduce to SLES over fixed rings. As one 
 application\, these closure properties provide normal forms for logics ext
 ended with solvability operators.\n \n[1] Albert Atserias\, Andrei A. Bula
 tov\, and Anuj Dawar. Affine systems of equations and counting infinitary 
 logic. Theor. Comput. Sci.\, 2009.\n \n[2] Anuj Dawar\, Martin Grohe\, Bja
 rki Holm\, and Bastian Laubner. Logics with rank operators. In LICS ’09:
  Proceedings of the 2009 24th Annual IEEE Symposium on Logic In Computer S
 cience\, 2009\n
LOCATION:Seminar Room 1\, Newton Institute
END:VEVENT
END:VCALENDAR