Arrow Research search

Author name cluster

Thomas Zeugmann

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.

30 papers
2 author rows

Possible papers

30

I&C Journal 2021 Journal Article

On the amount of nonconstructivity in learning formal languages from text

  • Sanjay Jain
  • Frank Stephan
  • Thomas Zeugmann

Nonconstructive computations by various types of machines and automata have been considered by, for example, Karp and Lipton as well as Freivalds. They allow to regard more complicated algorithms from the viewpoint of much more primitive computational devices. The amount of nonconstructivity is a quantitative characterization of the distance between types of computational devices with respect to solving a specific problem. This paper studies the amount of nonconstructivity needed to learn classes of formal languages. Different learning types are compared with respect to the amount of nonconstructivity needed to learn indexable classes and recursively enumerable classes, respectively, of formal languages from positive data. Matching upper and lower bounds for the amount of nonconstructivity needed are shown.

Details DOI

I&C Journal 2011 Journal Article

Teaching randomized learners with feedback

  • Frank J. Balbach
  • Thomas Zeugmann

The present paper introduces a new model for teaching randomized learners. Our new model, though based on the classical teaching dimension model, allows to study the influence of the learner’s memory size and of the presence or absence of feedback. Moreover, in the new model the order in which examples are presented may influence the teaching process. The resulting models are related to Markov decision processes, and characterizations of optimal teachers for memoryless learners with feedback and for learners with infinite memory and feedback are shown. Furthermore, in the new model it is possible to investigate new aspects of teaching like teaching from positive data only or teaching with inconsistent teachers. Characterization theorems for teachability from positive data for both ordinary teachers and inconsistent teachers with and without feedback are provided.

Details DOI

I&C Journal 2008 Journal Article

Consistent and coherent learning with δ-delay

  • Yohji Akama
  • Thomas Zeugmann

A consistent learner is required to correctly and completely reflect in its actual hypothesis all data received so far. Though this demand sounds quite plausible, it may lead to the unsolvability of the learning problem. Therefore, in the present paper several variations of consistent learning are introduced and studied. These variations allow a so-called δ -delay relaxing the consistency demand to all but the last δ data. Additionally, we introduce the notion of coherent learning (again with δ -delay) requiring the learner to correctly reflect only the last datum (only the n - δ th datum) seen. Our results are manyfold. First, we provide characterizations for consistent learning with δ -delay in terms of complexity and computable numberings. Second, we establish strict hierarchies for all consistent learning models with δ -delay in dependence on δ. Finally, it is shown that all models of coherent learning with δ -delay are exactly as powerful as their corresponding consistent learning models with δ -delay.

Details DOI

TCS Journal 2008 Journal Article

Foreword

  • John Case
  • Takeshi Shinohara
  • Thomas Zeugmann
  • Sandra Zilles
Details DOI

TCS Journal 2008 Journal Article

Learning indexed families of recursive languages from positive data: A survey

  • Steffen Lange
  • Thomas Zeugmann
  • Sandra Zilles

In the past 40 years, research on inductive inference has developed along different lines, e. g. , in the formalizations used, and in the classes of target concepts considered. One common root of many of these formalizations is Gold’s model of identification in the limit. This model has been studied for learning recursive functions, recursively enumerable languages, and recursive languages, reflecting different aspects of machine learning, artificial intelligence, complexity theory, and recursion theory. One line of research focuses on indexed families of recursive languages — classes of recursive languages described in a representation scheme for which the question of membership for any string in any of the given languages is effectively decidable with a uniform procedure. Such language classes are of interest because of their naturalness. The survey at hand picks out important studies on learning indexed families (including basic as well as recent research), summarizes and illustrates the corresponding results, and points out links to related fields such as grammatical inference, machine learning, and artificial intelligence in general.

Details DOI

TCS Journal 2008 Journal Article

Learning recursive functions: A survey

  • Thomas Zeugmann
  • Sandra Zilles

Studying the learnability of classes of recursive functions has attracted considerable interest for at least four decades. Starting with Gold’s (1967) model of learning in the limit, many variations, modifications and extensions have been proposed. These models differ in some of the following: the mode of convergence, the requirements intermediate hypotheses have to fulfill, the set of allowed learning strategies, the source of information available to the learner during the learning process, the set of admissible hypothesis spaces, and the learning goals. A considerable amount of work done in this field has been devoted to the characterization of function classes that can be learned in a given model, the influence of natural, intuitive postulates on the resulting learning power, the incorporation of randomness into the learning process, the complexity of learning, among others. On the occasion of Rolf Wiehagen’s 60th birthday, the last four decades of research in that area are surveyed, with a special focus on Rolf Wiehagen’s work, which has made him one of the most influential scientists in the theory of learning recursive functions.

