DROPS

Document

09281 Abstracts Collection – Search Methodologies

Authors: Rudolf Ahlswede, Ferdinando Cicalese, and Ugo Vaccaro

Published in: Dagstuhl Seminar Proceedings, Volume 9281, Search Methodologies (2009)

Abstract

From 05.07.09 to 10.07.09, the Dagstuhl Seminar 09281 on ``Search Methodologies '' was held in Schloss Dagstuhl~--~Leibniz Center for Informatics. Abstracts of the presentations given during the seminar are put together in this paper. The first section describes the seminar topics and goals in general. We also briefly comment on how the topics were addressed in the talks. Links to extended abstracts or full papers are provided, if available.

Cite as

Rudolf Ahlswede, Ferdinando Cicalese, and Ugo Vaccaro. 09281 Abstracts Collection – Search Methodologies. In Search Methodologies. Dagstuhl Seminar Proceedings, Volume 9281, pp. 1-15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)

Copy BibTex To Clipboard

@InProceedings{ahlswede_et_al:DagSemProc.09281.1,
  author =	{Ahlswede, Rudolf and Cicalese, Ferdinando and Vaccaro, Ugo},
  title =	{{09281 Abstracts Collection – Search Methodologies}},
  booktitle =	{Search Methodologies},
  pages =	{1--15},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2009},
  volume =	{9281},
  editor =	{Rudolf Ahlswede and Ferdinando Cicalese and Ugo Vaccaro},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.09281.1},
  URN =		{urn:nbn:de:0030-drops-22457},
  doi =		{10.4230/DagSemProc.09281.1},
  annote =	{Keywords: Search algorithms, group testing, fault-tolerance, identification, decision tree, multi-access communication}
}

Document

DOI: 10.4230/DagSemProc.09281.2

Explicit Non-Adaptive Combinatorial Group Testing Schemes

Authors: Ely Porat and Amir Rotschild

Published in: Dagstuhl Seminar Proceedings, Volume 9281, Search Methodologies (2009)

Abstract

Group testing is a long studied problem in combinatorics: A small set of r ill people should be identified out of the whole (n people) by using only queries (tests) of the form "Does set X contain an ill human?". In this paper we provide an explicit construction of a testing scheme which is better (smaller) than any known explicit construction. This scheme has \Theta(min[r2 log n, n])tests which is as many as the best non-explicit schemes have. In our construction we use a fact that may have a value by its own right: Linear error-correction codes with parameters [m, k, \delta m]q meeting the Gilbert-Varshamov bound may be constructed quite efficiently, in \Theta[q^{k}m) time.

Cite as

Ely Porat and Amir Rotschild. Explicit Non-Adaptive Combinatorial Group Testing Schemes. In Search Methodologies. Dagstuhl Seminar Proceedings, Volume 9281, pp. 1-13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)

Copy BibTex To Clipboard

@InProceedings{porat_et_al:DagSemProc.09281.2,
  author =	{Porat, Ely and Rotschild, Amir},
  title =	{{Explicit Non-Adaptive Combinatorial Group Testing Schemes}},
  booktitle =	{Search Methodologies},
  pages =	{1--13},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2009},
  volume =	{9281},
  editor =	{Rudolf Ahlswede and Ferdinando Cicalese and Ugo Vaccaro},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.09281.2},
  URN =		{urn:nbn:de:0030-drops-22414},
  doi =		{10.4230/DagSemProc.09281.2},
  annote =	{Keywords: Prime Numbers, Group Testing, Streaming, Pattern Matching}
}

Document

DOI: 10.4230/DagSemProc.09281.3

Locating and Detecting Arrays for Interaction Faults

Authors: Charles J. Colbourn and Daniel W. McClary

Published in: Dagstuhl Seminar Proceedings, Volume 9281, Search Methodologies (2009)

Abstract

