## Department seminars

### Summer semester 2021/22

The seminar takes place on Thursdays from 10:30-12:00, room 1094. Seminar topics: software engineering, software testing and quality, formal language theory, discrete mathematics, formal methods of software engineering, and graph theory.

**9 June 2022**

**Speaker: Artur Polański**

Description: Speech on the construction of cyclic codes that are then used to construct codes that can be used in quantum calculations. Adapted from Hai Q. Dinh, Tushar Bag, Ashish K. Upadhyay, Ramakrishna Bandi, Roengchai Tansuchat, "A class of skew cyclic codes and application in quantum codes construction" from Discrete Mathematics.

**2 June 2022**

**Speaker: Jakub Zygadło**

**26 May 2022**

**Speaker: Eryk Lipka**

Title: Ordered (non) deterministic automata

Description: Classical finite automata are generalized in many ways. During the speech, we will present automata, the states of which can be sorted in a natural way. In the class of these "Wheeler" automata, problems such as determination or minimization turn out to be much simpler than in ordinary automata, the complexity of many algorithms drops from exponential to polynomial. As part of the presentation, we will show where this natural order in states comes from, we will discuss why algorithms simplify and what the class of languages recognized by such.

**19 May 2022**

**Speaker: Piotr Bienias**

**Title: Simulating finite automata with context-free grammars**

**12 V 2022**

**Speaker: Natalia Durlik**

**Title: Lewis Carroll and the Red Hot Potato: A graph theoretic approach to a linear algebraic identity**

Description: The talk will be devoted to a graph theoretic interpretation of Dodgson's rule - identity used in computing determinants. I will talk about equivalent identity involving sum of pairs of forests. I will present proof of the identity using edge transferring algorithm - Red Hot Potato. The talk is based on the paper “Lewis Carroll and the Red Hot Potato: A graph theoretic approach to a linear algebraic identity” by Melanie Fraser.

**5 May 2022**

**Speaker: Piotr Bienias**

Title: Simulating finite automata with context-free grammars

Description: We consider simulating finite automata (both deterministic and nondeterministic) with context-free grammars in Chomsky Normal Form (CNF). We show that any unary DFA with n states can be simulated by a CNF grammar with O (n ^ (1/3)) variables, and this bound is tight. We show that any unary NFA with n states can be simulated by a CNF grammar with O (n ^ (2/3)) variables. Finally, for larger alphabets, we show that there exist languages that can be accepted by an n-state DFA, but which require \ Omega (n / log n) variables in any equivalent CNF grammar.

**21 April 2022**

**Speaker: Maciej Brzeski**

**Title: Upper Bounding the Graph Edit Distance**

Description: I will introduce the edit distance problem on graphs and how to find an approximation solution using the linear assignment sum problem. I will present some techniques to obtain more accurate results, both with node representation and prediction using ML techniques. The presentation is based on a paper by David B. Blumenthal et al. "Upper Bounding the Graph Edit Distance Based on Rings and Machine Learning"

**14 April 2022**

**Speaker: Mateusz Dobija**

**Title: The Impact of Mislabeled Changes by SZZ on Just-in-Time Defect Prediction**

Description: During the seminar I will present the topic of JIT (just-in-time) defect prediction, described in the article titled “The impact of Mislabeled Changes by SZZ on Just-In-Time Defect Prediction” (authors: Yuanrui Fan, Xin Xia, Daniel Alencar da Costa, David Lo, Ahmed E. Hassan, Shanping Li). I will discuss the SZZ approach (implemented by Śliwerski, Zimmermann and Zeller) used in the aim of identifying changes that introduce a bug. I will present 4 basic steps: identifying bug-fixing changes, identifying buggy lines, identifying potential bug-introducing changes, and filtering away incorrect bug-introducing changes. During the presentation, I will show the impact of mislabeled changes related to variants of SZZ on the defect prediction. As a data for the analysis, the changes from selected Apache open-source projects have been used.

**7 April 2022**

**Speaker: Adam Roman**

**Title: Software Defect Prediction and Data-Flow Metrics**

**17 March 2022**

**Speaker: Jakub Ruszil**

**Title: The kangaroo problem**

**24 March 2022**

**Speaker: Farnoud Ghasemi**

**Title: Complex adaptive systems**

