Projects funded by the NCN

Information on the principal investigator and host institution

Information of the project and the call

Keywords

Equipment

Delete all

Synchronization of automata and the Cerny conjecture

2013/09/N/ST6/01194

Keywords:

synchronizing automaton reset word Cerny conjecture

Descriptors:

  • ST6_4: Formal methods, foundations of computer science, including theoretical computer science, quantum algorithms
  • ST6_6: Algorithms, parallel, distributed and network algorithms, algorithmic game theory
  • ST1_15: Mathematical aspects of computer science

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: 2

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

Amount awarded: 76 550 PLN

Project start date (Y-m-d): 2014-03-25

Project end date (Y-m-d): 2016-03-24

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

Project status: Project settled

Equipment purchased [PL]

  1. Komputer stacjonarny dobrej klasy (7 000 PLN)

Information in the final report

  • Publication in academic press/journals (2)
  • Articles in post-conference publications (10)
  1. Forward and backward synchronizing algorithms
    Authors:
    Adam Roman, Marek Szykuła
    Academic press:
    Expert Systems with Applications (rok: 2015, tom: 42, strony: 9512--9527), Wydawca: Elsevier
    Status:
    Published
    DOI:
    10.1016/j.eswa.2015.07.071 - link to the publication
  2. Syntactic Complexity of Regular Ideals
    Authors:
    Janusz Brzozowski, Marek Szykuła, Yuli Ye
    Academic press:
    Theory of Computing Systems (rok: 2018, tom: 62, strony: 1175--1202), Wydawca: Elsevier
    Status:
    Published
    DOI:
    10.1007/s00224-017-9803-8 - link to the publication
  1. Synchronizing Automata with Extremal Properties
    Authors:
    Andrzej Kisielewicz, Marek Szykuła
    Conference:
    40th International Symposium on Mathematical Foundations of Computer Science (MFCS 2015) (rok: 2015, ), Wydawca: Springer Berlin Heidelberg
    Data:
    konferencja 24.08.2015--28.08.2015
    Status:
    Published
  2. Upper Bounds on Syntactic Complexity of Left and Two-Sided Ideals
    Authors:
    Janusz Brzozowski, Marek Szykuła
    Conference:
    18th International Conference on Developments in Language Theory (rok: 2014, ), Wydawca: Springer International Publishing
    Data:
    konferencja 26.08.2014 - 29.08.2014
    Status:
    Published
    DOI:
    link to the publication
  3. Complexity of Suffix-Free Regular Languages
    Authors:
    Janusz Brzozowski, Marek Szykuła
    Conference:
    20th International Symposium on Fundamentals of Computation Theory (FCT 2015) (rok: 2015, ), Wydawca: Springer International Publishing
    Data:
    konferencja 17.08.2015--19.08.2015
    Status:
    Published
  4. Evolving Chess-like Games Using Relative Algorithm Performance Profiles
    Authors:
    Jakub Kowalski, Marek Szykuła
    Conference:
    19th European Conference on the Applications of Evolutionary Computation (EvoApplications 2015) (rok: 2015, ), Wydawca: Springer International Publishing
    Data:
    konferencja 30.03.2016--01.04.2016
    Status:
    Published
  5. Experiments with Synchronizing Automata
    Authors:
    Andrzej Kisielewicz, Jakub Kowalski, Marek Szykuła
    Conference:
    21st International Conference on Implementation and Application of Automata (CIAA 2016) (rok: 2016, ), Wydawca: Springer International Publishing
    Data:
    konferencja 19.07.2016--22.07.2016
    Status:
    Published
  6. Large Aperiodic Semigroups
    Authors:
    Janusz Brzozowski, Marek Szykuła
    Conference:
    19th International Conference Implementation and Application of Automata (rok: 2014, ), Wydawca: Springer International Publishing
    Data:
    konferencja 30.07.2014 - 02.08.2014
    Status:
    Published
    DOI:
    link to the publication
  7. Algebraic Synchronization Criterion and Computing Reset Words
    Authors:
    Mikhail Berlinkov, Marek Szykuła
    Conference:
    40th International Symposium on Mathematical Foundations of Computer Science (MFCS 2015) (rok: 2015, ), Wydawca: Springer Berlin Heidelberg
    Data:
    konferencja 24.08.2015--28.08.2015
    Status:
    Published
  8. Checking Whether an Automaton Is Monotonic Is NP-complete
    Authors:
    Marek Szykuła
    Conference:
    20th International Conference on Implementation and Application of Automata (CIAA 2015) (rok: 2015, ), Wydawca: Springer International Publishing
    Data:
    konferencja 18.08.2015--21.08.2015
    Status:
    Published
  9. On the Number of Synchronizing Colorings of Digraphs
    Authors:
    Vladimir V. Gusev, Marek Szykuła
    Conference:
    20th International Conference on Implementation and Application of Automata (CIAA 2015) (rok: 2015, ), Wydawca: Springer International Publishing
    Data:
    konferencja 18.08.2015--21.08.2015
    Status:
    Published
  10. Upper Bound on Syntactic Complexity of Suffix-Free Languages
    Authors:
    Janusz Brzozowski, Marek Szykuła
    Conference:
    17th International Workshop on Descriptional Complexity of Formal Systems (DCFS 2015) (rok: 2015, ), Wydawca: Springer International Publishing
    Data:
    konferencja 25.06.2015--27.06.2015
    Status:
    Published

O Narodowym Centrum Nauki

Finansowanie nauki

Współpraca zagraniczna

Centrum prasowe

Deklaracja dostępności
Przetwarzanie danych osobowych
Polityka cookies

Partnerzy