The identification of interaction faults in component-based systems has focused on indicating the presence of faults, rather than their location and magnitude. While this is a valuable step in screening a system for interaction faults prior to its release, it provides little information to assist in the correction of such faults. Consequently tests to reveal the location of interaction faults are of interest. The problem of nonadaptive location of interaction faults is formalized under the hypothesis that the system contains (at most) some number d of faults, each involving (at most) some number t of interacting factors. Restrictions on the number and size of the putative faults lead to numerous variants of the basic problem. The relationships between this class of problems and interaction testing using covering arrays to indicate the presence of faults, designed experiments to measure and model faults, and combinatorial group testing to locate faults in a more general testing scenario, are all examined. While each has some definite similarities with the fault location problems for component-based systems, each has some striking differences as well. In this paper, we formulate the combinatorial problems for locating and detecting arrays to undertake interaction fault location. Necessary conditions for existence are established, and using a close connection to covering arrays, asymptotic bounds on the size of minimal locating and detecting arrays are established. A final version of this paper appears in J Comb Optim (2008) 15: 17-48.

Cite as

Charles J. Colbourn and Daniel W. McClary. Locating and Detecting Arrays for Interaction Faults. In Search Methodologies. Dagstuhl Seminar Proceedings, Volume 9281, pp. 1-34, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)

Copy BibTex To Clipboard

@InProceedings{colbourn_et_al:DagSemProc.09281.3,
  author =	{Colbourn, Charles J. and McClary, Daniel W.},
  title =	{{Locating and Detecting Arrays for Interaction Faults}},
  booktitle =	{Search Methodologies},
  pages =	{1--34},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2009},
  volume =	{9281},
  editor =	{Rudolf Ahlswede and Ferdinando Cicalese and Ugo Vaccaro},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.09281.3},
  URN =		{urn:nbn:de:0030-drops-22405},
  doi =		{10.4230/DagSemProc.09281.3},
  annote =	{Keywords: Covering array, Orthogonal array, Factorial design, Cover-free family, Disjunct matrix, Locating array, Detecting array}
}

Document

DOI: 10.4230/DagSemProc.09281.4

Minimax Trees in Linear Time with Applications

Authors: Pawel Gawrychowski and Travis Gagie

Published in: Dagstuhl Seminar Proceedings, Volume 9281, Search Methodologies (2009)

Abstract

A minimax tree is similar to a Huffman tree except that, instead of minimizing the weighted average of the leaves' depths, it minimizes the maximum of any leaf's weight plus its depth. Golumbic (1976) introduced minimax trees and gave a Huffman-like, $O (n log n)$-time algorithm for building them. Drmota and Szpankowski (2002) gave another $O (n log n)$-time algorithm, which takes linear time when the weights are already sorted by their fractional parts. In this paper we give the first linear-time algorithm for building minimax trees for unsorted real weights.

Cite as

Pawel Gawrychowski and Travis Gagie. Minimax Trees in Linear Time with Applications. In Search Methodologies. Dagstuhl Seminar Proceedings, Volume 9281, pp. 1-11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)

Copy BibTex To Clipboard

@InProceedings{gawrychowski_et_al:DagSemProc.09281.4,
  author =	{Gawrychowski, Pawel and Gagie, Travis},
  title =	{{Minimax Trees in Linear Time with Applications}},
  booktitle =	{Search Methodologies},
  pages =	{1--11},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2009},
  volume =	{9281},
  editor =	{Rudolf Ahlswede and Ferdinando Cicalese and Ugo Vaccaro},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.09281.4},
  URN =		{urn:nbn:de:0030-drops-22421},
  doi =		{10.4230/DagSemProc.09281.4},
  annote =	{Keywords: Data structures, data compression, prefix-free coding}
}

Document

DOI: 10.4230/DagSemProc.09281.5

Pattern matching with don't cares and few errors

Authors: Raphael Clifford, Klim Efremo, Ely Porat, and Amir Rotschild

Published in: Dagstuhl Seminar Proceedings, Volume 9281, Search Methodologies (2009)

Abstract

We present solutions for the k-mismatch pattern matching problem with don't cares. Given a text t of length n and a pattern p of length m with don't care symbols and a bound k, our algorithms find all the places that the pattern matches the text with at most k mismatches. We first give an \Theta(n(k + logmlog k) log n) time randomised algorithm which finds the correct answer with high probability. We then present a new deter- ministic \Theta(nk^2 log^m)time solution that uses tools originally developed for group testing. Taking our derandomisation approach further we de- velop an approach based on k-selectors that runs in \Theta(nk polylogm) time. Further, in each case the location of the mismatches at each alignment is also given at no extra cost.

