Arrow Research search

Author name cluster

F. Stephan

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.

4 papers
1 author row

Possible papers

4

I&C Journal 1995 Journal Article

Approximable Sets

  • R. Beigel
  • M. Kummer
  • F. Stephan

Much structural work on NP-complete sets has exploited SAT′s d-self-reducibility. In this paper, we exploit the additional fact that SAT is a d-cylinder to show that NP-complete sets are p-superterse unless P = NP. In fact, every set that is NP-hard under polynomial-time n o(1)-tt reductions is p-superterse unless P = NP. In particular, no p-selective set is NP-hard under polynomial-time n o(1)-tt reductions unless P = NP. In addition, no easily countable set is NP-hard under Turing reductions unless P = NP. Self-reducibility does not seem to suffice far our main result: in a relativized world, we construct a d-self-reducible set in NP − P that is polynomial-time 2-tt reducible to a p-selective set.

Details DOI

I&C Journal 1995 Journal Article

Language Learning from Texts: Mindchanges, Limited Memory, and Monotonicity

  • E. Kinber
  • F. Stephan

The paper explores language learning in the limit under various constraints on the number of mindchanges, memory, and monotonicity. We define language learning with limited (long term) memory and prove that learning with limited memory is exactly the same as learning via set driven machines (when the order of the input string is not taken into account). Further we show that every language learnable via a set driven machine is learnable via a conservative machine (making only justifiable mindchanges). We get a variety of separation results for learning with bounded number of mindchanges or limited memory under restrictions on monotonicity. A surprising result is that there are families of languages that can be monotonically learned with at most one mindchange, but can neither be weak-monotonically nor conservatively learned. Many separation results have a variant: If a criterion A can be separated from B, then often it is possible to find a family L of languages such that L is A and B learnable, but while it is possible to restrict the number of mindchanges or long term memory on criterion A, this is impossible for B.

Details DOI

I&C Journal 1995 Journal Article

Quantifying the Amount of Verboseness

  • R. Beigel
  • M. Kummer
  • F. Stephan

We study the fine structure of the classification of sets of natural numbers A according to the number of queries which are needed to compute the n-fold characteristic function of A. A complete characterization is obtained, relating the question to finite combinatorics. In order to obtain an explicit description we consider several interesting combinatorial problems.

Details DOI
v2026.09.13