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.
polski