Cite as

Raphael Clifford, Klim Efremo, Ely Porat, and Amir Rotschild. Pattern matching with don't cares and few errors. In Search Methodologies. Dagstuhl Seminar Proceedings, Volume 9281, pp. 1-19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)

Copy BibTex To Clipboard

@InProceedings{clifford_et_al:DagSemProc.09281.5,
  author =	{Clifford, Raphael and Efremo, Klim and Porat, Ely and Rotschild, Amir},
  title =	{{Pattern matching with don't cares and few errors}},
  booktitle =	{Search Methodologies},
  pages =	{1--19},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2009},
  volume =	{9281},
  editor =	{Rudolf Ahlswede and Ferdinando Cicalese and Ugo Vaccaro},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.09281.5},
  URN =		{urn:nbn:de:0030-drops-22442},
  doi =		{10.4230/DagSemProc.09281.5},
  annote =	{Keywords: Prime Numbers, Group Testing, Streaming, Pattern Matching}
}

Document

DOI: 10.4230/DagSemProc.09281.6

Rounds in Combinatorial Search

Authors: Gábor Wiener

Published in: Dagstuhl Seminar Proceedings, Volume 9281, Search Methodologies (2009)

Abstract

The search complexity of a separating system ${cal H} subseteq 2^{[m]}$ is the minimum number of questions of type ``$xin H$? hinspace '' (where $H in {cal H}$) needed in the worst case to determine a hidden element $xin [m]$. If we are allowed to ask the questions in at most $k$ batches then we speak of the emph{$k$-round} (or emph{$k$-stage}) complexity of ${cal H}$, denoted by $hbox{c}_k ({cal H})$. While $1$-round and $m$-round complexities (called non-adaptive and adaptive complexities, respectively) are widely studied (see for example Aigner cite{A}), much less is known about other possible values of $k$, though the cases with small values of $k$ (tipically $k=2$) attracted significant attention recently, due to their applications in DNA library screening. It is clear that $ |{cal H}| geq hbox{c}_{1} ({cal H}) geq hbox{c}_{2} ({cal H}) geq ldots geq hbox{c}_{m} ({cal H})$. A group of problems raised by {G. O. H. Katona} cite{Ka} is to characterize those separating systems for which some of these inequalities are tight. In this paper we are discussing set systems ${cal H}$ with the property $|{cal H}| = hbox{c}_{k} ({cal H}) $ for any $kgeq 3$. We give a necessary condition for this property by proving a theorem about traces of hypergraphs which also has its own interest.

Cite as

Gábor Wiener. Rounds in Combinatorial Search. In Search Methodologies. Dagstuhl Seminar Proceedings, Volume 9281, pp. 1-5, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)

Copy BibTex To Clipboard

@InProceedings{wiener:DagSemProc.09281.6,
  author =	{Wiener, G\'{a}bor},
  title =	{{Rounds in Combinatorial Search}},
  booktitle =	{Search Methodologies},
  pages =	{1--5},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2009},
  volume =	{9281},
  editor =	{Rudolf Ahlswede and Ferdinando Cicalese and Ugo Vaccaro},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.09281.6},
  URN =		{urn:nbn:de:0030-drops-22399},
  doi =		{10.4230/DagSemProc.09281.6},
  annote =	{Keywords: Search, group testing, adaptiveness, hypergraph, trace}
}

Document

DOI: 10.4230/DagSemProc.09281.7

Some Aspects of Finite State Channel related to Hidden Markov Process

Authors: Kingo Kobayashi

Published in: Dagstuhl Seminar Proceedings, Volume 9281, Search Methodologies (2009)

Abstract

We have no satisfactory capacity formula for most channels with finite states. Here, we consider some interesting examples of finite state channels, such as Gilbert-Elliot channel, trapdoor channel, etc., to reveal special characters of problems and difficulties to determine the capacities. Meanwhile, we give a simple expression of the capacity formula for Gilbert-Elliot channel by using a hidden Markov source for the optimal input process. This idea should be extended to other finite state channels.

Cite as

Kingo Kobayashi. Some Aspects of Finite State Channel related to Hidden Markov Process. In Search Methodologies. Dagstuhl Seminar Proceedings, Volume 9281, pp. 1-16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)

