﻿ Seznam abstraktů  -  Česko-Slovenská MELA 2014 - Meeting on Languages

# Seznam abstraktů (nekompletní)

#### Hidden Markov models: theoretical problems and applications in bioinformatics

Bronislava Brejová

Hidden Markov models (HMMs) are probabilistic models based on finite state automata with applications in many areas of computer science. We will concentrate on their use in bioinformatics, where they form basis of many frequently used tools for gene finding, sequence alignment and other problems. We will also talk about the choice of optimization function in HMM inference, which influences computational complexity of the problem as well as the accuracy of the results.

#### On-line multiplication in redundant numeration systems

Marta Brzicová

We describe algorithm for performing multiplication of two numbers with arbitrarily long representation in base 2. The algorithms was provided by Ercegovac and Trivedi in 1974. We discuss also a possible modification of their algorithm for a broader class of bases.

#### Aperiodic mixing and aperiodic shrinking generators -- Introduction

Ľubomíra Dvořáková

We define two pseudorandom number generators based on Combinatorics on Words. The mixing generator was introduced by Guimond at al. in 2001. They combine two periodic sequences according to a binary infinite aperiodic word. We have found a combinatorial condition guaranteeing aperiodicity and absence of the lattice structure for the mixing generator. We will compare the aperiodic mixing generator with the aperiodic shrinking generator studied in the thesis of I. Berzina. It is a special kind of the well-known shrinking generator obtained when two binary sequences are considered and only those symbols from the first one are kept that correspond to the occurrences of ones in the second sequence.

#### Spectral properties of cubic complex Pisot units

Tomáš Hejda

For a real number $\beta>1$, Erdős, Joó and Komornik study distances between consecutive points in the set $X^m(\beta)=\Bigl\{\sum_{j=0}^n a_j \beta^j : n\in\mathbb{N},\,a_k\in\{0,1,\dots,m\}\Bigr\} .$ Pisot numbers play a crucial role for the properties of $X^m(\beta)$. Following the work of Za\"imi, who considered $X^m(\gamma)$ with $\gamma\in\mathbb{C}\setminus\mathbb{R}$ and $|\gamma|>1$, we show that for any non-real $\gamma$ and $m<|\gamma|^2-1$, the set $X^m(\gamma)$ is not relatively dense in the complex plane. Then we focus on complex Pisot units $\gamma$ with a positive real conjugate $\gamma'$ and $m>|\gamma|^2-1$. If the number $1/\gamma'$ satisfies Property~(F), we deduce that $X^m(\gamma)$ is uniformly discrete and relatively dense, i.e., $X^m(\gamma)$ is a Delone set. Moreover, we present an algorithm for determining two parameters of the Delone set $X^m(\gamma)$ which are analogous to minimal and maximal distances in the real case $X^m(\beta)$. For $\gamma$ satisfying $\gamma^3+\gamma^2+\gamma-1=0$, explicit formulas for the two parameters are given.

#### Introduction to sofic-Dyck and finite-type-Dyck shifts

Pavel Heller

Shifts, certain sets of bi-infinite sequences of symbols, are the basic objects studied in symbolic dynamics. Sofic-Dyck and finite-type-Dyck shifts are two recently defined classes of shifts providing a common generalisation of more traditional sofic (accepted by a finite automaton), resp. finite-type (characterised by a finite set of forbidden blocks) shifts with Dyck shifts (well-matched sequences of parentheses). We will show their definitions and present some of the few facts that are known about them.

#### Aperiodic mixing and aperiodic shrinking generators -- Comparison

In this talk, we compare results of the aperiodic mixing generator and the aperiodic shrinking generator in statistical tests. We focus on the practical point of view -- we describe suitable implementation and possible use in practice.

#### Semigroups, Languages and Algebras

Tatiana Jajcayova