Details DOI

TCS Journal 2006 Journal Article

Foreword

  • Nicolò Cesa-Bianchi
  • Rüdiger Reischuk
  • Thomas Zeugmann
Details DOI

TCS Journal 2006 Journal Article

From learning in the limit to stochastic finite learning

  • Thomas Zeugmann

Inductive inference can be considered as one of the fundamental paradigms of algorithmic learning theory. We survey results recently obtained and show their impact to potential applications. Since the main focus is put on the efficiency of learning, we also deal with postulates of naturalness and their impact to the efficiency of limit learners. In particular, we look at the learnability of the class of all pattern languages and ask whether or not one can design a learner within the paradigm of learning in the limit that is nevertheless efficient. For achieving this goal, we deal with iterative learning and its interplay with the hypothesis spaces allowed. This interplay has also a severe impact to postulates of naturalness satisfiable by any learner. Furthermore, since a limit learner is only supposed to converge, one never knows at any particular learning stage whether or not the learner did already succeed. The resulting uncertainty may be prohibitive in many applications. We survey results to resolve this problem by outlining a new learning model, called stochastic finite learning. Though pattern languages can neither be finitely inferred from positive data nor PAC-learned, our approach can be extended to a stochastic finite learner that exactly infers all pattern languages from positive data with high confidence. Finally, we apply the techniques developed to the problem of learning conjunctive concepts.

Details DOI

TCS Journal 2006 Journal Article

Learning a subclass of regular patterns in polynomial time

  • John Case
  • Sanjay Jain
  • Rüdiger Reischuk
  • Frank Stephan
  • Thomas Zeugmann

An algorithm for learning a subclass of erasing regular pattern languages is presented. On extended regular pattern languages generated by patterns π of the form x 0 α 1 x 1 … α m x m, where x 0, …, x m are variables and α 1, .. ., α m strings of terminals of length c each, it runs with arbitrarily high probability of success using a number of examples polynomial in m (and exponential in c). It is assumed that m is unknown, but c is known and that samples are randomly drawn according to some distribution, for which we only require that it has certain natural and plausible properties. Aiming to improve this algorithm further we also explore computer simulations of a heuristic.

Details DOI

TCS Journal 2005 Journal Article

Inductive inference of approximations for recursive concepts

  • Steffen Lange
  • Gunter Grieser
  • Thomas Zeugmann

This paper provides a systematic study of inductive inference of indexable concept classes in learning scenarios where the learner is successful if its final hypothesis describes a finite variant of the target concept, i. e. , learning with anomalies. Learning from positive data only and from both positive and negative data is distinguished. The following learning models are studied: learning in the limit, finite identification, set-driven learning, conservative inference, and behaviorally correct learning. The attention is focused on the case that the number of allowed anomalies is finite but not a priori bounded. However, results for the special case of learning with an a priori bounded number of anomalies are presented, too. Characterizations of the learning models with anomalies in terms of finite tell-tale sets are provided. The observed varieties in the degree of recursiveness of the relevant tell-tale sets are already sufficient to quantify the differences in the corresponding learning models with anomalies. Finally, a complete picture concerning the relations of all models of learning with and without anomalies mentioned above is derived.

Details DOI

TCS Journal 2003 Journal Article

On learning of functions refutably

  • Sanjay Jain
  • Efim Kinber
  • Rolf Wiehagen
  • Thomas Zeugmann

Learning of recursive functions refutably informally means that for every recursive function, the learning machine has either to learn this function or to refute it, that is to signal that it is not able to learn it. Three modi of making precise the notion of refuting are considered. We show that the corresponding types of learning refutably are of strictly increasing power, where already the most stringent of them turns out to be of remarkable topological and algorithmical richness. Furthermore, all these types are closed under union, though in different strengths. Also, these types are shown to be different with respect to their intrinsic complexity; two of them do not contain function classes that are “most difficult” to learn, while the third one does. Moreover, we present several characterizations for these types of learning refutably. Some of these characterizations make clear where the refuting ability of the corresponding learning machines comes from and how it can be realized, in general. For learning with anomalies refutably, we show that several results from standard learning without refutation stand refutably. From this we derive some hierarchies for refutable learning. Finally, we prove that in general one cannot trade stricter refutability constraints for more liberal learning criteria.

Details DOI

TCS Journal 2002 Journal Article

Learning classes of approximations to non-recursive functions

  • Frank Stephan
  • Thomas Zeugmann

