RĂ¼diger Reischuk, Thomas Zeugmann

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 >>>

John Case, Sanjay Jain, Eric Martin, Arun Sharma, Frank Stephan

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 >>>

Stephen A. Fenner, William Gasarch, Brian Postow

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 >>>

Shuichi Hirahara, Mikito Nanashima

Pessiland is one of Impagliazzo's five possible worlds in which NP is hard on average, yet no one-way function exists. This world is considered the most pessimistic because it offers neither algorithmic nor cryptographic benefits.

In this paper, we develop a unified framework for constructing strong learning algorithms ... more >>>