Author name cluster

Jochen Nessel

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

TCS Journal 2007 Journal Article

Invertible classes

Sanjay Jain
Jochen Nessel
Frank Stephan

This paper considers when one can invert general recursive operators which map a class of functions F to F. In this regard, we study four different notions of inversion. We additionally consider enumeration of operators which cover all general recursive operators which map F to F in the sense that, for every general recursive operator Ψ mapping F to F, there is a general recursive operator in the enumerated sequence which behaves the same way as Ψ on F. Three different possible types of enumeration are studied.

Details DOI

TCS Journal 2005 Journal Article

Learning erasing pattern languages with queries

Jochen Nessel
Steffen Lange

A pattern is a finite string of constant and variable symbols. The non-erasing language generated by a pattern is the set of all strings of constant symbols that can be obtained by substituting non-empty strings for variables. In order to build the erasing language generated by a pattern, it is also admissible to substitute the empty string. The present paper deals with the problem of learning erasing pattern languages within Angluin's model of learning with queries. Moreover, the learnability of erasing pattern languages with queries is studied when additional information is available. The results obtained are compared with previously known results in case non-erasing pattern languages have to be learned. First, when regular pattern languages have to be learned, it is shown that the learnability results for the non-erasing case remain valid, if the proper superclass of all erasing regular pattern languages is the object of learning. Second, in the general case, serious differences have been observed. For instance, it turns out that arbitrary erasing pattern languages cannot be learned in settings in which, in the non-erasing case, even polynomially many queries will suffice.

Details DOI

TCS Journal 2003 Journal Article

Decision lists over regular patterns

Steffen Lange
Jochen Nessel

The paper introduces the notion of decision lists over regular patterns. This formalism provides a strict extension of regular erasing pattern languages and of containment decision lists. Formal properties of the resulting language class, a subclass of the regular languages, are investigated. In particular, we show that decision lists over regular patterns have exactly the same expressive power as decision trees over regular patterns. Moreover, we study the learnability of the resulting language class within different formal settings including Gold's model of learning in the limit as well as Valiant's model of approximately correct learning.

Details DOI

TCS Journal 2001 Journal Article

On the learnability of recursively enumerable languages from good examples

Sanjay Jain
Steffen Lange
Jochen Nessel

The present paper investigates identification of indexed families L of recursively enumerable languages from good examples. We distinguish class-preserving learning from good examples (the good examples have to be generated with respect to a hypothesis space having the same range as L ) and class-comprising learning from good examples (the good examples have to be selected with respect to a hypothesis space comprising the range of L ). A learner is required to learn a target language on every finite superset of the good examples for it. If the learner's first and only conjecture is correct then the underlying learning model is referred to as finite identification from good examples and if the learner makes a finite number of incorrect conjectures before always outputting a correct one, the model is referred to as limit identification from good examples. In the context of class-preserving learning, it is shown that the learning power of finite and limit identification from good text examples coincide. When class comprising learning from good text examples is concerned, limit identification is strictly more powerful than finite learning. Furthermore, if learning from good informant examples is considered, limit identification is superior to finite identification in the class preserving as well as in the class-comprising case. Finally, we relate the models of learning from good examples to one another as well as to the standard learning models in the context of Gold-style language learning.

Details DOI