In my talk, I will briefly summarize some of the topics presented at Akita conference: Semigroups, Languages and Algebras (Akita, Japan; August 2014). I will look then at so called hairpin completions. The hairpin completion is an operation on formal languages that has been introduced in 2006 by Cheptea, Martin-Vide, and Mitrana, and was inspired by the hairpin formation in DNA biochemistry and by DNA computing. Let Σ be an alphabet with an involution ̄: Σ → Σ. If a word w ∈ Σ∗ has a factorization w = γαβα ̄, then γαβα ̄γ ̄ is called a (right) hairpin completion of w. In particular, I will report the latest results of Fazekas and his colleagues on pseudo palindromic completions, that represent a special type of hairpin completions. They give descriptions of regular languages closed under their operation and characterize words which have a regular iterated completion. Based on this characterization, algorithms for some related decision problems are given.

#### Equivalences of Pushdown Systems

Petr Jančar

The talk aims to highlight some (un)decidability and complexity results in the area of equivalences of pushdown systems, including the language equivalence of deterministic pushdown automata (DPDA) and bisimulation equivalence of pushdown processes. The DPDA equivalence is a famous problem in language theory; G. S\'enizergues got the G\"odel Prize in 2002 for showing its decidability. Several new related results have appeared also in recent years, but the complexity of the central problem remains unclear so far.

#### On number expansions in lattices

Jakub Krásenský

A simultaneous representation of all components of a vector from $\mathbb{Z}^d$ is considered. The representation generalizes the classical positional representation of numbers. The base $\beta\in\mathbb{N}$ is replaced by the matrix from $\mathbb{Z}^{d,d}$ and as a digit set we use a nite subset of elements from the lattice $\mathbb{Z}^d$. This concept was introduced by Katai.

#### The verification of matrix product

Jan Legerský

Let $A, B$ and $C$ be $n \times n$ matrices. Our tasks is the verification whether $A\cdot B=C$. Wiedermann introduced an algorithm whose running time is $O(n^2 \log n)$. We summarize his results and also other problems close to the matrix multiplication - Boolean matrix product and witnesses for Boolean matrix multiplication.

#### A generalization of the problem on spectra of numbers

Zuzana Masáková

The problem of the so-called spectrum of a real number $\beta>1$ has been introduced by Erdős et al. The spectrum of $X^{\mathcal{A}}(\beta)$ for $\mathcal{A}=\{0,1,\dots,r\}\subset\mathbb{N}$ is the set of polynomials with non-negative integer coefficients in the alphabet $\mathcal{A}$, evaluated in $\beta$, $X^\mathcal{A}(\beta)=\big\{\sum_{j=0}^na_j\beta^j : n\in\mathbb{N},\ a_j\in\mathcal{A}\big\}$. Specific properties are valid if $\beta$ is taken to be a Pisot number, i.e.\ an algebraic integer with conjugates in modulus smaller than 1. In particular, there is only a finite number of distances between consecutive points of $X^\mathcal{A}(\beta)$, and the distance sequence can be generated by a substitution. A generalization of the spectra to the complex plane was considered by Hejda and Pelantová, who define the spectrum of a complex Pisot number $\beta$ and study its Voronoi tesselation for the case of cubic complex Pisot units. We consider a generalization in another direction. The base $\beta$ remains to be a real number $>1$, but the alphabet $\mathcal{A}$ of digits is taken to be a finite set of complex numbers. In particular, we study the cases leading to $X^\mathcal{A}(\beta)$ as subsets of cyclotomic integers, providing thus discrete aperiodic structures with crystallographically forbidden symmetries.

#### On Subword Complexity of Morphic Sequences

Kateřina Medková