Blum and Blum (Inform. and Control 28 (1975) 125–155) showed that a class B of suitable recursive approximations to the halting problem K is reliably EX-learnable but left it open whether or not B is in NUM. By showing B to be not in NUM we resolve this old problem. Moreover, variants of this problem obtained by approximating any given recursively enumerable set A instead of the halting problem K are studied. All corresponding function classes U(A) are still EX-inferable but may fail to be reliably EX-learnable, for example if A is non-high and hypersimple. Blum and Blum (1975) considered only approximations to K defined by monotone complexity functions. We prove this condition to be necessary for making learnability independent of the underlying complexity measure. The class B ̃ of all recursive approximations to K generated by all total complexity functions is shown to be not even behaviorally correct learnable for a class of natural complexity measures. On the other hand, there are complexity measures such that B ̃ is EX-learnable. A similar result is obtained for all classes U ̃ (A). For natural complexity measures, B is shown to be not robustly learnable, but again there are complexity measures such that B and, more generally, every class U(A) is robustly EX-learnable. This result extends the criticism of Jain et al. (J. Comput. System Sci. 62(1) (2001) 178–212), since the classes defined by artificial complexity measures turn out to be robustly learnable while those defined by natural complexity measures are not robustly learnable.

Details DOI

TCS Journal 2001 Journal Article

Learning one-variable pattern languages very efficiently on average, in parallel, and by asking queries

  • Thomas Erlebach
  • Peter Rossmanith
  • Hans Stadtherr
  • Angelika Steger
  • Thomas Zeugmann

A pattern is a finite string of constant and variable symbols. The language generated by a pattern is the set of all strings of constant symbols which can be obtained from the pattern by substituting non-empty strings for variables. We study the learnability of one-variable pattern languages in the limit with respect to the update time needed for computing a new single hypothesis and the expected total learning time taken until convergence to a correct hypothesis. Our results are as follows. First, we design a consistent and set-driven learner that, using the concept of descriptive patterns, achieves update time O(n2 logn), where n is the size of the input sample. The best previously known algorithm for computing descriptive one-variable patterns requires time O(n4 logn) (cf. Angluin, J. Comput. Systems Sci. 21(1) (1980) 46–62). Second, we give a parallel version of this algorithm that requires time O(logn) and O(n3/log n) processors on an EREW-PRAM. Third, using a modified version of the sequential algorithm as a subroutine, we devise a learning algorithm for one-variable patterns whose expected total learning time is O(ℓ2 logℓ) provided the sample strings are drawn from the target language according to a probability distribution with expected string length ℓ. The probability distribution must be such that strings of equal length have equal probability, but can be arbitrary otherwise. Thus, we establish the first algorithm for learning one-variable pattern languages having an expected total learning time that provably differs from the update time by a constant factor only. Finally, we show how the algorithm for descriptive one-variable patterns can be used for learning one-variable patterns with a polynomial number of superset queries with respect to the one-variable patterns as query language.

Details DOI

TCS Journal 2000 Journal Article

Learning languages and functions by erasing

  • Sanjay Jain
  • Efim Kinber
  • Steffen Lange
  • Rolf Wiehagen
  • Thomas Zeugmann

Learning by erasing means the process of eliminating potential hypotheses from further consideration thereby converging to the least hypothesis never eliminated. This hypothesis must be a solution to the actual learning problem. The capabilities of learning by erasing are investigated in relation to two factors: the choice of the overall hypothesis space itself and what sets of hypotheses must or may be erased. These learning capabilities are studied for two fundamental kinds of objects to be learned, namely languages and functions. For learning languages by erasing, the case of learning indexed families is investigated. A complete picture of all separations and coincidences of the considered models is derived. Learning by erasing is compared with standard models of language learning such as learning in the limit, finite learning and conservative learning. The exact location of these types within the hierarchy of the models of learning by erasing is established. Necessary and sufficient conditions for language learning by erasing are presented. For learning functions by erasing, mainly the case of learning minimal programs is studied. Various relationships and differences between the considered types of function learning by erasing and also to standard function learning are exhibited. In particular, these types are explored in Kolmogorov numberings that can be viewed as natural Gödel numberings of the partial recursive functions. Necessary and sufficient conditions for function learning by erasing are derived.

Details DOI

I&C Journal 1999 Journal Article

Incremental Concept Learning for Bounded Data Mining

  • John Case
  • Sanjay Jain
  • Steffen Lange
  • Thomas Zeugmann

