Francine Blanchet-Sadri

Research interests include Combinatorics on Words, Algorithms, and Algebraic Theory of Languages and Automata * REU Director of the National Science Foundation supported program entitled Algorithmic Combinatorics on Words * Professor of the 5th International Ph.D. School in Formal Languages and Applications, University Rovira i Virgili, Tarragona, Spain * Award from Faculdade de Ciencias e Tecnologia, Universidade Nova de Lisboa, Portugal and Forum for Interdisciplinary Mathematics for Outstanding Contributions in Mathematical Sciences * Invited plenary talk entitled "Partial Words" at the SCRA 2006-FIM XIII Thirteenth International Conference on Interdisciplinary Mathematical & Statistical Techniques, New University of Lisbon and Polytechnic Institute of Tomar, Portugal * Member of the program committee for LATA 2007 International Conference on Language and Automata Theory and Applications, Tarragona, Spain * Book entitled "Algorithmic Combinatorics on Partial Words" published by Chapman & Hall/CRC Press, Boca Raton, FL, 2008 * Member of the program committee for International Conference on Automata, Languages and Related topics, Debrecen, Hungary * Member of the program committee for AITC 2010 Advances in the Theory of Computing, Conference track of SYNASC 2010, 12th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing, Timisoara, Romania * One-hour invited lecture for AFL 2011, 13th International Conference on Automata and Formal Languages, Debrecen, Hungary * Paper "F. Blanchet-Sadri and S. Duncan, Partial Words and the Critical Factorization Theorem, Journal of Combinatorial Theory, Series A, Vol. 109, No. 2, 2005, pp 221-245" awarded the Journal of Combinatorial Theory, Series A Top Cited Article 2005-2010

There are 33 included publications by Francine Blanchet-Sadri :

