Marek Szykuła‎ > ‎

Promowane prace dyplomowe / Supervised diploma theses

3. (bachelor) Robert Ferens, 2016.
Złożoność języków regularnych bez prefiksów i sufiksów / Complexity of regular bifix-free languages.
Abstract: We study descriptive complexity properties of regular bifix-free languages. First, we complete the previous results by characterizing state complexity of product, star, and reversal, and analyzing atom complexity of bifix-free languages. Then we show that there exist ternary universal (stream of) bifix-free languages that meet all the bounds for basic operations. This is in contrast with suffix-free languages, where it is known that there does not exist such stream. We also present a stream of bifix-free languages that is most complex in terms of all basic operations, syntactic complexity, and the number of atoms and their complexities.

2. (bachelor) Tomasz Jurkiewicz, 2016.
Aplikacja do analizowania automatów synchronizowalnych / An application for analyzing synchronizing automata.
Abstract: The thesis presents a graphical application for analyzing synchronizing automata. Its main goal is to help understanding how synchronization works on particular automata, to observe the behavior of basic algorithms, and to test various properties related to synchronization. This should be a valuable tool for researchers working in this area. The program visualizes a finite (semi)automaton and allows to run and observe the behavior of basic algorithms for such problems as computing image of a subset under the action of a given word, finding a shortest reset word or a shortest word extending a selected subset. Moreover, the automaton can be easily edited, which helps in constructing automata with desired properties.

1. (bachelor) Jakub Sutowicz, 2016.
Translator języka Simplified Boardgames do Game Description Language / Simplified Boardgames to Game Description Language Translator.
Abstract: Simplified Boardgames is a subclass of chess-like board games. The language of Simplified Boardgames, first introduced by Bj\"{o}rnsson 2012, allows a readable and concise representation of board games in its class, in contrast with a more general languages such as Game Description Language. In particular, it is a very good source of new games, since it is easy to create new games by both manual writing and an automatic generation. However, the usefulness of such games is limited, unless they are available for a variety of playing programs. In the thesis we describe a translator of Simplified Boardgames language to Game Description Language, which is used by General Game Playing agents. To make the resulted code be easier played by players, we developed several optimizations that makes the GDL code shorter and allowing faster computation. We analyzed complexity of the algorithms used by the translator, and we experimentally tested a number of games for the behavior of a GGP agent under different translation options.
[the translator in C++]