Francine Blanchet-Sadri
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Previous Organizations / Institutes
The organizations / institutes from the scholar's other articles in the past ten years
Research Subjects
Francine Blanchet-Sadri has a total of 49 co-authors. Here are the top co-authors by number of shared publications:
- Robert Mercaş
Loughborough University
5 shared publications Sean Simmons
Department of Mathematics, Massachusetts Institute of Technology, Building 2, Room 236, 77 Massachusetts Avenue, Cambridge, MA 02139–4307, USA
4 shared publicationsAndrew Lohr
Department of Mathematics, Rutgers University, 110 Frelinghuysen Rd., Piscataway, NJ 08854–8019, USA
2 shared publicationsEric Weissenstein
Department of Mathematical Sciences, Rensselaer Polytechnic Institute, Troy, USA
2 shared publications- A. Shackleton
Department of Computer Science, Swarthmore College, 500 College Ave, Swarthmore, PA 19081, USA
1 shared publication Abraham Rashin
Rutgers University
1 shared publication
Latest Publications
- 1 September 2018
- Published by Elsevier in Discrete Applied Mathematics
- Vol. 246, 119-139
Computing longest common extensions in partial words
- 1 September 2018
- Published by Elsevier in Discrete Applied Mathematics
- Vol. 246, 119-139
Computing longest common extensions in partial words
- Open Access
- 21 August 2017
- Published by Open Publishing Association in Electronic Proceedings in Theoretical Computer Science
- Vol. 252, 71-85
Constructing Words with High Distinct Square Densities
Fraenkel and Simpson showed that the number of distinct squares in a word of length n is bounded from above by 2n, since at most two distinct squares have their rightmost, or last, occurrence begin at each position. Improvements by Ilie to $2n-\Theta(\log n)$ and by Deza et al. to 11n/6 rely on the study of combinatorics of FS-double-squares, when the maximum number of two last occurrences of squares begin. In this paper, we first study how to maximize runs of FS-double-squares in the prefix of a word. We show that for a given positive integer m, the minimum length of a word beginning with m FS-double-squares, whose lengths are equal, is 7m+3. We construct such a word and analyze its distinct-square-sequence as well as its distinct-square-density. We then generalize our construction. We also construct words with high distinct-square-densities that approach 5/6.Comment: In Proceedings AFL 2017, arXiv:1708.0622- 21 August 2017
- Published by Open Publishing Association in Electronic Proceedings in Theoretical Computer Science
- Vol. 252, 71-85
Open AccessConstructing Words with High Distinct Square Densities
Fraenkel and Simpson showed that the number of distinct squares in a word of length n is bounded from above by 2n, since at most two distinct squares have their rightmost, or last, occurrence begin at each position. Improvements by Ilie to $2n-\Theta(\log n)$ and by Deza et al. to 11n/6 rely on the study of combinatorics of FS-double-squares, when the maximum number of two last occurrences of squares begin. In this paper, we first study how to maximize runs of FS-double-squares in the prefix of a word. We show that for a given positive integer m, the minimum length of a word beginning with m FS-double-squares, whose lengths are equal, is 7m+3. We construct such a word and analyze its distinct-square-sequence as well as its distinct-square-density. We then generalize our construction. We also construct words with high distinct-square-densities that approach 5/6.Comment: In Proceedings AFL 2017, arXiv:1708.0622 - Open Access
- 21 August 2017
- Published by Open Publishing Association in Electronic Proceedings in Theoretical Computer Science
- Vol. 252, 56-70
Dyck Words, Lattice Paths, and Abelian Borders
We use results on Dyck words and lattice paths to derive a formula for the exact number of binary words of a given length with a given minimal abelian border length, tightening a bound on that number from Christodoulakis et al. (Discrete Applied Mathematics, 2014). We also extend to any number of distinct abelian borders a result of Rampersad et al. (Developments in Language Theory, 2013) on the exact number of binary words of a given length with no abelian borders. Furthermore, we generalize these results to partial words.Comment: In Proceedings AFL 2017, arXiv:1708.0622
- 21 August 2017
- Published by Open Publishing Association in Electronic Proceedings in Theoretical Computer Science
- Vol. 252, 56-70
Open AccessDyck Words, Lattice Paths, and Abelian Borders
We use results on Dyck words and lattice paths to derive a formula for the exact number of binary words of a given length with a given minimal abelian border length, tightening a bound on that number from Christodoulakis et al. (Discrete Applied Mathematics, 2014). We also extend to any number of distinct abelian borders a result of Rampersad et al. (Developments in Language Theory, 2013) on the exact number of binary words of a given length with no abelian borders. Furthermore, we generalize these results to partial words.Comment: In Proceedings AFL 2017, arXiv:1708.0622
- Open Access
- 21 August 2017
- Published by Open Publishing Association in Electronic Proceedings in Theoretical Computer Science
- Vol. 252, 26-40
Unavoidable Sets of Partial Words of Uniform Length
A set X of partial words over a finite alphabet A is called unavoidable if every two-sided infinite word over A has a factor compatible with an element of X. Unlike the case of a set of words without holes, the problem of deciding whether or not a given finite set of n partial words over a k-letter alphabet is avoidable is NP-hard, even when we restrict to a set of partial words of uniform length. So classifying such sets, with parameters k and n, as avoidable or unavoidable becomes an interesting problem. In this paper, we work towards this classification problem by investigating the maximum number of holes we can fill in unavoidable sets of partial words of uniform length over an alphabet of any fixed size, while maintaining the unavoidability property.Comment: In Proceedings AFL 2017, arXiv:1708.0622
- 21 August 2017
- Published by Open Publishing Association in Electronic Proceedings in Theoretical Computer Science
- Vol. 252, 26-40
Open AccessUnavoidable Sets of Partial Words of Uniform Length
A set X of partial words over a finite alphabet A is called unavoidable if every two-sided infinite word over A has a factor compatible with an element of X. Unlike the case of a set of words without holes, the problem of deciding whether or not a given finite set of n partial words over a k-letter alphabet is avoidable is NP-hard, even when we restrict to a set of partial words of uniform length. So classifying such sets, with parameters k and n, as avoidable or unavoidable becomes an interesting problem. In this paper, we work towards this classification problem by investigating the maximum number of holes we can fill in unavoidable sets of partial words of uniform length over an alphabet of any fixed size, while maintaining the unavoidability property.Comment: In Proceedings AFL 2017, arXiv:1708.0622
- 1 April 2017
- Published by EDP Sciences in RAIRO - Theoretical Informatics and Applications
- Vol. 51 (2) , 99-119
Minimal partial languages and automata
Partial words are sequences of characters from an alphabet in which some positions may be marked with a “hole” symbol, ⋄. We can create a ⋄-substitution mapping this symbol to a subset of the alphabet, so that applying such a substitution to a partial word results in a set of total words (ones without holes). This setup allows us to compress regular languages into smaller partial languages. Deterministic finite automata for such partial languages, referred to as ⋄-DFAs, employ a limited non-determinism that can allow them to have lower state complexity than the minimal DFAs for the corresponding total languages. Our paper focuses on algorithms for the construction of minimal partial languages, associated with some ⋄-substitution, as well as approximation algorithms for the construction of minimal ⋄-DFAs.
- 1 April 2017
- Published by EDP Sciences in RAIRO - Theoretical Informatics and Applications
- Vol. 51 (2) , 99-119
Minimal partial languages and automata
Partial words are sequences of characters from an alphabet in which some positions may be marked with a “hole” symbol, ⋄. We can create a ⋄-substitution mapping this symbol to a subset of the alphabet, so that applying such a substitution to a partial word results in a set of total words (ones without holes). This setup allows us to compress regular languages into smaller partial languages. Deterministic finite automata for such partial languages, referred to as ⋄-DFAs, employ a limited non-determinism that can allow them to have lower state complexity than the minimal DFAs for the corresponding total languages. Our paper focuses on algorithms for the construction of minimal partial languages, associated with some ⋄-substitution, as well as approximation algorithms for the construction of minimal ⋄-DFAs.
- 1 April 2016
- Published by EDP Sciences in RAIRO - Theoretical Informatics and Applications
- Vol. 50 (2) , 117-133
Computing Depths of Patterns
Pattern avoidance is an important research topic in combinatorics on words which dates back to Thue’s construction of an infinite word over three letters that avoids squares, i.e., a sequence with no two adjacent identical factors. This result finds applications in various algebraic contexts where more general patterns than squares are considered. A more general form of pattern avoidance has recently emerged to allow for undefined positions in sequences. New concepts on patterns such as depth have been introduced and a number of questions have been raised, some of them we answer. In the process, we prove a strict bound on the number of square occurrences in an unavoidable pattern, and consequently, any pattern with more square occurrences than distinct variables is avoidable over three letters. We also provide an algorithm that determines whether a given pattern is of bounded depth, and if so, computes its depth.
- 1 April 2016
- Published by EDP Sciences in RAIRO - Theoretical Informatics and Applications
- Vol. 50 (2) , 117-133
Computing Depths of Patterns
Pattern avoidance is an important research topic in combinatorics on words which dates back to Thue’s construction of an infinite word over three letters that avoids squares, i.e., a sequence with no two adjacent identical factors. This result finds applications in various algebraic contexts where more general patterns than squares are considered. A more general form of pattern avoidance has recently emerged to allow for undefined positions in sequences. New concepts on patterns such as depth have been introduced and a number of questions have been raised, some of them we answer. In the process, we prove a strict bound on the number of square occurrences in an unavoidable pattern, and consequently, any pattern with more square occurrences than distinct variables is avoidable over three letters. We also provide an algorithm that determines whether a given pattern is of bounded depth, and if so, computes its depth.
- 20 February 2016
- Published by Springer Nature in Lecture Notes in Computer Science
- p. 52-64
Longest Common Extensions in Partial Words
- 20 February 2016
- Published by Springer Nature in Lecture Notes in Computer Science
- p. 52-64
Longest Common Extensions in Partial Words
- 16 January 2016
- Published by Springer Nature in Theory of Computing Systems
- Vol. 60 (3) , 473-497
New Bounds and Extended Relations Between Prefix Arrays, Border Arrays, Undirected Graphs, and Indeterminate Strings
- 16 January 2016
- Published by Springer Nature in Theory of Computing Systems
- Vol. 60 (3) , 473-497
New Bounds and Extended Relations Between Prefix Arrays, Border Arrays, Undirected Graphs, and Indeterminate Strings
- 18 July 2015
- Published by Springer Nature
- p. 132-142
Squareable Words
- 7 June 2015
- Published by Springer Nature
- p. 86-97
Computing Primitively-Rooted Squares and Runs in Partial Words
- 7 June 2015
- Published by Springer Nature
- p. 86-97
Computing Primitively-Rooted Squares and Runs in Partial Words