Streaming Property Testing of Visibly Pushdown Languages∗
Nathanaël François†1 , Frédéric Magniez‡2 , Michel de Rougemont§3 , and Olivier Serre¶2
1

arXiv:1505.03334v4 [] 3 Nov 2015

2

Fakultät für Informatik, TU Dortmund, Germany
CNRS, LIAFA, Univ Paris Diderot, Sorbonne Paris-Cité, France
3
University of Paris II and LIAFA, CNRS, France

Abstract
In the context of language recognition, we demonstrate the superiority of streaming property testers
against streaming algorithms and property testers, when they are not combined. Initiated by Feigenbaum
et al., a streaming property tester is a streaming algorithm recognizing a language under the property
testing approximation: it must distinguish inputs of the language from those that are ε-far from it, while
using the smallest possible memory (rather than limiting its number of input queries).
Our main result is a streaming ε-property tester for visibly pushdown languages (V PL) with one-sided
error using memory space poly((log n)/ε).
This constructions relies on a (non-streaming) property tester for weighted regular languages based
on a previous tester by Alon et al. We provide a simple application of this tester for streaming testing
special cases of instances of V PL that are already hard for both streaming algorithms and property testers.
Our main algorithm is a combination of an original simulation of visibly pushdown automata using
a stack with small height but possible items of linear size. In a second step, those items are replaced by
small sketches. Those sketches relies on a notion of suffix-sampling we introduce. This sampling is the
key idea connecting our streaming tester algorithm to property testers.

∗

Partially supported by the French ANR projects ANR-12-BS02-005 (RDAM) and ANR-14-CE25-0017 (AGREG)
nathanael.francois@tu-dortmund.de
‡
frederic.magniez@cnrs.fr
§
mdr@liafa.univ-paris-diderot.fr
¶
Olivier.Serre@cnrs.fr
†

1

1 Introduction
Visibly pushdown languages (V PL) play an important role in formal languages with crucial applications
for databases and program analysis. In the context of structured documents, they are closely related with
regular languages of unranked trees as captured by hedge automata. A well-known result [3] states that,
when the tree is given by its depth-first traversal, such automata correspond to visibly pushdown automata
(V PA) (see e.g. [19] for an overview on automata and logic for unranked trees). In databases, this word
encoding of trees is known as XML encoding, where DTD specifications are examples of often considered
subclasses of V PL. In program analysis, V PA also capture natural properties of execution traces of recursive
finite-state programs, including non-regular ones such as those with pre and post conditions as expressed in
the temporal logic of calls and returns (CaRet) [5, 4].
Historically, V PL got several names such as input-driven languages or, more recently, languages of
nested words. Intuitively, a V PA is a pushdown automaton whose actions on stack (push, pop or nothing)
are solely decided by the currently read symbol. As a consequence, symbols can be partitioned into three
groups: push, pop and neutral symbols. The complexity of V PL recognition has been addressed in various
computational models. The first results go back to the design of logarithmic space algorithms [11] as well
as NC1 -circuits [13]. Later on, other models motivated by the context of massive data were considered, such
as streaming algorithms and property testers (described below).
Streaming algorithms (see e.g. [23]) have only a sequential access to their input, on which they can
perform a single pass, or sometimes a small number of additional passes. The size of their internal (random
access) memory is the crucial complexity parameter, which should be sublinear in the input size, and even
polylogarithmic if possible. The area of streaming algorithms has experienced tremendous growth in many
applications since the late 1990s. The analysis of Internet traffic [2], in which traffic logs are queried, was
one of their first applications. Nowadays, they have found applications with big data, notably to test graphs
properties, and more recently in language recognition on very large inputs. The streaming complexity of
language recognition has been firstly considered for languages that arise in the context of memory checking [8, 12], of databases [29, 28], and later on for formal languages [21, 7]. However, even for simple V PL,
any randomized streaming algorithm with p passes requires memory Ω(n/p), where n is the input size [18].
As opposed to streaming algorithms, (standard) property testers [9, 10, 16] have random access to their
input but in the query model. They must query each piece of the input they need to access. They should
sample only a sublinear fraction of their input, and ideally make a constant number of queries. In order
to make the task of verification possible, decision problems need to be approximated as follows. Given a
distance on words, an ε-tester for a language L distinguishes with high probability the words in L from those
ε-far from L, using as few queries as possible. Property testing of regular languages was first considered for
the Hamming distance [1]. When the distance allows sufficient modifications of the input, such as moves of
arbitrarily large factors, it has been shown that any context-free language becomes testable with a constant
number of queries [20, 15]. However, for more realistic distances, property testers for simple languages
require a large number of queries, especially if they have one-sided error only. For example the complexity
of an ε-tester for well-parenthesized expressions with two types of parentheses is between Ω(n1/11 ) and
O(n2/3 ) [26], and it becomes linear, even for one type of parentheses, if we require one-sided error [1]. The
difficulty of testing regular tree languages was also addressed when the tester can directly query the tree
structure [24, 25].
Faced by the intrinsic hardness of V PL in both streaming and property testing, we study the complexity of streaming property testers of formal languages, a model of algorithms combining both approaches.
Such testers were historically introduced for testing specific problems (groupedness) [14] relevant for network data. They were later studied in the context of testing the insert/extract-sequence of a priority-queue
structure [12]. We extend these studies to classes of problems. A streaming property tester is a streaming
algorithm recognizing a language under the property testing approximation: it must distinguish inputs of

2

the language from those that are ε-far from it, while using the smallest possible memory (rather than limiting its number of input queries). Such an algorithm can simulate any standard non-adaptive property tester.
Moreover, we will see that, using its full scan of the input, it can construct better sketches than in the query
model.
In this paper, we consider a natural notion of distance for V PL, the balanced-edit distance, which refines
the edit distance on balanced words (where for each push symbol there is a matching pop symbol at the
same height of the stack, and conversly). It can be interpreted as the edit distance on trees when trees are
encoded as balanced words. Neutral symbols can be deleted/inserted, but any push symbol can only be
deleted/inserted together with its matching pop symbol. Since our distance is larger than the standard edit
distance, our testers are also valid for that distance.
In Section 3, we first design an exact algorithm that maintains a small stack but whose items can be of
linear size as opposed to the standard simulation of a pushdown automaton which usually has a stack of
possible linear size but with constant size items. In our algorithm, stack items are prefixes of some peaks
(which we call unfinished peaks), where a peak is a balanced factor whose push symbols appear all before
the first pop symbol. Our algorithm compresses an unfinished peak u = u+ v− when it is followed by a long
enough sequence. More precisely, the compression applies to the peak v+ v− obtained by disregarding part
of the prefix of push sequence u+ . Those peaks are then inductively replaced, and therefore compressed, by
the state-transition relation they define on the given automaton. The relation is then considered as a single
symbol whose weight is the size of the peak it represents. In addition, to maintain a stack of logarithmic
depth, one of the crucial properties of our algorithm (Proposition 3.3) is rewriting the input word as a peak
formed by potentially a linear number of intermediate peaks, but with only a logarithmic number of nested
peaks.
In Section 4, for the case of a single peak, we show how to sketch the current unfinished peak of
our algorithm. The simplicity of those instances will let us highlight our first idea. Moreover, they are
already expressive enough in order to demonstrate the superiority of streaming testers against streaming
algorithms and property testers, when they are not combined. We first reduce the problem of streaming
testing such instances to the problem of testing regular languages in the standard model of property testing
(Theorem 4.9). Since our reduction induces weights on the letters of the new input word, we need a tester
for weighted regular languages (Theorem A.2). Such a property tester has previously been devised in [25]
extending constructions for unweighted regular languages [1, 24]. However, we consider a slightly simpler
construction that could be of independent interest. As a consequence we get a streaming property tester with
polylogarithmic memory for recognizing peak instances of any given V PL (Theorem 4.10), a task already
hard for streaming algorithms and property testers (Fact 4.1).
In Section 5, we construct our main tester for a V PL L given by some V PA. For this we introduce a
more involved notion of sketches made of a polylogarithmic number of samples. They are based on a new
notion of suffix sampling (Definition 5.1). This sampling consists in a decomposition of the string into
an increasing sequence of suffixes, whose weights increase geometrically. Such a decomposition can be
computed online on a data stream, and one can maintain samples in each suffix of the decomposition using
a standard reservoir sampling. This suffix decomposition will allow us to simulate an appropriate sampling
on the peaks we compress, even if we do not yet know where they start. Our sampling can be used to
perform an approximate computation of the compressed relation by our new property tester of weighted
regular languages which we also used for single peaks. We first establish a result of stability which basically
states that we can assume that our algorithm knows in advance where the peak it will compress starts
(Lemma 5.6). Then we prove the robustness of our algorithm: words that are ε-far from L are rejected
with high probability (Lemma 5.8). As a consequence, we get a one-pass streaming ε-tester for L with
2
one-sided error η and memory space O(m5 23m (log n)6 (log 1/η)/ε4 ), where m is the number of states of
a V PA recognizing L (Theorem 5.4).

3

Algorithm 1: Reservoir Sampling
1
2
3
4
5
6
7
8
9
10
11
12

Input: Data stream u, Integer parameter t > 1
Data structure:
σ ← 0 // Current weight of the processed stream
S ← empty multiset // Multiset of sampled letters
Code:
i ← 1, a ← Next(u), σ ← |a|
S ← t copies of a
While u not finished
i + +, a ← Next(u), σ ← σ + |a|
For each b ∈ S
Replace b by a with probability |a|/σ
Output S

