The research: Logic in Computer Science

A group of our young logicians has actively contributed to the area of logic for databases (6 papers on the top conference PODS since 2006), in particular, to the issues of algorithms for query evaluation on XML data (Bojanczyk and Parys), and translations between databases (Murlak). A crucial challenge is the potential infinity of the data values to be stored (e.g., natural numbers). Searching for the right model, Bojanczyk at al. (POPL 2012) proposed the use of theory of nominal sets, originally introduced by Fraenkel and Mostowski (in the 1930s) as a permutation model of the set theory. This theory extends the concept of finiteness to orbit-finiteness, which opens a way for a wide application of the automata-theoretic techniques to the query evaluation over infinite data.

Automata theory has been a traditional topic at MIMUW; the work by Bojanczyk, Murlak, Niwinski, Parys, Urzyczyn and others addresses the expressiveness and decidability issues of various models of tree automata. Another ambitious direction pursued in co-operation with several European universities (Edinburgh, Frankfurt, London, Paris, Rome), is an extension of the tree paradigm underlying XML to a unifying graph data paradigm.

A project of Tarlecki focuses on logical foundations of the semantics of programming languages. It aims at a general, modular, extensible, and practical formalism for semantic descriptions of programming and process languages, using universal algebra and category theory to mix the best of denotational and operational semantics. The plan relies on capitalising the experience, and on extensive collaboration with leading European centers such as Edinburgh, Cambridge, Munich, Pisa, and others.

Another project concerns the database query language 4QL, developed by Szalas, Dunin-Keplicz, and A.L.Nguyen in collaboration with the University of Linkoping (Sweden). It is founded on a four-valued semantics which can be traced back to Lukasiewicz logic. The planned research concerns, in particular, an application in the Semantic Web services.

Exploration of Semantic Web is also a subject of the research project SYNAT, developed by Skowron, Slezak, and H.S.Nguyen and their team. The theoretical foundation of this project is based on theory of rough sets, founded by Pawlak and Rasiowa in the 1980s. The Warsaw group is inspired by the concept of computational wisdom and focuses on creation of the modules that provide learning and searching capabilities for the storage of scientific documents.