Marek Szykuła

Teaching

Konsultacje: e-mail | Discord | Teams

Archiwum prac dyplomowych | Archiwum zajęć

Papers (orcid | scholar)

[46] (with Robert Ferens) Completely Reachable Automata: A Polynomial Algorithm and Quadratic Upper Bounds. [doi] [arxiv]
In International Colloquium on Automata, Languages, and Programming (ICALP 2023), volume 261 of LIPIcs, pages 59:1--59:17, 2023.

[45] (with Adam Zyzik) An Improved Algorithm for Finding the Shortest Synchronizing Words. [doi] [arxiv]
In European Symposium on Algorithms (ESA 2022), volume 244 of LIPIcs, pages 85:1--85:15, 2022.

[44] (with Jakub Kowalski, Maksymilian Mika, Wojciech Pawlik, Jakub Sutowicz, and Mark H. Winands) Split Moves for Monte-Carlo Tree Search. [doi] [arxiv]
In Proceedings of the AAAI Conference on Artificial Intelligence (AAAI 2022), volume 36(9), pages 10247--10255, 2022.

[43] (with Robert Ferens and Vojtěch Vorel) Lower Bounds on Avoiding Thresholds. [doi]
In Mathematical Foundations of Computer Science (MFCS 2021), volume 202 of LIPIcs, pages 46:1--46:14, 2021.

[42] (with Maksymilian Mika) The Frobenius and Factor Universality Problems of the Kleene Star of a Finite Set of Words. [doi] [arxiv]
Journal of the ACM, 68(3), 18:1--18:22, 2021.

[41] (with Mikhail V. Berlinkov, Robert Ferens, and Andrew Ryzhikov) Synchronizing Strongly Connected Partial DFAs. [doi] [arxiv]
In Symposium on Theoretical Aspects of Computer Science (STACS 2021), volume 187 of LIPIcs, pages 12:1--12:16, 2021.

[40] (with Mikhail V. Berlinkov and Robert Ferens) Preimage problems for deterministic finite automata. [doi] [arxiv]
Journal of Computer and System Sciences, 115:214--234, 2021.

[39] (with Janusz A. Brzozowski, Lila Kari, and Bai Li) State Complexity of Overlap Assembly. [doi] [arxiv]
International Journal of Foundations of Computer Science, 31(8):1113--1132, 2020.

[38] (with Jakub Kowalski, Radosław Miernik, Maksymilian Mika, Wojciech Pawlik, Jakub Sutowicz, and Andrzej Tkaczyk) Efficient Reasoning in Regular Boardgames. [doi] [arxiv]
In IEEE Conference on Games (CoG 2020), pages 455--462, 2020.

[37] (with Paweł Gawrychowski, Martin Lange, Narad Rampersad, and Jeffrey Shallit) Existential Length Universality. [doi] [arxiv]
In Symposium on Theoretical Aspects of Computer Science (STACS 2020), volume 154 of LIPIcs, pages 16:1--16:14, 2020.

[36] (with Jakub Kowalski) Experimental Studies in General Game Playing: An Experience Report. [link] [arxiv]
AAAI 2020 Workshop on Reproducible AI (RAI@AAAI 2020), 2020.

[35] (with John Wittnebel) Syntactic complexity of bifix-free regular languages. [doi] [arxiv]
Theoretical Computer Science, 787:45--76, 2019.

[34] (with Robert Ferens) Complexity of bifix-free regular languages. [doi] [arxiv]
Theoretical Computer Science, 787:14--27, 2019.

[33] (with Jakub Kowalski, Maksymilian Mika, and Jakub Sutowicz) Regular Boardgames. [doi] [arxiv]
In Proceedings of the AAAI Conference on Artificial Intelligence (AAAI 2019), volume 33(01), pages 1699--1706, 2019.

[32] (with Mikhail V. Berlinkov and Robert Ferens) Complexity of Preimage Problems for Deterministic Finite Automata. [doi] [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. [doi] [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. [doi] [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. [doi] [arxiv]
Theory of Computing Systems, 62(5):1175--1202, 2018.

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

[27] Improving the Upper Bound on the Length of the Shortest Reset Words. [doi] [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. [doi]
Expert Systems with Applications, 97:357--371, 2018.

[25] (with Michalina Dżyga, Robert Ferens, and Vladimir V. Gusev) Attainable Values of Reset Thresholds. [doi]
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. [doi] [arxiv]
Journal of Computer and System Sciences, 89:270--287, 2017.

[22] (with John Wittnebel) Syntactic Complexity of Bifix-Free Languages. [doi] [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. [doi] [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. [doi] [arxiv]
Information Sciences, 369:718--730, 2016.

[19] (with Vojtěch Vorel) An Extremal Series of Eulerian Synchronizing Automata. [doi] [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. [doi] [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. [doi] [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. [doi]
In Applications of Evolutionary Computation (Evostar: EvoApplications 2016), volume 9597 of LNCS, pages 574--589, 2016.

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

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

[13] (with Andrzej Kisielewicz) Synchronizing Automata with Extremal Properties. [doi] [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. [doi] [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. [doi] [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. [doi] [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. [doi] [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. [doi] [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. [doi]
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. [doi] [arxiv]
In Developments in Language Theory (DLT 2014), volume 8633 of LNCS, pages 13--24, 2014.

[5] (with Janusz A. Brzozowski) Large Aperiodic Semigroups. [doi] [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. [doi]
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. [doi]
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. [doi] [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. [doi]
Fundamenta Informaticae, 111(4):437--451, 2011.