Marek Szykuła

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


Teaching (in Polish)

Przerwa wakacyjna.



Research papers

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

[32] (with Mikhail V. Berlinkov and Robert Ferens) Complexity of Preimage Problems for Deterministic Finite Automata. [link] [arxiv]
In Mathematical Foundations of Computer Science (MFCS 2018), volume 117 of LIPIcs, pages 32:1--32:14, 2018.

[31] (with Andrew Ryzhikov) Finding Short Synchronizing Words for Prefix Codes. [link] [arxiv]
In Mathematical Foundations of Computer Science (MFCS 2018), volume 117 of LIPIcs, pages 21:1--21:14, 2018.

[30] (with Janusz A. Brzozowski, Lila Kari, and Bai Li) State Complexity of Overlap Assembly. [link] [arxiv]
In Implementation and Application of Automata (CIAA 2018), volume 10977 of LNCS, pages 109--120, 2018. Best paper award.

[29] (with Janusz A. Brzozowski and Yuli Ye) Syntactic complexity of regular ideals. [link] [arxiv]
Theory of Computing Systems, 62(5):1175--1202, 2018.

[28] (with Janusz A. Brzozowski) Syntactic complexity of suffix-free languages. [link] [arxiv]
Information and Computation, 259:174--190, 2018.

[27] Improving the Upper Bound on the Length of the Shortest Reset Words. [link] [arxiv]
In Symposium on Theoretical Aspects of Computer Science (STACS 2018), volume 96 of LIPIcs, pages 56:1--56:13, 2018.

[26] (with Igor Podolak, Adam Roman, and Bartosz Zieliński) A machine learning approach to synchronization of automata. [link]
Expert Systems with Applications, 97:357--371, 2018.

[25] (with Michalina Dżyga, Robert Ferens, and Vladimir V. Gusev) Attainable Values of Reset Thresholds. [link]
In Mathematical Foundations of Computer Science (MFCS 2017), volume 83 of LIPIcs, pages 40:1--40:14, 2017.

[24] (with Vladimir V. Gusev and Elena Pribavkina) Around the Road Coloring Theorem. [link]
In 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.