TitleDateViewsBrief Description
Algorithms for Approximate K-Covering of Strings 2005 2461 Computing approximate patterns in strings or sequences has important applications in DNA sequence analysis, data compression, musical text analysis, and so on. In this paper, we introduce approximate k-covers and study them under various commonly use...
Border Correlations of Partial Words 2010 2020 Partial words are finite sequences over a finite alphabet A that may contain a number of “do not know” symbols denoted by ◊’s. Setting = A◊ → {◊}, denotes the set of all partial words over A. In...
Codes, orderings, and partial words 2004 2137 Codes play an important role in the study of the combinatorics of words. In this paper, we introduce pcodes that play a role in the study of combinatorics ofpartial words. Partial words are strings over a finite alphabet that may contain a number of ...
Computing the Partial Word Avoidability Indices of Binary Patterns 2013 1431 We complete the classification of binary patterns in partial words that was started in earlier publications by proving that the partial word avoidability index of the binary pattern ABABA is two and the one of the binary pattern ABBA is three.
Computing the Partial Word Avoidability Indices of Ternary Patterns 2013 2232 We study pattern avoidance in the context of partial words. The problem of classifying the avoidable binary patterns has been solved, so we move on to ternary and more general patterns. Our results, which are based on morphisms (iterated or not), det...
Conjugacy on partial words 2002 1497 The study of the combinatorial properties of strings of symbols from a finite alphabet (also referred to as words) is profoundly connected to numerous fields such as biology, computer science, mathematics, and physics. In this paper, we examine to wh...
Counting Minimal Semi-Sturmian Words 2013 2102 A finite Sturmian word w is a balanced word over the binary alphabet {a,b}, that is, for all subwords u andv of w of equal length, ||u|a-|v|a|=1, where |u|a and |v|a denote the number of occurrences of the lettera in u and v, respectively. There are ...
Equations and Dot-Depth One 1993 1731 This paper studies the fine structure of the Straubing hierarchy of star-free languages. Sequences of equations are defined and are shown to be sufficiently strong to characterize completely the monoid varieties of a natural subhierarchy of level one...
EQUATIONS ON PARTIAL WORDS 2009 995 It is well-known that some of the most basic properties of words, like the commutativity (xy = yx) and the conjugacy (xz = zy), can be expressed as solutions of word equations. An important problem is to decide whether or not a given equation on word...
Equations on the semidirect product of a finite semilattice by a finite commutative monoid 1994 3182 Let Comt,q denote the variety of finite monoids that satisfy the equations xy = yx and xt = xt+q . The variety Com1,1 is the variety of finite semilattices also den...
Equations on Semidirect Products of Commutative Semigroups 1997 2049 In this paper; we study equations on semidirect products of commutative semigroups. Let Comq,r denote the pseudovariety of all finite semigroups that satisfy the equations xy = yx and xr + q = xr. The pseudovari...
Games, equations and dot-depth two monoids 1992 2167 Given any finite alphabet A and positive integers m1, …, mk, congruences on A*, denoted by ~(m1, …, mk) and related to a version of the Ehrenfeucht-Fraisse game, are defined. Level k of the Straubing hierarchy of aperiodic monoids can be characterize...
A generalization of Thue freeness for partial words 2009 2348 This paper approaches the combinatorial problem of Thue freeness for partial words. Partial words are sequences over a finite alphabet that may contain a number of ?holes?. First, we give an infinite word over a three-letter alphabet which avoids squ...
Multiset and Set Decipherable Codes 2001 2507 We extend some results of Lempel and Restivo on multiset decipherable codes to set decipherable codes.
Note on Decipherability of Three-Word Codes 2002 1929 The theory of uniquely decipherable (UD) codes has been widely developed in connection with automata theory, combinatorics on words, formal languages, and monoid theory. Recently, the concepts of multiset decipherable (MSD) and set decipherable (SD...
A NOTE ON THE NUMBER OF SQUARES IN A PARTIAL WORD WITH ONE HOLE 2009 2142 A well known result of Fraenkel and Simpson states that the number of distinct squares in a word of length n is bounded by 2n since at each position there are at most two distinct squares whose last occurrence starts. In this paper, we investigate sq...
Number of Holes in Unavoidable Sets of Partial Words I 2014 1602 Partial words are sequences over a finite alphabet that may contain some undefined positions called holes. We consider unavoidable sets of partial words of equal length. We compute the minimum number of holes in sets of size three over a binary alpha...
Number of Holes in Unavoidable Sets of Partial Words II 2012 1662 We are concerned with the complexity of deciding the avoidability of sets of partial words over an arbitrary alphabet. Towards this, we investigate the minimum size of unavoidable sets of partial words with a fixed number of holes. Additionally, we a...
On dot-depth two 1990 781 Etant donnés des entiers positifs m1, …, mk, on définit des congruences ~(m1, …, mk) en relation avec une version du jeu de Ehrenfeucht-Fraissé, et qui correspondent au niveau k de la hiérarchie de concaténation de Straubing. Etant donné un alphabet ...
On a Product of Finite Monoids 1998 1330 In this paper, for each positive integer m, we associate with a finite monoid S0 and m finite commutative monoids S1,…, Sm, a product ◊m(Sm,…, S1, S0). We give a representation o...
Partial words and the critical factorization theorem revisited 2007 2313 In this paper, we consider one of the most fundamental results on the periodicity of words, namely the critical factorization theorem. Given a word w and nonempty words u, v satisfying w = uv, the minimal local period associated with the factorizatio...
Periodicity on Partial Words 2004 2046 A partial word of length n over a finite alphabet A is a partial map from {0, … , n - 1} into A. Elements of {0, … , n-1} without image are called holes (a word is just a partial word without holes). A fundamental periodicity result on words due to F...
Periodicity properties on partial words 2008 2264 The concept of periodicity has played over the years a centra1 role in the development of combinatorics on words and has been a highly valuable too1 for the design and analysis of algorithms. Fine and Wilf’s famous periodicity result, which is one of...
Periods in Partial Words: An Algorithm 2012 2043 Partial words are finite sequences over a finite alphabet that may contain some holes. A variant of the celebrated Fine–Wilf theorem shows the existence of a bound L=L(h,p,q) such that if a partial word of length at least L with h holes has per...
Recurrent Partial Words 2011 926 Partial words are sequences over a finite alphabet that may contain wildcard symbols, called holes, which match or are compatible with all letters; partial words without holes are said to be full words (or simply words). Given an infinite partial wor...
Remarks on Two Nonstandard Versions of Periodicity in Words 2008 1720 In this paper, we study some periodicity concepts on words. First, we extend the notion of full tilings which was recently introduced by Karhumäki, Lifshits, and Rytter to partial tilings. Second, we investigate the notion of quasiperiods and show in...
Some Logical Characterizations of the Dot-Depth Hierarchy and Applications 1995 1972 A logical characterization of natural subhierarchies of the dot-depth hierarchy refining a theorem of Thomas and a congruence characterization related to a version of the Ehrenfeucht—Fraïssé game generalizing a theorem of Simon are given. For a seque...
Strict Bounds for Pattern Avoidance 2013 2590 Cassaigne conjectured in 1994 that any pattern with m distinct variables of length at least 3(2m-1) is avoidable over a binary alphabet, and any pattern with m distinct variables of length at least 2m is avoidable over a ternary alphabet. Building ...
Testing avoidability on sets of partial words is hard 2009 2131 We prove that the problem of deciding whether a finite set of partial words is unavoidable is NP-hard for any alphabet of size larger than or equal to two, which is in contrast with the well-known feasability results for unavoidability of a set of fu...
Testing primitivity on partial words 2007 2130 Primitive words, or strings over a finite alphabet that cannot be written as a power of another string, play an important role in numerous research areas including formal language theory, coding theory, and combinatorics on words. Testing whether or ...
Trees, Congruences and Varieties of Finite Semigroups 1998 1771 A classification scheme for regular languages or finite semigroups was proposed by Pin through tree hierarchies, a scheme related to the concatenation product, an operation on languages, and to the Schützenberger product, an operation on semigroups. ...
Unavoidable Sets of Partial Words 2009 2238 The notion of an unavoidable set of words appears frequently in the fields of mathematics and theoretical computer science, in particular with its connection to the study of combinatorics on words. The theory of unavoidable sets has seen extensive st...
Unbordered partial words 2009 3107 An unbordered word is a string over a finite alphabet such that none of its proper prefixes is one of its suffixes. In this paper, we extend the results on unbordered words to unbordered partial words. Partial words are strings that may have a number...