Copy BibTex To Clipboard

@InProceedings{kobayashi:DagSemProc.09281.7,
  author =	{Kobayashi, Kingo},
  title =	{{Some Aspects of Finite State Channel related to Hidden Markov Process}},
  booktitle =	{Search Methodologies},
  pages =	{1--16},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2009},
  volume =	{9281},
  editor =	{Rudolf Ahlswede and Ferdinando Cicalese and Ugo Vaccaro},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.09281.7},
  URN =		{urn:nbn:de:0030-drops-22434},
  doi =		{10.4230/DagSemProc.09281.7},
  annote =	{Keywords: Finite state channel, Hidden Markov source, Gilbert-Elliot channel, Trapdoor Channel}
}

Document

DOI: 10.4230/DagSemProc.06201.3

Local Minimax Learning of Approximately Polynomial Functions

Authors: Lee Jones and Konstantin Rybnikov

Published in: Dagstuhl Seminar Proceedings, Volume 6201, Combinatorial and Algorithmic Foundations of Pattern and Association Discovery (2006)

Abstract

Suppose we have a number of noisy measurements of an unknown real-valued function $f$ near point of interest $mathbf{x}_0 in mathbb{R}^d$. Suppose also that nothing can be assumed about the noise distribution, except for zero mean and bounded covariance matrix. We want to estimate $f$ at $mathbf{x=x}_0$ using a general linear parametric family $f(mathbf{x};mathbf{a}) = a_0 h_0 (mathbf{x}) ++ a_q h_q (mathbf{x})$, where $mathbf{a} in mathbb{R}^q$ and $h_i$'s are bounded functions on a neighborhood $B$ of $mathbf{x}_0$ which contains all points of measurement. Typically, $B$ is a Euclidean ball or cube in $mathbb{R}^d$ (more generally, a ball in an $l_p$-norm). In the case when the $h_i$'s are polynomial functions in $x_1,ldots,x_d$ the model is called locally-polynomial. In particular, if the $h_i$'s form a basis of the linear space of polynomials of degree at most two, the model is called locally-quadratic (if the degree is at most three, the model is locally-cubic, etc.). Often, there is information, which is called context, about the function $f$ (restricted to $B$ ) available, such as that it takes values in a known interval, or that it satisfies a Lipschitz condition. The theory of local minimax estimation with context for locally-polynomial models and approximately locally polynomial models has been recently initiated by Jones. In the case of local linearity and a bound on the change of $f$ on $B$, where $B$ is a ball, the solution for squared error loss is in the form of ridge regression, where the ridge parameter is identified; hence, minimax justification for ridge regression is given together with explicit best error bounds. The analysis of polynomial models of degree above 1 leads to interesting and difficult questions in real algebraic geometry and non-linear optimization. We show that in the case when $f$ is a probability function, the optimal (in the minimax sense) estimator is effectively computable (with any given precision), thanks to Tarski's elimination principle.

Cite as

Lee Jones and Konstantin Rybnikov. Local Minimax Learning of Approximately Polynomial Functions. In Combinatorial and Algorithmic Foundations of Pattern and Association Discovery. Dagstuhl Seminar Proceedings, Volume 6201, pp. 1-12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2007)

Copy BibTex To Clipboard

@InProceedings{jones_et_al:DagSemProc.06201.3,
  author =	{Jones, Lee and Rybnikov, Konstantin},
  title =	{{Local Minimax Learning of Approximately Polynomial Functions}},
  booktitle =	{Combinatorial and Algorithmic Foundations of Pattern and Association Discovery},
  pages =	{1--12},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2007},
  volume =	{6201},
  editor =	{Rudolf Ahlswede and Alberto Apostolico and Vladimir I. Levenshtein},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.06201.3},
  URN =		{urn:nbn:de:0030-drops-8912},
  doi =		{10.4230/DagSemProc.06201.3},
  annote =	{Keywords: Local learning, statistical learning, estimator, minimax, convex optimization, quantifier elimination, semialgebraic, ridge regression, polynomial}
}

Document

DOI: 10.4230/DagSemProc.06201.7

Solving Classical String Problems an Compressed Texts

Authors: Yury Lifshits

