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

Presented is an algorithm (for learning a subclass of erasing regular pattern languages) which can be made to run with arbitrarily high probability of success on extended regular languages generated by patterns $\pi$ of the form $x_0 \alpha_1 x_1 ... \alpha_m x_m$ for unknown $m$ but known $c$, from number ... more >>>

A recursive enumerator for a function $h$ is an algorithm $f$ which enumerates for an input $x$ finitely many elements including $h(x)$. $f$ is an $k(n)$-enumerator if for every input $x$ of length $n$, $h(x)$ is among the first $k(n)$ elements enumerated by $f$. If there is a $k(n)$-enumerator for ... more >>>

Pin & Weil [PW95] characterized the automata of existentially first-order definable languages. We will use this result for the following characterization of the complexity class NP. Assume that the Polynomial-Time Hierarchy does not collapse. Then a regular language L characterizes NP as an unbalanced polynomial-time leaf language if and only ... more >>>

Rice's Theorem says that every nontrivial semantic property of programs is undecidable. It this spirit we show the following: Every nontrivial absolute (gap, relative) counting property of circuits is UP-hard with respect to polynomial-time Turing reductions. more >>>

The paper analyzes in terms of polynomial time many-one reductions the computational complexity of several natural equivalence relations on Boolean functions which derive from replacing variables by expressions. Most of these computational problems turn out to be between co-NP and Sigma^p_2. more >>>