FFFrantisek Franek

Frantisek Franek

*This is an algorithmically generated author record based on publicly available information.

Current Organizations / Institutes

The organizations/institutes from the scholar's latest article


Frantisek Franek has a total of 13 co-authors. Here are the top co-authors by number of shared publications:


Latest Publications

  • Open Access

    Computing Maximal Lyndon Substrings of a String

    by Frantisek Franek, Michael Liut

    There are two reasons to have an efficient algorithm for identifying all right-maximal Lyndon substrings of a string: firstly, Bannai et al. introduced in 2015 a linear algorithm to compute all runs of a string that relies on knowing all right-maximal Lyndon substrings of the input string, and secondly, Franek et al. showed in 2017 a linear equivalence of sorting suffixes and sorting right-maximal Lyndon substrings of a string, inspired by a novel suffix sorting algorithm of Baier. In 2016, Franek et al. presented a brief overview of algorithms for computing the Lyndon array that encodes the knowledge of right-maximal Lyndon substrings of the input string. Among those presented were two well-known algorithms for computing the Lyndon array: a quadratic in-place algorithm based on the iterated Duval algorithm for Lyndon factorization and a linear algorithmic scheme based on linear suffix sorting, computing the inverse suffix array, and applying to it the next smaller value algorithm. Duval’s algorithm works for strings over any ordered alphabet, while for linear suffix sorting, a constant or an integer alphabet is required. The authors at that time were not aware of Baier’s algorithm. In 2017, our research group proposed a novel algorithm for the Lyndon array. Though the proposed algorithm is linear in the average case and has O(nlog(n)) worst-case complexity, it is interesting as it emulates the fast Fourier algorithm’s recursive approach and introduces τ-reduction, which might be of independent interest. In 2018, we presented a linear algorithm to compute the Lyndon array of a string inspired by Phase I of Baier’s algorithm for suffix sorting. This paper presents the theoretical analysis of these two algorithms and provides empirical comparisons of both of their C++ implementations with respect to the iterated Duval algorithm.

  • Open Access

    The Role of The Prefix Array in Sequence Analysis: A Survey

    by Frantisek Franek, W. F. Smyth, Xinfang Wang

    The prefix array was apparently first computed and used algorithmically in 1984, playing a pivotal role in an optimal algorithm to determine all the tandem repeats in a given (DNA or protein) sequence. However, it is especially since the turn of the 21st century that applications of the prefix array to fundamental sequencing problems have been recognized. An important aspect of this expanding role has been the recognition that the prefix table and the border array are “equivalent” data structures 一 that is, one can be computed from the other in linear time. Since the border array in turn specifies all the periods of every prefix of the sequence, the prefix array thus turns out to be a structure of central importance. In this paper we survey important applications of the prefix array 一 in particular to approximate string matching under Hamming distance, as well as to the computation of covers and enhanced covers 一 and show how, unlike border array algorithms, these are extendible to sequences containing “don’t-care” or indeterminate letters such as {a, c} or {g, t}. This extension leads to a surprising correspondence between prefix arrays and undirected graphs that seems likely to be a fertile source of new insights in future. We conclude with an overview of sequencing problems that the authors believe can be handled using prefix array technology

  • Open Access

    Algorithms to Compute the Lyndon Array

    by Frantisek Franek, A. S. M. Sohidull Islam, M. Sohel Rahman, W. F. Smyth

    We first describe three algorithms for computing the Lyndon array that have been suggested in the literature, but for which no structured exposition has been given. Two of these algorithms execute in quadratic time in the worst case, the third achieves linear time, but at the expense of prior computation of both the suffix array and the inverse suffix array of x. We then go on to describe two variants of a new algorithm that avoids prior computation of global data structures and executes in worst-case n log n time. Experimental evidence suggests that all but one of these five algorithms require only linear execution time in practice, with the two new algorithms faster by a small factor. We conjecture that there exists a fast and worst-case linear-time algorithm to compute the Lyndon array that is also elementary (making no use of global data structures such as the suffix array).

  • Open Access

    How many double squares can a string contain?

    by Antoine Deza, Frantisek Franek, Adrien Thierry

    Counting the types of squares rather than their occurrences, we consider the problem of bounding the number of distinct squares in a string. Fraenkel and Simpson showed in 1998 that a string of length n contains at most 2n distinct squares. Ilie presented in 2007 an asymptotic upper bound of 2n - Theta(log n). We show that a string of length n contains at most 5n/3 distinct squares. This new upper bound is obtained by investigating the combinatorial structure of double squares and showing that a string of length n contains at most 2n/3 double squares. In addition, the established structural properties provide a novel proof of Fraenkel and Simpson's result.

  • More results on overlapping squares

    by Frantisek Franek, Robert C.G. Fuller, Jamie Simpson, W.F. Smyth


  • On the structure of run-maximal strings

    by Andrew Baker, Antoine Deza, Frantisek Franek


  • Open Access

    Cliques in Steiner systems

    by Andrzej Dudek, František Franěk, Vojtěch Rödl

    A partial Steiner (k,l)-system is a k-uniform hypergraph with the property that every l-element subset of V is contained in at most one edge of . In this paper we show that for given k,l and t there exists a partial Steiner (k,l)-system such that whenever an l-element subset from every edge is chosen, the resulting l-uniform hypergraph contains a clique of size t. As the main result of this note, we establish asymptotic lower and upper bounds on the size of such cliques with respect to the order of Steiner systems.