2 Definitions and Preliminaries
Let N∗ be the set of positive integers, and for any integer n ∈ N∗ , let [n] = {1, 2, . . . , n}. A t-subset of a
set S is any subset of S of size t. For a finite alphabet Σ we denote the set of finite words over Σ by Σ∗ .
For a word u = u(1)u(2) · · · u(n), we call n the length of u, and u(i) the ith letter in u. We write u[i, j] for
the factor u(i)u(i + 1) · · · u(j) of u. When we mention letters and factors of u we implicitly also mention
their positions in u. We say that v is a sub-factor of v ′ , denoted v ≤ v ′ , if v = u[i, j] and v ′ = u[i′ , j ′ ] with
[i, j] ⊆ [i′ , j ′ ]. Similarly we say that v = v ′ if [i, j] = [i′ , j ′ ]. If i ≤ i′ ≤ j ≤ j ′ we say that the overlap of v
and v ′ is u[i′ , j]. If v is a sub-factor of v ′ then the overlap of v and v ′ is v. Given two multisets of factors S
and S ′ , we say that S ≤ S ′ if for each factor v ∈ S there is a corresponding factor v ′ ∈ S ′ such that v ≤ v ′ .
Weighted Words and Sampling. A weight function on a word u with n letters is a function λ : [n] → N∗
on the letters of u, whose value λ(i) is called the weight of u(i). A weighted word over Σ is a pair (u, λ)
where u ∈ Σ∗ and λ is a weight function on u. We define |u(i)| = λ(i) and |u[i, j]| = λ(i) + λ(i + 1) +
. . . + λ(j). The length of (u, λ) is the length of u. For simplicity, we will denote by u the weighted word
(u, λ). Weighted letters will be used to substitute factors of same weights. Therefore, restrictions may exist
on available weights for a given letter.
Our algorithms will be based on a sampling of small factors according to their weights. We introduce
a very specific notion adapted to our setting. For a weighted word u, we denote by k-factor sampling on u
the sampling over factors u[i, i + l] with probability |u(i)|/|u|, where l ≥ 0 is the smallest integer such that
|u[i, i + l]| ≥ k if it exists, otherwise l is such that i + l is the last letter of u. More generally, we call k-factor
such a factor. For the special case of k = 1, we call this sampling a letter sampling on u. Observe that both
of them can be implemented using a standard reservoir sampling (see Algorithm 1 for letter sampling).
Even if our algorithm will require several samples from a k-factor sampling, we will often only be
able to simulate this sampling by sampling either larger factors, more factors, or both. Let W1 be a
sampler producing a random multiset S1 of factors of some given weighted word u. Then W2 oversamples W1 if it produces a random multiset S2 of factors of u such that for each factor v, we have
Pr(∃v ′ ∈ S2 such that v is a factor of v ′ ) ≥ Pr(∃v ′ ∈ S1 such that v is a factor of v ′ ).
Finite State Automata and Visibly Pushdown Automata. A finite state automaton is a tuple of the form
A = (Q, Σ, Qin , Qf , ∆) where Q is a finite set of control states, Σ is a finite input alphabet, Qin ⊆ Q is a
subset of initial states, Qf ⊆ Q is a subset of final states and ∆ ⊆ Q × Σ × Q is a transition relation. We
u
write p−→q, to mean that there is a sequence of transitions in A from p to q while processing u, and we call
u
(p, q) a u-transitions. A word u is accepted if qin −→qf for some qin ∈ Qin and qf ∈ Qf . The language
L(A) of A is the set of words accepted by A, and we refer to such a language as a regular language. For

4

Σ′ ⊆ Σ, the Σ′ -diameter (or simply diameter when Σ′ = Σ) of A is the maximum over all possible pairs
u
(p, q) ∈ Q2 of min{|u| : p−→q and u ∈ Σ′∗ }, whenever this minimum is not over an empty set. We say
u′

u

that A is Σ′ -closed, when p−→q for some u ∈ Σ∗ if and only if p−→q for some u′ ∈ Σ′∗ .
A pushdown alphabet is a triple hΣ+ , Σ- , Σ= i that comprises three disjoint finite alphabets: Σ+ is a
finite set of push symbols, Σ- is a finite set of pop symbols, and Σ= is a finite set of neutral symbols. For any
such triple, let Σ = Σ+ ∪ Σ- ∪ Σ= . Intuitively, a visibly pushdown automaton [27] over hΣ+ , Σ- , Σ= i is a
pushdown automaton restricted so that it pushes onto the stack only on reading a push, it pops the stack only
on reading a pop, and it does not modify the stack on reading a neutral symbol. Up to coding, this notion is
similar to the one of input driven pushdown automata [22] and of nested word automata [6].
Definition 2.1 (Visibly pushdown automaton [27]). A visibly pushdown automaton (V PA) over hΣ+ , Σ- , Σ= i
is a tuple A = (Q, Σ, Γ, Qin , Qf , ∆) where Q is a finite set of states, Qin ⊆ Q is a set of initial states,
Qf ⊆ Q is a set of final states, Γ is a finite stack alphabet, and ∆ ⊆ (Q × Σ+ × Q × Γ) ∪ (Q × Σ- × Γ ×
Q) ∪ (Q × Σ= × Q) is the transition relation.
To represent stacks we use a special bottom-of-stack symbol ⊥ that is not in Γ. A configuration of a
V PA A is a pair (σ, q), where q ∈ Q and σ ∈ ⊥ · Γ∗ . For a ∈ Σ, there is an a-transition from a configuration
a
(σ, q) to (σ ′ , q ′ ), denoted (σ, q)−→(σ ′ , q ′ ), in the following cases:
a
• If a is a push symbol, then σ ′ = σγ for some (q, a, q ′ , γ) ∈ ∆, and we write q −→(q ′ , push(γ)).
a
• If a is a pop symbol, then σ = σ ′ γ for some (q, a, γ, q ′ ) ∈ ∆, and we write (q, pop(γ))−→q ′ .
a
• If a is a neutral symbol, then σ = σ ′ and (q, a, q ′ ) ∈ ∆, and we write q −→q ′ .
a
i
For a finite word u = a1 · · · an ∈ Σ∗ , if (σi−1 , qi−1 )−→(σ
i , qi ) for every 1 ≤ i ≤ n, we also
u
write (σ0 , q0 )−→(σn , qn ). The word u is accepted by a V PA if there is (p, q) ∈ Qin × Qf such that
u
(⊥, p)−→(⊥, q). The language L(A) of A is the set of words accepted by A, and we refer to such a
language as a visibly pushdown language (V PL).
At each step, the height of the stack is pre-determined by the prefix of u read so far. The height height(u)
of u ∈ Σ∗ is the difference between the number of its push symbols and of its pop symbols. A word u is
balanced if height(u) = 0 and height(u[1, i]) ≥ 0 for all i. We also say that a push symbol u(i) matches a
pop symbol u(j) if height(u[i, j]) = 0 and height(u[i, k]) > 0 for all i < k < j. By extension, the height
of u(i) is height(u[1, i − 1]) when u(i) is a push symbol, and height(u[1, i]) otherwise.
u
For all balanced words u, the property (σ, p)−→(σ, q) does not depend on σ, therefore we simply write
u
p−→q, and say that (p, q) is a u-transition. We also define similarly to finite automata the Σ′ -diameter of A
(or simply diameter) and the notion A being Σ′ -closed on balanced words only.
Our model is inherently restricted to input words having no prefix of negative stack height, and we
defined acceptance with an empty stack. This implies that only balanced words can be accepted. From now
on, we will always assume that the input is balanced as verifying this in a streaming context is easy.
Balanced/Standard Edit Distance. The usual distance between words in property testing is the Hamming
distance. In this work, we consider an easier distance to manipulate in property testing but still relevant for
most applications, which is the edit distance, that we adapt to weighted words.
Given a word u, we define two possible edit operations: the deletion of a letter in position i with
corresponding cost |u(i)|, and its converse operation, the insertion where we also select a weight, compatible
with the restrictions on λ, for the new u(i). Then the (standard) edit distance dist(u, v) between two
weighted words u and v is simply defined as the minimum total cost of a sequence of edit operations
changing u to v. Note that all letters that have not been inserted nor deleted must keep the same weight. For
a restricted set of letters Σ′ , we also define distΣ′ (u, v) where the insertions are restricted to letters in Σ′ .
We will also consider a restricted version of this distance for balanced words, motivated by our study
of V PL. Similarly, balanced-edit operations can be deletions or insertions of letters, but each deletion of
a push symbol (resp. pop symbol) requires the deletion of the matching pop symbol (resp. push symbol).
5

Similarly for insertions: if a push (resp. pop) symbol is inserted, then a matching pop (resp. push) symbol
must also be inserted simultaneously. The cost of these operations is the weight of the affected letters, as
with the edit operations. We define the balanced-edit distance bdist(u, v) between two balanced words as
the total cost of a sequence of balanced-edit operations changing u to v. Similarly to distΣ′ (u, v) we define
bdistΣ′ (u, v).
When dealing with a visibly pushdown language, we will always use the balanced-edit distance, whereas
we will use the standard-edit distance for regular languages. We also say that u is (ε, Σ′ )-far from v if
distΣ′ (u, v) > ε|u|, or bdistΣ′ (u, v) > ε|u|, depending on the context; otherwise we say that u is (ε, Σ′ )close to v. We omit Σ′ when Σ′ = Σ.
Streaming Property Testers. An ε-tester for a language L accepts all inputs which belong to L with
probability 1 and rejects with high probability all inputs which are ε-far from L, i.e. that are ε-far from any
element of L. In particular, a tester for some given distance is also a tester for any other smaller distance.
Two-sided error testers have also been studied but in this paper we stay with the notion of one-sided testers,
that we adapt in the context of streaming algorithm as in [14].
Definition 2.2 (Streaming property tester). Let ε > 0 and let L be a language. A streaming ε-tester for L
with one-sided error η and memory s(n) is a randomized algorithm A such that, for any input u of length n
given as a data stream:
• If u ∈ L, then A accepts with probability 1;
• If u is ε-far from L, then A rejects with probability at least 1 − η;
• A processes u within a single sequential pass while maintaining a memory space of O(s(n)) bits.

