Automatic Learners with Feedback Queries
John Case1 , Sanjay Jain?,2 , Yuh Shin Ong2 , Pavel Semukhin??,3 and Frank Stephan? ? ?,2,4
1

Department of Computer and Information Sciences,
University of Delaware, Newark, DE 19716-2586, USA.
case@cis.udel.edu
2
Department of Computer Science, National University of Singapore,
Singapore 117417, Republic of Singapore.
sanjay@comp.nus.edu.sg and yuhshin@gmail.com
3
Department of Computer Science, University of Regina,
Canadapavel@semukhin.name
4Department of Mathematics, National University of Singapore,
Singapore 119076, Republic of Singapore.
fstephan@comp.nus.edu.sg

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, in eachround, output a hypothesis and update a long-term memory, depending on the input
datum, via an automatic function, that is, via a function whose graph is recognised
by a finite automaton. Many variants of automatic learners are investigated: where
the long-term memory is restricted to be the current hypothesis whenever this exists,
cannot be of length larger than the length of the longest datum seen, or has toconsist of a constant number of examples seen so far. Furthermore, learnability isalso studied with respect to queries which reveal information about past data or past
computation history; the number of queries per round is bounded by a constant.
These models are generalisations of the model of feedback queries, given by Lange,
Wiehagen and Zeugmann.

1

Introduction

The basic model of learning in inductive inference may be described as follows. A learner isreceiving 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 more data. The learner is said to identify or learn the target concept
if its sequence of hypotheses stabilises on a correct hypothesis. This is basically the model of
explanatory learning considered by Gold [15]. Over time several other models of learning have?

Supported in part by NUS grant number C-252-000-087-001 and R252-000-420-112.
Supported in part by NUS grant number R146-000-114-112.
???
Supported in part by NUS grant numbers R146-000-114-112 and R252-000-420-112.
??

1

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 forthe case of inductive inference from positive data [1, 15]. Hence, it is worth investigating moreclosely 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
were later 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 automatic family over general indexed families[1, 26, 28] is that the first-order theory of automatic families, as well as of automatic structures ingeneral, is decidable [17, 18, 24]. Here the predicates (relations) and functions (mappings) allowedin the first-order theory are automatic. Furthermore, relations and functions that are firstorder 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 group theory [6, 12, 24, 30, 31, 34, 35]. Common examples of automatic predicates from theprior literature are predicates to compare the length of strings, the lexicographic order (denotedby ≤lex ) and the length-lexicographic order (denoted by ≤ll ). Here x is length-lexicographicallyless 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 to consider some restricted form of learners. One natural restriction,
as considered by [20], on learners is that they are automatic, i.e., their graph is accepted by afinite automaton. For this purpose, the learner is modeled as working in rounds and having along-term memory. In each round learner receives a new datum, and based on this datum andits previous long-term memory, updates its long-term memory and outputs a new hypothesis.
The learner learns the target language if its sequence of hypotheses converges to an index for thetarget language (where the index is interpreted in some hypothesis space, which is an automaticfamily). If we do not restrict the long-term memory or the computational power of the learner inany way, then this model of learning is equivalent to the above mentioned model of explanatory
learning. For automatic learner, we require that the mapping (previous memory, new datum)
7→ (new memory, hypothesis) is an automatic function, that is, its graph is recognised by afinite automaton. Such learners satisfy much more realistic complexity bounds than learners
which have access to the full history of all past data and computations. A further motivation
for studying learners which are automatic is that in some situations it may be more reasonable
to have finite automata as a model rather than Turing machines. Another motivation for thework goes back to the programme of Khoussainov and Nerode [24] to find which results fromcomputable model theory can be transferred to model theory based on finite automata. Somevery nice sub-classes of pattern languages [2] are automatic families and learnable by automaticlearners [9]. However, Jain, Luo and Stephan [20] showed that not every learnable automatic2

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 the length of the current hypothesis plus a
constant (we refer to this as hypothesis-length 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 referto this as datum-length long-term memory). It was shown that some automatic classes can belearnt by an automatic learner using datum-length long-term memory but not by any automaticlearner using hypothesis-length long-term memory. However it was open whether automaticlearners 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 simulatedby an 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 telltale condition. Since [20] several papers [9, 19, 22] have considered learning of automatic classes
by automatic learners. The present work carries on investigations into learnability of automaticfamilies by automatic learners.
The notion of learners with explicit bounds on the long-term memory had already beenstudied previously in the setting of algorithmic learners [14, 25]. Such memory restrictions wereconsidered as too restrictive. This led to enrichment of the learners by allowing feedback queries
and other instruments to access 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 the class of all automatic families satisfying Angluin’s tell-talecondition.
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 themain 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
per round and using datum-length long-term memory. Theorem 17 shows that there is a classwhich 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 thenumber of feedback queries per round. Section 5 deals with automatic learners using a marked
memory space (see Section 2 for definition). Theorem 21 shows 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 automatic3