The modeling of Complex Adaptive Systems (CAS) is an example for the integration of computer science into the very fabric of science. These models are used to understand and predict the dynamics of complex systems at both microscopic and macroscopic levels. In particular, we use the CAS theorems to study the dynamics of two-sided markets including platforms such as Uber, Airbnb and Amazon. On the other side, agent-based modeling (as a bottom-up study method) is used as a complementary tool to capture the interactions in the system. In an Agent-Based Model (ABM), the system is modeled as a collection of autonomous decision-making entities called agents and each agent interacts with the other agents in its own local environment. Collective behaviours of the agents give rise to emergent behaviors of the whole system which are not predictable through the individual behaviours of the agents at first sight. In this way, CAS models enable us to detect the relations and the interaction at a desired level and to study the feedback loops between the whole system and the individuals. Adaptation is another crucial feature of CAS models to reach the best models in terms of system dynamics considering the two main elements of decision making and learning. In particular, we use discrete choice models to obtain the desired behavior. These models from economics are based on random utility theory and widely used to reproduce choice behavior of the rational decision makers. CAS models enable us to detect the relations and the interaction at a desired level and to study the feedback loops between the whole system and the individuals. Adaptation is another crucial feature of CAS models to reach the best models in terms of system dynamics considering the two main elements of decision making and learning. In particular, we use discrete choice models to obtain the desired behavior. These models from economics are based on random utility theory and widely used to reproduce choice behavior of the rational decision makers. CAS models enable us to detect the relations and the interaction at a desired level and to study the feedback loops between the whole system and the individuals. Adaptation is another crucial feature of CAS models to reach the best models in terms of system dynamics considering the two main elements of decision making and learning. In particular, we use discrete choice models to obtain the desired behavior. These models from economics are based on random utility theory and widely used to reproduce choice behavior of the rational decision makers. we use discrete choice models to obtain the desired behavior. These models from economics are based on random utility theory and widely used to reproduce choice behavior of the rational decision makers. we use discrete choice models to obtain the desired behavior. These models from economics are based on random utility theory and widely used to reproduce choice behavior of the rational decision makers.

### Winter semester 2021/22

The seminar takes place on Thursdays from 10:30-12:00, room 0086. Seminar topics: software engineering, software testing and quality, formal language theory, discrete mathematics, formal methods of software engineering, and graph theory.

**27 Jan 2022**

**Speaker: Maciej Brzeski**

**Title: Approximating the editing distance of graphs using graph embeddings**

At the seminar, I will introduce the problem of editing distance on graphs, and present combinatorial approaches to solving this problem. However, in recent years, there has been a trend to use machine learning methods to approximate the editing distance. Based on the work of Runzhong Wang et al .: "Combinatorial Learning of Graph Edit Distance via Dynamic Embedding", I will show how these two areas can be combined.

**20 Jan 2022**

Speaker: Mateusz Dobija

Title: Predicting technical debt from commit contents: reproduction and extension with automated feature selection

During the seminar, I will present the issue of self-admitted technical debt on the basis of commit content, discussed in the work "Predicting technical debt from commit contents: reproduction and extension with automated feature selection" by Rantala & Mantyl. As part of the lecture, I will discuss methods of detecting commits introducing technological debt, taking into account three methods of natural language processing: "Bag of words", "topic modeling" and "word embedding vectors". I will present the obtained results with reference to the results of previous research, as well as present the limitations and further directions of the analyzes.

**13 I 2022**

Speaker: Rafał Brożek

Title: Data flow metrics

Presentation of own results as part of the written master's thesis on the use of data flow metrics to build defect prediction models.

**16 December 2021**

**Speaker: Piotr Bienias**

**Subject: Deterministic Finite Automata minimization based on Backward Depth Information.**

In this presentation, I will discuss the problem of finite automaton minimization and present the algorithm described in the article:

https://journals.plos.org/plosone/article?id=10.1371/journal.pone.0165864

This method uses the Backward Depth Information technique, which consists in finding the shortest paths to the automaton accepting states from all other states. The algorithm is characterized by performance similar to, and in some cases better than, the most effective Hopcroft algorithm so far, and applicable to any class of automata.

**December 9, 2021**

**Speaker: Dzhesika Nimets **

**Subject: Hamiltonian Paths in Cayley Graphs (based on the work of I. Pak)**

**2 December 2021**

**Speaker: Natalia Durlik**

**Subject: Complexity problems in enumerative combinatorics**

