Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with inductive inference:
TR98-069 | 7th December 1998
RĂ¼diger Reischuk, Thomas Zeugmann

An Average-Case Optimal One-Variable Pattern Language Learner

A new algorithm for learning one-variable pattern languages from positive data
is proposed and analyzed with respect to its average-case behavior.
We consider the total learning time that takes into account all
operations till convergence to a correct hypothesis is achieved.

For almost all meaningful distributions
defining how ... more >>>

TR04-058 | 28th May 2004
John Case, Sanjay Jain, Eric Martin, Arun Sharma, Frank Stephan

Identifying Clusters from Positive Data

The present work studies clustering from an abstract point of view
and investigates its properties in the framework of inductive inference.
Any class $S$ considered is given by a numbering
$A_0,A_1,...$ of nonempty subsets of the natural numbers
or the rational k-dimensional vector space as a hypothesis space.
A clustering ... more >>>

TR08-053 | 27th March 2008
Stephen A. Fenner, William Gasarch, Brian Postow

The complexity of learning SUBSEQ(A)

Higman showed that if A is *any* language then SUBSEQ(A)
is regular, where SUBSEQ(A) is the language of all
subsequences of strings in A. (The result we attribute
to Higman is actually an easy consequence of his work.)
Let s_1, s_2, s_3, ... more >>>

ISSN 1433-8092 | Imprint