Arrow Research search

Author name cluster

E.B. Kinber

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

5 papers
1 author row

Possible papers

5

I&C Journal 1995 Journal Article

How Inductive Inference Strategies Discover Their Errors

  • R. Freivalds
  • E.B. Kinber
  • R. Wiehagen

Several well-known inductive inference strategies change the actual hypothesis only when they discover that it "provably misclassifies" an example seen so far. This notion is made mathematically precise, and its general power is characterized. In spite of its strength, it is shown that this approach is not of universal power. Consequently, hypotheses are considered which "unprovably misclassify" examples, and the properties of this approach are studied. Among others, it turns out that this type is of the same power as monotonic identification. Then it is shown that universal power can be achieved only when an unbounded number of alternations of these dual types of hypotheses is allowed. Finally, a universal method is presented, enabling an inductive inference strategy to verify the incorrectness of any of its incorrect intermediate hypotheses.

Details DOI

TCS Journal 1993 Journal Article

On the power of inductive inference from good examples

  • R. Freivalds
  • E.B. Kinber
  • R. Wiehagen

The usual information in inductive inference available for the purposes of identifying an unknown recursive function f is the set of all input/output examples (x, f(x)), n εN. In contrast to this approach we show that it is considerably more powerful to work with finite sets of “good” examples even when these good examples are required to be effectively computable. The influence of the underlying numberings, with respect to which the identification has to be realized, to the capabilities of inference from good examples is also investigated. It turns out that nonstandard numberings can be much more powerful than Gödel numberings.

Details DOI

TCS Journal 1991 Journal Article

On complete sets of samples for generalized regular expressions

  • E.B. Kinber

The language of generalized regular expressions introduced by Brazma and Kinber [4] is a convenient tool for inductive formalization of sample computations. The decidability of the equivalence problem was proved and some other questions were investigated for this language in [4]. The following problem is important for the synthesis and is investigated in this paper: is it possible to specify an arbitrary class of equivalent programs by a finite set of samples. A positive answer to this question is obtained for a stronger equivalence relation when the equivalence implies a similarity of program structures.

Details DOI

TCS Journal 1983 Journal Article

On the power of probabilistic strategies in inductive inference

  • R. Wiehagen
  • R. Freivalds
  • E.B. Kinber

Inductive inference of programs of recursive functions from input/output examples by probabilistic strategies with an a priori bound n ϵ N of changes of hypotheses is investigated. Advantages of probabilistic strategies over deterministic ones are shown concerning their power in principle (for every n ⩾ 2, with probability arbitrarily close to 1, inference of function classes which cannot be inferred by any deterministic strategy with n changes of hypotheses), as well as their computational complexity (linear speed-up of the number of changes of hypotheses necessary for inference by deterministic strategies).

Details DOI
v2026.09.13