3 Exact Algorithm
Fix a V PA A recognizing some V PL L on Σ = Σ+ ∪ Σ- ∪ Σ= . In this section, we design an exact streaming
algorithm that decides whether an input belongs to L. Algorithm 2 maintains a stack of small height but
whose items can be of linear size. In Section 5, we replace stack items by appropriated small sketches

3.1 Notations and Algorithm Description
Call a peak a sequence of push symbols followed by a S
sequence of pop symbols, with possibly intermediate
neutral symbols, i.e. an element of the language Λ = j≥0 ((Σ= )∗ · Σ+ )j · (Σ= )∗ · (Σ- · (Σ= )∗ )j . One can
v

compress any pick v ∈ Λ by the set Rv = {(p, q) : p−→q} of the v-transitions, and consider Rv as a new
neutral symbol with weight |v|. In fact, for the purpose of the analysis of our algorithm, we augment neutral
symbols by many more relations for which A remains Σ-closed. For the rest of the paper, they will be the
only symbols with weight potentially larger than 1.
Definition 3.1. Let ΣQ be Σ= augmented by all weighted letters encoding a relation R ⊆ Q × Q such that
u
for every (p, q) ∈ R there is a balanced word u ∈ Σ∗ with p−→q. Let ΛQ be Λ where Σ= is replaced by
ΣQ .
R

We then write p−→q whenever (p, q) ∈ R, and extend A and L accordingly. Of course, our notion of
distance will be solely based on the initial alphabet Σ.
A general balanced input instance u will consist of many nested peaks. However, we will recursively
replace each factor v ∈ ΛQ by Rv with weight |v|.
Denote by Prefix(ΛQ ) the language of prefixes of words in ΛQ . While processing the prefix u[1, i] of
the data stream u, Algorithm 2 maintains a suffix u0 ∈ Prefix(ΛQ ) of u[1, i], that is an unfinished peak,
with some simplifications of factors v in ΛQ by their corresponding relation Rv . Therefore u0 consists of a
sequence of push symbols and neutral symbols possibly followed by a sequence of pop symbols and neutral

6

Algorithm 2: Exact Tester for a VPL
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

Input: Balanced data stream u
Data structure:
Stack ← empty stack // Stack of items v with v ∈ Prefix(ΛQ )
u0 ← ∅ // u0 ∈ Prefix(ΛQ ) is a suffix of the processed part u[1, i] of u
// with possibly some factors v ∈ ΛQ replaced by Rv
Rtemp ← {(p, p)}p∈Q // Set of transitions for the maximal prefix of u[1, i] in ΛQ
Code:
While u not finished
a ← Next(u) //Read and process a new symbol a
If a ∈ Σ+ and u0 has a letter in Σ- // u0 · a 6∈ Prefix(ΛQ )
Push u0 on Stack, u0 ← a
Else u0 ← u0 · a
If u0 is balanced // u0 ∈ ΛQ : compression
Compute Ru0 the set of u0 -transitions
If Stack = ∅, then Rtemp ← Rtemp ◦ Ru0 , u0 ← ∅
// where ◦ denotes the composition of relations
Else Pop v from Stack, u0 ← v · Ru0
Let (v1 · v2 ) ← top(Stack) s.t. v2 is maximal and balanced // v2 ∈ ΛQ
If |u0 | ≥ |v2 |/2 // u0 is big enough and v2 can be replaced by Rv2
Compute Rv2 the set of v2 -transitions, Pop v from Stack, u0 ← (v1 · Rv2 ) · u0
If (Qin × Qf ) ∩ Rtemp 6= ∅, Accept; Else Reject // Rtemp = Ru

symbols. The algorithm also maintains a subset Rtemp ⊆ Q × Q that is the set of transitions for the maximal
prefix of u[1, i] in ΛQ . When the stream is over, the set Rtemp is used to decide whether u ∈ L or not.
When a push symbol a comes after a pop sequence, u0 ·a is no longer in Prefix(ΛQ ) hence, Algorithm 2
puts u0 on the stack of unfinished peaks (see lines 10 to 11 and Figure 1a) and u0 is reset to a. In other
situations, it adds a to u0 . In case u0 becomes a word in ΛQ (see lines 13 to 17 and Figure 1b), Algorithm 2
computes the set of u0 -transitions Ru0 ∈ ΣQ , and adds Ru0 to the previous unfinished peak that is retrieved
on top of the stack and becomes the current unfinished peak; in the special case where the stack is empty
one simply updates the set Rtemp by taking its composition with Ru0 .

3.2 Algorithm Analysis
We now introduce the quantity Depth(v) for each factor v constructed in Algorithm 2. It quantifies the
number of processed nested picks in v as follows:
Definition 3.2. For each factor constructed in Algorithm 2, Depth is defined dynamically by Depth(a) = 0
when a ∈ Σ, Depth(v) = maxi Depth(v(i)) and Depth(Rv ) = Depth(v) + 1.
In order to bound the size of the stack, Algorithm 2 considers the maximal balanced suffix v2 of the
topmost element v1 · v2 of the stack and, whenever |u0 | ≥ |v2 |/2, it computes the relation Rv2 and continues
with a bigger current peak starting with v1 (see lines 18 to 20 and Figure 1c). A consequence of this
compression is that the elements in the stack have geometrically decreasing weight and therefore the height
of the stack used by Algorithm 2 is logarithmic in the length of the input stream. This can be proved by a
direct inspection of Algorithm 2.
Proposition 3.3. Algorithm 2 accepts exactly when u ∈ L, while maintaining a stack of at most log |u|
items.
We state that Algorithm 2, when processing an input u of length n, considers at most O(log n) nested
picks, that is Depth(v) = O(log n) for all factors constructed in Algorithm 2.
7

→

Rest of Stack

Top of Stack

u0

a

Top of u0
Stack

Rest of Stack

(a) Illustration of lines 10 to 11 from Algorithm 2

→

Rformer u0
Rest of Stack

u0

Top of Stack

new u0

Stack

(b) Illustration of lines 13 to 17 from Algorithm 2

→

v1
Rest of Stack

v1

v2

Top of Stack

u0

Stack

(c) Illustration of lines 18 to 20 from Algorithm 2

Figure 1: Illustration of Algorithm 2

8

Rv2
former u0
new u0

Lemma 3.4. Let v be the factor used to compute Rv at line either 14 or 20 of Algorithm 2. Then
|v(i)| ≤ 2|v|/3, for all i. Moreover, for any factor w constructed by Algorithm 2 it holds that Depth(w) =
O(log |w|).
Proof. One only has to consider letters in ΣQ . Hence, let Rw belongs to v for some w: either w was
simplified into Rw at line 14 or at line 20 of Algorithm 2.
Let us first assume that it was done at line 20. Therefore, there is some v ′ ∈ Prefix(ΛQ ) to the right
of w with total weight greater than |w|/2 = |Rw |/2. This factor v ′ is entirely contained within v: indeed,
when Rw is computed v includes v ′ . Therefore |Rw | ≤ 2|v|/3.
If Rw comes from line 14, then w = u0 and this u0 is balanced and compressed. We claim that at the
previous round the test in line 19 failed, that is |u0 | − 1 ≤ |v2 |/2 where v2 is the maximal balanced suffix
of top(Stack). Indeed, when performing the sequence of actions following a positive test in line 19, the
number of unmatched push symbols in the new u0 is augmented at least by 1 from the previous u0 : hence, it
cannot be equal to 1 as the elements in the stack have pending call symbols and therefore in the next round
u0 cannot be balanced. Therefore one has |u0 | − 1 ≤ |v2 |/2. Now when Rw = Ru0 is created, it is contains
in a factor that also contains v2 and at least one pending call before v2 . Hence, |Rw | ≤ 2|v|/3.
Finally, the fact that for any factor w constructed by Algorithm 2, Depth(w) = O(log |w|) derives from
the fact that if Depth(w) = k, then |w| ≥ (3/2)k . This can in turn be shown by induction on the depth.
Obviously any factor will have weight at least 1. Let us assume all factors of depth k have weight at least
(3/2)k , and let w(i) be a letter such that Depth(w(i)) = k + 1. By definition, w(i) = Rv for some factor v
with Depth(v) = k. This means v contains at least one letter v(j) of depth k. By our induction hypothesis,
|v(j)| ≥ (3/2)k , and therefore |w(i)| = |v| ≥ (3/2)|v(j)| ≥ (3/2)k+1 .

4 The Special Case Of Peaks
We now consider restricted instances consisting of a single peak. For these instances, Algorithm 2 never
uses its stack but u0 can be of linear size. We show how to replace u0 by a small random sketch in order
to get a streaming property tester using polylogarithmic memory. In Section 5, this notion of sketch will be
later extended to obtain our final streaming property tester for general instances.

