Seznam abstraktů (nekompletní)
Compression of Sheet Music
We study current formats for storing music compositions and explore possibilities to compress them using integer compression methods. We also trying to find a methodology for selecting the optimal method for a given dataset.
On Brlek-Reutenauer conjecture (coauthors Edita Pelantová and Štěpán Starosta)
Brlek and Reutenauer conjectured that any infinite word ${\mathbf u}$ with language closed under reversal satisfies the equality $2D({\mathbf u}) = \sum_{n=0}^{+\infty}T_{\mathbf u}(n)$ in which $D({\mathbf u})$ denotes the defect of $\mathbf u$ and $T_{\mathbf u}(n)$ denotes $\mathcal{C}_{\mathbf u}(n+1)-\mathcal{C}_{\mathbf u}(n) +2 - \mathcal{P}_{\mathbf u}(n+1) - \mathcal{P}_{\mathbf u}(n)$, where $\mathcal{C}_{\mathbf u}$ and $ \mathcal{P}_{\mathbf u}$ are the factor and palindromic complexity of ${\mathbf u}$, respectively. Brlek and Reutenauer verified their conjecture for periodic infinite words. Using their result, we proved the conjecture for uniformly recurrent words. Recently, we have succeeded to prove the Brlek-Reutenauer conjecture in full generality. Our contribution will be devoted to the main ideas of this proof, which is not based any more on the result for periodic words.
Harware accelerated anomalies detection in computer networks using FPGA
As the current computer networks grow and become faster, we need to use some efficient methods to monitor the status of networks to ensure the quality of service. There are several factors that can decrease the quality of service such as device malfunction or network attacks. Anomaly detection system can help us to discover possible connection problems on a network where the reliability and accessibility is very important. The efficiency of anomaly detection methods based on statistical processing of data flow is limited by two main factors. These factors are false alarm rate (FAR) and average detection delay (ADD). We should focus on both of them. The aim of my work is the study of anomaly detection methods on large high-speed computer networks working at speed faster than 10\,Gbps. Benefits from my study should be a methodology of hardware accelerated anomaly detections and an example implementation of hardware accelerated detection method based on FPGA chip on COMBO card. Processing of data should be done in real-time using the COMBO card, therefore the detection alarm should be triggered as soon as possible. The early detection of attack could allow us to take action to minimize the effects.
Integers in numeration systems with irrational bases
Let $\beta>1$ be a base of a numeration system defined by Rényi in 1957. The properties of the set of $\beta$-integers are already well known, while their negative base counterparts, the $(-\beta)$-integers, were quite recently introduced. We show how a generalization of a numeration system significantly affects the properties of the mentioned set and we present an interesting open problem, discussing the cases in which $\beta$-integers and $(-\beta)$-integers share certain similarities.
Covering Strings and Trees
Algorithms on finding covers as regularities of strings have been studied for many years. We study relation between algorithms on string and rooted trees and we try to find solution of similar problems using common principles. Finding covers of trees is still an open problem.
Extremal expansions in negative base system
We consider positional numeration systems with real base (both positive and negative) and study the extremal representations in these systems, called here the greedy and lazy representations. We focus on the base $\beta = - \phi$, where $\phi= \frac{1+\sqrt{5}}{2}$ is the golden mean. We show, that the algorithm introduced by Ito and Sadahiro in 2009 produces neither minimal nor maximal $(-\phi)$-representation with respect to the alternate order and we give algorithms for determination of these extremal strings. We also show that both extremal representations, as well as the Ito-Sadahiro representation, can be obtained using the positive base $\phi^2$ and a non-integer alphabet.
Numbers with periodic representation in Penney numeration system
In the Penney numeration system (base $i-1$, digits $0,1$), any complex number can be represented. We show specifically that complex numbers of the form $p +iq$ where $p,q \in \mathbb{Q}$ are those that have an eventually periodic representation in the system. We present an algorithm for finding such representations and explain how addition can be performed on them.
Finite Automata in Bioinformatics and Musicology
The theory of finite automata is very well developed. Can finite automata be efficiently used in bioinformatics and musicology? We show some examples of usage of various finite automata approaches.
Free and less free monoids
Most papers concerning words and/or languages contain somewhere a sentence like "We denote by $A^*$ the free monoid on the set $A$." I will give some more or less elementary comments on what this really means and how monoids which are not free can be (re)presented.
Word Graphs
We will introduce graphs (automata) that are closely related to inverse semigroups and monoinds. Actions of special groups on these graphs allow us to answer some structural questions about the original semigroups. In specific cases, eventhough automata we obtain are in general infinite, all vital information about the automaton is encoded in a "finite" subgraph - finite core. This will allow us to answer some algorithmic questions (the Word Problem, for instance) as well. We will also address the question of languages recognized by these automata.
Computing all subtree repeats in ordered trees
We consider the problem of computing all subtree repeats in a given ordered tree. We transform the tree to a string representing its postfix notation, and then present an algorithm based on the bottom-up technique to solve it. The proposed algorithm consists of two phases: the preprocessing phase and the phase where all subtree repeats are computed. Its linear time and space complexity are important parts of its quality, making it efficient in practice.
Descriptional Complexity of Finite Automata
Finite automata are one of the simplest computational models. Despite their simplicity, some challenging problems are still open. For instance, we recall the question of how many states are sufficient and necessary for two-way deterministic automata to simulate two-way nondeterministic automata. The importance of this problem is underlined by its relation to the well-known open question whether or not DLOGSPACE equals NLOGSPACE. We focus on deterministic, nondeterministic, alternating and two-way automata and provide a survey of results concerning (i) the simulation of one type of automata by some other type; (ii) the complexity of operations on languages represented by different types of finite automata. We conclude the talk with the current trends in descriptional complexity that include the investigation of subclasses of regular languages and the complexity of combined operations.
Monocultures in eco-grammar systems
We will present eco-grammar systems and systematically study influence of monocultures to environment in eco-grammar systems. Behavior of the environment will be represented by language of the environment, i.e. the set of string characterization of the states of the environment. We will discuss different kind of cooperation between organisms of monoculture and the environment. We will deal with generative power of the monocultures. Also the size of the monoculture, i.e. number of organisms will be taken into the consideration.
Algebraic theory of regular languages
In algebraic theory of regular languages, certain natural classes of languages are characterized by properties of their syntactic monoids or some other, more sophisticated, syntactic structures. Optimally, such a characterization gives an effective algorithm for membership problem for a considered class of languages. The most cited examples of such effective characterizations are Simon’s result stating that a regular language is piecewise testable if and only if its syntactic monoid is J-trivial, and Schutzenberger’s result stating that a regular language is star-free if and only if its syntactic monoid is aperiodic. On the other hand finding an effective characterization of languages of the second level in the dot-depth hierarchy is one of the most intriguing open problems in the theory of regular language for more than 40 years. In our talk we overview developments in the theory.
Codings of rotation
The number from the unit interval can be localized in many ways. The standard way is the decimal or binary expansion. In both cases, a long initial segment of the digital representation of the number determines a small subinterval the number lies in. The longer segment, the better precision and the smaller interval. The digits of the expansions can be achieved by the algorithm, which use repetitively the multiplication by the base and the integer part map. Another way how to localize the number is to use addition by an irrational number instead of multiplication by an integer. This approach leads to Sturmian sequences and codings of rotation. We show how the machinery works and present some classical results and one new result.
From quasicrystals to infinite words and numeration systems
Most of the quasicrystal models can be recast in the frame of the so-called cut-and-project scheme which enables one - by projection of higherdimensional lattices - to obtain discrete point sets with rotational symmetries forbidden in periodic structures. We shall explain the cut-and-project method and demonstrate the connection to symbolic dynamical systems, infinite words and number systems. We shall present several results from combinatorics on words and non-standard numeration obtained with the use of the properties of cut-and-project sets.
Introduction to numeration systems
For a given base $\beta \in \mathbb{C}$ and a digit set $\mathcal{A}\subset \mathbb{{C}}$, we define $(\beta,\mathcal{A})$-representation of a number $x \in \mathbb{C}$. This notion generalizes the decimal and binary representations of $x$. On several chosen pairs $(\beta,\mathcal{A})$, we illustrate arithmetical and combinatorial properties of the corresponding numeration systems.
On biautomata
We initiate the theory and applications of biautomata. A~biautomaton can read a word alternately from the left and from the right. We assign to each regular language $L$ its canonical biautomaton. This structure plays, among all biautomata recognizing the language $L$, the same role as the minimal deterministic automaton has among all deterministic automata recognizing the language $L$. We expect that from the graph structure of this automaton one could decide the membership of a given language in certain significant classes of languages. We present the first two results of this kind: namely, a~language $L$ is piecewise testable if and only if the canonical biautomaton of $L$ is acyclic. From this result Simon's famous characterization of piecewise testable languages easily follows. The second class of languages characterizable by the graph structure of their biautomata are prefix-suffix languages. In the Development in Language Theory's contribution we improved the result concerning $k$-piecewise testable languages in a~significant way.
Determinization of Real-Time Height-Deterministic PDAs
A novel method of determinisation of realtime height-deterministic pushdown automaton is presented. Its output is a two-state automaton with $2^{|Q_N|*|Z_N|*|Q_N|*|Z_N|}$ pushdown store symbols, where $Q_N$ and $Z_N$ are the set of states and set of pushdown store symbols of the original nondeterministic automaton, respectively.
More symmetries occurring in an infinite word: palindromic and G-palindromic defect (joint work with Edita Pelantová)
Given an infinite word $\mathbf{u}$ over a finite alphabet $\mathcal{A}$, we generalize the notion of palindromic defect of $\mathbf{u}$. Palindromic defect measures the saturation of $\mathbf{u}$ by distinct palindromes. A palindrome is a word invariant under the reversal antimorphism, for instance words $0, 00, 010$ are palindromes since they are read the same from the left as from the right. Words having palindromic defect $0$ are fully saturated by palindromes. The generalization of palindromic defect respects more symmetries occurring in $\mathbf{u}$. These symmetries are given by a finite group $G$ consisting of morphisms and antimorphisms over $\mathcal{A}$ such that the set of factors of $\mathbf{u}$, i.e., the set of all finite contiguous subsequences of $\mathbf{u}$, is invariant under all elements of $G$. We define the $G$-defect of $\mathbf{u}$ to be the difference between the maximum number of generalized palindromes (fixed points of involutive antimorphisms of $G$) and the actual number of generalized palindromes occurring in $\mathbf{u}$. This notion was first defined using a modification of Rauzy graphs. We also exhibit a class of so-called generalized Thue-Morse words which have $G$-defect $0$, where $G$ is isomorphic to a dihedral group.
Backward tree pattern matching
Trees are one of the fundamental data structures used in Computer Science. Backward pattern matching algorithms in strings are quadratic in the worst case but they can be also sublinear in practice. We try to use the principles of the string backward pattern matching for the backward pattern matching on trees. We try to solve the backward subtree matching using these techniques: bad character shift, good suffix shift and backward dawg matching and backward tree pattern matching using bad character shift. Our first experimental results show that subtrees can be found in a tree at least as fast as substrings in a string.
The generalized center of mass
The usual definition of the center of mass (also called centroid or the centre of gravity) of a subset in $\mathbb{R}^d$ is defined only for sets with finite and positive $d$-dimensional Lebesgue measure. It can be viewed as an expectation of the random variable uniformly distributed over the set of interest. For the purposes of the random closed sets theory it is however necessary to have such mapping defined on the sets with zero Lebesgue measure. Our aim is therefore to construct the generalized center of mass that is defined for arbitrary compact subsets of $\mathbb R^d$.
Arithmetics in number systems with negative quadratic Pisot base
We study arithmetical properties of number systems with the base $(-\beta),$ when $\beta$ is a quadratic Pisot number. We show that when $\beta$ is a quadratic Pisot unit, the set of $\mathbb{Z}_{-\beta}$ of $(-\beta)$-integers can be equipped with an operation $\oplus$ such that $(\mathbb{Z}_{-\beta},\oplus)$ is a group and $|(x+y)-(x\oplus y)|\leq C$ for all $x,y\in\mathbb{Z}_{-\beta}.$ We determine the possible values of $(x+y)-(x\oplus y)$. Further, we extend the results about the number of fractional digits arising when summing $(-\beta)$-integers from the class of quadratic Pisot units $\beta$ to the non-unit case. We also comment on exceptional arithmetic and geometric properties of a class of bases $-\beta$ where $\beta^r=m\beta^{r-1}+\cdots + m\beta+m$, $r\geq 2$, $m\geq 1$.