Characterizations of the Expressive Power of Logics over Trees

Add to your list(s) Download to your calendar using vCal

• Luc Segoufin (INRIA and ENS, Cachan)
• Thursday 09 September 2010, 15:00-16:00
• Room FW26, Computer Laboratory, William Gates Building.

If you have a question about this talk, please contact Anuj Dawar.

This talk will be about the expressive power of logics over trees. More precisely we will try to derive expressibility and inexpressibility results in a generic way.

Our yardstick will be MSO , and all the logical formalisms we will consider can be seen as fragments of MSO (monadic second order logic). Given a logical formalism L, we will try to see which of the properties expressible in MSO are also expressible in L by exhibiting a decidable characterization of L. By this we mean an algorithm deciding whether a formula of MSO is equivalent to a formula of L or not.

This talk will try to survey the known results in this research area.

This talk is part of the Logic and Semantics Seminar (Computer Laboratory) series.

This talk is included in these lists:

• All Talks (aka the CURE list)
• Cambridge talks
• Computing and Mathematics
• Department of Computer Science and Technology talks and seminars
• Interested Talks
• Logic and Semantics Seminar (Computer Laboratory)
• Room FW26, Computer Laboratory, William Gates Building
• School of Technology
• Trust & Technology Initiative - interesting events
• bld31
• tcw57’s list
• yk373's list

Note that ex-directory lists are not shown.