Published in: Dagstuhl Seminar Proceedings, Volume 6201, Combinatorial and Algorithmic Foundations of Pattern and Association Discovery (2006)

Abstract

How to solve string problems, if instead of input string we get only program generating it? Is it possible to solve problems faster than just "generate text + apply classical algorithm"? In this paper we consider strings generated by straight-line programs (SLP). These are programs using only assignment operator. We show new algorithms for equivalence, pattern matching, finding periods and covers, computing fingerprint table on SLP-generated strings. From the other hand, computing the Hamming distance is NP-hard. Main corollary is an $O(n2*m)$ algorithm for pattern matching in LZ-compressed texts.

Cite as

Yury Lifshits. Solving Classical String Problems an Compressed Texts. In Combinatorial and Algorithmic Foundations of Pattern and Association Discovery. Dagstuhl Seminar Proceedings, Volume 6201, pp. 1-10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)

Copy BibTex To Clipboard

@InProceedings{lifshits:DagSemProc.06201.7,
  author =	{Lifshits, Yury},
  title =	{{Solving Classical String Problems an Compressed Texts}},
  booktitle =	{Combinatorial and Algorithmic Foundations of Pattern and Association Discovery},
  pages =	{1--10},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2006},
  volume =	{6201},
  editor =	{Rudolf Ahlswede and Alberto Apostolico and Vladimir I. Levenshtein},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.06201.7},
  URN =		{urn:nbn:de:0030-drops-7984},
  doi =		{10.4230/DagSemProc.06201.7},
  annote =	{Keywords: Pattern matching, Compressed text}
}

Document

DOI: 10.4230/DagSemProc.06201.1

06201 Abstracts Collection – Combinatorial and Algorithmic Foundations of Pattern and Association Discovery

Authors: Rudolf Ahlswede, Alberto Apostolico, and Vladimir I. Levenshtein

Published in: Dagstuhl Seminar Proceedings, Volume 6201, Combinatorial and Algorithmic Foundations of Pattern and Association Discovery (2006)

Abstract

From 15.05.06 to 20.05.06, the Dagstuhl Seminar 06201 ``Combinatorial and Algorithmic Foundations of Pattern and Association Discovery'' was held in the International Conference and Research Center (IBFI), Schloss Dagstuhl. During the seminar, several participants presented their current research, and ongoing work and open problems were discussed. Abstracts of the presentations given during the seminar as well as abstracts of seminar results and ideas are put together in this paper. The first section describes the seminar topics and goals in general. Links to extended abstracts or full papers are provided, if available.

Cite as

Rudolf Ahlswede, Alberto Apostolico, and Vladimir I. Levenshtein. 06201 Abstracts Collection – Combinatorial and Algorithmic Foundations of Pattern and Association Discovery. In Combinatorial and Algorithmic Foundations of Pattern and Association Discovery. Dagstuhl Seminar Proceedings, Volume 6201, pp. 1-15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)

Copy BibTex To Clipboard

@InProceedings{ahlswede_et_al:DagSemProc.06201.1,
  author =	{Ahlswede, Rudolf and Apostolico, Alberto and Levenshtein, Vladimir I.},
  title =	{{06201 Abstracts Collection – Combinatorial and Algorithmic Foundations of Pattern and Association Discovery}},
  booktitle =	{Combinatorial and Algorithmic Foundations of Pattern and Association Discovery},
  pages =	{1--15},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2006},
  volume =	{6201},
  editor =	{Rudolf Ahlswede and Alberto Apostolico and Vladimir I. Levenshtein},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.06201.1},
  URN =		{urn:nbn:de:0030-drops-7873},
  doi =		{10.4230/DagSemProc.06201.1},
  annote =	{Keywords: Data compression, pattern matching, pattern discovery, search, sorting, molecular biology, reconstruction, genome rearrangements}
}

Document

DOI: 10.4230/DagSemProc.06201.2

06201 Executive Summary – Combinatorial and Algorithmic Foundations of Pattern and Association Discovery

Authors: Rudolf Ahlswede, Alberto Apostolico, and Vladimir I. Levenshtein

Published in: Dagstuhl Seminar Proceedings, Volume 6201, Combinatorial and Algorithmic Foundations of Pattern and Association Discovery (2006)

Abstract