I will present selected issues from the review work by Igor Pak on "Complexity problems in enumerative combinatorics". I will discuss what criteria can be used to find the formula for a given sequence of elements useful. I will consider the computational complexity of bijection between combinatorial structures and present the interpretations of selected sequences.

**25 November 2021**

**Speaker: Marcin Podhajski**

**Subject: No-three-line problem on torus**

**18 November 2021**

**Speaker: Patryk Staniszewski**

**Topic: Public, uniform defect database**

During the seminar, a public unified bug dataset will be introduced. The paper will describe the process of selecting minor data sets used to create the title unified set, their analysis, metrics, and the course of unification.

The possibilities of using the set obtained for error prediction will also be presented.

**4 November 2021**

**Speakers: Mikołaj Kondratek (continuation), Tomasz Homoncik**

**Topic: Proportion of Equivalent Mutants**

Mutation testing is based on creating modified versions of the program - mutants. Some of them, however, may be semantically equivalent to the base program. During the lecture, I will present the method of estimating the number of equivalent mutants and its application in mutation testing.

The presentation

**28 October 2021**

**Speakers: Jakub Ruszil (continuation), Mikołaj Kondratek**

**Topic: Latin squares from multiplication tables**

During the seminar, I will show that the partial multiplication table can be completed to the Latin square. The result will be more general as it is enough for the empty part of a partial Latin square to comply with some specific constraints. It will also turn out that this issue is related to Graham's Problem. I'll also explain what's special about 195.

**21 October 2021**

**Speaker: Jakub Ruszil**

**Topic: Automata synchronization from the point of view of formal languages**

Description: In my speech, I will describe the results of the automata synchronization theory from the point of view of formal languages. Based on the work of Principal ideal languages and synchronizing automata by V. Gusev et al. and Reset Complexity of Ideal Languages by M. Maslennikova.

### Summer semester 2020/21

The seminar takes place on Thursdays from 10:30-12:00, room 1086 (due to the epidemic - currently on MS Teams, you can join the team via the code: d70ru5i). Seminar topics: software testing and quality, theory of formal languages, graph theory.

**10 June 10, 2020**

**Speaker: Maciej Brzeski**

**Topic: Searching for similar subgraphs using chi-square statistics**

Description: Labeled graphs provide a natural way to represent various data or relationships. Having a given graph, we want to find the most similar in a given set of graphs (or the most similar subgraphs in a large graph). Approaches based on isomorphism or graph matching are NP-complete, which makes it impossible to use them for larger data sets. Approximating algorithms began to be considered as an alternative. In this speech I will present an approach where the graph is described by the distribution of labels in adjacent vertices, and the similarity characteristic of the graph is based on the statistical significance captured by the chi-square statistic. Paper based on the work of Sourav Dutt et al., "Neighbor-Aware Search for Approximate Labeled Graph Matching using the Chi-Square Statistics".

The presentation

**27 May 2021**

**Speaker: Jakub Ruszil**

**Topic: The problem of division into dominant sets for directed graphs**

Description: In this speech, I will focus on the problem of dividing the vertices of the graph into dominant sets. I will prove the NP-completeness of this problem in the general case, and then I will present a linear algorithm for solving this problem in the case of oriented trees. The presentation is based on the work Partitioning vertices into in- and out- dominating sets in digraphs - Kosuke Nakamura Toru Araki.

**20 May 2021**

**Speaker: Małgorzata Dymek**

**Topic: Acyclic graph coloring and entropy compression method**

Description: I will present the problem of acyclic graph coloring and the entropy compression method. I will show how it can be used to prove the constraint of an acyclic chromatic number by providing evidence of two such constraints for certain families of graphs.

The presentation

**13 May 2021**

**Speaker: Tomasz Homoncik**

**Subject: The problem of 4-path vertex coverage**

Description: During the lecture, I will present an algorithm that solves the problem of 4-path vertex coverage and discuss its parametric complexity.

**6 May 2021**

**Speaker: Mikołaj Kondratek**

**Topic: "tower" graphs**

Description: During the seminar I will present some properties of simplicial "tower" graphs (graphs of non-attacking towers on a multidimensional chessboard).

In particular, I will look at sets of dominant and independent vertices.

I will also consider some properties of cyclic simplicial "tower" graphs.

The presentation

**29 April 2021**

**Speaker: Jakub Zygadło**

**Topic: Introduction to parametric complexity**

