Projects funded by the NCN


Information on the principal investigator and host institution

Information of the project and the call

Keywords

Equipment

Delete all

Frontiers of tractability for recursive queries

2013/09/N/ST6/01170

Keywords:

complexity logic datalog xml trees

Descriptors:

  • ST6_4: Formal methods, foundations of computer science, including theoretical computer science, quantum algorithms

Panel:

ST6 - Computer science and informatics: informatics and information systems, computer science, scientific computing, intelligent systems

Host institution :

Uniwersytet Warszawski, Wydział Matematyki, Informatyki i Mechaniki

woj. mazowieckie

Other projects carried out by the institution 

Principal investigator (from the host institution):

dr Filip Mazowiecki 

Number of co-investigators in the project: 3

Call: PRELUDIUM 5 - announced on 2013-03-15

Amount awarded: 96 300 PLN

Project start date (Y-m-d): 2014-02-21

Project end date (Y-m-d): 2016-02-20

Project duration:: 24 months (the same as in the proposal)

Project status: Project settled

Equipment purchased [PL]

  1. Komputer stacjonarny (4 000 PLN)

Information in the final report

  • Publication in academic press/journals (2)
  • Articles in post-conference publications (4)
  1. Complexity of Two-variable Logic on Finite Trees
    Authors:
    Saguy Benaim, Michael Benedikt, Witold Charatonik, Emanuel Kieronski, Rastislav Lenhardt, Filip Mazowiecki, James Worrell
    Academic press:
    ACM Transactions on Computational Logic (TOCL) (rok: 2016, tom: 17, strony: 32:1--32:38), Wydawca: ACM
    Status:
    Published
  2. Monadic datalog and regular tree pattern queries
    Authors:
    Filip Mazowiecki, Filip Murlak, Adam Witkowski
    Academic press:
    ACM Transactions on Database Systems (TODS) (rok: 2016, tom: 41, strony: 20:1--20:43), Wydawca: ACM
    Status:
    Published
  1. Maximal Partition Logic: Towards a Logical Characterization of Copyless Cost Register Automata
    Authors:
    Filip Mazowiecki, Cristian Riveros
    Conference:
    CSL (rok: 2015, ), Wydawca: Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik
    Data:
    konferencja 7-10.9.2015
    Status:
    Published
  2. Decidability of weak logics with deterministic transitive closure
    Authors:
    Witold Charatonik, Emanuel Kieroński, Filip Mazowiecki
    Conference:
    CSL-LICS (rok: 2014, ), Wydawca: ACM
    Data:
    konferencja Lipiec 14 - 18, 2014
    Status:
    Published
  3. Eliminating Recursion from Monadic Datalog Programs on Trees
    Authors:
    Filip Mazowiecki, Joanna Ochremiak, Adam Witkowski
    Conference:
    MFCS (rok: 2015, ), Wydawca: Springer
    Data:
    konferencja 24-28.08.2015
    Status:
    Published
  4. Monadic Datalog and Regular Tree Pattern Queries
    Authors:
    Filip Mazowiecki, Filip Murlak, Adam Witkowski
    Conference:
    MFCS (rok: 2014, ), Wydawca: Springer
    Data:
    konferencja Sierpień 25-29
    Status:
    Published