Automatic Learners with Feedback Queries
John Casea , Sanjay Jainb,1 , Yuh Shin Ongb , Pavel Semukhinc,2 , Frank
Stephand,3a Department of Computer and Information Sciences, University of Delaware, Newark, DE

19716-2586, USA.
b Department of Computer Science, National University of Singapore, Singapore 117417,

Republic of Singapore.
c Department of Computer Science, University of Regina, Canada.
d Department of Mathematics, National University of Singapore, Singapore 119076, Republicof Singapore.

Abstract
Automatic classes are classes of languages for which a finite automaton can
decide whether a given element is in a set given by its index. The present work
studies the learnability of automatic families by automatic learners which, ineach round, output a hypothesis and update a long-term memory, dependingon the input datum, via an automatic function. Many variants of automaticlearners are investigated: where the long-term memory is restricted to be thecurrent hypothesis whenever this exists, cannot be of length larger than thelength of the longest datum seen, or has to consist of a constant number ofexamples seen so far. Learnability is also studied with respect to queries which
reveal information about past data or past computation history; the number ofqueries per round is bounded by a constant.

1. Introduction
The basic model of learning in inductive inference may be described as follows.
A learner is receiving data, one piece at a time, about a target concept. As
it is receiving data, it conjectures hypothesis about what the target concept
might be. The learner may update its hypothesis as it receives more and moredata. The learner is said to identify or learn the target concept if its sequenceof hypotheses stabilises on a correct hypothesis. This is basically the model of
explanatory learning considered by Gold [15]. Over time several other models

Email addresses: case@cis.udel.edu (John Case), sanjay@comp.nus.edu.sg (Sanjay
Jain ), yuhshin@gmail.com (Yuh Shin Ong), pavel@semukhin.name (Pavel Semukhin),fstephan@comp.nus.edu.sg (Frank Stephan)
1 Supported in part by NUS grant number C-252-000-087-001 and R252-000-420-112.
2 Supported in part by NUS grant number R146-000-114-112.
3 Supported in part by NUS grant numbers R146-000-114-112 and R252-000-420-112.

Preprint submitted to Elsevier

December 21, 2013

of learning have been investigated (see [23] for some of these models).
Although the class of all regular languages is learnable using queries [4],this is not true for the case of inductive inference from positive data [1, 15].
Hence, it is worth investigating more closely which classes of regular languages
are learnable from positive data and which are not. For example, Angluin [3]considered learnability of the class of k-reversible languages. These studies werelater extended [11, 13, 16].
An automatic family of languages is a family for which membership question
can be uniformly decided by a finite automaton. An advantage of an automaticfamily over general indexed families [1, 26, 28] is that the first-order theory of
automatic families, as well as of automatic structures in general, is decidable[17, 18, 24]. Here the predicates (relations) and functions (mappings) allowed in
the first-order theory are automatic. Furthermore, relations and functions thatare first-order defined from other automatic relations and functions are automatic again [17, 18, 24]. Also, automatic functions are linear time computable[9]. These nice properties of automatic structures make them a useful tool not
only in learning theory but also in other areas such as model checking and grouptheory [6, 12, 24, 30, 31, 34, 35]. Common examples of automatic predicatesfrom the prior literature are predicates to compare the length of strings, thelexicographic order (denoted by ≤lex ) and the length-lexicographic order (denoted by ≤ll ). Here x is length-lexicographically less than y iff either |x| < |y|or |x| = |y| and x <lex y, where |x| denotes the length of string x.
Jain, Luo and Stephan [20] (see also, [9, 19, 22]) considered learnability of
automatic families [21]. They showed that any automatic family can be explanatorily learnt by a recursive learner iff it satisfies a condition known as Angluin’s
tell-tale condition (see Proposition 2 below). Thus, it was more interesting toconsider some restricted form of learners. One natural restriction, as considered by [20], on learners is that they are automatic, i.e., their graph is acceptedby a finite automaton. For this purpose, the learner is modeled as working inrounds and having a long-term memory. In each round learner receives a new
datum, and based on this datum and its previous long-term memory, updates
its long-term memory and outputs a new hypothesis. The learner learns thetarget language if its sequence of hypotheses converges to an index for the target language (where the index is interpreted in some hypothesis space, which
is an automatic family). If we do not restrict the long-term memory or thecomputational power of the learner in any way, then this model of learning isequivalent to the above mentioned model of explanatory learning. For automaticlearner, we require that the mapping (previous memory, new datum) 7→ (newmemory, hypothesis) is an automatic function, that is, its graph is recognised
by a finite automaton. Such learners satisfy much more realistic complexity
bounds than learners which have access to the full history of all past data andcomputations. A further motivation for studying learners which are automaticis that in some situations it may be more reasonable to have finite automata asa model rather than Turing machines. Another motivation for the work goesback to the programme of Khoussainov and Nerode [24] to find which resultsfrom computable model theory can be transferred to model theory based on2

finite automata. Some very nice sub-classes of pattern languages [2] are automatic families and learnable by automatic learners [9]. However, Jain, Luo andStephan [20] showed that not every learnable automatic family can be learnt by
an automatic learner (see Example 14 and Theorem 17 below).
Jain, Luo and Stephan [20] considered some natural restrictions on long-term
memory of the learner: the long-term memory of the learner is its current hypothesis (iterative learning), the long-term memory is bounded in length by thelength of the current hypothesis plus a constant (we refer to this as hypothesislength long-term memory), and the long-term memory is bounded in length by
the length of the longest datum seen so far plus a constant (we refer to this as
datum-length long-term memory). It was shown that some automatic classes
can be learnt by an automatic learner using datum-length long-term memory
but not by any automatic learner using hypothesis-length long-term memory.
However it was open whether automatic learners using datum-length long-term
memory are as powerful as general automatic learners or whether any automatic learner using hypothesis-length long-term memory can be simulated byan iterative automatic learner or by an automatic learner using datum-length
long-term memory. Jain, Luo and Stephan [20] showed that if one considers
fat texts, i.e., the inputs where every element of the target language appears
infinitely often, then automatic learners using datum-length long-term memory
can learn all automatic families which satisfy Angluin’s tell-tale condition. Since[20] several papers [9, 19, 22] have considered learning of automatic classes byautomatic learners. The present work carries on investigations into learnabilityof automatic families by automatic learners.
The notion of learners with explicit bounds on the long-term memory had
already been studied previously in the setting of algorithmic learners [14, 25].
Such memory restrictions were considered as too restrictive. This led to enrichment of the learners by allowing feedback queries and other instruments toaccess some, but not all information about the past [8, 27, 38]. The present work
investigates these notions for the case of automatic learners learning automaticfamilies. We do not investigate all possible combinations of memory models,
but look at some of the more typical and natural combinations. In particular,
we will look at what additional features allow an automatic learner to learn theclass of all automatic families satisfying Angluin’s tell-tale condition.
Outline of the paper. Section 2 gives the basic notation and definitions. Section 3 provides some examples to give some insight into the above definitions
and notions. Section 4 provides the main results on learning with feedback
queries. Theorem 16 shows that every automatic family satisfying Angluin’s
tell-tale condition has an automatic feedback learner with only one query perround and using datum-length long-term memory. Theorem 17 shows that there
is a class which has an automatic learner employing only one feedback query
per round and without any long-term memory but which does not have an
automatic learner relying on long-term memory only. Theorems 18 and 20 relate various memory types with feedback queries and investigate the hierarchies
which result from counting the size of the bounded example memory and the3number of feedback queries per round. Section 5 deals with automatic learners using a marked memory space (see Section 2 for definition). Theorem 21shows that the more general marked memory space of type 2 permits to learn
any learnable class by an automatic learner using hypothesis-length long-term
memory. In contrast to this, Theorem 22 shows that such a result is not possible for a marked memory space of type 1. It is an open problem whether an
automatic learner using hypothesis-length long-term memory can be replacedby an iterative automatic learner [20]. Theorem 23 gives a partial answer: thisis possible if the iterative automatic learner has additionally access to a marked
memory space of type 1. The following tables summarise the main inclusions
and non-inclusions; all learners considered in these tables are automatic:
Inclusion
Theorem 16

Given Criterion
Angluin’s tell-tale criterion

Theorem 21

Angluin’s tell-tale criterion

Theorem 23

hypothesis-length memory

Implied Criterion
one feedback queryplus datum-length
memoryhypothesis-length
memory plus type 2
marked memory space
iterative plus hypothesis
queries

Non-Inclusion
Theorem 17
Theorem 18

Satisfied Criterion
memoryless one feedback query1-bounded example memory

Theorem 18

hypothesis-length memory
plus feedback query

Theorem 19

k-bounded example memory

Theorem 20

k-bounded example memory /memoryless k-feedback queries /constantly bounded memory

Theorem 22

datum-length memory

Diagonalised Criterion
automatic learners
iterative plus feedback
queries
iterative plus feedback
queries(k − 1)-bounded
example memory plus
feedback queries(k − 1)-bounded
example memory /memoryless(k − 1)-feedback
queries
hypothesis-length
memory plus type 1
marked memory space