The goals of this seminar have been (1) to identify and match recently developed methods to specific tasks and data sets in a core of application areas; next, based on feedback from the specific applied domain, (2) to fine tune and personalize those applications, and finally (3) to identify and tackle novel combinatorial and algorithmic problems, in some cases all the way to the development of novel software tools.

Cite as

Rudolf Ahlswede, Alberto Apostolico, and Vladimir I. Levenshtein. 06201 Executive Summary – Combinatorial and Algorithmic Foundations of Pattern and Association Discovery. In Combinatorial and Algorithmic Foundations of Pattern and Association Discovery. Dagstuhl Seminar Proceedings, Volume 6201, pp. 1-2, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)

Copy BibTex To Clipboard

@InProceedings{ahlswede_et_al:DagSemProc.06201.2,
  author =	{Ahlswede, Rudolf and Apostolico, Alberto and Levenshtein, Vladimir I.},
  title =	{{06201 Executive Summary – Combinatorial and Algorithmic Foundations of Pattern and Association Discovery}},
  booktitle =	{Combinatorial and Algorithmic Foundations of Pattern and Association Discovery},
  pages =	{1--2},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2006},
  volume =	{6201},
  editor =	{Rudolf Ahlswede and Alberto Apostolico and Vladimir I. Levenshtein},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.06201.2},
  URN =		{urn:nbn:de:0030-drops-7926},
  doi =		{10.4230/DagSemProc.06201.2},
  annote =	{Keywords: Data compression, pattern matching, pattern discovery, search, sorting, molecular biology, reconstruction, genome rearrangements}
}

Document

DOI: 10.4230/DagSemProc.06201.4

Non--binary error correcting codes with noiseless feedback, localized errors, or both

Authors: Rudolf Ahlswede, Christian Deppe, and Vladimir Lebedev

Published in: Dagstuhl Seminar Proceedings, Volume 6201, Combinatorial and Algorithmic Foundations of Pattern and Association Discovery (2006)

Abstract

We investigate non--binary error correcting codes with noiseless feedback, localized errors, or both. It turns out that the Hamming bound is a central concept. For block codes with feedback we present here a coding scheme based on an idea of erasions, which we call the {\bf rubber method}. It gives an optimal rate for big error correcting fraction $\tau$ ($>{1\over q}$) and infinitely many points on the Hamming bound for small $\tau$. We also consider variable length codes with all lengths bounded from above by $n$ and the end of a word carries the symbol $\Box$ and is thus recognizable by the decoder. For both, the $\Box$-model with feedback and the $\Box$-model with localized errors, the Hamming bound is the exact capacity curve for $\tau <1/2.$ Somewhat surprisingly, whereas with feedback the capacity curve coincides with the Hamming bound also for $1/2\leq \tau \leq 1$, in this range for localized errors the capacity curve equals 0. Also we give constructions for the models with both, feedback and localized errors.

Cite as

Rudolf Ahlswede, Christian Deppe, and Vladimir Lebedev. Non--binary error correcting codes with noiseless feedback, localized errors, or both. In Combinatorial and Algorithmic Foundations of Pattern and Association Discovery. Dagstuhl Seminar Proceedings, Volume 6201, pp. 1-4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)

Copy BibTex To Clipboard

@InProceedings{ahlswede_et_al:DagSemProc.06201.4,
  author =	{Ahlswede, Rudolf and Deppe, Christian and Lebedev, Vladimir},
  title =	{{Non--binary error correcting codes with noiseless feedback, localized errors, or both}},
  booktitle =	{Combinatorial and Algorithmic Foundations of Pattern and Association Discovery},
  pages =	{1--4},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2006},
  volume =	{6201},
  editor =	{Rudolf Ahlswede and Alberto Apostolico and Vladimir I. Levenshtein},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.06201.4},
  URN =		{urn:nbn:de:0030-drops-7849},
  doi =		{10.4230/DagSemProc.06201.4},
  annote =	{Keywords: Error-correcting codes, localized errors, feedback, variable length codes}
}

Document

DOI: 10.4230/DagSemProc.06201.5

On the Monotonicity of the String Correction Factor for Words with Mismatches

Authors: Alberto Apostolico and Cinzia Pizzi

Published in: Dagstuhl Seminar Proceedings, Volume 6201, Combinatorial and Algorithmic Foundations of Pattern and Association Discovery (2006)

Abstract

The string correction factor is the term by which the probability of a word $w$ needs to be multiplied in order to account for character changes or ``errors'' occurring in at most $k$ arbitrary positions in that word. The behavior of this factor, as a function of $k$ and of the word length, has implications on the number of candidates that need to be considered and weighted when looking for subwords of a sequence that present unusually recurrent replicas within some bounded number of mismatches. Specifically, it is seen that over intervals of mono- or bi-tonicity for the correction factor, only some of the candidates need be considered. This mitigates the computation and leads to tables of over-represented words that are more compact to represent and inspect. In recent work, expectation and score monotonicity has been established for a number of cases of interest, under {em i.i.d.} probabilistic assumptions. The present paper reviews the cases of bi-tonic behavior for the correction factor, concentrating on the instance in which the question is still open.

Cite as

Alberto Apostolico and Cinzia Pizzi. On the Monotonicity of the String Correction Factor for Words with Mismatches. In Combinatorial and Algorithmic Foundations of Pattern and Association Discovery. Dagstuhl Seminar Proceedings, Volume 6201, pp. 1-9, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)

Copy BibTex To Clipboard

@InProceedings{apostolico_et_al:DagSemProc.06201.5,
  author =	{Apostolico, Alberto and Pizzi, Cinzia},
  title =	{{On the Monotonicity of the String Correction Factor for Words with Mismatches}},
  booktitle =	{Combinatorial and Algorithmic Foundations of Pattern and Association Discovery},
  pages =	{1--9},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2006},
  volume =	{6201},
  editor =	{Rudolf Ahlswede and Alberto Apostolico and Vladimir I. Levenshtein},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.06201.5},
  URN =		{urn:nbn:de:0030-drops-7899},
  doi =		{10.4230/DagSemProc.06201.5},
  annote =	{Keywords: Pattern discovery, Motif, Over-represented word, Monotone score, Correction Factor}
}

Document

DOI: 10.4230/DagSemProc.06201.6

Sequence prediction for non-stationary processes

Authors: Daniil Ryabko and Marcus Hutter

Published in: Dagstuhl Seminar Proceedings, Volume 6201, Combinatorial and Algorithmic Foundations of Pattern and Association Discovery (2006)

Abstract

We address the problem of sequence prediction for nonstationary stochastic processes. In particular, given two measures on the set of one-way infinite sequences over a finite alphabet, consider the question whether one of the measures predicts the other. We find some conditions on local absolute continuity under which prediction is possible.

Cite as

Daniil Ryabko and Marcus Hutter. Sequence prediction for non-stationary processes. In Combinatorial and Algorithmic Foundations of Pattern and Association Discovery. Dagstuhl Seminar Proceedings, Volume 6201, pp. 1-12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)

Copy BibTex To Clipboard

@InProceedings{ryabko_et_al:DagSemProc.06201.6,
  author =	{Ryabko, Daniil and Hutter, Marcus},
  title =	{{Sequence prediction for non-stationary processes}},
  booktitle =	{Combinatorial and Algorithmic Foundations of Pattern and Association Discovery},
  pages =	{1--12},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2006},
  volume =	{6201},
  editor =	{Rudolf Ahlswede and Alberto Apostolico and Vladimir I. Levenshtein},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.06201.6},
  URN =		{urn:nbn:de:0030-drops-7900},
  doi =		{10.4230/DagSemProc.06201.6},
  annote =	{Keywords: Sequence prediction, probability forecasting, local absolute continuity}
}

Document

DOI: 10.4230/DagSemProc.06201.8

Some Results for Identification for Sources and its Extension to Liar Models

Authors: Zlatko Varbanov

Published in: Dagstuhl Seminar Proceedings, Volume 6201, Combinatorial and Algorithmic Foundations of Pattern and Association Discovery (2006)

Abstract