Description: During this presentation I will discuss the basics of parametric complexity, which is an attempt at a more detailed analysis of computationally difficult problems - in particular, in some cases this method answers the question when difficult problems can be considered as possible to be effectively solved and "what causes" their difficulty. The complexity of the algorithm solving a given problem is given here as a function depending not only on the size of the input data but also on the value of a certain parameter. I will present some classic problems considered difficult with their "natural" parameters and examples of the most commonly used techniques (tree searching, kernelization).

**22 April 2021**

**Speaker: Maciej Brzeski**

**Topic: Kernel methods on graphs**

Description: I will introduce you to kernel methods on graphs based on the work of S.V.N. Vishwanathan et al. - "Graph Kernels". I will show their properties, applications and the most popular kernels. Then I will focus on the kernel: "random walk" - I will show you how to calculate it efficiently and its relationship with other kernels by reducing it to the Sylvester equation.

The presentation

**15 April 2021**

**Speaker: Jakub Ruszil**

**Topic: Linear algebra methods in automata synchronization**

Description: Presentation based on the work of B. Steinberg "The Černý conjecture for one-cluster automata with prime length cycle". I will discuss the methods of applying linear algebra in the theory of automata synchronization. In this work, there is a proof of the Cerny hypothesis for single-cluster automata with a prime cycle length.

**8 April 2021**

**Speaker: Tomasz Homoncik**

**Subject: Online algorithm to determine the 3-path vertex coverage of a graph**

Description: I will present an online algorithm that determines 3-path vertex coverage.

Then I will show that the competitiveness factor of this algorithm is at most equal to the degree of the given graph.

**25 March 2021**

**Speaker: Małgorzata Dymek**

**Topic: Polynomial algorithm for determining morphism for a given fixed point**

Description: A finite word is a fixed point of a morphism that is not identity, as long as it does not change under its action (h (w) = w). Having a given word, can we say that it is a fixed point of some non-trivial morphism? Concepts related to fixed points, their construction and construction characteristics will be presented, as well as a polynomial algorithm that not only answers the above question, but also constructs an appropriate morphism.

The presentation

**18 March 2021**

**Speaker: Mikołaj Kondratek**

**Theme: Rikudo is NP-complete**

Rikudo is a game of finding Hamilton's path in a graph built on cells of a hexagonal grid. I will present the problem of Hamiltonian cycles in graphs built on the edges of a hexagonal grid. Using appropriate reductions, I will show that the game is NP-complete. I will also consider the difficulty of the puzzle for already given values with specific forms.

The presentation

**11 March 2021**

**Speaker: Eryk Lipka**

**Subject: Lie complexity**

As part of the presentation, we will introduce the concept of Lie complexity for infinite words over a finite alphabet; it is another way of describing the number of different finite factors of a given word. This concept has a certain algebraic interpretation, by which it has been called so and no other. With the help of this tool, we will prove a few facts about words whose factor complexity is linear. Paper based on the recent work by Bell, Shallit "Lie complexity of words".
### Winter semester 2020/21

**28 January 2021**

**Speaker: Adam Roman**

**Subject: Data Flow Analysis**

I will discuss the basic issues related to data flow analysis, show the historical development of this analysis techniques related to determining the reachability or lifetime of variables in the code and discuss the issues of using DFA to measure and construct data flow metrics; I will discuss in particular the dep-degree metric and its interesting properties.

**21 January 2021**

**Speaker: Sławomir Bakalarski**

**Topic: Divisors on graphs - continuation**

**14 January 2021**

**Speaker: Mateusz Piątkowski**

**Topic: Elliptic curves in cryptography - continuation**

**Speaker: Sławomir Bakalarski**

**Topic: Divisors on graphs**

The aim of the presentation is to familiarize students with the theory of divisors on graphs. The presentation will be purely combinatorial, no previous knowledge of algebraic geometry is required. In addition to the basic concepts, we will discuss, among others the Riemann-Roch theorem for graphs (proved in 2007 by Baker and Norine), and we will also show its use to solve the problem of a winning strategy in the so-called "chip - firing game". In the second part of the paper we will discuss the computational determination of Picard's group of a graph (and its Jacobian). In the third part, we move on to the presentation of the Riemann-Hurwitz theorem in a graphical version (also proved by the above-mentioned authors). The presentation is based on selected items from the literature, in particular the work of Baker and Norine.

Link to the meeting

**7 January 2021**

**Speaker: Mateusz Piątkowski**

**Topic: Elliptic curves in cryptography**

