Marek Szykuła

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


Teaching (in Polish)

Zajęcia w semestrze letnim 2016/2017:
  • Algorytmy i struktury danych (ćwiczenia): czwartek 10:15 -- 12:00. s. 4. [strona przedmiotu]
Konsultacje: wtorek 14:15 -- 16:00; proszę umawiać się e-mailem.



Research papers

-- (with Michalina Dżyga, Robert Ferens, and Vladimir V. Gusev) Attainable values of reset thresholds.

-- (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. [arxiv]

-- (with Janusz A. Brzozowski) Complexity of suffix-free regular languages. [arxiv]

-- (with John Wittnebel) Syntactic complexity of bifix-free languages. [arxiv]
Accepted to CIAA 2017.

-- (with Robert Ferens) Complexity of bifix-free regular languages. [arxiv]
Accepted to CIAA 2017.

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

[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 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. [open access]
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.