Let (${cal U}, P$) be a source, where ${cal U} = {1,2,dots,N}, P = {P_1, P_2, dots, P_N}$, and let ${cal C} = {c_1,c_2,dots,c_N}$ be a binary prefix code (PC) for this source with $||c_u||$ as length of $c_u$. Introduce the random variable $U$ with Prob($U=u$) = $p_u$ for $u = 1,2,dots,N$ and the random variable $C$ with $C = c_u = (c_1,c_2,dots,c_{u||c_u||})$ if $U=u$. We use the PC for noiseless identification, that is user $u$ wants to know whether the source output equals $u$, that is, whether $C$ equals $c_u$ or not. The user iteratively checks whether $C$ coincides with $c_u$ in the first, second, etc. letter and stops when the first different letter occurs or when $C = c_u$. What is the expected number $L_{cal C}(P,u)$ of checkings? In order to calculate this quantity we introduce for the binary tree $T_{cal C}$, whose leaves are the codewords $c_1,c_2,dots,c_N$, the sets of leaves ${cal C}_{ik} (1 leq i leq N; 1 leq k)$, where ${cal C}_{ik} = {c in {cal C}: c$ coincides with $c_i$ exactly until the $k$'th letter of $c_i}$. If $C$ takes a value in ${cal C}_{uk}, 0 leq k leq ||c_u||-1$, the answers are $k$ times "Yes" and 1 time "No". For $C = c_u$ the $$ L_{cal C}(P,u) = sum_{k=0}^{||c_u||-1}P(C in {cal C}_{uk})(k+1) + ||c_u||P_u. $$ For code ${cal C}$,~ $L_{cal C}(P) = max L_{cal C}(P,u)$, $1 geq u geq N$, is the expected number of checkings in the worst case and $L(P) = min L_{cal C}(P)$ is this number for the best code ${cal C}$. Let $P = P^N = {frac{1}{N}, dots, frac{1}{N}}$. We construct a prefix code ${cal C}$ in the following way. In each node (starting at the root) we split the number of remaining codewords in proportion as close as possible to $(frac{1}{2},frac{1}{2})$. It is known that $$ lim_{N ightarrow infty} L_{cal C}(P^N) = 2 $$ (Ahlswede, Balkenhol, Kleinewachter, 2003) We know that $L(P) leq 3$ for all $P$ (Ahlswede, Balkenhol, Kleinewachter, 2003). Also, the problem to estimate an universal constant $A = sup L(P)$ for general $P = (P_1,dots, P_N)$ was stated (Ahlswede, 2004). We compute this constant for uniform distribution and this code ${cal C}$. $$ sup_N L_{cal C}(P^N) = 2+frac{log_2(N-1)-2}{N} $$ Also, we consider the average number of checkings, if code ${cal C}$ is used: $ L_{cal C}(P,P) = sum P_u L_{cal C}(P,u)$, for ${u in {cal U}}$. We calculate the exact values of $L_{cal C}(P^N)$ and $L_{cal C}(P^N,P^N)$ for some $N$. Other problem is the extension of identification for sources to liar models. We obtain a upper bound for the expected number of checkings $L_{cal C}(P^N;e)$, where $e$ is the maximum number of lies. $$ L_{cal C}(P^N;e) leq M_{cal C}(P^N;e) = (e+1)L_{cal C}(P^N) + e; ~~ lim_{N ightarrow infty} M_{cal C}(P^N;e) = 3e+2 $$

Cite as

Zlatko Varbanov. Some Results for Identification for Sources and its Extension to Liar Models. In Combinatorial and Algorithmic Foundations of Pattern and Association Discovery. Dagstuhl Seminar Proceedings, Volume 6201, pp. 1-4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)

Copy BibTex To Clipboard

@InProceedings{varbanov:DagSemProc.06201.8,
  author =	{Varbanov, Zlatko},
  title =	{{Some Results for Identification for Sources and its Extension to Liar Models}},
  booktitle =	{Combinatorial and Algorithmic Foundations of Pattern and Association Discovery},
  pages =	{1--4},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2006},
  volume =	{6201},
  editor =	{Rudolf Ahlswede and Alberto Apostolico and Vladimir I. Levenshtein},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.06201.8},
  URN =		{urn:nbn:de:0030-drops-7820},
  doi =		{10.4230/DagSemProc.06201.8},
  annote =	{Keywords: Identification for sources, lies, prefix code}
}

18 Search Results for "Ahlswede, Rudolf"

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Thanks for your feedback!

Could not send message