learner using hypothesis-length long-term memory can be replaced by an iterative automaticlearner [20]. Theorem 23 gives a partial answer: this is possible if the iterative automatic learnerhas 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
Given Criterion
Implied Criterion
Theorem 16 Angluin’s tell-tale criterion one feedback queryplus datum-length memory
Theorem 21 Angluin’s tell-tale criterion hypothesis-length memory
plus type 2 marked memory space
Theorem 23 hypothesis-length memory iterative plus hypothesis queries
Non-Inclusion Satisfied Criterion
Theorem 17 memoryless one feedback query
Theorem 18 1-bounded example memory
Theorem 18 hypothesis-length memory
plus feedback query
Theorem 19 k-bounded example memory
Theorem 20

Theorem 22

2

Diagonalised Criterion
automatic learners
iterative plus feedback

iterative plus feedback(k − 1)-bounded example memory
plus feedback queries
k-bounded example memory /(k − 1)-bounded example memory /memoryless k-feedback queries / memoryless (k − 1)-feedback queries
constantly bounded memory
datum-length memory
hypothesis-length memory
plus type 1 marked memory space

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 isdenoted by |x|. Empty string is denoted by ε. For a string x, x(i) denotes the (i + 1)-th elementin the string x; thus, string x is same as 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 Σ ofthe 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 , and y 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].
4

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 Σ suchthat 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 question of 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 mapping from N to
Σ ∗ ∪ {#}. Traditionally, # is used to denote pauses in the presentation of data and is alsoneeded as the only text for empty language is #∞ ; one could come around the use of # byrequiring that all languages to be learnt are non-empty, but this turned out to be notationallyawkward 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 asequence σ = T [n], denoted content(σ), is {T (i) : i < n} − {#}. Let |σ| denote the length of thesequence σ. For sequences σ and τ , let σ ◦ τ denote the concatenation of σ and τ . Furthermore,let σ ◦ x denote concatenation of σ and the sequence consisting of just the element x. Note thatxx is a string obtained 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} by a 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 repeatof 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 ∪ {?}).
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 anda 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).
5(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 of learners 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, the learner receives the input T (n), updates
its previous long-term memory memn to memn+1 and outputs a hypothesis βn+1 . For generallearners 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 learner does not known, unless it stores it in its long-term memory). The learner learns [15] a language L iff for all
texts T for L, for βn as defined above, the sequence β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 fromtext 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].
Proposition 2 (Based on Angluin [1]). An automatic family {Lα : α ∈ I} is learnable byan algorithmic learner iff, for every α ∈ I, there is a bound bα such that, for all β ∈ I, theimplication{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 tell-tale condition. Note that we can takebα = |α| + 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 are also automatic [20], that is, themapping (memn , T (n)) 7→ (memn+1 , βn+1 ) for the learners is automatic. The hypothesis and the
updated long-term memory of 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 accessthe 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 some past data. In general, the requirement of alearner to be automatic is a real restriction [20] (for examples of a learnable automatic classwhich cannot be learnt 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 by an automatic learner (which uses long6

term memory bounded in length by the length of the longest datum seen so far) iff the family
satisfies Angluin’s tell-tale condition.
Jain, Luo and Stephan [20] had considered various ways in which the long-term memory of theautomatic learners can be bounded in length. The length-restrictions considered are as follows.
For the following, T is an arbitrary input text, memn and βn denotes the long-term memory andhypothesis of the learner just 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 hypothesis-length memory.
(b) the length of the longest datum seen so far plus a constant; that is, for some constant 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 (independent of 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 thelearner is not constrained regarding which alphabet it uses for 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 (orbetter) long-term 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 all sets 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 to acorrect hypothesis would not be possible. The class given in Theorem 20 can also be learnt witha 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 thelongest 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 hypothesislength memory is more adequate; the reason is that these bounds come out naturally from theframework: first, the length of minimal indices is quite invariant over hypotheses spaces used;second, the smallest indices of a finite set in an automatic family corresponds, up to a constantdepending 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 maximum of the long-term memory lengthand 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 be remembered in the long-term7memory by automatic learners. If one considers fat texts [32], where every data item is repeatedinfinitely 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 to learn all automaticfamilies satisfying Angluin’s tell-tale condition. Hence, the present work looks at criteria which
are more powerful than just limited memory structure but less powerful than fat texts. Thesemethods are based on active strategies of the learner, such as making feedback queries about
whether some data item has already been seen in the past. While the mechanisms presented
here are well-studied in the case of algorithmic learners, the combination of such mechanisms
with automatic learners is novel. Also novel is the generalised model of marked memory space,which subsumes feedback learning and related criteria.
For the following definitions, Σ is the alphabet for the languages, Γ is the alphabet usedby the learner for its long-term memory. L = {Lβ : β ∈ I} refers to the language class being
learnt; Lα refers to the target language, and a 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 βn denote 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 a set. For this,conv(x1 , x2 , . . . , xr ) represents the set {x1 , x2 , . . . , xr }. When we consider long-term memory asa set, we assume that it was in sorted order: that is, x1 <ll x2 <ll . . . <ll xr . This allows forautomatic updating and testing of elements in a set. For ease of notation, we will often referdirectly to the sets in these 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 k-bounded example
memory iff, for all n, memn ⊆ content(T [n]), number of elements in memn is at most k, andmemn+1 ⊆ memn ∪ {T (n)} (note that the 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 alearner which uses k feedback queries) is a learner, with an associated automatic query function
Q asking k questions per round, defined as follows. The initial long-term memory of the learneris mem0 and the initial hypothesis of the learner is β0 . Given an input text T , let memn , andβn denote the long-term memory and hypothesis of the learner after having seen T [n] (that isjust 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, (memn , T (n), b1 , b2 , . . . , bk ) 7→ (memn+1 , βn+1 ) is automatic.
8

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 a finite alphabet ∆. This marked
memory will only grow (set inclusion wise) as the learner gets more data. Marked memory canbe considered as a generalisation of feedback learning since feedback learning can be simulated
by Type 1 memory.
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, forsome 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 the learner is β0 andinitial 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 that for 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 with cardinality 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 automatic learner using amarked 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 case of an automaticlearner 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 instead of ∆∗ , 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 give the queries madeby the learner at each input, rather than giving details of Xn and Zn .
Many of these learning notions had been defined earlier without requiring that the learners areautomatic. The general notion of learning which is underlying the notion of an automatic learneris due to Gold [15] and is called explanatory learning. The variant with an explicit long-term
memory as used here was introduced by Freivalds, Kinber and Smith [14]. The special case of iterative learning is quite popular and predates the definition of general memory limitations, it was
9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 thisstudy. Wiehagen [38] and Lange 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 useful to prove some ofour 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 (in the 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 canchoose the hypothesis space H to be equal to L. This may sometimes cause a restriction, forexample, 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 from one automatic family to another for the languages which are common to bothautomatic families. This stands in a contrast to the corresponding results for indexed familiesof recursive languages [27, 28]. A result in the present work which depends on the choice of the
hypothesis space is Theorem 23. In the case that the hypothesis space does not matter, often, forthe ease of notation, the languages 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 memory of automaticlearners.
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 and hypothesis of M after having
seen input σ, then max {|mem|, |hyp|} ≤ c + c ∗ |σ| + max {|w| : w ∈ content(σ)}.

3Some illustrative examples

We now provide some examples to give insight into the learning criteria considered and theirproperties. 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 learner 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 tell-tale condition. The open interval
10Lconv(000,1) is the ascending union of the open intervals Lconv(000,01m ) ; already Gold [15] observedthat classes of this form cannot be learnt from positive data.
Example 14 shows that learnability by automatic learners cannot be characterised from theinclusion structure of a family alone, as the inclusion structure in 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 automaticand 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 query answer remains
negative forever.
In contrast, the family of all sets {0}∗ − {x}, with x ∈ {0}∗ , has an automatic learner using
datum-length long-term memory. This follows from Theorem 3.
Example 15 shows the limitations and possibilities for learners which use a marked memory
space but do not have access to any long-term memory. In case (a) the marked memory spaceconsists 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 itreconstructs part of the hypotheses history using the current datum and hypothesis queries.
Example 15. (a) An automatic learner without any long-term memory, but using 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 long-term memory,cannot learn the class {S ⊆ {0, 1}∗ : S has at most two elements}.
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 learner computes the y with succ(y) = x, ifany. 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 learnerconjectures hypothesis x. If y as above does not exist and queries determine that hypothesis x
was not conjectured previously, then the learner conjectures x. In all other cases (including thecase of the input being of the form 1n for some n), the learner conjectures ? in order to signalthat 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 never conjecturessucc(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 some hypothesis space {Hα : α ∈ J}). Now
11

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 xsuch that, 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 prior literature 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 powerfulas 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 belearnt by an automatic learner using one feedback query per round and 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 automatic family [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 to find an α suchthat(a) the input contains {w : |w| ≤ |α| + c} ∩ Lα , (which is a tell-tale set for Lα ) and(b) every element in the input is contained in Lα .
Intuitively, for each potential conjecture α, the learner checks if the above tell-tale 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 the learner tries the next possible conjecture α. However,potential obstacles for doing this are− the learner may not yet have seen the above tell-tale set for Lα , but these elements appear
later in the input;− the learner may already have seen an element outside Lα , forgotten this fact, and the future
elements to be seen are all in Lα .
12

To address the first problem above, each potential α will be tested more and more times until
the algorithm finds the correct hypothesis. To address the second problem, feedback queries areused to check, for all strings length-lexicographically at most the length-lexicographically largest
datum seen before current conjecture α was tried, if any of them has been seen earlier but notin Lα .
The long-term memory of the learner is of the form conv(z, α, y, b). Here z is the lengthlexicographically largest datum seen so far (z is ε for the case that the input does not containany datum), α is the current conjecture (which will be of length at most |z| + c), b ∈ {0, 1}
is used to remember whether the algorithm is testing clause (a) or (b) above, and y is used toremember which current string (relevant to (a) and (b) above) is being tested (the length ofy will be at most max {|z|, |α|} + c). Note that for (b), the algorithm need only use feedback
for strings 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 aretested 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 length-lexicographicallylargest 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 pred(ε) = ε). 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 predecessorof α, otherwise α0 is the length-lexicographically largest index of length at most |z 0 | + c;
conjecture of the learner is irrelevant in this case. (* Here the learner has not seen theabove tell-tale set for Lα , and thus tries the next possible α. *)Else If y is the length-lexicographically largest string of length at most |α| + c
Then new long-term memory of the learner is (z 0 , α, z 0 , 1), where z 0 is the length-lexicographically largest string seen so far. The conjecture of the learner is Lα . (* Here thelearner 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 new long-term memory of the learner be (z 0 , α, succ(y), 0) and the conjecture of thelearner be Lα , where z 0 is the length-lexicographically largest string seen so far. (* Herethe 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= # and x 6∈ Lα ]: The
new long-term memory of the learner is (z 0 , α0 , ε, 0), where z 0 is the length-lexicographically13largest datum seen so far; if α 6= ε, then α0 is the length-lexicographic predecessor of α,
otherwise α0 is the length-lexicographically largest index of length at most |z 0 | + c; conjectureof the learner is irrelevant in this case. (* Here the learner has seen a datum not belonging
to Lα , and thus tries the next possible α. *)Neither of the two cases above: The new long-term memory of the learner is (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 long-term 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 casethat the learner 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 thelearner 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 the learner has verified that all the elements of theabove tell-tale set for Lα are present 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, the learner 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 withfeedback and limitations on the long-term memory. First, it is shown that there are cases where
feedback queries are more 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 an automatic learner using one feedback query per round but cannot be learnt by an automatic learnerwithout any marked space memory. However, the learner in Example 14 needs hypothesis-length
long-term memory or datum-length long-term 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
learner learns L.
14

(b) Suppose by way of contradiction that M is automatic and learns L. Without loss ofgenerality assume that M always outputs a hypothesis.
Let m be so large that there are two sequences σ1 and σ2 , each containing m elementsof {0, 1}m , such that content(σ1 ) 6= content(σ2 ) and M has the same long-term memory andhypothesis 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 afterm
seeing such σ1 or σ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 a text 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 thesame hypothesis or diverges on both, though these 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 over just 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}∗ . Then the 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 per round, along with ahypothesis-length long-term memory;(c) L cannot be learnt by an automatic iterative learner using feedback queries.
Proof. (a) Intuitively, the learner keeps in long-term memory the longest string seen, while theinput is contained in L0 . Once the learner sees an element x 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 long-term memory A,
updates its memory and outputs a hypothesis based on the following table.
old memory A
input datum z new memory A0 hypothesis—#
A0 = A
?
+
0
A=∅
z∈0
A = {z}L0∗0A=∅z ∈ {0, 1} 1
A = {z}
Lconv(z,0|z| )A = {0n }z ∈ 0+
A0 = {0max {n,|z|} } L0
A = {0n }z ∈ {0, 1}∗ 1
A0 = {z}Lconv(z,0max {n,|z|} )∗0
A = {x} ⊆ {0, 1} 1 |z| > |x|
A =A
Lconv(x,z)∗
0A = {x} ⊆ {0, 1} 1 |z| ≤ |x|
A =A?
It is easy to see that the learner above is automatic. We now show that the learner 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 this hypothesis on receipt of the datum x and from then on abstain fromconjecturing 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 learner15

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 learnerlearns 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 learner learns Lconv(x,y) as well.
(b) The automatic learner using feedback queries and hypothesis-length long-term 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 aneven or an odd number of distinct data items from 0∗ have been seen so far — this parity bit canbe updated if a not previously seen datum from 0∗ is observed in the input (whether a datumis new or old can be determined by making one feedback query). Along with these, the learneralso 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 order to determine
whether the parity of the number of strings from 0∗ already seen in the input coincides with thenumber of the elements in Lconv(x,0|x| ) . If so, then the 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
memory) of the form conv(x, 0r ), and correspondingly querying 0r in the next round, wherer = |x| + 1, |x| + 2, |x| + 3, . . .).
Here, note that, during the above searching process, if a new datum, not previously seen, isobserved by the learner, then the parity of the number of observed 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 sequence for M on L0 , that is, there
exists a σ such that the conjecture of M does not change beyond σ on any text for L0 whichstarts 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 greaterthan 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 for two 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 programp 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 roundcan learn L.
Proof. (a) The automatic learner memorises the first i distinct elements in the input. If thelearner has already memorised i elements and sees a datum not in the long-term memory, then16

it conjectures the corresponding set of i + 1 elements, else it outputs ?. It is easy to verify thatthe above learner learns L.
(b) Suppose by way of contradiction 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 thatthese strings are distinct and in lexicographic ascending order and C(x0 x1 . . . xi ) ≥ (i + 1) · k − cwhere C is the (plain) Kolmogorov complexity [29] and c is a constant depending on i but notkk
on k such 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 k whenever k > i. At each time where
M makes a correct conjecture on a text for {x0 , x1 , . . . , xi }, one can compute x0 x1 . . . xi fromthe 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; the current 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 isa constant which depends on i, j but not on k; this implies (i + 1) · k − c ≤ i · k + j + d andk ≤ j + c + d, a contradiction 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 sizek 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, theoverall 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 can learn 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 regularset. 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 learnermemorises 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 the17

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 inputm
0 , the learner first finds an n such that (k + 1)n ≤ m < (k + 1)(n + 1). Note that this can bedone automatically. The automatic learner then queries the elements in {0` : (k + 1)n ≤ ` <(k + 1)(n + 1), ` 6= m}, and outputs 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 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 segment with content(τ ) = SF .
(d) Suppose by way of contradiction otherwise. Let σ be an initial sequence of #∞ such thatthe 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, foreach number ` < k +1, whether it has seen a string of length (k +1)·n+` for some n. Whenever adatum of the form 0(k+1)n+m is observed, the learner updates the long-term memory accordingly,
determines the number 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 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 leastindex for the correct 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 ofsize 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 generalisation of a learnerusing feedback queries. Hence it follows from Theorem 16 that every automatic class satisfying
Angluin’s tell-tale condition can be learnt by an automatic learner with marked memory spaceof type 1 and datum-length long-term 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.

18

Theorem 21. Every automatic family satisfying Angluin’s tell-tale condition has an automaticlearner using hypothesis-length long-term memory and a marked 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 of generality assume that for all distinct
α, α0 in I, Lα 6= Lα0 .
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 idea of the proof is similar to that ofTheorem 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 consisting of entries ofthe 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) and succ(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 that y is only used totest whether all elements of a tell-tale set are in the input seen so far. Recall from Proposition 2that there is a constant c such that the strings 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 initialvalues of α and y are ε. In the marked memory space, an element of the form (z, 2) is used forremembering the data seen so far; an element of the form (α, 1) is used to denote that Lα does
not contain some input string seen so far (thus the main remaining job of the algorithm is tocheck whether the tell-tale set for Lα is contained in the input seen so far); an element of theform (α, 0) is used to denote that hypotheses length-lexicographically smaller than α have been
considered earlier. This allows us to consider each possible hypothesis arbitrarily often until acorrect hypothesis is found. 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) in the marked memory
space for all β where x ∈/ Lβ .
19

7. Output the hypothesis α.
8. The new long-term memory is the new value of conv(α, y).
End of the round.
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 the old 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 lossof generality, that every language in the class has exactly one index. Suppose that Lγ is thelanguage to be learnt. Further suppose all elements of Lγ which are of length at most |γ| + chave already shown up in the input. If the current index α is not equal to γ, then either during
the inference process some x ∈/ Lα shows up, causing (α, 1) to be placed in the marked 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 tell-tale set property). In the later case, eventually the variable y will takethe 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 to all the values again until
it eventually reaches the value of γ. Then steps 2 and 3 will not apply. Furthermore, as all themembers of Lγ of length at most |γ| + c have 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γ islearnt 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 the long-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 of type 2 in the above
result. The next result shows that in some cases this is indeed 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 thiswith 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 automatic learnability using
datum-length long-term memory from automatic learnability using hypothesis-length long-term
memory. The diagonalisation method used here 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}∗ .
20

Then, L has an automatic learner using datum-length long-term memory. However, an automatic learner using hypothesis-length long-term memory plus 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 canshow that, when learning the language {0}+ , there is a sequence σ and a constant c such thatthe 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 (plusa constant), which does not change beyond σ). Furthermore, there is a constant c0 such that,when reading an input 0n , the learner queries or places in the marked memory only strings oflength 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 learner has seen σ. Note that, on input σ ◦ 0n1 ◦ 0n2 ◦ . . .,there is a long-term memory value which is repeated infinitely often in the above run of thelearner (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 enoughsuch that long-term memory of the learner after seeing σ ◦ 0n1 ◦ 0n2 ◦ . . . ◦ 0nk is mem, and any
string of length at most c0 which is ever in 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, thelearner converges on this input text to some conjecture (say β) and does not query or places inmarked memory space any string of length 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 the learner is
mem after having seen σ ◦ 0n1 ◦ 0n2 ◦ . . . ◦ 0nk ◦ 0nk+1 ◦ . . . ◦ 0nr−1 and also after having seenσ ◦ 0n1 ◦ 0n2 ◦ . . . ◦ 0nk ◦ 0nk+1 ◦ . . . ◦ 0nr−1 ◦ 0nr ◦ . . . ◦ 0nr0 . Note that there exist such r and r0 , as thelearner has long-term memory mem infinitely often on the input σ ◦ 0n1 ◦ 0n2 ◦ . . .; thus, the longterm memory of the learner 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 ◦ 0nr+1 ◦ . . . ◦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
21

It is open whether an automatic learner using hypothesis-length long-term memory can be madeiterative [20]. Theorem 23 deals with the counterpart of this problem 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 memoryand 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 automatic learner M is learning L = {Li : i ∈ I} using a 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 andhypothesis 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 is the initial long-term memory of M andinithyp 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 withconv(inithyp, initmem). Then the update function of N is the following one:N (conv(i, g), x) =F (conv(i, g), x), conv(i, g),

if F (conv(i, g), x) had not been
conjectured previously;
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 some language in L. Then there are sequences τ0 , τ1 , . . . (with τncontaining elements from {x0 , x1 , . . . , xn }) such that F after processing x0 ◦τ0 ◦x1 ◦τ1 ◦. . .◦xn ◦τnhas 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 canchoose τn to be empty sequence. If N (conv(in−1 , gn−1 ), xn ) is defined via the second clause inits definition, then suppose 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 ) is then the initial22

hypothesis of N ). One then chooses τn to be xm+1 ◦ τm+1 ◦ xm+2 ◦ τm+2 ◦ . . . ◦ xn−1 ◦ τn−1 . It iseasy 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 old abandoned hypotheses, the sequence of conv(in , gn ) also
converges to a pair conv(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 like to thank theanonymous referees of the conference and this journal for several useful comments.

References
1. Dana Angluin. Inductive inference of formal languages from positive data. Information andControl, 45:117–135, 1980.
2. Dana Angluin. Finding patterns common to a set of strings. Journal of Computer 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 andComputation, 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 Annual IEEE Symposiumon 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 learningfor bounded data mining. Information and Computation, 152:74–110, 1999.
9. John Case, Sanjay Jain, Trong Dao Le, Yuh Shin Ong, Pavel Semukhin and Frank Stephan.
Automatic Learning of Subclasses of Pattern Languages. Accepted for Information and Computation. Preliminary version appeared in Language and Automata Theory and Applications,
5th International Conference, LATA 2011, Proceedings. Springer LNCS 6638:192–203, 2011.
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.
23

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 ofMontré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 automaticclasses 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 automatic classes. To appear
in Journal of Computer and System Sciences. Preliminary version appeared in Language andAutomata Theory and Applications, 4th International Conference, LATA 2010, Proceedings.
Springer LNCS 6031:321-332, 2010.
21. Sanjay Jain, Yuh Shin Ong, Shi Pu and Frank Stephan. On automatic families. Proceedingsof the 11th Asian Logic Conference, ALC 2009, in Honor of Professor Chong Chitat’s 60thbirthday, pages 94–113. World Scientific, 2011.
22. Sanjay Jain, Eric Martin and Frank Stephan. Robust learning of automatic classes 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. Logicaland Computational Complexity. Springer LNCS 960:367–392, 1995.
25. Efim Kinber and Frank Stephan. Language learning from texts: mind changes, 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 ofComputer and System Sciences, 53:88–103, 1996.
28. Steffen Lange, Thomas Zeugmann and Sandra Zilles. Learning indexed families of recursive
languages from positive data: a survey. Theoretical Computer 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.
24

31. André Nies and Pavel Semukhin. Finite automata presentable Abelian groups. Annals ofPure 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 andInductive 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 string case. The Bulletinof Symbolic Logic, 14:169–209, 2008.
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.

25