4.1 Hard Peak Instances
Peaks are already hard for both streaming algorithms and property testing algorithms. Indeed, consider the
language Disj ⊆ Λ over alphabet Σ = {0, 1, 0, 1, a} and defined as the union of all languages a∗ · x(1) · a∗ ·
. . . · x(j) · a∗ · y(j) · a∗ · . . . · y(1) · a∗ , where j ≥ 1, x, y ∈ {0, 1}j , and x(i)y(i) 6= 1 for all i.
Then Disj can be recognized by a V PA with 3 states, Σ+ = {0, 1}, Σ- = {0, 1} and Σ= = {a}. However, the following fact states its hardness for both models. The hardness for non-approximation streaming
algorithms comes for a standard reduction to Set-Disjointness. The hardness for property testing algorithms
is a corollary of a similar result due to [26] for parenthesis languages with two types of parentheses.
Fact 4.1. Any randomized p-pass streaming algorithm for Disj requires memory space Ω(n/p), where n
is the input length. Moreover, any (non-streaming) (2−6 )-tester for Disj requires to query Ω(n1/11 / log n)
letters of the input word.
Proof. The Set-Disjointness problem is defined as follows. Two players have respectively a A and B of
{1, . . . , n} and they must output whether A ∩ B = ∅. The communication complexity of this problem is
well known to be Ω(n). Therefore using the standard reduction of streaming algorithms to communication
protocols, any randomised p-pass algorithm for Disj will require memory space Ω(n/p).
To prove the hardness of testing Disj in the query model, we use a result from [26] (Theorem 2) which
states that any Hamming distance query model property tester for PAR2 ∩ Λ the language on the alphabet
{(, [, ], ), ∗} consisting of well-parenthesized words that are also in Λ requires Ω(n1/11 ) queries.
9

)
γ)
h(
us

p
•

(p′ , q ′ ) •

q
•

(p, q) •

•
qin •
u = v1

•

• qf
a1 · · · vi ai vi+1 · · · ahvh+1bh · · · wi+1bi wi · · · b1 w1

(qin , qf ) •

· · · (ah , bh )

,p

q′
•

•

op

•
(q ′
,p

′

(p

•
p′

(ai , bi )

i

a→
p−

(γ
)) b
−→i
q

(r, r) •

u
b = (v1 (1), I) · · ·

r
•

Run in the slicing automaton Ab on u
b

Run in the V PA A on u

Figure 2: Slicing of a word u ∈ Λ and evolution of the stack height for u.

We first note that because of the way PAR2 ∩Λ is constructed, the Hamming distance and the edit distance
of any word in Λ to PAR2 ∩ Λ are within a constant factor of one another. Indeed, if a sequence of insertions
brings some word u inside PAR2 ∩ Λ, then the deletions of the parentheses matching the insertions would do
the same. And all deletions can similarly be replaced by a substitution of the character being deleted with ∗.
It is also easy to reduce that language to Disj: we replace ( by 01, ) by 01, [ by 10, and ] by 10.
Surprisingly, for every ε > 0, we will show that languages of the form L ∩ Λ, where L is a V PL, become
easy to ε-test by streaming algorithms. This is mainly because, given their full access to the input, streaming
algorithms can perform an input sampling which makes the property testing task easy, using only a single
pass and few memory.

4.2 Slicing Automaton
Observe that Algorithm 2 will never use the stack in the case of a single peak. After Algorithm 2 has
processed the i-th letter of the data stream, u0 contains u[1, i]. We will show how to compute Ru0 at line 14
using a standard finite state automaton without any stack.
b such that testing whether u ∈ L ∩ Λ
Indeed, for every V PL L, one can construct a regular language L
b For this, let I be a special symbol not in
is equivalent to test whether some other word u
b belongs to L.
Σ= encoding the relation set {(p, p) : p ∈ Q}. For a word v ∈ Σl= , write [v, I] for
I) ·
 Qthe word (v(1),

j
(v(2), I) · · · (v(l), I), and similarly [I, v]. Consider a weighted word of the form u =
i=1 vi · ai · vj+1 ·
Q

1
∗
b
i=j bi · wi , where ai ∈ Σ+ , bi ∈ Σ- , and vi , wi ∈ Σ= . Then the slicing of u (see Figure 2) is the word u
Q

j
b = (Σ+ × Σ- ) ∪ (Σ= × {I}) ∪ ({I} × Σ= ) defined by u
over the alphabet Σ
b=
i=1 [vi , I] · [I, wi ] · (ai , bi ) ·
[vj+1 , I].
Definition 4.2. Let A = (Q, Σ, Γ, Qin , Qf , ∆) be a V PA. The slicing of A is the finite automaton
b Σ,
b Q
d
c b
b
d
c
Ab = (Q,
in , Qf , ∆) where Q = Q × Q, Qin = Qin × Qf , Qf = {(p, p) : p ∈ Q}, and the tranb are:
sitions ∆
(a,b)
a
b
1. (p, q)−→(p′ , q ′ ) when p−→(p′ , push(γ)) and (q ′ , pop(γ))−→q are both transitions of ∆.
(c,I)

(I,c)

c

c

2. (p, q)−→(p′ , q), resp. (p, q)−→(p, q ′ ), when p−→p′ , resp. q −→q ′ , is a transition of ∆.

10

This construction will be later used in Section 5 for weighted languages. In that case, we define the
cQ for
weight of a letter in u
b by |(a, b)| = |a| + |b|, with the convention that |I| = 0. Moreover, we write Σ
b using ΣQ instead of Σ= . Note that the slicing automaton Ab defined on
the alphabet obtained similarly to Σ
c
b
b
ΣQ is Σ-closed and has Σ-diameter at most 2m2 .
b = {b
Lemma 4.3. If A is a V PA accepting L, then Ab is a finite automaton accepting L
u : u ∈ L ∩ Λ}.

b correProof. Because transitions on push symbols do not depend on the top of the stack, transitions in ∆
d
spond to slices that are valid for ∆ (see Figure 2). Finally, Qin ensures that a run for L must start in Qin and
cf that a state at the top of the peak is consistent from both sides.
end in Qf , and Q
v
b

w
b

Proposition 4.4. Let v ∈ Λ be s.t. (p, q)−→(p′ , q ′ ). There is w ∈ Λ s.t. |w| ≤ 2m2 and (p, q)−→(p′ , q ′ ).

4.3 Random Sketches
We are now ready to build a tester for L ∩ Λ. To test a word u we use a property tester for the regular
b Regular languages are known to be ε-testable for the Hamming distance with O((log 1/ε)/ε)
language L.
non-adaptive queries on the input word [1], that is queries that can all be made simultaneously. Those
queries define a small random sketch of u0 that can be sent to the tester for approximating Ru0 . Since the
Hamming distance is larger than the edit distance, those testers are also valid for the latter distance. Observe
also that, for u, v ∈ ΛQ , we have bdist(u, v) ≤ 2dist(b
u, vb). The only remaining difficulty is to provide to
the tester an appropriate sampling on u
b while processing u.
We will proceed similarly for the general case in Section 5, but then we will have to consider weighted
words. Therefore we show how to sketch u0 in that general case already. Indeed, the tester of [1] was
simplified for the edit distance in [24], and later on adapted for weighted words in [25]. We consider here an
alternative approach that we believe simpler, but slightly less efficient than the tester of [25]. In particular, we
introduce in Appendix A a new criterion, κ-saturation, that permits to significantly simplify the correctness
proof of the tester compared to the one in [1] and in [25].
Our tester for weighted regular languages is based on k-factor sampling on u
b that we will simulate by
an over-sampling built from a letter sampling on u, that is according to the weights of the letters of u only.
This new sampling can be easily performed given a stream of u using a standard reservoir sampling.
Definition 4.5. For a weighted word u ∈ ΛQ , denote by Wk (u) the sampling over subwords of u constructed
as follows (see Figure 3):
(1) Sample a factor u[i, i + k] of u with probability |u(i)|/|u|.
(2) If u(i) is in the push sequence of u, let u[j, j ′ ] be the matching pop sequence of u[i, i + k], including the
first k neutral symbols after the last pop symbol, if any. Add u[j ′ − 2k, j ′ ] to the sample.1
Fact 4.6. There is a randomized streaming algorithm with memory O(k + log n) which, given k and u as
input, samples Wk (u).
Proof. (1) can easily be obtained using reservoir sampling. If the sampling enters the pop sequence as the
current candidate is part of the push sequence, then (2) can be done for that candidate, and forgotten if the
sampling eventually picks another one. That eventual candidate will not be part of the push sequence, so we
are done.
Lemma 4.7. Let u be a weighted word, and let k be such that 4k ≤ |u|. Then 4k independent copies of
Wk (u) over-sample the k-factor sampling on u
b.
1

Some matching pops of u[i, i + k] may be ignored.

11

k
u(i)

k+1

u(i + k)

u(j) u(j ′ − 2k)

2k + 1

u(j ′ )

Figure 3: The sampling Wk (u) from Definition 4.5: sample is in red, dotted parts are for omitted neutral
symbols
c the k-factor sampling on u
Proof. Denote by W
b, and by W some 4k independent copies of Wk (u). For any
c is at most the probability that vb is
k-factor v of u
b, we will show that the probability that vb is sampled by W
a factor of an element sampled by W. For that, we distinguish the following three cases:
c is equal to the
• vb contains only letters in {I} × ΣQ . Then the probability that vb is sampled by W
probability that it is sampled by Wk (u) in step (1).
• vb starts by a letter (a, b) in Σ+ × Σ− or by a letter in ΣQ × {I}. Then the probability that the
u(i) selected by Wk (u) is a is at least half of the probability that Wk (u) samples vb, as a (push,pop)
pair in u
b has weight 2 while a push has weight 1 in u. Because vb is a k-factor, it is contained in
c is at most the probability
(u[i, i + k], u[j ′ − 2k, j ′ ]). Hence, the probability that vb is sampled by W
that vb is a factor of an element sampled by Wk (u) in step (2).
• vb starts by a letter in {I} × ΣQ but also contains letters outside of this set. Since |b
u| ≥ |u|/2, we get
Pr(Wk (u) samples vb) ≥ 1/|u|

and

c samples vb)≤k/|b
Pr(W
u| ≤ 2k/|u|.

Thus the probability that one of the 4k samples of W has the factor vb is at least 1 − (1 − 1/|u|)4k .
4k
1
= |u|+4k
≥ 2k/|u| when |u| ≥ 4k, we conclude again that the
As 1 − (1 − 1/|u|)4k ≥ 1 − 1+4k/|u|
c is at most the probability that vb is a factor of an element sampled
probability that vb is sampled by W
by Wk (u) in step (2).

We can now give an analogue of the property tester for weighted regular languages in L ∩ ΛQ . For that,
we use the following notion of approximation.
Definition 4.8. Let R ⊆ Q2 . Then R (ε, Σ)-approximates a balanced word u ∈ (Σ+ ∪ Σ- ∪ ΣQ )∗ on A, if
u
v
for all p, q ∈ Q: (1) (p, q) ∈ R when p−→q; (2) u is (ε, Σ)-close to some word v satisfying p−→q when
(p, q) ∈ R.
Our tester is going to be robust enough in order to consider samples that do not exactly match the peaks
we want to compress.
Theorem 4.9. Let A be a V PA with m ≥ 2 states and Σ-diameter d ≥ 2. Let ε > 0, η > 0, t =
2⌈4dm3 (log 1/η)/ε⌉, k = ⌈4dm/ε⌉ and T = 4kt. There is an algorithm that, given T random subwords
z1 , . . . , zT of some weighted word v ∈ ΛQ , such that each zi comes from an independent sampling Wk (v),
12

outputs a set R ⊆ Q × Q that (ε, Σ)-approximates v on A with bounded error η.
Let v ′ be obtained from v by at most ε|v| balanced deletions. Then, the conclusion is still true if the algorithm
is given an independent Wk (v ′ ) for each zi instead, except that R now provides a (3ε, Σ)-approximation.
Last, each sampling can be replaced by an over-sampling.
b where A has been exProof. The argument uses as a subroutine the algorithm of Theorem A.2 for A,
b
b Also observe that
tended to ΣQ . Recall that A is Σ-closed and its Σ-diameter is also the Σ-diameter of A.
u, vb).
bdistΣ (u, v) ≤ 2distΣb (b
By Lemma 4.7, the T independent samplings Wk (v) provide us the sampling we need for Theorem A.2.
For the case where we do not have an exact k-factor sampling on v however, we need to compensate for
the prefix of v of size ε|v| that may not be included in the sampling. This introduces potentially an additional
error of weight 2ε|v| on the approximation R.
As a consequence we get our first streaming tester for L ∩ Λ.
Theorem 4.10. Let A be a V PA for L with m ≥ 2 states, and let ε, η > 0. Then there is a streaming ε-tester
for L ∩ Λ with one-sided error η and memory space O((m8 log(1/η)/ε2 )(m3 /ε + log n)), where n is the
input length.
Proof. We use Algorithm 2 where we replace the current factor u0 by T = 4kt independent samplings
Wk (u0 ). We know that such samplings can be computed using memory space O(k + log n) by Fact 4.6.
b
By Proposition 4.4, the slicing automaton has Σ-diameter
d at most 2m2 . Therefore, from Theorem 4.9,
taking t = 4⌈4dm3 (log 1/η)/ε⌉ and k = ⌈4dm/ε⌉ leads to the desired conclusion.

5 Algorithm With Sketching
5.1 Sketching Using Suffix Samplings
We now describe the sketches used by our main algorithm. They are based on the generalization of the
random sketches described in Section 4.3. Moreover, they rely on a notion of suffix samplings, that ensures
a good letter sampling on each suffix of a data stream. Recall that the letter sampling on a weighted word u
samples a random letter u(i) (with its position) with probability |u(i)|/|u|.
Definition 5.1. Let u be a weighted word and let α > 1. An α-suffix decomposition of u of size s (see
Figure 4) is a sequence of suffixes (ul )1≤l≤s of u such that: u1 = u, us is the last letter of u, and for all l,
ul+1 is a strict suffix of ul and if |ul | > α|ul+1 | then ul = a · ul+1 where a is a single letter.
An (α, t)-suffix sampling on u of size s is an α-suffix decomposition of u of size s with t letter samplings
on each suffix of the decomposition.
An (α, t)-suffix sampling can be either concatenated to another one, or compressed as stated below.
Proposition 5.2. Given as input an (α, t)-suffix sampling Du on u of size su and another one Dv on v of
size sv , there is an algorithm Concatenate(Du , Dv ) computing an (α, t)-suffix sampling on the concatenated word u · v of size at most su + sv in time O(su ).
Moreover, given as input an (α, t)-suffix sampling Du on u of size su , there is also an algorithm
Simplify(Du ) computing an (α, t)-suffix sampling on u of size at most 2⌈log |u|/ log α⌉ in time O(su ).
Proof. We sketch those procedures. They are fully described in Algorithm 3. For Concatenate, it suffices
to do the following. For each suffix ul of Du : (1) replace ul by ul · v; and (2) replace the i-th sampling of ul
by the i-th sampling of v with probability |v|/(|u| + |v|), for i = 1, . . . , t.
For Simplify, do the following. For each suffix ul of Du , from l = su (the smallest one) to l = 1 (the
largest one): (1) replace all suffixes ul−1 , ul−2 , . . . , um by the largest suffix um such that |um | ≤ α|ul |; and
(2) suppress all samples from deleted suffixes.
13

u
..
.

us

ul+1
..

ul

.

u1 = u

Figure 4: An α suffix decomposition of u of size s. For every l either |ul | ≤ α|ul+1 | or ul = a · ul+1 where
a is a letter.

Using this proposition, one can easily design a streaming algorithm constructing online a suffix decomposition of polylogarithmic size. Starting with an empty suffix-sampling S, simply concatenate S with
the next processed letter a of the stream, and then simplify it. We formalize this, together with functions
Concatenate and Simplify, in Algorithm 3
Lemma 5.3. Given a weighted word u as a data stream and a parameter α > 1, Online-Suffix-Sampling
in Algorithm 3 constructs an α-suffix sampling on u of size at most 1 + 2⌈log |u|/ log α⌉.
One can then slightly modify Algorithm 3 so that within each suffix of the decomposition it simulates t
letter samplings in order to construct an (α, t)-suffix sampling.

5.2 The Algorithm
Our final algorithm is a modification of Algorithm 2: in particular it will approximate relations Rv (in the
spirit of Definition 4.8), instead of exactly computing them. Therefore, it may fail at various steps and
produce relations that do not correspond to any word. But still, it will produce relations R such that for any
u
(p, q) ∈ R, there is a balanced word u ∈ Σ∗ with p−→q, that is R ∈ ΣQ .
To mimic Algorithm 2 we need to encode (compactly) each unfinished peak v of the stack and u0 :
for that we use the data structure described in Algorithm 4. Our final algorithm, Algorithm 5, is simply
Algorithm 2 with this new data structure and corresponding adapted operations, where ε′ = ε/(6 log n).
We now detail the methods, where we implicitly assume that each letter processed by the algorithm
comes with its respective height and (exact or approximate) weight. They use functions Concatenate and
Simplify described in Proposition 5.2 (and in details in Algorithm 3), while adapting them.
In the next section, we show that the samplings Svl are close enough to an (1 + ε′ )-suffix sampling on
l
v . This let us build an over-sampling of an (1 + ε′ )-suffix sampling. We also show that it only requires a
polylogarithmic number of samples. Then, we explain how to recursively apply the tester from Theorem 4.9
(with ε′ ) in order to obtain the compressions at line 14 and 20 while keeping a cumulative error below ε. We
now state our main result whose proof relies on Lemmas 5.6 and 5.8.
Theorem 5.4. Let A be a V PA for L with m ≥ 2 states, and let ε, η > 0. Then there is an ε-streaming
2
algorithm for L with one-sided error η and memory space O(m5 23m (log6 n)(log 1/η)/ε4 ), where n is the
input length.
Proof. We use Algorithm 5, which uses the tester from Theorem 4.9 for the compressions at lines 14 and 20
of Algorithm 2. We know from Lemma 5.8 and Lemma 4.7 that it is enough to choose ε′ = ε/(6 log n),
2
2
η ′ = η/n, and Fact 5.5 gives us d = 2m . Therefore we need T = 2304m4 22m (log2 n)(log 1/η)/ε2
2
independent k-factor samplings of u augmented by one, with k = 24m2m (log n)/ε. Lemma 5.6 tells us

14

Algorithm 3: α-Suffix Sampling
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

Data structure:
// D, Du , Dv , Dtemp stacks of items (σ, b), one for each suffix
// of the decomposition where σ encodes the weight and b the t samples
Code:
Concatenate(Du , Dv )
D ← Du
(c1 , . . . , ct ) ← all t samples on v (the largest suffix in Dv )
For each (σ, b) ∈ S where b = (b1 , . . . , bt )
Replace each bi by ci with probability |v|/(|v| + σ)
Replace (σ, b) by (σ + |v|, b)
Append Dv to the top of D
Return D
Simplify(Du )
D ← Du
For each (σ, b) ∈ D from top to bottom
Dtemp ← elements (τ, c) ∈ D below (σ, b) with τ ≤ ασ
Replace Dtemp in D by the bottom most element of Dtemp
Return D
Online-Suffix-Sampling
D←∅
While u not finished
a ← Next(u)
Concatenate(D, a) where a encodes the suffix sampling (|a|, (a, . . . , a))
Simplify(D)
Return D

Algorithm 4: Sketch for an unfinished peak
1
2
3
4
5
6
7
8
9

′

Parameters: real ε > 0, integer T ≥ 1
Data structure for a weighted word v ∈ Prefix(ΛQ )
Weights of v and of its first letter v(1)
Height of v(1)
Boolean indicating whether v contains a pop symbol
(1 + ε′ )-suffix decomposition v 1 , . . . , v s of v encoded by
Estimates |v l |low and |v l |high of |v l |
T independent samplings Svl on v l // see details below
with corresponding weights and heights

15

Algorithm 5: Adaptation of Algorithm 2 using sketches
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

Run Algorithm 2 using data structure from Algorithm 4 and with the following adaptations:
Adaption of functions from Proposition 5.2
Concatenate(Du , Dv ) with an exact estimate of |v| is modified s.t.
the replacement probability is now |v|/(|u|high + |v|)
and |ul · v|z ← |ul |z + |v|, for z = low, high
Simplify(Du ) with α = 1 + ε′ has now the relaxed condition |um |high ≤ (1 + ε′ )|ul |low
Adaption of operations on factors used in Algorithm 2
Compute relation: Rv
Run the algorithm of Theorem 4.9 using samples in Dv
Decomposition: v1 · v2 ← v
Find largest suffix v i in Dv s.t. v i ∈ Prefix(ΛQ ) // i.e. s.t. v i is in v2
Dv|v1 ← suffixes (v l )l<i with their samples
Dv2 ← suffix v i with its samples and weight estimates: // for computing Rv2
- (|v i |high , |v i |low ) when v i−1 and v i differ by exactly one letter (then v i = v2 )
- (|v i−1 |high , |v i |low ) otherwise
Test: |u0 | ≥ |v2 |/2 using |v2 |low instead of |v2 |
Concatenation: u0 ← (v1 · Rv2 ) · u0
Dv′ ← (Dv|v1 , Rv2 ) replacing each samples of Dv|v1 in v2 by Rv2
\\ The height of a sample determines whether it is in v2
Du0 ← Simplify(Concatenate(Dv′ , Du0 ))

that using twice as many samples from our algorithm, that is for each Svl , is enough in order to over-sample
them.
Because of the sampling variant we use, the size of each decomposition is at most 96(log 2 n)/ε +
O(log n) by Lemma 5.6. The samplings in each element of the decomposition use memory space k, and
there are 2T of them. Furthermore, each element of the stack has its own sketch, and the stack is of
height at most log n. Multiplying all those together gives us the upper bound on the memory space used by
Algorithm 5.

5.3 Final Analysis
As Algorithm 5 may fail at various steps, the relations it considers may not correspond to any word. However,
cQ
each relation R that it produces is still in ΣQ . Furthermore, the slicing automaton Ab that we define over Σ
2
m
b
b
is Σ-closed.
Fact 5.5 below bounds the Σ-diameter
of Ab (which is equal to the Σ-diameter of A) by 2 .
Note that for simpler languages, as those coming from a DTD, this bound can be lowered to m.
2

Fact 5.5. Let A be a V PA with m states. Then the Σ-diameter of A is at most 2m .
Proof. A similar statement is well known for any context-free grammar given in Chomsky normal form.
Let N be the number of non-terminal symbols used in the grammar. If the grammar produces one balanced
word from some non-terminal symbol, then it can also produce one whose length is at most 2N from the
same non-terminal symbol. This is proved using a pumping argument on the derivation tree. We refer the
reader to the textbook [17].
Now, in the setting of visibly pushdown languages one needs to transform A into a context-free grammar
in Chomsky normal form. For that, consider first an intermediate grammar whose non-terminal symbols are
all the Xpq where p and q are states from A: such a non-terminal symbol will produce exactly those words
u
u such that p−→q, hence our initial symbol will be those of the form Xq0 qf where q0 is an initial state and
qf is a final state. The rewriting rules are the following ones:
• Xpp → ε
16

• Xpq → Xpr Xrq for any state r
a
a
• Xpq → aXp′ q′ b whenever one has in the automaton p−→(p′ , push(γ)) and (q ′ , pop(γ))−→q for some
push symbol a, pop symbol b and stack letter γ.
a
• Xpq → aXp′ q whenever one has in the automaton p−→p′ for some neutral symbol a.
a
• Xpq → Xpq′ a whenever one has in the automaton q ′ −→q for some neutral symbol a.
Obviously, this grammar generates language L(A).
As we are here interested only in the length of the balanced words produced by the grammar, we can
replace any terminal symbol by a dummy symbol ♯. Now, once this is done we can put the grammar into
Chomsky normal form by using an extra non-terminal symbol (call it X♯ as it is used to produce the ♯
terminal). As we have m2 + 1 non-terminal in the resulting grammar we are almost done. To get to the tight
bound announced in the statement, one simply removes the extra non-terminal symbol X♯ and reasons on
the length of the derivation directly.
We first show that the decomposition, weights and sampling we maintain are close enough to an (1 + ε′ )suffix sampling with the correct weights. Recall that ε′ = ε/(6 log n).
Lemma 5.6 (Stability lemma). Let v, W be an unfinished peak with a sampling maintained by the algorithm.
Then W ⊗2 over-samples an (1 + ε′ )-suffix sampling on v, and W has size at most 144(log |v|)(log n)/ε +
O(log n).
Before proving the stability lemma, we first prove that Algorithm 5 maintains a strucutre that is not too
far from (1 + ε′ )-suffix sampling.
Proposition 5.7. Let v be an unfinished peak, and let v 1 , . . . , v s be the suffix decomposition maintained by
the algorithm. The following is true:
(1) v 1 , . . . , v s is a valid (1 + ε′ )-suffix decomposition of v.
(2) For each letter a of every v l , and for every sample s, Pr[Svl = a] ≥ |a|/|v l |high .
(3) Each v l satisfies |v l |high − |v l |low ≤ 2ε′ |v l |low /3.
Proof. Property (1) is guaranteed by the (modified) Simplify function used in Algorithm 5, which preserves
even more suffixes than the original algorithm.
Properties (2) and (3) are proven by induction on the last letter read by Algorithm 5. Both are true when
no symbol has been read yet.
We start with property (2). Let us first consider the case where we use bullet-concatenation after the
last letter was read. Then for all v l , the (modified) Concatenate function ensures Svl becomes a with
probability 1/|v l |high . Otherwise, Svl remains unchanged and by induction Svl = b with probability at least
(1 − 1/|v l |high )|b|/(|v l |high − 1) = |b|/|v l |high , for each other letter b of v l .
The other case is that some Rv2 is computed at line 20 of Algorithm 2. In this case, v is equal to
some (v1 · Rv2 ) · u0 concatenation. For each suffix (v1 · v2 )l in D(v1 ·v2 ) containing Rv2 , we proceed in
the same way with the Concatenate function, replacing any sample in v2 with Rv2 . Now consider v2i the
largest suffix of D(v1 ·v2 ) contained in v2 , and v l = Rv2 · u0 . We use the fact that Concatenate looks at
|v l |high ≥ |u0 | + |Rv2 | for replacing samples. This means that we choose Rv2 as a sample for v l with
probability (|v l |high − |u0 |)/|v l |high ≥ |Rv2 |/|v l |high , and therefore the property is verified.
We now prove property (3). If v l has just been created, it contains only one letter of weight 1, and obviously |v l |low = |v l |high = |v l |. In addition, unless some Rv2 has been computed at line 20 of Algorithm 2
when the last letter was read, then |v l | is only augmented by some exactly known |a| or |u0 | compared to
the previous step. Therefore the difference |v l |high − |v l |low does not change, and by induction it remains
smaller than 2ε′ |v l |low /3 which can only increase. Now consider Rv2 computed at line 20 and v l = Rv2 · u0 .

17

We again consider v2i for the largest suffix in the decomposition of v1 · v2 that is contained within v2 , as used
in Algorithm 5, and v2i−1 is the suffix immediately preceding v2i in that decomposition.
If |v2i−1 |high > (1+ε′ )|v2i |low , then from the Simplify function, the difference between those two suffixes
cannot be more than one letter, and then v2i = v2 . Therefore, we have |Rv2 · u0 |high = |v2 |high + |u0 | and
|Rv2 · u0 |low = |v2 |low + |u0 |. We conclude by induction on |v2 |.
We end with the case |v2i−1 |high ≤ (1 + ε′ )|v2i |low . By definition, |Rv2 · u0 |high = |v2i−1 |high + |u0 | and
|Rv2 · u0 |low = |v2i |low + |u0 |. Therefore the difference |v l |high − |v l |low is at most ε′ |v2i |low . Since the test at
line 19 of Algorithm 2 (modified by ALgorithm 5) was satisfied, we know that |v2i |low ≤ 2|u0 |, and finally
ε′ |v2i |low ≤ 2ε′ (|v2i |low + |u0 |)/3 ≤ 2ε′ |v l |low /3, which concludes the proof.
We can now prove the stability lemma.
Proof of Lemma 5.6. The first property is a direct consequence of property (1) and (2) in Proposition 5.7, as
in the proof of Lemma 4.7.
The second is a consequence of the (modified) Simplify used in Algorithm 5: Dtemp is defined as
the set of suffixes below with m < l such that |v m |high ≤ (1 + ε′ )|v l |low . Because Simplify deletes
all but one elements from Dtemp , it follows that |v l−2 |high > (1 + ε′ )|v l |low . Now, from property (3) of
Proposition 5.7 we have that |v l |low ≥ |v l |high − 2ε′ |v l |low /3 ≥ (1 − 2ε′ /3)|v l |high . Therefore we have that
|v l−2 |high > (1 + ε′ )(1 − 2ε′ /3)|v l |high
By successive applications, we obtain |v l−6 |high > (1+ ε′ )3 (1− 2ε′ /3)3 |v l |high . Now, as |v l |high > |v l |
and |v l | ≥ |v l |low ≥ (1−2ε′ /3)|v l |high we have: |v l−6 |/(1−2ε′ /3) > (1+ε′ )3 (1−2ε′ /3)3 |v l |. Equivalently,
|v l−6 | > (1 + ε′ )3 (1 − 2ε′ /3)4 |v l |.
Thus, the size of the suffix decomposition is at most 6 log(1+ε′ )3 (1−2ε′ /3)4 |v| ≤ 6 log |v|/ log(1 + ε′ /3 +
O(ε′2 )) ≤ 144(log |v|)(log n)/ε + O(log(n)).
Using the tester from Theorem 4.9 for computing each R, we can then prove the robustness lemma.
Lemma 5.8 (Robustness lemma). Let A a V PA recognizing L and let u ∈ Σn . Let Rfinal be the final value
of Rtemp in the Algorithm 5, using the tester from Theorem 4.9 at lines 14 and 20 of Algorithm 2. If u ∈ L,
then Rfinal ∈ L; and if Rfinal ∈ L, then bdistΣ (u, L) ≤ εn with probability at least 1 − η.
Proof. One way is easy. A direct inspection reveals that each substitution of a factor w by a relation R
enlarges the set of possible w-transitions.Therefore Rfinal ∈ L when u ∈ L.
For the other way, consider some word u such that Rfinal ∈ L. Since the tester of Theorem 4.9 has
bounded error η ′ = η/n and was called at most than n times, none of the calls fails with probability at least
1 − η. From now on we assume that we are in this situation.
Let h = Depth(Rfinal ). We will inductively construct sequences u0 = u, . . . , uh = Rfinal and
vh = Rfinal , . . . , v0 such that for every 0 ≤ l ≤ h, ul , vl ∈ (Σ+ ∪Σ− ∪ΣQ )∗ , bdistΣ (ul , vl ) ≤ 3(h−l)ε′ |ul |
and vl ∈ L. Furthermore, each word ul will be the word u with some substitutions of factors by relations
R computed by the tester. Therefore, Depth(ul ) is well defined and will satisfy Depth(ul ) = l. This will
conclude the proof using that Depth(Rfinal ) ≤ log3/2 n from Lemma 3.4. This will give us bdistΣ (u, v0 ) ≤
6ε′ n log n ≤ εn.
We first define the sequence (ul )l (see Figure 5 for an illustration). Starting from u0 = u, let ul+1 be the
word ul where some factors in ΛQ have been replaced by a (3ε′ , Σ)-approximation in ΣQ . These correspond
to all the approximations eventually performed by the algorithm that did not involve a symbol already in
ΣQ . Observe that after this collapse, the symbol is still a (3ε′ , Σ)-approximation. In particular, uh = Rfinal ,
ul ∈ (Σ+ ∪ Σ− ∪ ΣQ )∗ and Depth(ul ) = l by construction.
We now define the sequence (vl )l such that vl ∈ L. Each letter of vl will be annotated by an accepting
run of states for A. Set vh = Rfinal with an accepting run from pin to qf for some (pin , qf ) ∈ Rfinal ∩
18

R′

R′′

R

Rfinal

Figure 5: Constructing the words u0 , u1 and u2 as in Lemma 5.8 where Depth(Rfinal ) = 2
(Qin × Qf ). Consider now some level l < h. Then vl is simply vl+1 where some letters R ∈ ΣQ in common
with ul+1 are replaced by some factors in w ∈ (ΛQ )∗ as explained in the next paragraph. Those letters are
the ones that are present in ul but not ul+1 , and are still present in vl+1 (i.e. they have not been further
approximated down the chain from ul+1 to uh , or deleted by edit operations moving up from vh to vl+1 ).
Let w ∈ (ΛQ )∗ be one of those factors and R ∈ ΣQ its respective (3ε′ , Σ)-approximation. By hypothesis
R is still in vl+1 and corresponds to a transition (p, q) of the accepting run of vl+1 . We replace R by a factor
w′

w′ such that p−→q and bdistΣ (w, w′ ) ≤ 3ε′ |w|, and annotate w′ accordingly. By construction, the resulting
word vl satisfies vl ∈ L and bdistΣ (ul , vl ) ≤ 3(h − l)ε′ |ul |.

References
[1] N. Alon, M. Krivelevich, I. Newman, and M. Szegedy. Regular languages are testable with a constant
number of queries. SIAM Journal on Computing, 30(6), 2000.
[2] N. Alon, Y. Matias, and M. Szegedy. The space complexity of approximating the frequency moments.
Journal of Computer and System Sciences, 58(1):137–147, 1999.
[3] R. Alur. Marrying words and trees. In Proc. of 26th ACM Symposium on Principles of Database
Systems, pages 233–242, 2007.
[4] R. Alur, M. Arenas, P. Barceló, K. Etessami, N. Immerman, and L. Libkin. First-order and temporal
logics for nested words. In Proc. of 22nd IEEE Symposium on Logic in Computer Science, pages
151–160, 2007.
[5] R. Alur, K. Etessami, and P. Madhusudan. A temporal logic of nested calls and returns. In Proc. of
10th International Conference on Tools and Algorithms for the Construction and Analysis of Systems,
pages 467–481, 2004.
[6] R. Alur and P. Madhusudan. Adding nesting structure to words. Journal of the ACM, 56(3), 2009.
[7] A. Babu, N. Limaye, and G. Varma. Streaming algorithms for some problems in log-space. In Proc.
of 7th Conference on Theory and Applications of Models of Computation, pages 94–104, 2010.
[8] M. Blum, W. Evans, P. Gemmell, S. Kannan, and M. Naor. Checking the correctness of memories.
Algorithmica, pages 90–99, 1995.
[9] M. Blum and S. Kannan. Designing programs that check their work. Journal of the ACM, 42(1):269–
291, 1995.
19

[10] M. Blum, M. Luby, and R. Rubinfeld. Self-testing/correcting with applications to numerical problems.
Journal of Computer and System Sciences, 47(3):549–595, 1993.
[11] B. von Braunmühl and R. Verbeek. Input-driven languages are recognized in log n space. In Proc. of
4th Conference on Fundamentals of Computation Theory, volume 158, pages 40–51, 1983.
[12] M. Chu, S. Kannan, and A. McGregor. Checking and spot-checking the correctness of priority queues.
In Proc. of 34th International Colloquium on Automata, Languages and Programming, pages 728–739,
2007.
[13] P. Dymond. Input-driven languages are in log n depth. Information Processing Letters, 26(5):247–250,
1988.
[14] J. Feigenbaum, S. Kannan, M. Strauss, and M. Viswanathan. Testing and spot-checking of data streams.
Algorithmica, 34(1):67–80, 2002.
[15] E. Fischer, F. Magniez, and M. de Rougemont. Approximate satisfiability and equivalence. SIAM
Journal on Computing, 39(6):2251–2281, 2010.
[16] O. Goldreich, S. Goldwasser, and D. Ron. Property testing and its connection to learning and approximation. In Proc. of 37th IEEE Symposium on Foundations of Computer Science, pages 339–348,
1996.
[17] J. Hopcroft, R. Motwani, and J. Ullman. Introduction to Automata Theory, Languages, and Computation (3rd Edition). Addison-Wesley, 2006.
[18] C. Konrad and F. Magniez. Validating XML documents in the streaming model with external memory.
ACM Transactions on Database Systems, 38(4):27, 2013. Special issue of ICDT’12.
[19] L. Libkin. Logics for unranked trees: An overview. Logical Methods in Computer Science, 2(3), 2006.
[20] F. Magniez and M. de Rougemont. Property testing of regular tree languages. Algorithmica, 49(2):127–
146, 2007.
[21] F. Magniez, C. Mathieu, and A. Nayak. Recognizing well-parenthesized expressions in the streaming
model. SIAM Journal on Computing, 43(6):1880–1905, 2014.
[22] K. Mehlorn. Pebbling mountain ranges and its application to dcfl-recognition. In Proc. of 7th International Colloquium on Automata, Languages, and Programming, pages 422–435, 1980.
[23] S. Muthukrishnan. Data streams: Algorithms and applications. Foundations and Trends in Theoretical
Computer Science, 1(2):117–236, 2005.
[24] A. Ndione, A. Lemay, and J. Niehren. Approximate membership for regular languages modulo the
edit distance. Theoretical Computer Science, 487:37–49, 2013.
[25] A. Ndione, A. Lemay, and J. Niehren. Sublinear DTD validity. In Proc. of 19th International Conference on Language and Automata Theory and Applications, pages 739–751, 2015.
[26] M. Parnas, D. Ron, and R. Rubinfeld. Testing membership in parenthesis languages. Random Structures & Algorithms, 22(1):98–138, 2003.
[27] A. Rajeev and P. Madhusudan. Visibly pushdown languages. In Proc. of 36th ACM Symposium on
Theory of Computing, pages 202–211, 2004.
20

[28] L. Segoufin and C. Sirangelo. Constant-memory validation of streaming XML documents against
DTDs. In Proc. of 11th International Conference on Database Theory, pages 299–313, 2007.
[29] L. Segoufin and V. Vianu. Validating streaming XML documents. In Proc. of 11th ACM Symposium
on Principles of Database Systems,, pages 53–64, 2002.

21

A

A Tester for Weighted Regular Languages

We design a non-adaptive property tester for weighted regular languages that serves as a basic routine of our
main algorithm. Property testing of regular languages was first considered in [1] for the Hamming distance
and we adapt this tester to weighted words for the simple case of edit distance. Such a property tester has
been already constructed first for edit distance in [24], and later on for weighted words in [25], with an
approach based on [1].
In this work, we take an alternative approach that we believe simpler, but slightly less efficient than the
tester of [25]. We consider the graph of components of the automaton and focus on paths in this graph; we
however introduce a new criterion, κ-saturation (for some parameter 0 < κ ≤ 1), that permits to significantly
simplify the correctness proof of the tester compared to the one in [1] and in [25]. In particular Lemma A.5
permits to design a non-adaptive tester for L and also to approximate the action of u on A as follows.
Definition A.1. Let Σ′ ⊆ Σ and R ⊆ Q × Q. Then R (ε, Σ′ )-approximates a word u on A (or simply
u
ε-approximates when Σ′ = Σ), if for all p, q ∈ Q: (1) (p, q) ∈ R when p−→q; (2) u is (ε, Σ′ )-close to some
v
word v satisfying p−→q when (p, q) ∈ R.
Our main contribution is the following one.
Theorem A.2. Let A be an automaton with m ≥ 2 states and diameter d ≥ 2. Let ε > 0, η > 0, t ≥
2⌈2dm3 (log 1/η)/ε⌉ and k ≥ ⌈2dm/ε⌉. There is an algorithm that, given t random factors of v1 , . . . , vt of
some weighted word u, such that each vi comes from an independent k-factor sampling on u, outputs a set
R ⊆ Q × Q that ε-approximates u on A with one-sided error η.
This is still true with any combination of the following generalization:
• The algorithm is given an over-sampling of each of factors vi instead.
• When A is Σ′ -closed, and d is the Σ′ -diameter of A, then R also (ε, Σ′ )-approximates u on A.
The rest of this section is devoted to the proof of Theorem A.2 and therefore we fix a regular language
L recognized by some finite state automaton A on Σ with a set of states Q of size m ≥ 2, and a diameter
a
d ≥ 2. Define the directed graph GA on vertex set Q whose edges are pairs (p, q) when p−→q for some
a ∈ Σ.
A component C of GA is a maximal subset (w.r.t. inclusion) of vertices of GA such that for every p1 , p2
in C one has a path in GA from p1 to p2 . The graph of components GA of GA describes the transition
relation of A on components of GA : its vertices are the components and there is a directed edge (C1 , C2 ) if
there is an edge of GA from a vertex in C1 toward a vertex in C2 .
Definition A.3. Let C be a component of GA , let Π = (C1 , . . . , Cl ) be a path in GA .
u
• A word u is C-compatible if there are states p, q ∈ C such that p−→q.
vi
• A word u is Π-compatible if u can be partitioned into u = v1 a1 v2 . . . al−1 vl such that pi −→q
i and
ai
qi −→pi+1 , where vi is a factor, ai a letter, and pi , qi ∈ Ci .
• A sequence of factors (v1 , . . . , vt ) of a word u is Π-compatible if they are factors of another Πcompatible word with the same relative order and same overlap.
Note that the above properties are easy to check. Indeed, C-compatibility is a reachability property
while the two others easily follow from C-compatibility checking.
We now give a criterion that characterizes those words u that are ε-far to every Π-compatible word. Note
that it will not be used in the tester that we design in Theorem A.2 for weighted regular languages, but only
in Lemma A.5 which is the key tool to prove its correctness.
For a component C and a C-incompatible word v, let v1 · a be the shortest C-incompatible prefix of v.
We define and denote the C-cut of v as v = v1 · a · v2 . When v1 is not the empty word, we say that v1 is a
C-factor and a is a C-separator for v1 , otherwise we say that a is a strong C-separator.
22

Fix a path Π = (C1 , . . . , Cl ) in GA , a parameter 0 < κ ≤ 1, and consider a weighted word u. We
define a natural partition of u according to Π, that we call the Π-partition of u. For this, start with the first
component C = C1 , and consider the C1 -cut u1 · a · u2 of u. Next, we inductively continue this process with
either the suffix a · u2 if a is a C1 -separator, or the suffix u2 if a is a strong C1 -separator. Based on some
criterion defined below we will move from the current component Ci to a next component Cj of Π, where
most often j = i + 1, until the full word u is processed. If we reach j = l + 1, we say that u κ-saturates
Π and the process stops. We now explain how we move on in Π. We stay within Ci as long as both the
number of Ci -factors and the total weight of strong Ci -separators are at most κ|u| each. Then, we continue
the decomposition with some fresh counting and using a new component Cj selected as follows. One sets
j = i + 1 except when the transition is the consequence of a strong Ci -separator a of weight greater than
κ|u|, that we call a heavy strong separator. In that case only, one lets j ≥ i + 1, if exists, to be the minimal
a
integer such that q −→q ′ with q ∈ Cj−1 ∪ Cj and q ′ ∈ Cj , and j = l + 1 otherwise.
Proposition A.4. Let 0 < κ ≤ ε/(2dl). If u is ε-far to every Π-compatible word, then u κ-saturates Π.
Proof. The proof is by contraposition. For this we assume that u does not κ-saturate Π and we correct u to
a Π-compatible word as follows.
First, we delete each strong separator of weight less that κ|u|. Their total weight is at most 2lκ|u|.
Because u does not saturate, each strong separator of weight larger than κ|u| fits in the Π-partition, and does
not need to be deleted.
We now have a sequence of consecutive Ci -factors and of heavy strong Ci -separators, for some 1 ≤ i ≤
l, in an order compatible with Π. However, the word is not yet compatible with Π since each factor may
end with a state different than the first state of the next factor. However, for each such pair there is a path
connecting them. We can therefore bridge all factors by inserting a factor of weight at most d, the diameter
of A.
The resulting word is then Π-compatible by construction, and the total cost of the edit operations is at
most (2l + dl)κ|u| ≤ ε|u|, since d ≥ 2.
For a weighted word u, we remind that the k-factor sampling on u is defined in Section 2. The following
lemma is the key lemma for the tester for weighted regular languages.
Lemma A.5. Let u be a weighted word, let Π = C1 . . . Cl be a path in GA . Let 0 < κ ≤ ε/(2dl) and let W
denote the ⌈2/κ⌉-factor sampling on u. Then for every 0 < η < 1 and t ≥ 2l(log 1/η)/κ, the probability
P (u, Π) = Pr(v1 ,...,vt )∼W ⊗t [(v1 , . . . , vt ) is Π-compatible] satisfies P (u, Π) = 1 when u is Π-compatible,
and P (u, Π) ≤ η when u is ε-far for from being Π-compatible.
Proof. The first part of the theorem is immediate. For the second part, assume that u is ε-far from any Πcompatible word. For simplicity we assume that 2/κ and κ|u|/2 are integers. We first partition u according
to Π and κ. Then, Proposition A.4 tells us that u κ-saturates Π. For each Ci , we have three possible cases.
1. There are κ|u| disjoint Ci -factors in u. Since they have total weight at most |u|, there are at least
κ|u|/2 of them whose weight is at most 2/κ each. Since each letter has weight at least 1, the total
weight of the first letters of each of those factors is at least κ|u|/2. Therefore one of them together
with its Ci -separator is a sub-factor of some sampled factor vj with probability at least 1 − (1 − κ/2)t .
2. The total weight of strong Ci -separators of u is at least κ|u|. Therefore one of them is the first letter
of some sampled factor vj with probability at least 1 − (1 − κ)t .
3. There is not any Ci -factor and any Ci -separator of u, because of a strong Ci′ -separator of weight
greater than κ|u|, for some i′ < i. This separator is the first letter of some sampled factor vj with
probability at least 1 − (1 − κ)t .

23

By union bound, the probability that one of the above mentioned samples fails to occurs is at most
l(1 − κ)t ≤ η. We assume now that they all occur, and we show that they form a Π-incompatible sequence.
For each i, let wi be the above described sub-factors of those samples. Each wi appears in u after wi−1 or,
in the case of a strong separator of heavy weight, wi = wi−1 . Moreover each factor wi which is distinct
from wi−1 forces next factors to start from some component Ci′ with i′ > i. As a result (w1 , . . . , wl ) is not
Π-compatible, and as a consequence (v1 , . . . , vt ) neither, so the result.
We can now conclude with the proof of Theorem A.2.
Proof of Theorem A.2. The algorithm is very simple:
1. Set R = ∅
2. For all states p, q ∈ Q
v

(a) Check if factors v1 , . . . , vt could come from a word v such that p−→q
// Step (a) is done using the graph GA of connected components of A
(b) If yes, then add (p, q) to R
3. Return R
u

It is clear that this R contains every (p, q) such that p−→q. Now for the converse, we will show that,
with bounded error η, the output set R only contains pairs (p, q) such that there exists a path Π = C1 , . . . , Cl
on GA such that p ∈ C1 , q ∈ Cl , and u is Π-compatible. In that case, there is an ε-close word v satisfying
v
p−→q.
Indeed, using l ≤ m and Lemma A.5 with t, κ = ε/(2dm) and η ′ = η/2m , the samples satisfy
P (u, Π) ≤ η/2m , when u is not Π-compatible. Therefore, we can conclude using a union bound argument
on all possible paths on GA , which have cardinality at most 2m , that, with probability at least 1 − η, there is
no Π such that the samples are Π-compatible but u is not Π-compatible.
The structure of the tester is such that it has only more chances to reject a word that is not Π-compatible
u
given an over-sampling as input instead. Words u such that p−→q will always be accepted no matter the
amount and length of samples. Therefore the theorem still holds with an over sampling.
Last, A being Σ′ -closed ensures that the notions of compatibility and saturation remain unchanged.
Using the Σ′ -diameter in Lemma A.5 (and therefore in Proposition A.4) let us use bridges in Σ′∗ instead of
Σ∗ with weight at most d.

24

