Projects funded by the NCN

Information on the principal investigator and host institution

Information of the project and the call

Keywords

Equipment

Delete all

Classical problems in the theory of finite automata: new approaches, variants, and applications

2017/25/B/ST6/01920

Keywords:

avoiding word finite automaton general game playing regular language universality

Descriptors:

  • ST6_4: Formal methods, foundations of computer science, including theoretical computer science, quantum algorithms
  • ST1_15: Mathematical aspects of computer science
  • ST6_7: Artificial intelligence, intelligent systems, multi-agent systems

Panel:

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

Host institution :

Uniwersytet Wrocławski, Wydział Matematyki i Informatyki

woj. dolnośląskie

Other projects carried out by the institution 

Principal investigator (from the host institution):

dr Marek Szykuła 

Number of co-investigators in the project: 5

Call: OPUS 13 - announced on 2017-03-15

Amount awarded: 520 400 PLN

Project start date (Y-m-d): 2018-01-19

Project end date (Y-m-d): 2021-07-18

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

Project status: Project settled

Project description

Download the project description in a pdf file

Note - project descriptions were prepared by the authors of the applications themselves and placed in the system in an unchanged form.

Equipment purchased [PL]

  1. Komputer stacjonarny.
  2. Laptop (8 000 PLN)

Information in the final report

  • Publication in academic press/journals (4)
  • Articles in post-conference publications (11)
  1. Complexity of bifix-free regular languages
    Authors:
    Robert Ferens, Marek Szykuła
    Academic press:
    Theoretical Computer Science (rok: 2019, tom: 787, strony: 14--27), Wydawca: Elsevier
    Status:
    Published
    DOI:
    10.1016/j.tcs.2018.09.016 - link to the publication
  2. Preimage problems for deterministic finite automata
    Authors:
    Mikhail V. Berlinkov, Robert Ferens, Marek Szykuła
    Academic press:
    Journal of Computer and System Sciences (rok: 2021, tom: 115, strony: 214-234), Wydawca: Elsevier
    Status:
    Published
    DOI:
    10.1016/j.jcss.2020.08.002 - link to the publication
  3. Syntactic complexity of bifix-free regular languages
    Authors:
    Marek Szykuła, John Wittnebel
    Academic press:
    Theoretical Computer Science (rok: 2019, tom: 787, strony: 45--76), Wydawca: Elsevier
    Status:
    Published
    DOI:
    10.1016/j.tcs.2018.12.025 - link to the publication
  4. The Frobenius and Factor Universality Problems of the Kleene Star of a Finite Set of Words
    Authors:
    Maksymilian Mika, Marek Szykuła
    Academic press:
    Journal of the ACM (rok: 2021, tom: 68, strony: 18:1--18:22), Wydawca: Association for Computing Machinery
    Status:
    Published
    DOI:
    10.1145/3447237 - link to the publication
  1. Evolutionary Approach to Collectible Arena Deckbuilding using Active Card Game Genes
    Authors:
    Jakub Kowalski, Radosław Miernik
    Conference:
    2020 IEEE Congress on Evolutionary Computation (CEC) (rok: 2020, ), Wydawca: IEEE
    Data:
    konferencja 2020.07.19--2020.07.24
    Status:
    Published
  2. Finding Short Synchronizing Words for Prefix Codes
    Authors:
    Andrew Ryzhikov, Marek Szykuła
    Conference:
    43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018) (rok: 2018, ), Wydawca: Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany
    Data:
    konferencja 27.08.2018--31.08.2018
    Status:
    Published
    DOI:
    link to the publication
  3. Lower Bounds on Avoiding Thresholds
    Authors:
    Robert Ferens, Marek Szykuła, Vojtěch Vorel
    Conference:
    46rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2021) (rok: 2021, ), Wydawca: Schloss Dagstuhl -- Leibniz-Zentrum für Informatik, Dagstuhl, Germany
    Data:
    konferencja 2021.08.23--2021.08.27
    Status:
    Published
  4. Efficient Reasoning in Regular Boardgames
    Authors:
    Jakub Kowalski, Radosław Miernik, Maksymilian Mika, Wojciech Pawlik, Jakub Sutowicz, Marek Szykuła, Andrzej Tkaczyk
    Conference:
    IEEE Conference on Games (CoG 2020) (rok: 2020, ), Wydawca: IEEE
    Data:
    konferencja 24.08.2020--27.08.2020
    Status:
    Published
  5. Existential Length Universality
    Authors:
    Paweł Gawrychowski, Martin Lange, Narad Rampersad, Jeffrey Shallit, Marek Szykuła
    Conference:
    37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020) (rok: 2020, ), Wydawca: Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl Publishing, Germany
    Data:
    konferencja 2020-03-10 -- 2020-03-13
    Status:
    Published
  6. Synchronizing Strongly Connected Partial DFAs
    Authors:
    Mikhail V. Berlinkov, Robert Ferens, Andrew Ryzhikov, Marek Szykuła
    Conference:
    Symposium on Theoretical Aspects of Computer Science (STACS 2021) (rok: 2021, ), Wydawca: Schloss Dagstuhl -- Leibniz-Zentrum für Informatik, Dagstuhl Publishing, Germany
    Data:
    konferencja 2021.03.16--2021.03.19
    Status:
    Published
    DOI:
    link to the publication
  7. Complexity of Preimage Problems for Deterministic Finite Automata
    Authors:
    Mikhail V. Berlinkov, Robert Ferens, Marek Szykuła
    Conference:
    43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018) (rok: 2018, ), Wydawca: Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany
    Data:
    konferencja 27.08.2018--31.08.2018
    Status:
    Published
    DOI:
    link to the publication
  8. Experimental Studies in General Game Playing: An Experience Report
    Authors:
    Jakub Kowalski, Marek Szykuła
    Conference:
    AAAI 2020 Workshop on Reproducible AI (RAI@AAAI 2020) (rok: 2020, ), Wydawca: --
    Data:
    konferencja 43868
    Status:
    Published
  9. Regular Language Inference for Learning Rules of Simplified Boardgames
    Authors:
    Jakub Kowalski, Andrzej Kisielewicz
    Conference:
    IEEE Conference on Computational Intelligence and Games (CIG) (rok: 2018, ), Wydawca: IEEE
    Data:
    konferencja 14.08.2018 -- 17.08.2018
    Status:
    Published
  10. Improving the Upper Bound on the Length of the Shortest Reset Words
    Authors:
    Marek Szykuła
    Conference:
    35th Symposium on Theoretical Aspects of Computer Science (STACS 2018) (rok: 2018, ), Wydawca: Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl Publishing, Germany
    Data:
    konferencja 28.02.2018--3.03.2018
    Status:
    Published
    DOI:
    link to the publication
  11. Regular Boardgames
    Authors:
    Jakub Kowalski, Maksymilian Mika, Jakub Sutowicz, Marek Szykuła
    Conference:
    AAAI Conference on Artificial Intelligence (rok: 2019, ), Wydawca: AAAI Press
    Data:
    konferencja 27.01.2019 -- 1.02.2019
    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