Let $\Sigma$ be a finite alphabet. A mapping $\varphi : \Sigma^* \rightarrow \Sigma^*$ is called a \textit{morphism} if $\varphi(uv) = \varphi(u)\varphi(v)$ for all $u, v \in \Sigma^*$. A morphism is called \textit{coding} if $\vert \varphi(a) \vert = 1$ for each $a \in \Sigma$. Let $\varphi(s) = su$ for some $s \in \Sigma$, $u \in \Sigma^*$, and suppose $\forall n$ $\varphi^n(u)$ is not empty. Then an infinite sequence $\varphi^\infty(s) = \lim_{n \rightarrow \infty}\varphi^n(s)$ is well-defined and is called \textit{pure morphic sequence}. Sequences of the form $\psi(\varphi^\infty(s))$ with coding $\psi$ are called \textit{morhic sequences}. \textit{Subword complexity} of a sequence $\beta$ is a function $p_\beta: \mathbb{N} \rightarrow \mathbb{N}$ where $p_\beta(n)$ is the number of all different $n$-length subword occuring in $\beta$. We will refer an article by Rostislav Deviatov from 2008. The author sketches the proof of the following result: the subword complexity of arbitrary morphic sequences is either $\Theta(n^2)$, or $O(n^{\frac{3}{2}})$.

#### Spectra of the Tribonnaci number

Jaň Mrkos

