Projects funded by the NCN

Information on the principal investigator and host institution

Information of the project and the call

Keywords

Equipment

Delete all

Limits of decidability in automata theory

2012/07/D/ST6/02443

Keywords:

higher-order pushdown automata quantitative extensions of regular languages decidability

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 Paweł Parys 

Number of co-investigators in the project: 2

Call: SONATA 4 - announced on 2012-09-15

Amount awarded: 304 200 PLN

Project start date (Y-m-d): 2013-07-09

Project end date (Y-m-d): 2016-07-08

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

Project status: Project settled

Information in the final report

  • Publication in academic press/journals (3)
  • Articles in post-conference publications (12)
  1. On the Expressive Power of Higher-Order Pushdown Systems
    Authors:
    Paweł Parys
    Academic press:
    Logical Methods in Computer Science (rok: 2017, ), Wydawca: Technische Universität Braunschweig
    Status:
    Submitted
    DOI:
    brak - link to the publication
  2. A Characterization of Lambda-terms Transforming Numerals
    Authors:
    Paweł Parys
    Academic press:
    Journal of Functional Programming (rok: 2016, tom: 26, strony: artykuł nr 12 (36 stron)), Wydawca: Cambridge University Press
    Status:
    Published
    DOI:
    10.1017/S0956796816000113 - link to the publication
  3. Separation Property for wB- and wS-regular Languages.
    Authors:
    Michał Skrzypczak
    Academic press:
    Logical Methods in Computer Science (rok: 2014, tom: 10 (1), strony: artykuł nr 8 (20 stron)), Wydawca: Technische Universität Braunschweig
    Status:
    Published
    DOI:
    10.2168/LMCS-10(1:8)2014 - link to the publication
  1. Measure Quantifier in Monadic Second Order Logic
    Authors:
    Henryk Michalewski, Matteo Mio
    Conference:
    Logical Foundations of Computer Science - International Symposium, LFCS 2016 (rok: 2016, ), Wydawca: Springer
    Data:
    konferencja 4-7.01.2016
    Status:
    Published
    DOI:
    link to the publication
  2. The Diagonal Problem for Higher-Order Recursion Schemes is Decidable
    Authors:
    Lorenzo Clemente, Pawel Parys, Sylvain Salvati, Igor Walukiewicz
    Conference:
    Thirty-First Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2016 (rok: 2016, ), Wydawca: IEEE Computer Society
    Data:
    konferencja 5-8.07.2016
    Status:
    Published
  3. Intersection Types and Counting
    Authors:
    Paweł Parys
    Conference:
    Eighth Workshop on Intersection Types and Related Systems, ITRS 2016 (rok: 2016, ), Wydawca: Electronic Proceedings in Theoretical Computer Science
    Data:
    konferencja 26.06.2016
    Status:
    Published
    DOI:
    link to the publication
  4. On the Regular Emptiness Problem of Subzero Automata
    Authors:
    Matteo Mio, Henryk Michalewski and Mikołaj Bojańczyk
    Conference:
    9th Interaction and Concurrency Experience, ICE 2016 (rok: 2016, ), Wydawca: Electronic Proceedings in Theoretical Computer Science
    Data:
    konferencja 8-9.06.2016
    Status:
    Published
    DOI:
    link to the publication
  5. Deciding the Topological Complexity of Büchi Languages
    Authors:
    Michał Skrzypczak, Igor Walukiewicz
    Conference:
    43rd International Colloquium on Automata, Languages, and Programming (rok: 2016, ), Wydawca: Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik
    Data:
    konferencja 12-15.07.2016
    Status:
    Published
    DOI:
    link to the publication
  6. Models of Lambda-Calculus and the Weak MSO Logic
    Authors:
    Paweł Parys, Szymon Toruńczyk
    Conference:
    25th EACSL Annual Conference on Computer Science Logic, CSL 2016 (rok: 2016, ), Wydawca: Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik
    Data:
    konferencja 29.08-1.09.2016
    Status:
    Published
    DOI:
    link to the publication
  7. On the Decidability of MSO+U on Infinite Trees
    Authors:
    Mikołaj Bojańczyk, Tomasz Gogacz, Henryk Michalewski, Michał Skrzypczak
    Conference:
    Automata, Languages, and Programming - 41st International Colloquium, ICALP 2014 (rok: 2014, ), Wydawca: Springer
    Data:
    konferencja 8-11.07.2014
    Status:
    Published
    DOI:
    link to the publication
  8. Ordered Tree-Pushdown Systems
    Authors:
    Lorenzo Clemente, Paweł Parys, Sylvain Salvati, Igor Walukiewicz
    Conference:
    35th IARCS Annual Conference on Foundation of Software Technology and Theoretical Computer Science, FSTTCS 2015 (rok: 2015, ), Wydawca: Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik
    Data:
    konferencja 16-18.12.2015
    Status:
    Published
    DOI:
    link to the publication
  9. Cost Functions Definable by Min/Max Automata
    Authors:
    Thomas Colcombet, Denis Kuperberg, Amaldev Manuel, Szymon Toruńczyk
    Conference:
    33rd Symposium on Theoretical Aspects of Computer Science, STACS 2016 (rok: 2016, ), Wydawca: Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik
    Data:
    konferencja 17-20.02.2016
    Status:
    Published
    DOI:
    link to the publication
  10. How Many Numbers Can a Lambda-Term Contain?
    Authors:
    Paweł Parys
    Conference:
    Functional and Logic Programming - 12th International Symposium, FLOPS 2014 (rok: 2014, ), Wydawca: Springer
    Data:
    konferencja 4-6.06.2014
    Status:
    Published
    DOI:
    link to the publication
  11. First-Order Logic on CPDA Graphs
    Authors:
    Paweł Parys
    Conference:
    Computer Science - Theory and Applications - 9th International Computer Science Symposium in Russia, CSR 2014 (rok: 2014, ), Wydawca: Springer
    Data:
    konferencja 7-11.06.2014
    Status:
    Published
    DOI:
    link to the publication
  12. The MSO+U Theory of (N, <) Is Undecidable
    Authors:
    Mikołaj Bojańczyk, Paweł Parys, Szymon Toruńczyk
    Conference:
    33rd Symposium on Theoretical Aspects of Computer Science, STACS 2016 (rok: 2016, ), Wydawca: Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik
    Data:
    konferencja 17-20.02.2016
    Status:
    Published
    DOI:
    link to the publication

O Narodowym Centrum Nauki

Finansowanie nauki

Współpraca zagraniczna

Centrum prasowe

Deklaracja dostępności
Przetwarzanie danych osobowych
Polityka cookies

Partnerzy