Frantisek Franek
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:
- Antoine Deza
McMaster University
4 shared publications - William F. Smyth
McMaster University
3 shared publications - Abu Sayed Md Sohidull Islam
School of Computational Science & Engineering McMaster University Hamilton Canada
1 shared publication - Adrien Thierry
Department of Computing and Software Advanced Optimization Laboratory McMaster University Hamilton Ontario Canada
1 shared publication Andrew Baker
Department of Computing and Software, McMaster University, 280 Main St. West, Hamilton, Ontario, Canada
1 shared publication- Andrzej Dudek
Department of Mathematics and Computer Science, Emory University, Atlanta, GA, USA
1 shared publication
Latest Publications
- Open Access
- 12 November 2020
- Published by MDPI AG in Algorithms
- Vol. 13 (11) , 294
Computing Maximal Lyndon Substrings of a String
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 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.- 12 November 2020
- Published by MDPI AG in Algorithms
- Vol. 13 (11) , 294
Open AccessComputing Maximal Lyndon Substrings of a String
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 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
- 1 January 2017
- Published by American Institute of Mathematical Sciences (AIMS) in AIMS Medical Science
- Vol. 4 (3) , 261-273
The Role of The Prefix Array in Sequence Analysis: A Survey
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
- 1 January 2017
- Published by American Institute of Mathematical Sciences (AIMS) in AIMS Medical Science
- Vol. 4 (3) , 261-273
Open AccessThe Role of The Prefix Array in Sequence Analysis: A Survey
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
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 AccessAlgorithms to Compute the Lyndon Array
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?
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.
Open AccessHow many double squares can a string contain?
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.
- 31 May 2013
- Published by Elsevier in Journal of Discrete Algorithms
- Vol. 20, 43-50
A computational framework for determining run-maximal strings
- 31 May 2013
- Published by Elsevier in Journal of Discrete Algorithms
- Vol. 20, 43-50
A computational framework for determining run-maximal strings
- 30 October 2012
- Published by Elsevier in Journal of Discrete Algorithms
- Vol. 17, 9-14
On a conjecture of Erdős for multiplicities of cliques
- 30 October 2012
- Published by Elsevier in Journal of Discrete Algorithms
- Vol. 17, 9-14
On a conjecture of Erdős for multiplicities of cliques
- 3 April 2012
- Published by Elsevier in Journal of Discrete Algorithms
- Vol. 17, 2-8
More results on overlapping squares
- 3 April 2012
- Published by Elsevier in Journal of Discrete Algorithms
- Vol. 17, 2-8
More results on overlapping squares
- 11 August 2011
- Published by Elsevier in Journal of Discrete Algorithms
- Vol. 10, 10-14
On the structure of run-maximal strings
- 11 August 2011
- Published by Elsevier in Journal of Discrete Algorithms
- Vol. 10, 10-14
On the structure of run-maximal strings
- Open Access
- 8 January 2009
- Published by Walter de Gruyter GmbH in Mathematica Slovaca
- Vol. 59 (1) , 109-120
Cliques in Steiner systems
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.
- 8 January 2009
- Published by Walter de Gruyter GmbH in Mathematica Slovaca
- Vol. 59 (1) , 109-120
Open AccessCliques in Steiner systems
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.
- 1 July 2002
- Published by Springer Nature in Combinatorica
- Vol. 22 (3) , 451-454
On Erdős's Conjecture on Multiplicities of Complete Subgraphs Lower Upper Bound for Cliques of Size 6
- 1 July 2002
- Published by Springer Nature in Combinatorica
- Vol. 22 (3) , 451-454
On Erdős's Conjecture on Multiplicities of Complete Subgraphs Lower Upper Bound for Cliques of Size 6