Consider $q$, real root of $x^3-x^2-x-1=0$. As $q>1$ and its conjugates are less than one in absolute value, $q$ is a Pisot number. The spectrum of $q$ is the set \begin{equation*} \begin{split} Y^m(q)&:=\{\xi_nq^n+\ldots+\xi_0 | \xi_i\in\{0,\ldots,m\},n\in\mathbb{N}\}\\ &=\{0=y_0

#### Spectra, cut-and-project sets and k-interval exchange transformation

Katka Pastirčáková

The talk focuses on the study of relation between spectra and cut-and-project sets. A spectrum of real number $\beta>1$ is defined for given $m\in\mathbb N$ as the set $$X^m(\beta) = \bigg\{ \sum_{i=0}^{n} a_i \beta^i \colon a_i \in \{0, 1, \ldots, m\}, n\in \mathbb N \bigg\} .$$ Cut-and-project set is defined for given irrational numbers $\varepsilon, \eta, \varepsilon \neq \eta,$ and interval $\Omega$ as $$\Sigma_{\varepsilon, \eta}(\Omega)=\{a+b\eta\colon a+b\varepsilon \in \Omega, a, b\in\mathbb{Z} \}.$$ We give a detailed characterization of spectra $X^m(\beta)$ for $\beta$ quadratic Pisot unit. We show the connection of spectra and cut-and-project sets, due to which we are able to determine the values of distances between consecutive points and their corresponding frequencies. We also consider generalized spectra, in which the base $\beta$ is negative, or the set of digits contains also negative elements. In this case we show that generalized spectra are equal to cut-and-project sets. Cut-and-project sets can be generated quickly by substitution, using $k$ interval exchange transformation. We show that by proper choice of parameters, we can generate the cut-and-project set by substitution over at most 5 letter alphabet.

#### Palindromic sequences generated from marked morphisms

Edita Pelantová

An infinite word is called palindromic if its language contains infinitely many palindromes. In 1995, Hof, Knill, and Simon defined certain subclass $P$ of primitive morphisms and showed that any fixed point of a morphism from this class is palindromic. In 2007, Bo Tan proved that if a fixed point of a primitive morphism $\varphi$ over binary alphabet is palindromic, then a power $\varphi^k$ has a conjugate in the class $P$. As demonstrated by Labb\'e in 2013, in general this statement is not valid on ternary alphabet. In talk, we extend the result of B. Tan to fixed points of marked morphisms over arbitrary alphabet. (In collaboration with S. Labb\'e)

#### Perspectives of Edwards curves for uses in cryptography

Lukáš Pohanka

This talk highlights the advantages of recently discovered Edwards curves and Twisted Edwards curves for elliptic curve cryptography. These new alternative representations of elliptic curves, mainly due to Bernstein et al., not only achieve current speed records in integer factorization, but are also capable of speeding up conventional cryptographic EC-based schemes. We recently showed that Edwards curves over $\mathbb{F}_p$ are also more suitable for highly parallel GPU implementations.

#### The validity of weighted automata

Jacques Sakarovitch

This talk addresses the problem of deciding the validity of weighted automata in which the presence of $\epsilon$-circuits results in infinite summations. Earlier works either rule out such automata or characterise the semirings in which these infinite sums are all well-defined. By means of a topological approach, a definition of validity is taken that is strong enough to insure that in any kind of semirings, any closure algorithm will succeed on every valid weighted automaton and turn it into an equivalent proper automaton. This definition is stable with respect to natural transformations of automata. The classical closure algorithms, in particular algorithms based on the computation of the star of the matrix of $\epsilon$-transitions, can not be used to decide validity. This decision problem remains open for general topological semirings. It is shown that validity can be decided for a certain subclass of topological ordered positive semirings, from which is derived a decision procedure for the validity of automata with weights in $\mathbb{Q}$ or $\mathbb{R}$, two cases that had never been treated before.

#### Generalized Trapezoidal Words

Štěpán Starosta

We present recent results of Amy Glen and Florence Levé on generalized trapezoidal words. They generalize trapezoidal words (finite words having their complexity function in a form of a regular trapezoid or isosceles triangle) to larger alphabets and show that not all of these generalized words are rich in palindromes, unlike the binary case.

Milena Svobodová

#### The Perron-Jacobi Algorithm

Helena Svobodová

Perron-Jacobi algorithm looks for best rational approximations of couple of irra- tional numbers. We present properties of this algorithm and explain its connection to 2-dimensional cut and project sets with one-dimensional acceptance window.

#### Word equations with fixed lengths of variables

Jiří Sýkora

The currently best result concerning solvability of equations on words shows that the problem lies in PSPACE. Moreover, the problem is conjectured to be NP-complete. We show that, when the lengths of variables are fixed, there exists a polynomial-time algorithm that decides whether a given equation has a solution. This result combined with the conjectured exponential bound on the length of a minimal solution would lead to the proof of NP-completeness of the general problem.

#### From rhombus to circle

Eduard Šubert

How to generate two dimensional quasicrystal with circular window from the knowledge of quasicrystals with rhombus window. Summary of: Classification of Voronoi and Delone tiles in quasicrystals: I. General method. Possibly with application to quasicrystals of irracionality $\beta = 2+\sqrt{3}$.

#### Nondeterministic prefix and postfix tree pattern matching automata

Jan Trávníček

A new pushdown store automata finding all occurrences of tree patterns in subject trees in prefix ranked and postfix ranked notations are presented. These pushdown store automata are nondeterministic, however they follow the definition of height deterministic pushdown store automata, hence they are easily determinisable. When deterministic, the matching time is $O(n)$, where $n$ is a size of the subject tree.

#### Real functions computable by finite state transducers

Tomáš Vávra

We study the class of functions computable by finite state transducers in Möbius number systems with sofic expansion subshift. This class, however, is difficult to describe and contains, for example, a continuous nowhere differentiable function. Nevertheless, we will show that among analytic functions in extended real line, only Möbius transformations are computable by a finite state transducer. We will discuss the possibility of generalization of this result to more general classes of functions.

#### The Factor Complexity of Pseudostandard Episturmian Words

Tereza Velká

Standard episturmian words are extensively studied for more than 40 years and there are many deep results about this class of words. The generalization of these words based on multiple antimorphisms is a relatively new concept and only a few characteristics of these words are known. In our talk we look for main reasons of di erent behaviour of pseudostandard episturmian words.

#### Privileged words

Vojtěch Veselý

Our contribution is based on a recent work of Jarkko Peltomaki, who de ned a new class of so called privileged words. We recall their de nition and give a list of their properties. Also connection to other classes of words is discussed.

Zvaní řečníci
Důležité info
Termín konání
sobota 13.9. až pondělí 15.9.2014
Místo konání
Nám. Zachariáše z Hradce čp. 3, 588 56 Telč, (mapa)
Konec registrace
25.7.2014
Abstrakty do
1.9.2014
Kontakt na organizátory