Marek Szykuła

msz (at) cs (dot) uni (dot) wroc (dot) pl


Teaching (in Polish)
  • Wstęp do programowania w języku C (pracownia): wtorek 12:15 -- 14:00 [strona wykładu]
  • Sztuczna inteligencja w grach (pracownia): środa 14:15 -- 16:00 [strona wykładu]
  • Seminarium: O automatach skończonych (seminarium): środa 16:14 -- 18:00 [strona seminarium]
Konsultacje: wtorek 16:15 -- 17:00, środa 13:15 -- 14:00. Proszę o powiadomienie e-mailem.



Research papers

-- (with Janusz A. Brzozowski, Lila Kari, and Bai Li) State Complexity of Overlap Assembly. [arxiv]

-- (with Igor Podolak, Adam Roman, and Bartosz Zieliński) A machine learning approach to synchronization of automata.

-- (with Mikhail V. Berlinkov and Robert Ferens) Extending word problems in deterministic finite automata. [arxiv]

-- Improving the upper bound on the length of the shortest reset words. [arxiv]

-- (with Paweł Gawrychowski, Narad Rampersad, and Jeffrey Shallit) Existential length universality. [arxiv]

-- (with Janusz A. Brzozowski and Yuli Ye) Syntactic complexity of regular ideals. [link] [arxiv]
Accepted to Theory of Computing Systems. 2017.

-- (with Janusz A. Brzozowski) Syntactic complexity of suffix-free languages. [link] [arxiv]
Accepted to Information and Computation. 2017.

-- (with Michalina Dżyga, Robert Ferens, and Vladimir V. Gusev) Attainable values of reset thresholds. [link]
Accepted to MFCS 2017.

[24] (with Vladimir V. Gusev and Elena Pribavkina) Around the Road Coloring Theorem. [link]
Proceedings of the Fourth Russian Finnish Symposium on Discrete Mathematics (RuFiDim 2017), volume 26 of TUCS Lecture Notes, pages 52--56, 2017.

[23] (with Janusz A. Brzozowski) Complexity of suffix-free regular languages. [link] [arxiv]
Journal of Computer and System Sciences 89:270--287, 2017.

[22] (with John Wittnebel) Syntactic Complexity of Bifix-Free Languages. [link] [arxiv]
In Implementation and Application of Automata (CIAA 2017), volume 10329 of LNCS, pages 201--212, 2017.

[21] (with Robert Ferens) Complexity of Bifix-Free Regular Languages. [link] [arxiv]
In Implementation and Application of Automata (CIAA 2017), volume 10329 of LNCS, pages 76--88, 2017.

[20] (with Mikhail V. Berlinkov) Algebraic synchronization criterion and computing reset words. [link] [arxiv]
Information Sciences 369:718--730, 2016.

[19] (with Vojtěch Vorel) An Extremal Series of Eulerian Synchronizing Automata. [link] [arxiv]
In Developments in Language Theory (DLT 2016), volume 9840 of LNCS, pages 380--392, 2016.

[18] (with Andrzej Kisielewicz and Jakub Kowalski) Experiments with Synchronizing Automata. [link] [arxiv]
In Implementation and Application of Automata (CIAA 2016), volume 9705 of LNCS, pages 176--188, 2016.

[17] (with Janusz A. Brzozowski, Galina Jirásková, Bo Liu, and Aayush Rajasekaran) On the State Complexity of the Shuffle of Regular Languages. [link] [arxiv]
In Descriptional Complexity of Formal Systems (DCFS 2016), volume 9777 of LNCS, pages 73--86, 2016.

[16] (with Jakub Kowalski) Evolving Chesslike Games Using Relative Algorithm Performance Profiles. [link]
In Applications of Evolutionary Computation (Evostar: EvoApplications 2016), volume 9597 of LNCS, pages 574--589, 2016.

[15] (with Janusz A. Brzozowski) Large aperiodic semigroups. [link] [arxiv]
International Journal of Foundations of Computer Science 26(7):913--931, 2015.

[14] (with Adam Roman) Forward and backward synchronizing algorithms. [link]
Expert Systems With Applications 42(24):9512--9527, 2015.

[13] (with Andrzej Kisielewicz) Synchronizing Automata with Extremal Properties. [link] [arxiv]
In Mathematical Foundations of Computer Science (MFCS 2015), volume 9234 of LNCS, pages 331--343, 2015.

[12] (with Mikhail V. Berlinkov) Algebraic Synchronization Criterion and Computing Reset Words. [link] [arxiv]
In Mathematical Foundations of Computer Science (MFCS 2015), volume 9234 of LNCS, pages 103--115, 2015.

[11] (with Janusz A. Brzozowski) Complexity of Suffix-Free Languages. [link] [arxiv]
In Fundamentals of Computation Theory (FCT 2015), volume 9210 of LNCS, pages 146--159, 2015.

[10] (with Vladimir V. Gusev) On the Number of Synchronizing Colorings of Digraphs. [link] [arxiv]
In Implementation and Application of Automata (CIAA 2015), volume 9223 of LNCS, pages 127--139, 2015.

[9] Checking Whether an Automaton Is Monotonic Is NP-complete. [link] [arxiv]
In Implementation and Application of Automata (CIAA 2015), volume 9223 of LNCS, pages 279--291, 2015.

[8] (with Janusz A. Brzozowski) Upper Bound on Syntactic Complexity of Suffix-Free Languages. [link] [arxiv]
In Descriptional Complexity of Formal Systems (DCFS 2015), volume 9118 of LNCS, pages 33--45, 2015.

[7] (with Andrzej Kisielewicz and Jakub Kowalski) Computing the shortest reset words of synchronizing automata. [link]
Journal of Combinatorial Optimization, 29(1):88--124, 2015.

[6] (with Janusz A. Brzozowski) Upper Bounds on Syntactic Complexity of Left and Two-Sided Ideals. [link] [arxiv]
In Developments in Language Theory (DLT 2014), volume 8633 of LNCS, pages 13--24, 2014.

[5] (with Janusz A. Brzozowski) Large Aperiodic Semigroups. [link] [arxiv]
In Implementation and Application of Automata (CIAA 2014), volume 8587 of LNCS, pages 124--135, 2014.

[4] (with Jakub Kowalski) Game Description Language Compiler Construction. [link]
In AI 2013: Advances in Artificial Intelligence (AUS-AI 2013), volume 8272 of LNCS, pages 234--245, 2013.

[3] (with Andrzej Kisielewicz) Generating Small Automata and the Černý Conjecture. [link]
In Implementation and Application of Automata (CIAA 2013), volume 7982 of LNCS, pages 340--348, 2013.

[2] (with Andrzej Kisielewicz and Jakub Kowalski) A Fast Algorithm Finding the Shortest Reset Words. [link] [arxiv]
In Computing and Combinatorics (COCOON 2013), volume 7936 of LNCS, pages 182--196, 2013.

[1] (with Andrzej Kisielewicz) Rainbow induced subgraphs in proper vertex colorings. [link]
Fundamenta Informaticae, 111(4):437--451, 2011.