Search Results

Documents authored by Blanchet-Sadri, Francine

Document
DOI: 10.4230/LIPIcs.STACS.2014.162
New Bounds and Extended Relations Between Prefix Arrays, Border Arrays, Undirected Graphs, and Indeterminate Strings

Authors: Francine Blanchet-Sadri, Michelle Bodnar, and Benjamin De Winkle

Published in: LIPIcs, Volume 25, 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014)

Abstract
We extend earlier works on the relation of prefix arrays of indeterminate strings to undirected graphs and border arrays. If integer array y is the prefix array for indeterminate string w, then we say w satisfies y. We use a graph theoretic approach to construct a string on a minimum alphabet size which satisfies a given prefix array. We relate the problem of finding a minimum alphabet size to finding edge clique covers of a particular graph, allowing us to bound the minimum alphabet size by n plus square root of n for indeterminate strings, where n is the size of the prefix array. When we restrict ourselves to prefix arrays for partial words, we bound the minimum alphabet size by sqrt(2n). Moreover, we show that this bound is tight up to a constant multiple by using Sidon sets. We also study the relationship between prefix arrays and border arrays. We show that the slowly-increasing property completely characterizes border arrays for indeterminate strings, whence there are exactly C_n distinct border arrays of size $n$ for indeterminate strings (here C_n is the nth Catalan number). We also bound the number of prefix arrays for partial words of a given size using Stirling numbers of the second kind.
Cite as

Francine Blanchet-Sadri, Michelle Bodnar, and Benjamin De Winkle. New Bounds and Extended Relations Between Prefix Arrays, Border Arrays, Undirected Graphs, and Indeterminate Strings. In 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 25, pp. 162-173, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)

Copy BibTex To Clipboard

@InProceedings{blanchetsadri_et_al:LIPIcs.STACS.2014.162,
  author =	{Blanchet-Sadri, Francine and Bodnar, Michelle and De Winkle, Benjamin},
  title =	{{New Bounds and Extended Relations Between Prefix Arrays, Border Arrays, Undirected Graphs, and Indeterminate Strings}},
  booktitle =	{31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014)},
  pages =	{162--173},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-65-1},
  ISSN =	{1868-8969},
  year =	{2014},
  volume =	{25},
  editor =	{Mayr, Ernst W. and Portier, Natacha},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2014.162},
  URN =		{urn:nbn:de:0030-drops-44552},
  doi =		{10.4230/LIPIcs.STACS.2014.162},
  annote =	{Keywords: Indeterminate strings, Partial words, Prefix arrays, Border arrays, Undirected graphs}
}
Document
DOI: 10.4230/LIPIcs.STACS.2011.225
On Minimal Sturmian Partial Words

Authors: Francine Blanchet-Sadri and John Lensmire

Published in: LIPIcs, Volume 9, 28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011)

Abstract
Partial words, which are sequences that may have some undefined positions called holes, can be viewed as sequences over an extended alphabet A_diamond=A cup {diamond}$ where {diamond} stands for a hole and matches (or is compatible with every letter in A. The subword complexity of a partial word w, denoted by p_w(n), is the number of distinct full words (those without holes) over the alphabet that are compatible with factors of length n of w. A function f: N -> N is (k,h)-feasible if for each integer N geq 1, there exists a k-ary partial word w with h holes such that p_w(n) = f(n) for all n, 1 <= n <= N. We show that when dealing with feasibility in the context of finite binary partial words, the only linear functions that need investigation are f(n)=n+1 and f(n)=2n It turns out that both are (2,h)-feasible for all non-negative integers h. We classify all minimal partial words with $h$ holes of order $N$ with respect to f(n)=n+1, called Sturmian, computing their lengths as well as their numbers, except when h=0 in which case we describe an algorithm that generates all minimal Sturmian full words. We show that up to reversal and complement, any minimal Sturmian partial word with one hole is of the form a^i{diamond}a^jba^l, where i, j, l are integers satisfying some restrictions, that all minimal Sturmian partial words with two holes are one-periodic, and that up to complement, {diamond}(a^{N-1}{diamond})^{h-1} is the only minimal Sturmian partial word with h >= 3$holes. Finally, we give upper bounds on the lengths of minimal partial words with respect to f(n)=2n$ which are tight for h=0, 1 or 2.
Cite as

Francine Blanchet-Sadri and John Lensmire. On Minimal Sturmian Partial Words. In 28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011). Leibniz International Proceedings in Informatics (LIPIcs), Volume 9, pp. 225-236, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)

Copy BibTex To Clipboard

@InProceedings{blanchetsadri_et_al:LIPIcs.STACS.2011.225,
  author =	{Blanchet-Sadri, Francine and Lensmire, John},
  title =	{{On Minimal Sturmian Partial Words}},
  booktitle =	{28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011)},
  pages =	{225--236},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-25-5},
  ISSN =	{1868-8969},
  year =	{2011},
  volume =	{9},
  editor =	{Schwentick, Thomas and D\"{u}rr, Christoph},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2011.225},
  URN =		{urn:nbn:de:0030-drops-30131},
  doi =		{10.4230/LIPIcs.STACS.2011.225},
  annote =	{Keywords: Automata and formal languages; Combinatorics on words; Graph theory; Subword complexity; Feasible functions; Partial words; Sturmian words.}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact