Projekty finansowane przez NCN


Dane kierownika projektu i jednostki realizującej

Szczegółowe informacje o projekcie i konkursie

Słowa kluczowe

Aparatura

Wyczyść formularz

Granice rozstrzygalności w teorii automatów

2012/07/D/ST6/02443

Słowa kluczowe:

automaty ze stosem wyższego rzędu ilościowe rozszerzenia języków regularnych rozstrzygalność

Deskryptory:

  • ST6_4: Metody formalne, teoretyczne podstawy informatyki w tym informatyka teoretyczna

Panel:

ST6 - Informatyka i technologie informacyjne: technologie i systemy informacyjne, informatyka, obliczenia naukowe, systemy inteligentne, m.in.:

Jednostka realizująca:

Uniwersytet Warszawski, Wydział Matematyki, Informatyki i Mechaniki

woj. mazowieckie

Inne projekty tej jednostki 

Kierownik projektu (z jednostki realizującej):

dr Paweł Parys 

Liczba wykonawców projektu: 2

Konkurs: SONATA 4 - ogłoszony 2012-09-15

Przyznana kwota: 304 200 PLN

Rozpoczęcie projektu: 2013-07-09

Zakończenie projektu: 2016-07-08

Planowany czas trwania projektu: 36 miesięcy (z wniosku)

Status projektu: Projekt rozliczony

Dane z raportu końcowego

  • Publikacje w czasopismach (3)
  • Teksty w publikacjach pokonferencyjnych (12)
  1. A Characterization of Lambda-terms Transforming Numerals IF: ,784
    Autorzy:
    Paweł Parys
    Czasopismo:
    Journal of Functional Programming (rok: 2016, tom: 26, strony: artykuł nr 12 (36 stron)), Wydawca: Cambridge University Press
    Status:
    Opublikowane
    Doi:
    10.1017/S0956796816000113 - link do publikacji
  2. Separation Property for wB- and wS-regular Languages. IF: ,443
    Autorzy:
    Michał Skrzypczak
    Czasopismo:
    Logical Methods in Computer Science (rok: 2014, tom: 10 (1), strony: artykuł nr 8 (20 stron)), Wydawca: Technische Universität Braunschweig
    Status:
    Opublikowane
    Doi:
    10.2168/LMCS-10(1:8)2014 - link do publikacji
  3. On the Expressive Power of Higher-Order Pushdown Systems
    Autorzy:
    Paweł Parys
    Status:
    Złożone
  1. How Many Numbers Can a Lambda-Term Contain?
    Autorzy:
    Paweł Parys
    Konferencja:
    Functional and Logic Programming - 12th International Symposium, FLOPS 2014 (rok: 2014, ), Wydawca: Springer
    Data:
    konferencja 4-6.06.2014
    Status:
    Opublikowane
  2. Intersection Types and Counting
    Autorzy:
    Paweł Parys
    Konferencja:
    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:
    Opublikowane
  3. On the Decidability of MSO+U on Infinite Trees
    Autorzy:
    Mikołaj Bojańczyk, Tomasz Gogacz, Henryk Michalewski, Michał Skrzypczak
    Konferencja:
    Automata, Languages, and Programming - 41st International Colloquium, ICALP 2014 (rok: 2014, ), Wydawca: Springer
    Data:
    konferencja 8-11.07.2014
    Status:
    Opublikowane
  4. Ordered Tree-Pushdown Systems
    Autorzy:
    Lorenzo Clemente, Paweł Parys, Sylvain Salvati, Igor Walukiewicz
    Konferencja:
    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:
    Opublikowane
  5. Deciding the Topological Complexity of Büchi Languages
    Autorzy:
    Michał Skrzypczak, Igor Walukiewicz
    Konferencja:
    43rd International Colloquium on Automata, Languages, and Programming (rok: 2016, ), Wydawca: Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik
    Data:
    konferencja 12-15.07.2016
    Status:
    Opublikowane
  6. On the Regular Emptiness Problem of Subzero Automata
    Autorzy:
    Matteo Mio, Henryk Michalewski and Mikołaj Bojańczyk
    Konferencja:
    9th Interaction and Concurrency Experience, ICE 2016 (rok: 2016, ), Wydawca: Electronic Proceedings in Theoretical Computer Science
    Data:
    konferencja 8-9.06.2016
    Status:
    Opublikowane
  7. First-Order Logic on CPDA Graphs
    Autorzy:
    Paweł Parys
    Konferencja:
    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:
    Opublikowane
  8. Models of Lambda-Calculus and the Weak MSO Logic
    Autorzy:
    Paweł Parys, Szymon Toruńczyk
    Konferencja:
    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:
    Opublikowane
  9. Cost Functions Definable by Min/Max Automata
    Autorzy:
    Thomas Colcombet, Denis Kuperberg, Amaldev Manuel, Szymon Toruńczyk
    Konferencja:
    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:
    Opublikowane
  10. Measure Quantifier in Monadic Second Order Logic
    Autorzy:
    Henryk Michalewski, Matteo Mio
    Konferencja:
    Logical Foundations of Computer Science - International Symposium, LFCS 2016 (rok: 2016, ), Wydawca: Springer
    Data:
    konferencja 4-7.01.2016
    Status:
    Opublikowane
  11. The Diagonal Problem for Higher-Order Recursion Schemes is Decidable
    Autorzy:
    Lorenzo Clemente, Pawel Parys, Sylvain Salvati, Igor Walukiewicz
    Konferencja:
    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:
    Opublikowane
  12. The MSO+U Theory of (N, <) Is Undecidable
    Autorzy:
    Mikołaj Bojańczyk, Paweł Parys, Szymon Toruńczyk
    Konferencja:
    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:
    Opublikowane