1 Search Results for "De Winkle, Benjamin"

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-dev.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}
}
  • Refine by Author
  • 1 Blanchet-Sadri, Francine
  • 1 Bodnar, Michelle
  • 1 De Winkle, Benjamin

  • Refine by Classification

  • Refine by Keyword
  • 1 Border arrays
  • 1 Indeterminate strings
  • 1 Partial words
  • 1 Prefix arrays
  • 1 Undirected graphs

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2014

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 Imprint Privacy Contact