2. Notations, learning with feedback queries and memory limitations
The symbol N denotes the set of natural numbers, {0, 1, 2, . . .}. The length of
the string x is denoted by |x|. Empty string is denoted by ε. For a string x,
x(i) denotes the (i + 1)-th element in the string x; thus, string x is same as4x(0)x(1) . . . x(|x| − 1). Let x <lex y denote that x is lexicographically before y(where we assume some fixed ordering of letters of the alphabet Σ of the strings).
Let x ≤lex y iff x <lex y or x = y, let x >lex y iff y <lex x, and let x ≥lex y iff
y ≤lex x. We say that x is length-lexicographically less than y (written x <ll y)iff either |x| < |y| or |x| = |y| and x <lex y. Let x ≤ll y iff x = y or x <ll y, let
x >ll y iff y <ll x, and let x ≥ll y iff y ≤ll x.
Given two strings x = x(0)x(1) . . . x(n − 1) and y = y(0)y(1) . . . y(m − 1)over the alphabet Σ, we define the convolution [24], conv(x, y), over the alphabet(Σ ∪ {})2 as follows (where  6∈ Σ). Let p = max {n, m}, and x0 = xp−n , andy 0 = yp−m . Then, conv(x, y) = (x0 (0), y 0 (0))(x0 (1), y 0 (1)) . . . (x0 (p − 1), y 0 (p −1)). Similarly, one can define conv on multiple arguments. A relation (predicate) R or a function f is called automatic if the set {conv(x1 , x2 , . . . , xn ) :R(x1 , x2 , . . . , xn )} or {conv(x1 , x2 , . . . , xm , y) : f (x1 , x2 , . . . , xm ) = y}, respectively, is regular [24].
A family of languages {Lα : α ∈ I} is said to be automatic [20, 21] iff (a) I(called the index domain) is a regular set of strings over some finite alphabet, (b)there is a finite alphabet Σ such that each Lα ⊆ Σ∗ and (c) the set {conv(α, x) :α ∈ I ∧ x ∈ Lα } is regular.
Automatic structures are structures given by finitely many automatic relations and functions. Historically, much work has been dedicated to the questionof which natural structures are isomorphic to the automatic ones, for example(N, +, <) is isomorphic to an automatic one while, (Q, +) is not [36].
Fix a finite alphabet Σ for the languages. Let # 6∈ Σ∗ . A text is a mappingfrom N to Σ∗ ∪{#}. Traditionally, # is used to denote pauses in the presentationof data and is also needed as the only text for empty language is #∞ ; one could
come around the use of # by requiring that all languages to be learnt are nonempty, but this turned out to be notationally awkward in various cases. The
content of a text T , denoted content(T ), is {T (i) : i ∈ N} − {#}. We say that T
is a text for L iff content(T ) = L. Sequences are initial segments of texts. We
let T [n] denote T (0)T (1) . . . T (n−1). We let Λ denote the empty sequence. The
content of a sequence σ = T [n], denoted content(σ), is {T (i) : i < n}−{#}. Let|σ| denote the length of the sequence σ. For sequences σ and τ , let σ ◦ τ denotethe concatenation of σ and τ . Furthermore, let σ ◦ x denote concatenation ofσ and the sequence consisting of just the element x. Note that xx is a stringobtained by concatenating x with itself while x ◦ x is a data sequence where thedatum x is presented twice as input.
We will be considering learning of an automatic family L = {Lα : α ∈ I} bya learner using as hypothesis space an automatic family H = {Hβ : β ∈ J}.
Definition 1. (Based on Gold [15]) Suppose Σ is a finite alphabet for languages, and I, J are regular index sets over some finite alphabet. Suppose ? 6∈ J
is a special symbol (denoting repeat of previous conjecture by the learner).
Let L = {Lα : α ∈ I} be the class to be learnt and H = {Hβ : β ∈ J}
be a hypothesis space, where both are automatic families, with languages being
subset of Σ∗ . Suppose Γ is a finite alphabet used for storing memory by learners.
(a) A learner is an algorithmic mapping from Γ∗ × (Σ∗ ∪ {#}) to Γ∗ × (J ∪ {?}).
5

A learner has an initial long-term memory mem0 ∈ Γ∗ and initial hypothesis hyp0 ∈ J ∪ {?}.
(b) Suppose a learner M with initial long-term memory mem0 and initial
hypothesis hyp0 and a text T for a language L is given.
(i) Let memT0 = mem0 , hypT0 = hyp0 .
(ii) For k > 0, let (memTk , hypTk ) = M (memTk−1 , T (k − 1)).
Intuitively, memTk and hypTk are the long-term memory and hypothesis of the learner M after having seen the input T [k].
(iii) M converges on text T to β iff there exists a t such that hypTt = βand, for all t0 ≥ t, hypTt0 ∈ {β, ?}.
(iv) M learns the language L (using hypothesis space H) from the text
T iff M converges on text T to a hypothesis β such that Hβ = L.
(c) M learns a language L (using hypothesis space H) iff M learns L from all
texts for the language L (using hypothesis space H).
(d) M learns L (using hypothesis space H) iff M learns all languages in L
(using hypothesis space H).
(e) L is said to be learnable iff some learner M learns L using some hypothesis
space H0 .
For ease of notation, when T is implicit, we will drop T from the superscript of
memTn and hypTn .
For a learner M , let M (σ) denote the hypothesis of the learner M after
having seen input segment σ. This notation applies even for other kinds oflearners defined below.
Intuitively, one can view the learner as operating in stages (rounds) on an
input text T for a target language L. The learner has initial long-term memory
mem0 ∈ Γ∗ and initial hypothesis β0 ∈ J ∪ {?}. In stage (round) n, thelearner receives the input T (n), updates its previous long-term memory memn
to memn+1 and outputs a hypothesis βn+1 . For general learners as studied
by Gold [15], there is no restriction on the learners except for the mapping(memn , T (n)) 7→ (memn+1 , βn+1 ) being computable (here note that the learnerdoes not know n, unless it stores it in its long-term memory). The learnerlearns [15] a language L iff for all texts T for L, for βn as defined above, thesequence β0 , β1 , . . . converges to an index (in J for the hypothesis space H) for
L. This model of learning is also referred to as explanatory learning from text
or TxtEx-learning. We used the symbol ? to denote that either the learner does
not change its previous hypothesis (this is useful for some long-term memory
limited models of learner) or the learner has not yet seen enough data for its
initial conjecture.
For learning automatic families of languages a characterisation based on
Angluin’s condition [1] determines when an automatic family is learnable [20].

6Proposition 2 (Based on Angluin [1]). An automatic family {Lα : α ∈ I}
is learnable by an algorithmic learner iff, for every α ∈ I, there is a bound bα
such that, for all β ∈ I, the implication{x ∈ Lα : |x| ≤ bα } ⊆ Lβ ⊆ Lα ⇒ Lβ = Lαholds. We call the set {x ∈ Lα : |x| ≤ bα } a tell-tale set for Lα . The condition“{x ∈ Lα : |x| ≤ bα } ⊆ Lβ ⊆ Lα ⇒ Lβ = Lα ” is called Angluin’s telltale condition. Note that we can take bα = |α| + c for a suitable constant c
independent of α.
Therefore, the challenge is to study learnability by more restrictive learners. In
the setting of automatic structures, it is natural to require that the learners arealso automatic [20], that is, the mapping (memn , T (n)) 7→ (memn+1 , βn+1 ) forthe learners is automatic. The hypothesis and the updated long-term memoryof such a learner can be computed in time linear in their previous long-term
memory and current datum [9]. The price paid is that the learner can no longer
access the full past history of the data observed, as the automaticity of the
mapping (memn , T (n)) 7→ (memn+1 , βn+1 ), forces the learner to forget somepast data. In general, the requirement of a learner to be automatic is a real
restriction [20] (for examples of a learnable automatic class which cannot belearnt by an automatic learner, see Example 14 and Theorem 17). However, forunary alphabets, automatic learners are as powerful as non-automatic ones.
Theorem 3 (Jain, Luo and Stephan [20]). Suppose {Lα : α ∈ I} is an automatic family over a unary alphabet. Then, {Lα : α ∈ I} is learnable byan automatic learner (which uses long-term memory bounded in length by thelength of the longest datum seen so far) iff the family satisfies Angluin’s tell-talecondition.
Jain, Luo and Stephan [20] had considered various ways in which the longterm memory of the automatic learners can be bounded in length. The lengthrestrictions considered are as follows. For the following, T is an arbitrary input
text, memn and βn denotes the long-term memory and hypothesis of the learnerjust before getting input T (n).
(a) the length of the hypothesis plus a constant; that is, for some constant c(independent of T and n), |memn | ≤ |βn |+c; we refer to this as hypothesislength memory.
(b) the length of the longest datum seen so far plus a constant; that is, for someconstant c (independent of T and n), |memn | ≤ max {|T (i)| : i < n} + c;
we refer to this as datum-length memory.
(c) just constant length; that is, |memn | ≤ c, for some constant c (independentof T and n); we refer to this as constant-length memory.
For ease of notation, the “plus a constant” is omitted in the notations below.
Note that the learner is not constrained regarding which alphabet it uses for7

its long-term memory; therefore, it might, for example, store the convolution of
up to k many examples in the case that it uses datum-length memory (here k
is some constant). Note that, in the case of hypothesis-length (or better) longterm memory, the learner can memorise the most recent hypothesis output,
and, thus, abstain from outputting ? (since it can output the stored most recent
hypothesis).
Furthermore, it should be noted that for most of our results, the restriction in(c) is strengthened to not to use any memory at all. There are, however, classes
where constant-length long-term memory helps, for example when learning allsets of the form {x} or {x0, x1}; the long-term memory keeps track of whether
strings ending with 0 have been seen so far and whether strings ending with 1
have been seen so far. Without that constant long-term memory, convergence toa correct hypothesis would not be possible. The class given in Theorem 20 can
also be learnt with a constant amount of long-term memory as defined under(c) and without queries of any type.
Also note that, as one can choose the alphabet size of the long-term memory, the usage of the “plus some constant” could be replaced by using max{d, 1}
where d is the length of the longest datum seen so far or the length of the current hypothesis. Therefore often the literature on long-term memory bounds[14, 25] takes into account the number of binary bits one has to use to represent it. In the field of automatic learning, however, using datum-length or
hypothesis-length memory is more adequate; the reason is that these bounds
come out naturally from the framework: first, the length of minimal indices isquite invariant over hypotheses spaces used; second, the smallest indices of afinite set in an automatic family corresponds, up to a constant depending on
the family and not on the set, with the length of its longest element; third, theautomatic functions doing the updates of the long-term memory and computing
the hypotheses and queries cannot make their values longer than the maximumof the long-term memory length and the length of the current datum plus a
constant [20, 21].
As such memory limited learners are quite restrictive, it is natural to consider mechanisms which provide some access to past data, besides what can beremembered in the long-term memory by automatic learners. If one considers
fat texts [32], where every data item is repeated infinitely often in the text,
then Jain, Luo and Stephan [20] showed that automatic learners (without any
long-term memory restrictions except due to the definition of automatic learners, but not using any marked memory space as considered below) are able tolearn all automatic families satisfying Angluin’s tell-tale condition. Hence, thepresent work looks at criteria which are more powerful than just limited memory
structure but less powerful than fat texts. These methods are based on active
strategies of the learner, such as making feedback queries about whether somedata item has already been seen in the past. While the mechanisms presented
here are well-studied in the case of algorithmic learners, the combination ofsuch mechanisms with automatic learners is novel. Also novel is the generalisedmodel of marked memory space, which subsumes feedback learning and related
criteria.
8

For the following definitions, Σ is the alphabet for the languages, Γ is thealphabet used by the learner for its long-term memory. L = {Lβ : β ∈ I}
refers to the language class being learnt; Lα refers to the target language, anda text T for Lα is the input given to the learner. H = {Hβ : β ∈ J} refers to
the family used by the learner as hypothesis space. Furthermore, memn and βndenote the long-term memory and hypothesis of the learner just before receiving
input T (n). We sometimes consider the long-term memory of the learner as aset. For this, conv(x1 , x2 , . . . , xr ) represents the set {x1 , x2 , . . . , xr }. When we
consider long-term memory as a set, we assume that it was in sorted order: thatis, x1 <ll x2 <ll . . . <ll xr . This allows for automatic updating and testing ofelements in a set. For ease of notation, we will often refer directly to the sets inthese cases, rather than the representation.
Definition 4 (Based on [37, 38]). An automatic learner is called iterative
iff, for all n, memn = βn .
Definition 5 (Based on [27, 32]). An automatic learner is a learner with kbounded example memory iff, for all n, memn ⊆ content(T [n]), number of elements in memn is at most k, and memn+1 ⊆ memn ∪ {T (n)} (note thatthe long-term memory of the learner here is interpreted as a set). If k is not
specified, we call the learner a bounded example memory learner.
The following notion of feedback learning for general inductive inference was
first studied by Wiehagen [38] and Lange and Zeugmann [27].
Definition 6 (Based on [8, 27, 38]). An automatic learner using k-feedback(also called a learner which uses k feedback queries) is a learner, with an associated automatic query function Q asking k questions per round, defined asfollows. The initial long-term memory of the learner is mem0 and the initial
hypothesis of the learner is β0 . Given an input text T , let memn , and βn denotethe long-term memory and hypothesis of the learner after having seen T [n] (thatis just before receiving input T (n)).
(a) Q is an automatic mapping from Γ∗ × (Σ∗ ∪ {#}) to the set of subsets of
Σ∗ of size k.
(b) Suppose, Q(memn , T (n)) = Sn = {y1 , y2 , . . . , yk }. Let bi = 1 iff yi ∈content(T [n]). Then, the mapping given by (memn , T (n), b1 , b2 , . . . , bk ) 7→
(memn+1 , βn+1 ) is automatic.
For the following definition, we provide an automatic learner with a different
kind of memory (called marked memory space), which is a set of strings over afinite alphabet ∆. This marked memory will only grow (set inclusion wise) as thelearner gets more data. Marked memory can be considered as a generalisation of
feedback learning since feedback learning can be simulated by Type 1 memory.

9Definition 7. An automatic learner using a marked memory space is a learner,with an associated marked memory space, an automatic query function Q (asking k questions per round, for some constant k), and a marked memory space
updater F defined as follows on input text T .
Initial long-term memory of the learner is mem0 , initial hypothesis of thelearner is β0 and initial marked memory space is Z0 = ∅. Furthermore, memn ,Zn and βn denote the long-term memory, the marked memory and hypothesis of
the learner after having seen the input T [n] (that is just before receiving input
T (n)).
(a) Q is an automatic mapping from Γ∗ × (Σ∗ ∪ {#}) to the set of subsets of∆∗ of size k.
(b) Suppose, Q(memn , T (n)) = Sn = {y1 , y2 , . . . , yk }. Let bi = 1 iff yi ∈Zn . Then, the mapping, (memn , T (n), b1 , b2 , . . . , bk ) 7→ (memn+1 , βn+1 )is automatic. Furthermore, Zn+1 = Zn ∪ Xn+1 , where(i) for Type 1 memory space, there is an automatic function F such that
F (memn , T (n), b1 , b2 , . . . , bk ) = Xn+1 , and(ii) for Type 2 memory space, there is an automatic function F such thatfor all w ∈ ∆∗ , F (memn , T (n), b1 , b2 , . . . , bk , w) = 1 iff w ∈ Xn+1 .
Note that in the case of Type 1 memory space, Xn+1 is technically represented
as a convolution of the elements of the set, and is thus necessarily finite withcardinality bounded by some constant. For Type 2 memory, Xn+1 may be
infinite.
Remark 8. An automatic feedback learner is a special case of an automaticlearner using a marked memory space of Type 1, for which, in Definition 7, Σ∗is used for memory instead of ∆∗ , and Xn+1 = {T (n)} ∩ Σ∗ .
Definition 9. An automatic learner using k-hypothesis queries is a special caseof an automatic learner using a marked memory space of Type 1 for which, in
Definition 7, the index set J of the hypothesis space is used for memory insteadof ∆∗ , Xn+1 = {βn+1 }−{?} and Q is an automatic mapping from Γ∗ ×(Σ∗ ∪{#})
to the set of subsets of J of size k. This allows a learner to check whether it
had earlier issued a particular hypothesis.
For ease of notation, when describing hypothesis query learners, we just givethe queries made by the learner at each input, rather than giving details of Xn
and Zn .
Many of these learning notions had been defined earlier without requiring thatthe learners are automatic. The general notion of learning which is underlying
the notion of an automatic learner is due to Gold [15] and is called explanatory learning. The variant with an explicit long-term memory as used here wasintroduced by Freivalds, Kinber and Smith [14]. The special case of iterative10

learning is quite popular and predates the definition of general memory limitations, it was introduced by Wiehagen [38] and later by Wexler and Culicover[37]. Bounded example memory was considered by Osherson, Stob and Weinstein [32]; Lange and Zeugmann [27] extended this study. Wiehagen [38] andLange and Zeugmann [27] introduced and studied feedback learning; Case, Jain,
Lange and Zeugmann [8] quantified the number of feedback queries per round.
The following definition and lemma by L. Blum and M. Blum [5] is usefulto prove some of our results.
Definition 10 (Blum and Blum [5]). A sequence σ is said to be a locking
sequence for M on L, if (i) content(σ) ⊆ L, (ii) M (σ) is an index for L (inthe hypothesis space used by M ), and (iii) for all τ such that content(τ ) ⊆ L,
M (σ) = M (σ ◦ τ ), that is M does not change its hypothesis beyond σ on any
text for L starting with σ.
Lemma 11 (Blum and Blum [5]). Suppose a learner M learns L. Then
there exists a locking sequence for M on L.
For some of the restrictions/variations of automatic learners for automatic families, one can choose the hypothesis space H to be equal to L. This may sometimes cause a restriction, for example, in the case of hypothesis-length long-term
memory or iterative learning. The main reason for hypothesis space not to be
crucial in many cases is that one can automatically convert the indices fromone automatic family to another for the languages which are common to bothautomatic families. This stands in a contrast to the corresponding results forindexed families of recursive languages [27, 28]. A result in the present work
which depends on the choice of the hypothesis space is Theorem 23. In the casethat the hypothesis space does not matter, often, for the ease of notation, thelanguages are given in place of the indices as conjectures of the learner.
The following lemma is useful to bound the length of the long-term memoryof automatic learners.
Lemma 12 (Jain, Luo and Stephan [20]). Let M be an automatic learner.
For some constant c, for all σ, if mem and hyp are the long-term memory andhypothesis of M after having seen input σ, then max {|mem|, |hyp|} ≤ c + c ∗|σ| + max {|w| : w ∈ content(σ)}.
3. Some illustrative examples
We now provide some examples to give insight into the learning criteria considered and their properties. Example 13 deals with intervals of the lexicographic
ordering; one could formulate similar results also with other automatic linear
orderings. For the case of the lexicographic order, there is a difference between
closed and open intervals.
Example 13. The family of the closed intervals Lconv(x,y) = {z ∈ {0, 1}∗ :x ≤lex z ≤lex y} is automatic and can also be learnt by an automatic learner11with 2-bounded example memory. Furthermore, it has an automatic iterative
learner. Both learners memorise, either explicitly or implicitly by padding into
the hypothesis, the lexicographically least and greatest data seen so far.
The family of the open intervals Lconv(x,y) = {z ∈ {0, 1}∗ : x <lex z <lex y}is also automatic. However, it cannot be learnt as it violates Angluin’s telltale condition. The open interval Lconv(000,1) is the ascending union of theopen intervals Lconv(000,01m ) ; already Gold [15] observed that classes of this formcannot be learnt from positive data.
Example 14 shows that learnability by automatic learners cannot be characterised from the inclusion structure of a family alone, as the inclusion structurein the class of co-singleton sets is independent of the alphabet size.
Example 14. The family of all co-singleton sets {0, 1}∗ −{x}, with x ∈ {0, 1}∗ ,is automatic and satisfies Angluin’s tell-tale condition. It does not have an
automatic learner, as such a learner cannot memorise all the data observed[20]. However, it can be learnt by an automatic feedback learner (using one
query per round), which converges to a hypothesis for {0, 1}∗ − {x}, for thelength-lexicographically least member x of {0, 1}∗ for which the feedback queryanswer remains negative forever.
In contrast, the family of all sets {0}∗ −{x}, with x ∈ {0}∗ , has an automaticlearner using datum-length long-term memory. This follows from Theorem 3.
Example 15 shows the limitations and possibilities for learners which use amarked memory space but do not have access to any long-term memory. In
case (a) the marked memory space consists of the hypotheses that have been
issued and the data-items that have been observed. Note that the family in (a)is the same as in Example 14, though in contrast the learner here does not have
any long-term memory and thus does not remember its previous hypothesis;
instead it reconstructs part of the hypotheses history using the current datum
and hypothesis queries.
Example 15. (a) An automatic learner without any long-term memory, butusing at most one feedback and at most two hypothesis queries per round,can learn the class of all co-singleton subsets of {0, 1}∗ .
(b) An automatic learner, using a marked memory space of type 1 but no longterm memory, cannot learn the class {S ⊆ {0, 1}∗ : S has at most twoelements}.
Proof. (a) The automatic learner for the class is the following. For y ∈ {0, 1}∗ ,let Ly = {0, 1}∗ − {y}. Let succ(x) be the length-lexicographic successor of x in
{0, 1}∗ . Assume that the input is of the form x01n for some n. Then the learnercomputes the y with succ(y) = x, if any. If y exists and queries determine that
hypothesis y was conjectured previously, hypothesis x was not conjectured previously and y has been observed in the input data, then the learner conjectures
hypothesis x. If y as above does not exist and queries determine that hypothesis
12x was not conjectured previously, then the learner conjectures x. In all othercases (including the case of the input being of the form 1n for some n), thelearner conjectures ? in order to signal that there is no new conjecture (that is,
it repeats the previous conjecture). When learning Lx , it is easy to see that,for all y <ll x, eventually y is conjectured, y is observed in the input and, then,succ(y) is conjectured. Hence, x is eventually conjectured. The learner neverconjectures succ(x) as x never shows up in the input; indeed, the learner will
output ? after the time it conjectures x.
(b) Suppose an automatic learner using marked memory space of type 1(and no long-term memory) learns the class {{x, y} : x <ll y} (using somehypothesis space {Hα : α ∈ J}). Now consider the text y ◦ x ◦ x ◦ x ◦ . . . being
presented to the learner. Note that the learner, when it receives input x, can
ask only constantly many questions. Thus, there are two strings y, z >ll x suchthat, among the strings queried by x, the same strings are placed in the marked
memory space by the learner on input y or on input z. It follows that the learner
either converges on the texts y ◦ x ◦ x ◦ x ◦ . . . and z ◦ x ◦ x ◦ x ◦ . . . to the same
conjecture, or abstains from taking x into account for making its conjecture,
which is thus based on y or z only, respectively. Hence, the learner fails to learn
one of the languages {y}, {z}, {x, y}, {x, z}. 2
Further examples on learnable automatic families can be found in the priorliterature on automatic learners [20, 21].
4. Learning with feedback queries
The following result shows that feedback queries, together with datum-length
long-term memory, allows automatic learners to learn every automatic family
satisfying Angluin’s tell-tale condition. Equivalently one can also say that the
automatic learners with feedback are as powerful as algorithmic learners without
memory limitations. Later (Theorem 22) we will show that hypothesis-length
long-term memory is not enough to get such a result.
Theorem 16. If an automatic family L satisfies Angluin’s tell-tale condition,then L can be learnt by an automatic learner using one feedback query per roundand datum-length long-term memory.
Proof. Suppose L = {Lα : α ∈ I} is an automatic family satisfying Angluin’s
tell-tale condition. As one can decide equivalence of indices in an automaticfamily [21], without loss of generality assume that every distinct α, α0 ∈ I satisfy
Lα 6= Lα0 (otherwise, we can ignore non-minimal indices). By results from [21],there exists a constant c such that (i) for each α ∈ I, {w : |w| ≤ |α| + c} ∩ Lα
is a tell-tale set for Lα (below, tell-tale set for Lα will refer to this set) and (ii)for each L ∈ L, if L is finite, then there exists an index α such that L = Lα and|α| ≤ c + max {|x| : x ∈ L}. Fix such a constant c. The goal of the learner is tofind an α such that(a) the input contains {w : |w| ≤ |α| + c} ∩ Lα , (which is a tell-tale set for Lα )and
13

(b) every element in the input is contained in Lα .
Intuitively, for each potential conjecture α, the learner checks if the above telltale set for Lα is contained in the input. If so, then it checks if every string in
the input language is contained in Lα . If any of these are violated, then thelearner tries the next possible conjecture α. However, potential obstacles fordoing this are• the learner may not yet have seen the above tell-tale set for Lα , but theseelements appear later in the input;• the learner may already have seen an element outside Lα , forgotten thisfact, and the future elements to be seen are all in Lα .
To address the first problem above, each potential α will be tested more andmore times until the algorithm finds the correct hypothesis. To address thesecond problem, feedback queries are used to check, for all strings lengthlexicographically at most the length-lexicographically largest datum seen before
current conjecture α was tried, if any of them has been seen earlier but not in
Lα .
The long-term memory of the learner is of the form conv(z, α, y, b). Here z is
the length-lexicographically largest datum seen so far (z is ε for the case that the
input does not contain any datum), α is the current conjecture (which will be oflength at most |z| + c), b ∈ {0, 1} is used to remember whether the algorithm istesting clause (a) or (b) above, and y is used to remember which current string(relevant to (a) and (b) above) is being tested (the length of y will be at mostmax {|z|, |α|} + c). Note that for (b), the algorithm need only use feedback forstrings length-lexicographically smaller than the length-lexicographically largest
string seen up to the point at which the algorithm started testing for (b) above;
the rest of the strings are tested as they arrive.
Without loss of generality assume that ε is the length-lexicographically least
string in Σ∗ (the domain for the languages) as well as in I, the set of indices.
Initial long-term memory of the learner is (ε, α, ε, 0), where α is the lengthlexicographically largest index which is of length at most c. Let succ(y), pred(y)denote the length-lexicographic successor and predecessor of y in Σ∗ , and pred(α)
denote the length-lexicographic predecessor of α in the index set I (here we letpred(ε) = ε). On input x and previous long-term memory (z, α, y, b) the algorithm follows the first of the three cases below which applies. Here the feedback
query asked by the learner is y.
Case b = 0: (* this step checks whether the learner has already seen the above
tell-tale set for Lα *)If y ∈ Lα and y has not been seen in the input so far
Then the new long-term memory of the learner is (z 0 , α0 , ε, 0), where z 0 is
the length-lexicographically largest datum seen so far; if α 6= ε, then
α0 is length-lexicographic predecessor of α, otherwise α0 is the lengthlexicographically largest index of length at most |z 0 | + c; conjecture14

of the learner is irrelevant in this case. (* Here the learner has notseen the above tell-tale set for Lα , and thus tries the next possible
α. *)Else If y is the length-lexicographically largest string of length at most|α| + cThen new long-term memory of the learner is (z 0 , α, z 0 , 1), where z 0 is thelength-lexicographically largest string seen so far. The conjecture of
the learner is Lα . (* Here the learner has seen the above tell-tale set
for Lα , and thus goes on to test if the input language is a subset of
Lα . *)
Else let the new long-term memory of the learner be (z 0 , α, succ(y), 0)
and the conjecture of the learner be Lα , where z 0 is the lengthlexicographically largest string seen so far. (* Here the learner continues checking whether the above tell-tale set for Lα has been seen
or not. *)Case b = 1 and [y 6∈ Lα but y has been seen in the input so far or x 6= # andx 6∈ Lα ]: The new long-term memory of the learner is (z 0 , α0 , ε, 0), wherez 0 is the length-lexicographically largest datum seen so far; if α 6= ε, then
α0 is the length-lexicographic predecessor of α, otherwise α0 is the lengthlexicographically largest index of length at most |z 0 | + c; conjecture of thelearner is irrelevant in this case. (* Here the learner has seen a datum notbelonging to Lα , and thus tries the next possible α. *)Neither of the two cases above: The new long-term memory of the learneris (z 0 , α, pred(y), 1), where z 0 is the the length-lexicographically largest
datum seen so far; conjecture of the learner is Lα .
Suppose the input text is for a target language Lγ . If Lα 6= Lγ , then any longterm memory of the form (·, α, ·, ·), will eventually be updated with changed
value of α as either the input does not contain the above tell-tale set for Lα or
the input contains an element not in Lα . Also, as length of γ is at most |z| + c,
for the longest datum z in the input, eventually it will be the case that thelearner has a long-term memory of the form (z, α, ε, 0), where Lα = Lγ and the
input seen already contains all the elements in {x ∈ Lα : |x| ≤ |α| + c}. But this
implies that the learner will eventually have long-term memory (z 0 , α, y = z 0 , 1),
where z 0 is the longest datum seen up to that time (this happens when thelearner has verified that all the elements of the above tell-tale set for Lα arepresent in the input). From then on the value of y decreases (until its value
reaches ε) in each stage, and the learner always conjectures Lα . Thus, thelearner learns the target language Lγ . 2Thus, the learners considered in the above result are as general as recursive
learners (see Proposition 2). Therefore, the next results compare various more
restrictive models of learning with feedback and limitations on the long-term
memory. First, it is shown that there are cases where feedback queries are more15

important than any form of long-term memory (including bounded example
memory). Note that Example 14 also gives a class which can be learnt by anautomatic learner using one feedback query per round but cannot be learnt by
an automatic learner without any marked space memory. However, the learnerin Example 14 needs hypothesis-length long-term memory or datum-length longterm memory. The feedback learner in the following theorem does not use any
long-term memory.
Theorem 17. Let Σ = {0, 1, 2}. Let Lε = {0, 1}+ . For all x ∈ {0, 1}+ ,let Lx = {y ∈ {0, 1}∗ : |y| ≤ |x|, y 6= x} ∪ {y2n : |y| = |x|, n > 0}. Let
L = {Lx : x ∈ {0, 1}∗ }. Then, the following two statements hold:(a) An automatic learner without any long-term memory, but using one feedback
query per round, can learn L;(b) No automatic learner learns L.
Proof. (a) L can be learnt by an automatic learner (without any long-term
memory) using 1 feedback query as follows. On inputs from {0, 1}∗ , query if εbelongs to the input seen — if not, then output Lε ; otherwise, output ?. On
inputs of the form x2n , n > 0, query whether x belongs to the input seen — if
not, then output Lx else output ?. It is easy to verify that the above learnerlearns L.
(b) Suppose by way of contradiction that M is automatic and learns L.
Without loss of generality assume that M always outputs a hypothesis.
Let m be so large that there are two sequences σ1 and σ2 , each containing
m elements of {0, 1}m , such that content(σ1 ) 6= content(σ2 ) and M has thesame long-term memory and hypothesis after processing either σ1 or σ2 . As
M is automatic, such m, σ1 and σ2 exist (as, by Lemma 12, the long-term
memory of M can be of length at most a constant times m after seeing such σ1
mor σ2 , and there are (2m ) different subsets of {0, 1}m of size m). Let x1 be incontent(σ1 ) − content(σ2 ) and x2 be in content(σ2 ) − content(σ1 ). Let T be atext for {y : |y| ≤ m, y 6= x1 , y 6= x2 } ∪ {y2n : |y| = m and n > 0}. Then, M on
σ1 ◦ T and σ2 ◦ T converges to the same hypothesis or diverges on both, thoughthese are respectively texts for Lx2 and Lx1 . Thus, M does not learn L. 2
The next two results give advantages of having bounded example memory overjust feedback queries (without any long-term memory).
Theorem 18. Let Σ = {0, 1}. Let L consist of L0 = {0}+ and Lconv(x,y) ={x, y} ∪ {0n+1 : x(n) = 1}, where x ∈ {0, 1}∗ · {1} and y ∈ {0}|x| · {0}∗ . Thenthe following three statements hold:(a) L can be learnt by an automatic learner with 1-bounded example memory;(b) L can be learnt by an automatic learner using two feedback queries perround, along with a hypothesis-length long-term memory;(c) L cannot be learnt by an automatic iterative learner using feedback queries.
16

Proof. (a) Intuitively, the learner keeps in long-term memory the longest
string seen, while the input is contained in L0 . Once the learner sees an elementx not in 0∗ , it memorises x. This long-term memory, along with the new input
element, determines the conjecture of the learner.
The learner using the bounded example memory, on every input z and longterm memory A, updates its memory and outputs a hypothesis based on thefollowing table.
old memory A
—
A=∅
A=∅
A = {0n }A = {0n }A = {x} ⊆ {0, 1}∗ 1
A = {x} ⊆ {0, 1}∗ 1

input z#z ∈ 0+z ∈ {0, 1}∗ 1
z ∈ 0+z ∈ {0, 1}∗ 1|z| > |x||z| ≤ |x|

new memory A0
A0 = A
A0 = {z}A0 = {z}A0 = {0max {n,|z|} }A0 = {z}A0 = A
A0 = Ahypothesis?
L0
Lconv(z,0|z| )L0
Lconv(z,0max {n,|z|} )Lconv(x,z)?

It is easy to see that the learner above is automatic. We now show that thelearner learns L. Clearly, the learner succeeds to learn L0 , as the learner conjectures L0 when the first datum appears in the input and then never changes
its mind. Furthermore, when learning Lconv(x,0|x| ) , the learner will issue thishypothesis on receipt of the datum x and from then on abstain from conjecturing a new hypotheses. When learning Lconv(x,y) with y ∈ {0}+ and |y| > |x|,
there are two cases: If the learner receives the datum y at least one time after
receiving x, then the learner will conjecture conv(x, y) on the receipt of this y;
as y is the only member of {0}+ ∩ Lconv(x,y) which is longer than x, this is the
only case when such a hypothesis is issued; thus the learner learns Lconv(x,y) .
Otherwise the learner receives y before x and thus A = {y} when x is received
by the learner as input for the first time — at which point the learner will issue
the hypothesis Lconv(x,y) and output ? from then onwards. Thus the learnerlearns Lconv(x,y) as well.
(b) The automatic learner using feedback queries and hypothesis-length longterm memory initially conjectures hypothesis for L0 . The learner keeps in its
long-term memory the string x, if any, in the input such that x 6∈ 0∗ along with
one bit of information which tells whether an even or an odd number of distinct
data items from 0∗ have been seen so far — this parity bit can be updated if a
not previously seen datum from 0∗ is observed in the input (whether a datum is
new or old can be determined by making one feedback query). Along with these,
the learner also keeps in memory some other information as needed below.
If the learner has seen x 6∈ 0∗ in the input, then the parity bit is used in orderto determine whether the parity of the number of strings from 0∗ already seen in
the input coincides with the number of the elements in Lconv(x,0|x| ) . If so, thenthe learner conjectures Lconv(x,0|x| ) . Otherwise, the learner searches, using its
second feedback query in each round, for an n > |x| such that 0n appears in the
input (this can be done by using hypotheses (which can be stored in long-term

17memory) of the form conv(x, 0r ), and correspondingly querying 0r in the next
round, where r = |x| + 1, |x| + 2, |x| + 3, . . .).
Here, note that, during the above searching process, if a new datum, notpreviously seen, is observed by the learner, then the parity of the number ofobserved data becomes consistent with Lconv(x,0|x| ) and the algorithm given
above switches back to outputting Lconv(x,0|x| ) .
(c) Suppose by way of contradiction that an automatic iterative learner M
using feedback queries learns L. Thus, by Lemma 11, there is a locking sequencefor M on L0 , that is, there exists a σ such that the conjecture of M does notchange beyond σ on any text for L0 which starts with σ (see [5, 32]). Without
loss of generality assume that σ contains at least one string. Let x be such that
Lconv(x,0|x| ) = {x}∪content(σ). While processing the text T = σ ◦x◦x◦x . . ., M
asks only finitely many different feedback queries. Let n be such that n > |x|,n is greater than length of any element in content(σ) and 0n is not queried by
M on the text T . Then M converges on the texts σ ◦ 0n ◦ x ◦ x ◦ x ◦ x . . . andσ ◦ x ◦ x ◦ x ◦ x ◦ x . . . to the same hypothesis although these two texts are fortwo different languages, namely Lconv(x,0|x| ) and Lconv(x,0n ) . 2
Let C(x) denote the plain Kolmogorov complexity [29], that is, the length of
the smallest program p such that U (p) = x, where U is some fixed Universal
Turing machine.
Theorem 19. Let i, j ≥ 1. Let the alphabet for the languages be Σ = {0, 1}.
Let L = {F ⊆ Σ∗ : |F | = i + 1}. Then,(a) Some automatic learner can learn L using i-bounded example memory.
(b) No learner with (i − 1)-bounded example memory and using j-feedback
queries per round can learn L.
Proof.(a) The automatic learner memorises the first i distinct elements in the
input. If the learner has already memorised i elements and sees a datum notin the long-term memory, then it conjectures the corresponding set of i + 1
elements, else it outputs ?. It is easy to verify that the above learner learns L.
(b) Suppose by way of contradiction that a learner M learns L using (i − 1)bounded example memory and j-feedback queries. Then, consider x0 , x1 , . . . , xi
∈ {0, 1}k with k > i such that these strings are distinct and in lexicographic
ascending order and C(x0 x1 . . . xi ) ≥ (i + 1) · k − c where C is the (plain)
Kolmogorov complexity [29] and c is a constant depending on i but not on kkksuch that (2i+1 ) ≥ 2(i+1)·k−c for all k > i; note that there are at least (2i+1 )many ascendingly ordered tuples of distinct i + 1 binary strings of length kwhenever k > i. At each time where M makes a correct conjecture on a text for{x0 , x1 , . . . , xi }, one can compute x0 x1 . . . xi from the hypothesis of the learner,
which depends only on M ’s current long-term memory and M ’s current datum
and the answers to the feedback queries. Up to an additive constant independentof k: the long-term memory has Kolmogorov complexity at most (i − 1) · k; thecurrent datum has Kolmogorov complexity at most k; the feedback answers have
Kolmogorov complexity at most j. It follows that x0 x1 . . . xi has Kolmogorov
complexity at most i · k + j + d where d is a constant which depends on i, j
18but not on k; this implies (i + 1) · k − c ≤ i · k + j + d and k ≤ j + c + d, acontradiction to the fact that k can be arbitrarily large. 2
Note that the proof of part (b) of Theorem 19 also shows that the class L cannot
be learnt using feedback queries and constant-length long-term memory.
The following gives a class which can be learnt using either bounded example
memory of size k or using at most k feedback queries, but not using smaller
bounded example memory size or smaller number of feedback queries. Although
Theorem 20 also uses cardinality techniques, the overall proof method is quite
different and the resulting class can be learnt with constant-length long-term
memory.
Theorem 20. Let k ≥ 1. Let L = {F : ∃n [∅ ⊆ F ⊆ {0m : (k + 1)n ≤ m <(k + 1)(n + 1)}]}. Then the following statements hold:(a) Some automatic learner can learn L using k-bounded example memory;(b) Some automatic learner without any long-term memory can learn L using
k feedback queries;(c) L cannot be learnt by any automatic learner using only (k − 1) bounded
example memory (where the learner does not have any memory besides
the examples memorised);(d) An automatic learner without any long-term memory cannot learn L using
only k − 1 feedback queries.
(e) An automatic learner using a constant amount of long-term memory canlearn L without queries of any type.
Proof. Note that L is an automatic family, as one can use the index set{conv(x0 , x1 , . . . , xk ) : (∃n)(∀i ≤ k) [xi = # or xi ∈ 0∗ and [(k + 1)n ≤ |xi | <(k+1)(n+1)]]}, which is clearly a regular set. Then, L is the family of languages
Lconv(x0 ,x1 ,...,xk ) = {xi : i ≤ k, xi 6= #}.
(a) The initial conjecture and long-term memory of the learner are ∅. The
automatic learner memorises its inputs as long as it sees at most k elements. If
the input element is # or is in the long-term memory, then the learner outputs?. Otherwise (the input element is not in the long-term memory), the learner
outputs a conjecture for the set of memorised elements plus the new element
seen. It is easy to verify that the above learner learns L.
(b) The initial conjecture of the learner is ∅. On input #, the learner outputs?. On input 0m , the learner first finds 0(k+1)n such that (k + 1)n ≤ m <(k + 1)(n + 1). Note that this can be done automatically. The automatic learnerthen queries the elements in {0` : (k + 1)n ≤ ` < (k + 1)(n + 1), ` 6= m}, andoutputs the conjecture corresponding to the set S ∪ {0m }, where S is the set of
queries answered positively.
(c) Suppose by way of contradiction that an automatic learner learns L using
at most (k − 1) memory elements. Let F ∈ L be of minimal cardinality such

19

that, for some input segment σ with content(σ) = F , the long-term memory of
the learner after seeing σ is a proper subset of F . Suppose SF is the long-term
memory. Thus, SF is a proper subset of F and for every input sequence σ 0 with
content SF , the long-term memory of the learner after seeing σ 0 is SF . Let x be
such that x 6∈ F and F ∪ {x} ∈ L. Now, the learner cannot distinguish between
input being σ ◦ x ◦ x ◦ x ◦ x . . . and τ ◦ x ◦ x ◦ x ◦ x . . ., where τ is some segmentwith content(τ ) = SF .
(d) Suppose by way of contradiction otherwise. Let σ be an initial sequenceof #∞ such that the feedback learner outputs the conjecture for ∅ on σ. Let x
be any member of {0}∗ . Suppose n is such that (k + 1)n ≤ |x| < (k + 1)(n + 1).
Let y be such that, (k + 1)n ≤ |y| < (k + 1)(n + 1), y 6= x and the learner does
not query y on input x. Then, both {x} and {x, y} are in L, but the learner
fails to learn the input text on at least one of the texts σ ◦ y ◦ x ◦ x ◦ x ◦ x ◦ . . .
and σ ◦ x ◦ x ◦ x ◦ x ◦ . . ., as the learner cannot remember whether it has seen y.
(e) The learner starts with a hypothesis for ∅, and in its long-term memory
keeps track, for each number ` < k + 1, whether it has seen a string of length(k + 1) · n + ` for some n. Whenever a datum of the form 0(k+1)n+m , m < k + 1,
is observed, the learner updates the long-term memory accordingly, determines0(k+1)n and conjectures the (least index for the) set {0(k+1)n+` : ` < k + 1 and `is in the long-term memory}. The learner outputs ? in the case that it observes#. Eventually the learner sees the last of the strings 0(k+1)n+m , m < k + 1, on
the input and due to the long-term memory it conjectures the right hypothesis;
from now on, all hypotheses of the learner are either the least index for thecorrect set in the hypothesis space or ?. Hence the learner learns L. 2
Parts (a) and (b) of the above theorem can be generalised to show that the class
L can be learnt by an automatic learner which uses, for given r ∈ {0, 1, . . . , k},a bounded example memory of size r and k − r feedback queries. We do not yet
know if this is optimal.
5. Learning using a marked memory space
An automatic learner using a marked memory space of type 1 is a generalisationof a learner using feedback queries. Hence it follows from Theorem 16 thatevery automatic class satisfying Angluin’s tell-tale condition can be learnt by anautomatic learner with marked memory space of type 1 and datum-length longterm memory. Hence, the explorations in this section target at more restricted
limitations of the long-term memory combined with the usage of a marked
memory space.
Theorem 21. Every automatic family satisfying Angluin’s tell-tale condition
has an automatic learner which uses hypothesis-length long-term memory and amarked memory space of type 2.
Proof. Suppose Σ is the alphabet for the languages, and {Lα : α ∈ I} is an
automatic family which satisfies Angluin’s tell-tale condition. Without loss ofgenerality assume that for all distinct α, α0 in I, Lα 6= Lα0 .
20

The aim of the learner is to search for an α such that a tell-tale set for Lα
is contained in the input, and the input language is contained in Lα . The ideaof the proof is similar to that of Theorem 16. However a marked memory space
is used instead of feedback queries. Furthermore, the long-term memory needs
will be less than that used in Theorem 16.
In the algorithm for the learner, one uses a marked memory space consistingof entries of the form (hypothesis, 0), (hypothesis, 1) and (datum, 2). The
algorithm has two variables, α ranging over the indices and y ranging over Σ∗ .
Let succ(α) denote the length-lexicographic successor of index α (in I) andsucc(y) denote the length-lexicographic successor of datum y (in Σ∗ ). Without
loss of generality, suppose ε is the length-lexicographically least element of I.
The long-term memory holds the hypothesis α and the pointer y. Note thaty is only used to test whether all elements of a tell-tale set are in the input
seen so far. Recall from Proposition 2 that there is a constant c such that thestrings in Lα of length at most |α| + c forms a tell-tale set for Lα . Hence,
the length of the long-term memory conv(α, y) is bounded by the length of the
hypothesis α plus a constant. Furthermore, x refers to the current datum, but
x will not be memorised in the long-term memory and discarded when reading
the next datum. The initial values of α and y are ε. In the marked memory
space, an element of the form (z, 2) is used for remembering the data seen sofar; an element of the form (α, 1) is used to denote that Lα does not containsome input string seen so far (thus the main remaining job of the algorithm
is to check whether the tell-tale set for Lα is contained in the input seen sofar); an element of the form (α, 0) is used to denote that hypotheses lengthlexicographically smaller than α have been considered earlier. This allows us toconsider each possible hypothesis arbitrarily often until a correct hypothesis isfound. In each round of the algorithm the following is done:
Beginning of the round.
1. Current long-term memory is conv(α, y) and the new input is x.
Query whether (α, 0), (α, 1) and (y, 2) are in the marked memory space.
2. If (α, 0) is not in marked memory space,then place (α, 0) in the marked memory space, let α = ε, let y = ε and go
to step 6.
3. If (α, 1) is in the marked memory space or x 6= # and x ∈/ Lα ,
then let α = succ(α), let y = ε and go to step 6.
4. If y ∈ Lα and (y, 2) is not in the marked memory space and y 6= x,
then let α = succ(α), let y = ε and go to step 6.
5. If |succ(y)| ≤ |α| + c,then let y = succ(y) and go to step 6.
6. Place (x, 2) in the marked memory space. If x 6= #, then place (β, 1) inthe marked memory space for all β where x ∈/ Lβ .
7. Output the hypothesis α.
8. The new long-term memory is the new value of conv(α, y).
End of the round.
21

Placing of elements in the marked memory space is done after the queries on
the old marked memory space has been done and the updates depend on theold marked memory space.
The algorithm can be realised by automatic functions using the answers to
the queries given and the queries can also be determined by automatic functions.
Now it remains to show that the algorithm learns the class L. For this,assume, without loss of generality, that every language in the class has exactly
one index. Suppose that Lγ is the language to be learnt. Further suppose all
elements of Lγ which are of length at most |γ| + c have already shown up in
the input. If the current index α is not equal to γ, then either during theinference process some x ∈/ Lα shows up, causing (α, 1) to be placed in themarked memory space, and thus causing α to be updated to succ(α) in step 3,
or there exists a z ∈ Lα −Lγ with |z| ≤ |α|+c (due to the tell-tale set property).
In the later case, eventually the variable y will take the value z and then α will
be updated to succ(α) by step 4, as z will never be observed and, therefore,(z, 2) will never be placed in the marked memory space. Furthermore, when α
takes a new value not taken before, step 2 will reset α to ε and α will cycle toall the values again until it eventually reaches the value of γ. Then steps 2 and3 will not apply. Furthermore, as all the members of Lγ of length at most |γ| + chave already been observed, step 4 will also not apply. Therefore, the value of
α will no longer change and y will eventually stabilise. So the algorithm would
converge to α = γ and will conjecture Lγ from that point of time onwards.
Thus, Lγ is learnt by the algorithm. 2
Note that the learner in the above theorem can be made iterative, if one uses
arbitrary hypothesis space rather than as given by the class being learnt. For
this, one chooses the hypothesis space Hconv(α,y) = Lα . Note here that thelong-term memory of the learner in the above proof also converges, and thus
if one takes the hypothesis of the learner as its long-term memory, then thelearner becomes iterative.
One might ask whether it is necessary to have a marked memory space oftype 2 in the above result. The next result shows that in some cases this isindeed needed and a marked memory space of type 1 is not enough. This result
also shows that just hypothesis-length long-term memory (even with feedback
queries) is not enough to learn all automatic families. Contrast this with Theorem 16, where datum-length long-term memory along with one feedback query
every round was enough to learn all the automatic families satisfying Angluin’s
tell-tale condition.
The following theorem uses the class used in [20] to separate automaticlearnability using datum-length long-term memory from automatic learnability
using hypothesis-length long-term memory. The diagonalisation method usedhere is a generalisation of the technique used in [20].
Theorem 22. Let L be the class consisting of L0 = {0}+ and all finite sets
Lα = {0i : α(i) = 1}, for α ∈ {1} · {0, 1}∗ .
Then, L has an automatic learner using datum-length long-term memory.
However, an automatic learner using hypothesis-length long-term memory plus
22

a marked memory space of type 1, cannot learn L.
Proof. Note that ε ∈ Lα , for all α ∈ {1} · {0, 1}∗ . As L satisfies Angluin’s
tell-tale condition, learnability of L by an automatic learner using datum-length
long-term memory follows from Theorem 3.
Now consider any automatic learner with type 1 marked memory space,but with only hypothesis-length long-term memory. Using standard locking
sequence methods [5, 32], one can show that, when learning the language {0}+ ,there is a sequence σ and a constant c such that the learner, on any text for{0}+ starting with σ, does not change the conjecture after having processed σ
and never takes a long-term memory value of length longer than c (this holds as
the long-term memory of the learner is bounded in length by the length of its
hypothesis (plus a constant), which does not change beyond σ). Furthermore,
there is a constant c0 such that, when reading an input 0n , the learner queriesor places in the marked memory only strings of length up to c0 or of length
between n − c0 and n + c0 .
Now consider the learner on input σ ◦0n1 ◦0n2 ◦. . ., where ni+1 > ni +2c0 and
n1 > a + 2c0 + m for a being the length of the longest datum in σ and m being
the length of the longest string in the marked memory space after the learnerhas seen σ. Note that, on input σ ◦ 0n1 ◦ 0n2 ◦ . . ., there is a long-term memory
value which is repeated infinitely often in the above run of the learner (because
the number of possible long-term memory values on this text is finite, as they
are bounded in length by c). Let this long-term memory value be mem. Let
k be large enough such that the long-term memory of the learner after seeingσ ◦ 0n1 ◦ 0n2 ◦ . . . ◦ 0nk is mem, and any string of length at most c0 which is everin marked memory space (on input text σ ◦ 0n1 ◦ 0n2 ◦ . . .), gets in the marked
memory space by the time the learner sees σ ◦ 0n1 ◦ 0n2 ◦ . . . ◦ 0nk . Now consider
the behaviour of the learner on input σ ◦ 0n1 ◦ 0n2 ◦ . . . ◦ 0nk ◦ ε ◦ ε ◦ ε · · ·. As
this input is in L, the learner converges on this input text to some conjecture(say β) and does not query or places in marked memory space any string oflength larger than a number d (as the learner receives only finitely many strings
in input).
Let r and r0 > r be such that nr > nk + d + 2c0 and long-term memory of thelearner is mem after having seen σ ◦ 0n1 ◦ 0n2 ◦ . . . ◦ 0nk ◦ 0nk+1 ◦ . . . ◦ 0nr−1 andalso after having seen σ ◦ 0n1 ◦ 0n2 ◦ . . . ◦ 0nk ◦ 0nk+1 ◦ . . . ◦ 0nr−1 ◦ 0nr ◦ . . . ◦ 0nr0 .
Note that there exist such r and r0 , as the learner has long-term memory mem
infinitely often on the input σ ◦ 0n1 ◦ 0n2 ◦ . . .; thus, the long-term memory of thelearner is also mem after having seen σ ◦0n1 ◦0n2 ◦. . .◦0nk ◦0nr ◦0nr+1 ◦. . .◦0nr0
as the learner’s outputs only depend on its long-term memory and the answer
to the queries asked.
Thus, the learner also converges to β on the input σ ◦0n1 ◦0n2 ◦. . .◦0nk ◦0nr ◦nr+1
0◦ . . . ◦ 0nr0 ◦ ε ◦ ε ◦ ε · · ·. It follows that the learner converges to the same
conjecture on the two texts (representing two different languages) σ ◦ 0n1 ◦ 0n2 ◦. . .◦0nk ◦ε◦ε◦ε · · · and σ ◦0n1 ◦0n2 ◦. . .◦0nk ◦0nr ◦0nr+1 ◦. . .◦0nr0 ◦ε◦ε◦ε◦ε · · ·.
Thus, the learner fails to learn L. 2

23

It is open whether an automatic learner using hypothesis-length long-term memory can be made iterative [20]. Theorem 23 deals with the counterpart of thisproblem when we permit a marked memory space of type 1 to the simulator.
Theorem 23. If a class L has an automatic learner using hypothesis-length
long-term memory and not using any marked memory space, then L also has
an automatic iterative learner using hypothesis queries and a new underlying
automatic family as hypothesis space.
Proof. Assume that the automatic learner M is learning L = {Li : i ∈ I}
using hypothesis-length long-term memory over Γ∗ . Without loss of generality
assume that the initial hypothesis of M is not ?. Let Hconv(i,g) = Li for all i ∈ I
and g ∈ Γ∗ . For a current datum x and long-term memory g and hypothesis i,letconv(i, h), if M on input x and long-term memory g
conjectures ? and takes new long-termmemory h;
F (conv(i, g), x) =conv(j,h),
if M on input x and long-term memory g
conjectures
j and takes new long-termmemory h.
The function F is automatic. Note that F can be considered as a learner
which starts with initial hypothesis conv(inithyp, initmem), where initmem isthe initial long-term memory of M and inithyp is the initial hypothesis of M .
Then, for any input segment σ, F (σ) = conv(i, g), where i is the most recent
hypothesis of M after reading input σ and g is the long-term memory of M
after reading input σ.
Now one builds a new automatic iterative learner N , which uses hypothesis
space {Hconv(i,g) : i ∈ I, g ∈ Γ∗ } and which tries to follow M and F as closely as
possible, but which does not return to a hypothesis it has once abandoned. N
starts with the same initial hypothesis as F that is with conv(inithyp, initmem).
Then the update function of N is the following one:F (conv(i, g), x), if F (conv(i, g), x) had not beenconjectured previously;
N (conv(i, g), x) =conv(i,g),
if F (conv(i, g), x) had beenconjectured previously.
Note that N can find out using a hypothesis query whether F (conv(i, g), x) had
been conjectured previously. As F is automatic, so is N . Furthermore, assume
that N (x0 ◦ x1 ◦ . . . ◦ xn ) = conv(in , gn ) for some text x0 ◦ x1 ◦ . . . for somelanguage in L. Then there are sequences τ0 , τ1 , . . . (with τn containing elementsfrom {x0 , x1 , . . . , xn }) such that F after processing x0 ◦τ0 ◦x1 ◦τ1 ◦. . .◦xn ◦τn has
the hypothesis (in , gn ). We now show this by induction on n. It is clearly true
for n = 0, as one can choose τ0 = ε. Assume n > 0 and assume the statement
to be true for values smaller than n. If N (conv(in−1 , gn−1 ), xn ) is defined via
the first clause in its definition, then one can choose τn to be empty sequence.
24

If N (conv(in−1 , gn−1 ), xn ) is defined via the second clause in its definition, thensuppose F (conv(in−1 , gn−1 ), xn ) = conv(im , gm ), which was conjectured by N
after x0 ◦ x1 ◦ . . . ◦ xm (here m could be −1 and F (conv(in−1 , gn−1 ), xn ) isthen the initial hypothesis of N ). One then chooses τn to be xm+1 ◦ τm+1 ◦xm+2 ◦ τm+2 ◦ . . . ◦ xn−1 ◦ τn−1 . It is easy to verify that N (x0 ◦ x1 ◦ . . . ◦ xn ) =F (x0 ◦ τ0 ◦ x1 ◦ τ1 ◦ . . . ◦ xn ◦ τn ).
Suppose that the sequence of hypotheses of M converges on the text x0 ◦ τ0 ◦x1 ◦ τ1 ◦ . . . to i. Then, for almost all n, in as defined above is i. Furthermore,|gn | ≤ |i| + c for some constant c and all n. As N does not return to oldabandoned hypotheses, the sequence of conv(in , gn ) also converges to a pairconv(i, g); here the first component must be i as almost all in are i. It follows
from Hconv(i,g) = Li that N learns the input language. 2
Acknowledgements
A preliminary version of this paper appeared in CiE 2011 [10]. We would liketo thank the anonymous referees of the conference and this journal for several
useful comments.
References[1] Dana Angluin. Inductive inference of formal languages from positive data.
Information and Control, 45:117–135, 1980.
[2] Dana Angluin. Finding patterns common to a set of strings. Journal ofComputer and System Sciences, 21:46–62, 1980.
[3] Dana Angluin. Inference of reversible languages. Journal of the ACM,
29:741–765, 1982.
[4] Dana Angluin. Learning regular sets from queries and counterexamples.
Information and Computation, 75:87–106, 1987.
[5] Lenore Blum and Manuel Blum. Toward a mathematical theory of inductive
inference. Information and Control, 28:125–155, 1975.
[6] Achim Blumensath. Automatic structures. Diploma thesis, RWTH Aachen,
1999.
[7] Achim Blumensath and Erich Grädel. Automatic structures. 15th AnnualIEEE Symposium on Logic in Computer Science, LICS 2000, pages 51–62.
IEEE Computer Society, 2000.
[8] John Case, Sanjay Jain, Steffen Lange and Thomas Zeugmann. Incremental
concept learning for bounded data mining. Information and Computation,
152:74–110, 1999.

25

[9] John Case, Sanjay Jain, Trong Dao Le, Yuh Shin Ong, Pavel Semukhin andFrank Stephan. Automatic Learning of Subclasses of Pattern Languages.
Information and Computation, 218: 17–35, 2012.
[10] John Case, Sanjay Jain, Yuh Shin Ong, Pavel Semukhin and Frank
Stephan. Automatic Learners with Feedback Queries. Seventh conference on Computability in Europe, CiE 2011, Proceedings. Springer LNCS
6735:31–40, 2011.
[11] François Denis, Aurélien Lemay and Alain Terlutte. Some classes of regular languages identifiable in the limit from positive data. Sixth International Colloquium on Grammatical Inference: Algorithms and Applications(ICGI), pages 63–76, Springer LNCS 2484, 2002.
[12] David Epstein, James Cannon, Derek Holt, Silvio Levy, Michael Paterson
and William Thurston. Word Processing in Groups. Jones and Bartlett
Publishers, Boston, Massachusetts, 1992.
[13] Henning Fernau. Identification of function distinguishable languages. Theoretical Computer Science, 290:1679–1711, 2003.
[14] Rusins Freivalds, Efim Kinber and Carl H. Smith. On the impact of forgetting on learning machines. Journal of the ACM, 42:1146–1168, 1995.
[15] E. Mark Gold. Language identification in the limit. Information and Control, 10:447–474, 1967.
[16] Tom Head, Satoshi Kobayashi and Takashi Yokomori. Locality, reversibility, and beyond: learning languages from positive data. Algorithmic
Learning Theory, Ninth International Conference, ALT 1998, Proceedings.
Springer LNAI 1501:191–204, 1998.
[17] Bernard R. Hodgson. Théories décidables par automate fini. Ph.D. thesis,
University of Montréal, 1976.
[18] Bernard R. Hodgson. Décidabilité par automate fini. Annales des sciences
mathématiques du Québec, 7(1):39–57, 1983.
[19] Sanjay Jain, Qinglong Luo, Pavel Semukhin and Frank Stephan. Uncountable automatic classes and learning. Theoretical Computer Science,
412:1805–1820, 2011. Special Issue on Algorithmic Learning Theory, 2009.
[20] Sanjay Jain, Qinglong Luo and Frank Stephan. Learnability of automaticclasses. Journal of Computer and System Sciences, 78:1910–1927, 2012.
[21] Sanjay Jain, Yuh Shin Ong, Shi Pu and Frank Stephan. On automaticfamilies. Proceedings of the 11th Asian Logic Conference, ALC 2009, in
Honor of Professor Chong Chitat’s 60th birthday, pages 94–113. World
Scientific, 2011.

26

[22] Sanjay Jain, Eric Martin and Frank Stephan. Robust learning of automaticclasses of languages. Algorithmic Learning Theory, 22nd International Conference, ALT 2011, Proceedings. Springer LNAI 6925: 55–69, 2011.
[23] Sanjay Jain, Daniel N. Osherson, James S. Royer and Arun Sharma. Systems That Learn. MIT Press, 2nd Edition, 1999.
[24] Bakhadyr Khoussainov and Anil Nerode. Automatic presentations of structures. Logical and Computational Complexity. Springer LNCS 960:367–392,
1995.
[25] Efim Kinber and Frank Stephan. Language learning from texts: mindchanges, limited memory and monotonicity. Information and Computation,
123:224–241, 1995.
[26] Steffen Lange and Thomas Zeugmann. Language learning in dependence
on the space of hypotheses. Proceedings of the Sixth Annual Conference on
Computational Learning Theory, COLT 1993, pages 127–136. ACM Press,
1993.
[27] Steffen Lange and Thomas Zeugmann. Incremental learning from positive
data. Journal of Computer and System Sciences, 53:88–103, 1996.
[28] Steffen Lange, Thomas Zeugmann and Sandra Zilles. Learning indexedfamilies of recursive languages from positive data: a survey. TheoreticalComputer Science, 397:194–232, 2008.
[29] Ming Li and Paul Vitányi. An Introduction to Kolmogorov Complexity and
Its Applications. Third Edition, Springer, 2008.
[30] André Nies. Describing groups. Bulletin of Symbolic Logic, 13(3):305–339,
2007.
[31] André Nies and Pavel Semukhin. Finite automata presentable Abeliangroups. Annals of Pure and Applied Logic, 161:458–467, 2009.
[32] Daniel Osherson, Michael Stob and Scott Weinstein. Systems That Learn,
An Introduction to Learning Theory for Cognitive and Computer Scientists.
Bradford — The MIT Press, Cambridge, Massachusetts, 1986.
[33] Lenny Pitt. Inductive inference, DFAs, and computational complexity.
Analogical and Inductive Inference, Proceedings of the Second International
Workshop, AII 1989. Springer LNAI 397:18–44, 1989.
[34] Sasha Rubin. Automatic Structures. Ph.D. Thesis, The University of Auckland, 2004.
[35] Sasha Rubin. Automata presenting structures: a survey of the finite stringcase. The Bulletin of Symbolic Logic, 14:169–209, 2008.

27

[36] Todor Tsankov. The additive group of the rationals does not have an
automatic presentation. The Journal of Symbolic Logic, 76(4):1341–1351,
2011.
[37] Kenneth Wexler and Peter W. Culicover. Formal Principles of Language
Acquisition. Cambridge, Massachusetts, The MIT Press, 1980.
[38] Rolf Wiehagen. Limes-Erkennung rekursiver Funktionen durch spezielle
Strategien. Elektronische Informationsverarbeitung und Kybernetik (EIK),
12:93–99, 1976.

28