federated and organized in parallel by Masaryk University in Brno, Czech Republic.The MFCS symposia, organized since 1972, encourage high-quality research in all branches of theoretical computer science.The broad scope of MFCS provides an opportunity to bring together researchers who do not usually meet at specialized conferences.Computer Science Logic (CSL) is the annual conference of the European Association for Computer Science Logic (EACSL).The conference is intended for computer scientists whose research activities involve logic, as well as for logicians working on issues significant for computer science.

In this paper, we reconsider the definition of procrastinating learning machines. In the original definition of Freivalds and Smith [FS93], constructive ordinals are used to bound mindchanges. We investigate possibility of using arbitrary linearly ordered sets to bound mindchanges in similar way. It turns out that using certain ordered sets it is possible to define inductive inference types different from the previously known ones. We investigate properties of the new inductive inference types and compare them to other types.

The functions of finite support have played a ubiquitous role in the study of inductive inference since its inception. In addition to providing a clear and simple example of a learnable class, the functions of finite support are employed in many proofs that distinguish various types and features of learning. Recent results show that this ostensibly simple class requires as much space to learn as any other learnable set and, furthermore, is as intrinsically difficult as any other learnable set. Since the class of functions of finite support sit at the top of two very different complexity hierarchies, this class is a candidate for being a canonical learning problem. We argue for this point in the paper and discuss the ramifications.

We study 1-way quantum finite automata (QFAs). First, we compare them with their classical counterparts. We show that, if an automaton is required to give the correct answer with a large probability (greater than 7/9), then any 1-way QFAs can be simulated by a 1-way reversible automaton. However, quantum automata giving the correct answer with smaller probabilities are more powerful than reversible automata. Second, we show that 1-way QFAs can be very space-efficient. We construct a 1-way QFA that is exponentially smaller than any equivalent classical (even randomized) finite automaton. We think that this construction may be useful for design of other space-efficient quantum algorithms. Third, we consider several generalizations of 1-way QFAs. Here, our goal is to find a model which is more powerful than 1-way QFAs keeping the quantum part as simple as possible.

We generalize the traditional concept of team learning.The success of an asymmetric team in learning some function depends upon the successes of participant machines by an arbitrary nondecreasing Boolean function.Asymmetric team types are ordered accordingly to their learning power by basic reductions.The problem to determine this order for an arbitrary pair of asymmetric teams is shown to be NP-hard.Basic reductions are independent of the properties of any particular definition of learning.Many learning types (e.g.EX, -learning with no more than n mindchanges) have additional team order relations which vary from case to case.We define a learning type PINFlN which allows only the basic reductions between its teams.The relation between asymmetric team learning and probabilistic learning is described by a zerosum matrix game.

Introduction The starting point for studies in inductive inference is the model of learning by example introduced by Gold [Gol67]. This is a simple model of learning algorithms that input examples of some function and produce programs that are intended to compute the function generating the examples. Learning takes place as the "correct " program must be produced after the learning algorithm has seen only finitely many examples. The functions used as input are typically (partial) recursive functions. Using traditional encoding techniques, this class of functions is rich enough to model a wide range of phenomena [AS83]. Researchers in inductive inference have used the basic model of Gold to study the effects of other parameters of the learning process such as errors tolerance, plurality of approaches, probability of success, learning via queries, etc. Herein we combine traditional studies of inductive inference and classical continuous mathematics to produce a study of learning

People tend not to have perfect memories when it comes to learning, or to anything else for that matter.Most formal studies of learning, however, assume a perfect memory.Some approaches have restricted the number of items that could be retained.We introduce a This work was facilitated by an international

Article Free Access Share on Co-learning of total recursive functions Authors: Rūsiņš Freivalds Department of Computer Science, University of Latvia, Raina bulvaris 29, LV-1459, Riga Latvia Department of Computer Science, University of Latvia, Raina bulvaris 29, LV-1459, Riga LatviaView Profile , Marek Karpinski Department of Computer Science, University of Bonn, Römerstrasse 164, D-5300, Bonn 1 Germany Department of Computer Science, University of Bonn, Römerstrasse 164, D-5300, Bonn 1 GermanyView Profile , Carl H. Smith Department of Computer Science, University of Maryland, College Park, MD Department of Computer Science, University of Maryland, College Park, MDView Profile Authors Info & Claims COLT '94: Proceedings of the seventh annual conference on Computational learning theoryJuly 1994 Pages 190–197https://doi.org/10.1145/180139.181098Published:16 July 1994Publication History 8citation28DownloadsMetricsTotal Citations8Total Downloads28Last 12 Months12Last 6 weeks1 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

In this paper we introduce a formal framework for investigating the relationship of inductive inference and the task of classification. We give the first results on the relationship between functions that can be identified in the limit and functions that can be acquired from unclassified objects only. Moreover, we present results on the complexity of classification functions and the preconditions necessary in order to allow the computation of such functions.

constant, finite amount of memory, there are and T such that

Article Free Access Share on On the role of procrastination for machine learning Authors: Rūsiņš Freivalds Institute of Mathematics and Computer Science, University of Latvia, Raina bulvaris 29, 226250, Riga, Latvia Institute of Mathematics and Computer Science, University of Latvia, Raina bulvaris 29, 226250, Riga, LatviaView Profile , Carl H. Smith Department of Computer Science and Institute for Advanced Computer Studies, The University of Maryland, College Park, MD Department of Computer Science and Institute for Advanced Computer Studies, The University of Maryland, College Park, MDView Profile Authors Info & Claims COLT '92: Proceedings of the fifth annual workshop on Computational learning theoryJuly 1992 Pages 363–376https://doi.org/10.1145/130385.130426Published:01 July 1992Publication History 1citation62DownloadsMetricsTotal Citations1Total Downloads62Last 12 Months51Last 6 weeks7 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF