Academic Journal
Indeterminate strings, prefix arrays & undirected graphs
| العنوان: | Indeterminate strings, prefix arrays & undirected graphs |
|---|---|
| المؤلفون: | Christodoulakis, M., Ryan, P.J., Smyth, W.F., Wang, S. |
| بيانات النشر: | Elsevier BV |
| سنة النشر: | 2015 |
| الوصف: | An integer array y=y[1.n] is said to be feasible if and only if y[1]=n and, for every i∈2.n, i≤i+y[i]≤n+1. A string is said to be indeterminate if and only if at least one of its elements is a subset of cardinality greater than one of a given alphabet Σ; otherwise it is said to be regular. A feasible array y is said to be regular if and only if it is the prefix array of some regular string. We show using a graph model that every feasible array of integers is a prefix array of some (indeterminate or regular) string, and for regular strings corresponding to y, we use the model to provide a lower bound on the alphabet size. We show further that there is a 1–1 correspondence between labelled simple graphs and indeterminate strings, and we show how to determine the minimum alphabet size σ of an indeterminate string x based on its associated graph Gx. Thus, in this sense, indeterminate strings are a more natural object of combinatorial interest than the strings on elements of Σ that have traditionally been studied. |
| نوع الوثيقة: | article in journal/newspaper |
| وصف الملف: | |
| اللغة: | English |
| تدمد: | 0304-3975 |
| Relation: | ispartof: Theoretical Computer Science spage 34 epage 48 vol 600; WOS:000362131800004; http://dx.doi.org/10.1016/j.tcs.2015.06.056; 991005541678307891; https://researchportal.murdoch.edu.au/esploro/outputs/journalArticle/Indeterminate-strings-prefix-arrays--undirected/991005541678307891; https://researchportal.murdoch.edu.au/view/delivery/61MUN_INST/12135569970007891/13136801230007891; alma:61MUN_INST/bibs/991005541678307891 |
| DOI: | 10.1016/j.tcs.2015.06.056 |
| الاتاحة: | https://doi.org/10.1016/j.tcs.2015.06.056 https://researchportal.murdoch.edu.au/esploro/outputs/journalArticle/Indeterminate-strings-prefix-arrays--undirected/991005541678307891 https://researchportal.murdoch.edu.au/view/delivery/61MUN_INST/12135569970007891/13136801230007891 |
| Rights: | © 2015 Elsevier B.V. ; Open |
| رقم الانضمام: | edsbas.9658AE14 |
| قاعدة البيانات: | BASE |
Full Text Finder | تدمد: | 03043975 |
|---|---|
| DOI: | 10.1016/j.tcs.2015.06.056 |