Important refinements of concept learning in the limit from positive data considerably restricting the accessibility of input data are studied. Let c be any concept; every infinite sequence of elements exhausting c is called positive presentation of c. In all learning models considered the learning machine computes a sequence of hypotheses about the target concept from a positive presentation of it. With iterative learning, the learning machine, in making a conjecture, has access to its previous conjecture and the latest data items coming in. In k-bounded example-memory inference (k is a priori fixed) the learner is allowed to access, in making a conjecture, its previous hypothesis, its memory of up to k data items it has already seen, and the next element coming in. In the case of k-feedback identification, the learning machine, in making a conjecture, has access to its previous conjecture, the latest data item coming in, and, on the basis of this information, it can compute k items and query the database of previous data to find out, for each of the k items, whether or not it is in the database (k is again a priori fixed). In all cases, the sequence of conjectures has to converge to a hypothesis correctly describing the target concept. Our results are manyfold. An infinite hierarchy of more and more powerful feedback learners in dependence on the number k of queries allowed to be asked is established. However, the hierarchy collapses to 1-feedback inference if only indexed families of infinite concepts are considered, and moreover, its learning power is then equal to learning in the limit. But it remains infinite for concept classes of only infinite r. e. concepts. Both k-feedback inference and k-bounded example-memory identification are more powerful than iterative learning but incomparable to one another. Furthermore, there are cases where redundancy in the hypothesis space is shown to be a resource increasing the learning power of iterative learners. Finally, the union of at most k pattern languages is shown to be iteratively inferable.

Details DOI

TCS Journal 1996 Journal Article

Monotonic and dual monotonic language learning

  • Steffen Lange
  • Thomas Zeugmann
  • Shyam Kapur

Monotonic and dual monotonic language learning from positive as well as from positive and negative examples is investigated. Three different notions of monotonicity are considered. Each of them reflects an alternative formalization of the requirement that the learner has to produce better and better generalizations when fed more and more data on the concept to be learned. Strong-monotonicity absolutely requires that only better and better generalizations be produced. Monotonic learning reflects the demand that for any two guesses the one output later has to be, with respect to the target language, at least as good as the earlier one. Weak-monotonicity is the analogue in learning theory of cumulativity. The corresponding three versions of dual monotonicity describe the requirement that the inference device only produces specializations that fit the target language better and better. Dual strong-monotonic learning generates a chain of shrinking specializations converging to the target language. Dual monotonicity describes the same goal with respect to the target language and dual weak-monotonic learning is the analogue of the dual of cumulativity. The power of each of these types of monotonic and dual monotonic inference from positive as well as from positive and negative data in the context of algorithmic language learning theory is completely investigated, thereby obtaining strong hierarchies.

Details DOI

I&C Journal 1992 Journal Article

Highly parallel computations modulo a number having only small prime factors

  • Thomas Zeugmann

Highly parallel algorithms computing the inverse, discrete roots, or a large power modulo a number that has only small prime factors are presented. The elaborated uniform families of Boolean circuits simultaneously achieve depth O(log n) and size O(n 0(1)) for P-uniformity and depth O(log n log log n) and size O(n 0(1)) for log-space uniformity.

Details DOI

I&C Journal 1991 Journal Article

One-sided error probabilistic inductive inference and reliable frequency identification

  • Efim Kinber
  • Thomas Zeugmann

Fox EX- and BC-type identification, one-sided error probabilistic inference and reliable frequency identification on sets of functions are introduced. In particular, we relate the one to the other and characterize one-sided error probabilistic inference to exactly coincide with reliable frequency identification, on any setM. Moreover, we show that reliable EX and BC-frequency inference forms a new discrete hierarchy having the breakpoints 1, 1/2, 1/3, ….

Details DOI

MFCS Conference 1990 Conference Paper

Computing Large Polynomial Powers Very Fast in Parallel

  • Thomas Zeugmann

Abstract Very fast parallel algorithms computing the inverse and large powers of polynomials over finite fields are presented provided the modulus has only small prime factors. The elaborated uniform families of Boolean circuits simultaneously achieve depth O(log n) and size O(n o(1) ) for P-uniformity and depth O(log n loglog n) and size O(n o(1) ) for log-space uniformity.

Details

TCS Journal 1988 Journal Article

On the power of recursive optimizers

  • Thomas Zeugmann

Problems of the effective synthesis of fastest programs (modulo a recursive factor) for recursive functions given by input-output examples or an arbitrary program are investigated. In contrast to the non-existence result proved by Alton (1974, 1976) we show various existence results. Thereby we deal in detail with the influence of the recursive factor in dependence of the concrete formalization of a fastest program. In particular, we shall show that, even for function classes containing arbitrarily complex functions, the effective synthesis of fastest programs (modulo a simple recursive operator) can be achieved sometimes.

Details DOI
v2026.09.13