At the next meeting, we will deal with the subject of elliptic curves in cryptography, in particular the issue of twisted Edwards curves. In addition, we will compare the use of traditional Weierstrass curves with twisted curves using the factorization algorithm (Lenstra) as an example to observe the optimization of time. For the uninitiated, we will make an appropriate introduction to the crux of the matter (Galois bodies + the basics of the construction of curves on Galois bodies).

Link to the meeting

**10 December 2020**

**Speaker: Tomasz Homoncik**

**Subject: Hunters and Rabbits**

Description: I will present the game Hunters and Rabbits (a variant of the game Cops and Robbers).

I will discuss the case of a game played on a hypercube and for graphs with the property of isoperimetric nesting. Finally, I will focus on the variant of the game in which the rabbit is not forced to move between shots.

Link to the meeting

**3 December 2020**

**Speaker: Adam Ćwiertnia**

**Subject: Exponential improvement of lower bounds for Ramsey numbers**

Description: A history of successive corrections for the lower and upper bounds of the Ramsey numbers will be presented, including the Erdős probalistic method. Next, the exponential improvement will be shown for the so far known lower values of these limits, with three or more colorings of the graphs.

Link to the meeting

**26 November 2020**

**Speaker: Eryk Lipka**

**Topic: Upper bound in Graham-Rothschild problem**

Description: At the beginning of the lecture, we will introduce the subject of Ramsey Theory and classical problems of this theory. In the second part we consider what is known as the Graham-Rothschild problem. We build a clique whose vertices are the vertices of an n-dimensional cube and then we double-color its edges. One should find the smallest n such that, irrespective of the coloring, in this graph one can find four points lying on one plane creating a monochrome clique. Initial estimates for this dimension can be briefly described only using the Ackerman type function, while we will present the latest results that give a limitation using only tetration.

Meeting link | The presentation

**19 November 2020**

**Speaker: Edward Szczypka**

**Topic: Compression methods in discrete mathematics and algorithmics (part II)**

Description: The idea of using a heavily underrated compression method in various problems in discrete mathematics, formal languages, and algorithms will be presented. As one of the developments of this method, you can treat the so-called complexity of Kolmogorov, thanks to which a number of problems were solved, which had been attacked without success for many years.

Link to the meeting

**12 November 2020**

**Speaker: Edward Szczypka**

**Topic: Compression methods in discrete mathematics and algorithmics**

Description: The idea of using a heavily underrated compression method in various problems in discrete mathematics, formal languages and algorithms will be presented. As one of the developments of this method, you can treat the so-called complexity of Kolmogorov, thanks to which a number of problems were solved, which had been attacked without success for many years.

Link to the meeting

**5 November 2020**

**Speaker: Maciej Brzeski**

**Topic: Editing distance for trees**

Description: The similarity of two graphs can be thought of very differently - the most frequently considered is the similarity based on structure or labels. At the seminar, I will introduce the problem of "graph matching" on labeled graphs, where it is important to determine corresponding vertices. I will discuss the paper introducing the concept of the editing distance for trees and the algorithm finding the minimum distance, and then its relation to the above problem. Finally, I will briefly discuss the difficulties in extending the above problem to a wider class of graphs.

Meeting link | The presentation

**29 October 2020**

**Speaker: Mikołaj Kondratek**

**Subject: Coefficients in Infinite Product (1-x ^ (F_n))**

Description: I will present proof of the fact that the coefficients in the infinite product (1-x ^ (F_n)) are always -1, 0 or 1 (where F_n is the nth term of the Fibonacci sequence).

The purpose of the introduction is to present the numerical Fibonacci system.

The proof is based on a 4-state deterministic finite automaton.

I will raise the issue of linear representation related to an automaton.

Finally, I will present the automaton calculating the coefficient at x ^ F_n.

Meeting link | The presentation

**22 October 2020**

**Speaker: Artur Polański**

**Subject: Detection of a single defect in DFA**

Description: Discussion of the known result concerning the heureistic algorithm for detecting a single defect in a deterministic finite state machine with the possibilities of its improvement and the problems encountered.

**15 October 2020**

**Speaker: Jakub Ruszil**

**Subject: Synchronization of automata with partial transition function**

Description: An automaton is called synchronizing when there is a word that converts each state of this automaton into one fixed state. In the paper, I will present the results concerning the synchronization of automata with partial transition function, in particular, I will describe the construction of an infinite family of automata for which the synchronizing words have an exponential length depending on the number of states.