University of Cambridge > Talks.cam > Logic and Semantics Seminar (Computer Laboratory) > Characterizations of the Expressive Power of Logics over Trees

Characterizations of the Expressive Power of Logics over Trees

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

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.

Tell a friend about this talk:

This talk is included in these lists:

Note that ex-directory lists are not shown.

 

© 2006-2020 Talks.cam, University of Cambridge. Contact Us | Help and Documentation | Privacy and Publicity