License: 
Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported license (CC BY-NC-ND 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2011.225
URN: urn:nbn:de:0030-drops-30131
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2011/3013/
Blanchet-Sadri, Francine ;
Lensmire, John
On Minimal Sturmian Partial Words
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.
BibTeX - Entry
@InProceedings{blanchetsadri_et_al:LIPIcs:2011:3013,
author = {Francine Blanchet-Sadri and John Lensmire},
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 = {Thomas Schwentick and Christoph D{\"u}rr},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2011/3013},
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.}
}
|
Keywords: |
|
Automata and formal languages; Combinatorics on words; Graph theory; Subword complexity; Feasible functions; Partial words; Sturmian words. |
|
Collection: |
|
28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011) |
|
Issue Date: |
|
2011 |
|
Date of publication: |
|
11.03.2011 |
