0:00:01.040,0:00:04.160
Hello everyone! I'm Antoine
Amarilli from Télécom Paris.
0:00:04.800,0:00:08.640
This is the presentation
for ICALP'2021 of our work
0:00:08.640,0:00:12.560
with Louis Jachiet and Charles Paperman
about the problem of dynamic
0:00:12.560,0:00:17.520
membership for regular languages.
So let me first define what the problem
0:00:17.520,0:00:23.280
is. We fix a regular language L.
We are given as input a word w,
0:00:23.280,0:00:27.840
for instance this one here
We will now do two phases.
0:00:27.840,0:00:31.280
The first phase is that we preprocess
this input word in linear time.
0:00:32.080,0:00:35.840
This allows us in particular to determine
if the input word belongs to L or not
0:00:36.560,0:00:39.760
But we can also use this time to
build auxiliary data structures.
0:00:40.800,0:00:45.360
Then we will receive a sequence
of updates to the input word.
0:00:45.360,0:00:50.080
These updates are substitution updates:
for instance, one update could be
0:00:50.080,0:00:52.800
"Replace the third character
of the input word by a."
0:00:53.680,0:00:57.840
If we do this update, then the word
now belongs to the target language L.
0:00:58.560,0:01:01.840
Our work is to receive the
updates and perform them in w
0:01:02.720,0:01:06.720
while maintaining at every step the
information of whether w belongs to L or not.
0:01:07.440,0:01:11.040
For instance, a second update could
then change this character to be an a
0:01:11.040,0:01:14.000
And then the word would no
longer belong to the language;
0:01:14.000,0:01:17.200
and if we change it back to a b then
the word belongs to the language again.
0:01:20.320,0:01:24.160
As we will be studying the complexity of
this problem, and it will be quite low
0:01:24.160,0:01:27.200
I need to give you some information
about the design choices that we make.
0:01:28.000,0:01:33.040
Our model is the RAM model: the cells
have logarithmic size in the input word
0:01:33.040,0:01:37.120
and we assume that arithmetic operations
on such cells take constant time.
0:01:37.120,0:01:39.840
For instance, adding two numbers
will only take constant time
0:01:39.840,0:01:42.560
even though both numbers can be of
logarithmic size in the input word.
0:01:43.440,0:01:46.080
The updates that we allow are only substitutions,
0:01:46.080,0:01:48.960
so in particular the length
n of the word never changes.
0:01:49.600,0:01:54.080
The reason why we do not allow more expressive
updates like insertions and deletions
0:01:54.080,0:01:57.920
is because, if such updates can take
place at arbitrary places in the word,
0:01:57.920,0:02:01.520
then just maintaining the current state of
the word efficiently is already quite tricky.
0:02:02.560,0:02:06.480
The memory usage has to be polynomial
in the length of the input word
0:02:06.480,0:02:11.120
because we cannot store larger integers than this.
The upper bounds that we will show will only
0:02:11.120,0:02:16.000
need a linear amount of space in the input word,
and we will show lower bounds that will apply even
0:02:16.000,0:02:20.560
without making this linear space assumption.
As for the preprocessing time,
0:02:20.560,0:02:24.400
our upper bounds will again only need
linear preprocessing in the input word
0:02:24.400,0:02:27.680
and our lower bounds will apply no
matter which preprocessing is allowed.
0:02:29.360,0:02:33.280
So let me first explain to you an
algorithm that can solve this problem
0:02:33.280,0:02:37.280
In logarithmic time for every update,
no matter what the language is.
0:02:38.400,0:02:42.560
If we fix the regular language L, we can
consider an automaton for this language.
0:02:43.120,0:02:48.400
Then, if we are given an input word w, we
can build in linear time in the preprocessing
0:02:48.400,0:02:52.080
a balanced binary tree structure on
this word, for instance this one.
0:02:52.880,0:02:59.040
Then, we can label every node of the
tree with information about the effect
0:02:59.040,0:03:05.200
of reading in the automaton the word
labeling the leaves of this subtree.
0:03:06.160,0:03:10.960
The specific information that we need is
the set of all possible pairs of states
0:03:10.960,0:03:14.880
such that we can go from one state to the
other while reading this specific word.
0:03:15.440,0:03:17.840
In this example, this is the
information that we obtain.
0:03:18.400,0:03:22.640
This labeling can be computed in linear
time as well during the preprocessing.
0:03:22.640,0:03:26.880
It allows us in particular to know
whether the word belongs to L or not:
0:03:26.880,0:03:30.640
we can simply look at the
annotation of the root and see
0:03:30.640,0:03:33.760
if there is a path from the
initial state to the final state.
0:03:34.880,0:03:36.800
And crucially this representation can
0:03:36.800,0:03:40.240
be updated in logarithmic time
whenever a substitution occurs.
0:03:40.240,0:03:44.160
If we change this character here for
instance, we only need to recompute
0:03:44.160,0:03:48.240
the information of the nodes on the path
from this leaf to the root of the tree.
0:03:48.880,0:03:53.280
This path has logarithmic size, and
updating every node is in constant time
0:03:53.280,0:03:56.000
because we assumed that the language
and that the automaton are fixed.
0:03:57.040,0:04:02.720
So in this way we can figure out that the
word now belongs to the target language.
0:04:03.520,0:04:08.240
This complexity of O(log n) can be
improved to O(log n / log log n)
0:04:08.240,0:04:13.840
by using some tricks on the RAM model and using
a log-ary tree instead of a binary tree.
0:04:14.400,0:04:18.960
The question that we study in our work is:
can we do better than logarithmic time.
0:04:18.960,0:04:23.360
It is not difficult to see that this is indeed
the case, at least for some target languages.
0:04:23.920,0:04:25.920
For the language (ab)^*, for instance,
0:04:25.920,0:04:30.000
we can handle updates in constant
time instead of logarithmic time.
0:04:30.000,0:04:34.160
How can we do this? Well, first, we check
that the length of the input word is even
0:04:34.160,0:04:38.240
because, otherwise, as this length can never
change, then the word can never belong to L.
0:04:39.120,0:04:47.200
Then, once we are given a word w, we can in
the linear-time preprocessing simply count
0:04:47.200,0:04:50.960
the number of violations, so the number of
characters that are not the correct one.
0:04:52.800,0:04:56.000
This information can be maintained
in constant time at every update
0:04:56.000,0:04:59.840
as we can see whether we have
removed, or added, a violation.
0:05:02.320,0:05:06.640
The word w belongs to the language
L iff there are no violations, i.e.,
0:05:06.640,0:05:11.120
iff the counter of violations is currently zero.
Thus, this algorithm can handle updates
0:05:11.120,0:05:14.480
in constant time per update, and
hence the question that we study:
0:05:14.480,0:05:17.120
what is the complexity of the
dynamic membership problem
0:05:17.120,0:05:19.760
depending on the regular
language L that we have fixed.
0:05:21.840,0:05:25.600
To answer this question, we also
study a variant of the problem
0:05:25.600,0:05:30.720
called the dynamic word problem for monoids.
This is the same problem but, instead of fixing
0:05:30.720,0:05:34.400
a language, we fix a monoid, which is
a set with an associative composition
0:05:34.400,0:05:38.080
law and a neutral element.
The word is now a word of elements
0:05:38.080,0:05:42.880
of the monoid and our work is to maintain
the product of these elements according
0:05:42.880,0:05:48.080
to the monoid law, and the updates
are again substitution updates, where
0:05:48.080,0:05:51.840
one element of the word can be changed
to a different element of the monoid.
0:05:52.560,0:05:56.880
So this is a special case of the dynamic
membership problem for regular languages.
0:05:56.880,0:06:01.600
But it is coarser, for instance, we assume
that the monoid contains a neutral element,
0:06:01.600,0:06:05.120
whereas in the case of languages
there might not be a neutral letter
0:06:05.120,0:06:08.080
that has no effect on belonging
to the target language or not.
0:06:08.960,0:06:15.440
And this problem was studied previously, by
Skovbjerg Frandsen et al. in a JACM paper in 1997.
0:06:16.160,0:06:21.280
They show that this problem is in constant
time per update for commutative monoids,
0:06:21.280,0:06:25.680
which is not too difficult to understand.
They show a more complicated result
0:06:25.680,0:06:29.200
that for group-free monoids, so,
monoids that do not contain a group,
0:06:29.200,0:06:32.320
the problem can be solved
in O(log log n) per update.
0:06:33.120,0:06:37.440
Further, they show that for a certain
class of monoids, there a lower bound
0:06:37.440,0:06:41.840
of Ω(log n / log log n). This matches
the upper bound of O(log n / log log n)
0:06:41.840,0:06:45.200
that we showed previously, which also
applies to this problem of monoids.
0:06:45.200,0:06:47.840
So in this case the complexity is tight.
0:06:49.120,0:06:52.240
We study also this variant
of our problem on monoids
0:06:52.240,0:06:56.160
and our results for the dynamic word
problem on monoids are the following:
0:06:56.160,0:07:01.360
We identify a class of monoids that we
define algebraically by an equation here
0:07:01.360,0:07:04.640
and we show that for any monoid
that falls in this class,
0:07:04.640,0:07:07.040
the dynamic word problem is in constant time.
0:07:07.600,0:07:13.040
We also show that for any monoid which
is not in this class, then we can reduce
0:07:13.040,0:07:17.040
from a certain problem to the
dynamic word problem for that monoid.
0:07:17.040,0:07:22.000
We conjecture that this problem is not in
O(1), giving us a conditional lower bound.
0:07:23.040,0:07:28.000
We also identify a class satisfying
a somewhat more complicated equation
0:07:28.000,0:07:31.200
and we show that every monoid
satisfying this equation
0:07:31.200,0:07:38.480
has a complexity of O(log log n) per update.
We also show that any monoid not in this class
0:07:38.480,0:07:41.600
is covered by the lower bound
of Skovbjerg Frandsen et al.
0:07:43.680,0:07:48.640
This means that, for every monoid not in SG,
the complexity is in Θ(log n / log log n).
0:07:50.720,0:07:54.160
We then come back to the problem that
we were originally interested in:
0:07:54.160,0:07:56.480
the dynamic membership
problem for regular languages.
0:07:57.040,0:08:01.280
We show that this conditional trichotomy
on monoids extends to languages
0:08:01.840,0:08:06.080
on regular language classes called
QLZG and QSG that I will define later.
0:08:07.840,0:08:11.760
So this concludes the presentation
of the problem and of our results.
0:08:11.760,0:08:14.960
Let me first give you some information
about how these results are proven.
0:08:15.920,0:08:19.200
Let me first talk about the
results on the problem for monoids.
0:08:20.320,0:08:24.480
And let me first talk about the upper bounds,
and specifically the constant-time upper bound
0:08:25.360,0:08:28.320
There is first this result,
by Skovbjerg Frandsen et al.,
0:08:28.320,0:08:32.400
that the dynamic word problem for commutative
monoids is in constant-time per update.
0:08:32.960,0:08:37.920
This is not too difficult to understand.
The algorithm is simply that we count
0:08:37.920,0:08:41.440
the number of occurrences of
every monoid element in the word
0:08:43.920,0:08:51.120
and maintain a counter for every monoid element.
Then, we maintain these counts under updates,
0:08:51.120,0:08:55.440
so, whenever an element is changed,
we simply update the corresponding counter.
0:08:56.320,0:09:02.480
And then, to maintain the image, i.e., the
result of the evaluation of this in the monoid,
0:09:02.480,0:09:06.480
we simply use commutativity:
the product of the monoid elements
0:09:06.480,0:09:09.040
exponentiated to their number
of occurrences in the word.
0:09:09.760,0:09:13.680
These powers can be simply computed in
linear time as part of the preprocessing
0:09:13.680,0:09:17.200
and the composition can then be done in
constant time, so we can maintain this
0:09:17.200,0:09:23.920
information in constant time.
We also know that the classes
0:09:23.920,0:09:28.640
of tractable monoids are closed under
the operations of a variety of monoids,
0:09:28.640,0:09:34.560
so, if a monoid is tractable then all
submonoids of that monoid are also tractable.
0:09:34.560,0:09:39.600
If two monoids are tractable,
e.g., are in O(1) per update,
0:09:39.600,0:09:44.080
then a direct product of the two monoids
is also tractable in O(1) per update.
0:09:44.800,0:09:49.360
This means that the class of monoids
enjoying this property of updates being
0:09:49.360,0:09:52.800
handleable in constant time
forms a variety of monoids.
0:09:54.320,0:09:57.680
But are there more things in this
variety than simply commutative monoids?
0:09:58.480,0:10:03.440
In fact, there is another case: the monoids
that are obtained from a nilpotent semigroup
0:10:03.440,0:10:07.200
by adding an identity to it also
enjoy constant-time per update.
0:10:07.840,0:10:12.720
A nilpotent semigroup is just a set with
a composition law and no neutral element
0:10:13.280,0:10:16.800
such that the image of the composition
can be determined by looking at
0:10:16.800,0:10:20.000
a small number of elements.
If we combine too many elements,
0:10:20.000,0:10:25.680
then we fall to a special "zero" element.
If we add an identity to this object,
0:10:25.680,0:10:29.600
then the resulting monoid can also be
handled in constant time per update.
0:10:29.600,0:10:32.640
To give you an idea of the
proof, let's go back to languages
0:10:32.640,0:10:36.800
and let's look at the specific
language here: e^* a e^* b e^*.
0:10:37.920,0:10:42.000
This is the language where we say: there
is only one a, there is only one b,
0:10:42.000,0:10:46.560
the a has to be before the b, and there is
a letter e that intuitively does not matter:
0:10:46.560,0:10:50.560
it is a neutral letter, it corresponds
intuitively to a neutral element in the monoid.
0:10:51.440,0:10:56.000
How can we maintain dynamically membership
to this language in constant-time per update.
0:10:56.720,0:11:00.720
This is a somewhat surprising algorithm
even though it's not that complicated.
0:11:01.360,0:11:06.000
In the preprocessing we will
prepare a doubly-linked list
0:11:06.560,0:11:13.200
of the positions that contain a's and b's.
We will maintain this list whenever we add
0:11:13.200,0:11:17.200
or remove b's or a's to the word,
so whenever an e gets
0:11:17.200,0:11:22.320
substituted to/from an a or a b.
To do this, we can simply insert the new
0:11:22.320,0:11:28.160
a or b or remove the a or be in constant-time
using the property of a doubly-linked list.
0:11:28.720,0:11:32.880
We will not preserve the order of the list
so the doubly-linked list will in general
0:11:32.880,0:11:35.680
be unsorted, it will just
contain all of the positions
0:11:35.680,0:11:40.800
with a's and b's. And now, to know if the current
word belongs to the target language or not,
0:11:41.520,0:11:47.120
if L contains more than two positions, or less
than two positions, then the answer is no:
0:11:47.120,0:11:52.960
it cannot contain exactly one a and exactly one
b. Otherwise, since it contains two positions,
0:11:52.960,0:11:58.000
we can simply extract the two corresponding
elements and check that the first one is an a
0:11:58.000,0:12:04.400
and the second one is a b; and this only takes
constant time. This technique generalizes
0:12:04.400,0:12:09.200
to monoids where we intuitively need to track only
a constant number of elements, and then the rest
0:12:09.200,0:12:11.760
is the neutral element that
we do not need to consider.
0:12:13.920,0:12:17.440
So, to summarize these results in
a consistent algebraic framework,
0:12:17.440,0:12:20.480
we introduce a variety of
monoids defined by an equation.
0:12:21.360,0:12:28.640
This equation here applies to all elements of the
monoid, and considers x exponentiated to ω+1
0:12:28.640,0:12:33.840
where ω is the idempotent power of
x, i.e., x^ω x^ω = x^ω.
0:12:35.280,0:12:42.080
Elements of the form x^{ω+1} are intuitively
those that belong to a subgroup of the monoid,
0:12:42.080,0:12:47.440
in particular all of the idempotents of
the monoid. We assert by the equation
0:12:47.440,0:12:51.120
that these elements from a subgroup
are central: they must commute with
0:12:51.120,0:12:56.000
all other elements. We show that the
monoids that satisfy this equation
0:12:56.000,0:12:59.280
are precisely those that can be
obtained from commutative monoids,
0:12:59.280,0:13:04.240
which obviously satisfy the equation,
and monoids of the form S^1 from the previous
0:13:04.240,0:13:10.480
slide, via the monoid variety operators.
This implies that the dynamic word problem
0:13:10.480,0:13:13.360
for monoids in this class is
in constant time per update.
0:13:15.280,0:13:18.711
Now let us move to the upper bound of O(log log n).
This is shown on a different class SG
0:13:18.711,0:13:26.800
defined by a somewhat scarier equation here.
The intuition for this equation is that
0:13:28.000,0:13:33.200
a group element here can be swapped
with an identity for that group:
0:13:33.200,0:13:38.160
x^ω must be the identity of the
group to which x^{ω+1} belongs.
0:13:39.120,0:13:44.720
Which monoids satisfy this equation? We can
easily show that ZG monoids satisfy the equation
0:13:44.720,0:13:48.240
because x^{ω+1} elements
commute with everything,
0:13:48.240,0:13:53.040
Group-free monoids studied by Skovbjerg Frandsen
et al. must also satisfy the equation because
0:13:53.040,0:13:58.000
they have no non-trivial subgroups,
and this also covers new monoids that
0:13:58.000,0:14:00.720
were not covered by the result
of Skovbjerg Frandsen et al.,
0:14:00.720,0:14:04.080
for instance the direct product of a
commutative monoid and a group-free monoid.
0:14:05.040,0:14:10.080
We show that the dynamic word problem for
monoids in this class is in O(log log n).
0:14:10.800,0:14:14.800
I will not go into the details of the
proof, but intuitively it proceeds by
0:14:14.800,0:14:20.880
an induction on J-classes on the monoid
using the Rees-Sushkevich theorem at every class,
0:14:20.880,0:14:26.080
and using a Van Emde Boas tree data structure
to intuitively jump over some runs of elements.
0:14:26.080,0:14:29.280
This is where the O(log log
n) complexity comes from,
0:14:29.280,0:14:32.000
and the same was true of the
result of Skovbjerg Frandsen et al.
0:14:33.600,0:14:38.000
Let me give you an idea of how we show
lower bounds for the monoid problems.
0:14:38.000,0:14:41.680
All of our lower bounds are shown by
reducing from a different problem called
0:14:41.680,0:14:46.560
the prefix problem for a language L.
The prefix problem is to maintain
0:14:46.560,0:14:51.200
a word under substitution updates and to
maintain a different kind of information:
0:14:51.200,0:14:56.000
instead of maintaining whether the word belongs
to L or not, we must maintain a data structure
0:14:56.000,0:15:01.840
that we can use to query if a given prefix of
the word belongs to L or does not belong to L.
0:15:02.800,0:15:08.480
So we have substitution updates and we have
the prefix query that asks, given a prefix,
0:15:08.480,0:15:12.320
whether it belongs to L or not
in the current state of the word.
0:15:12.320,0:15:18.320
We specifically study two kinds of
prefix problems: prefix-ℤ_d, where
0:15:18.320,0:15:26.400
e.g. prefix-ℤ_2 asks on a binary word like this
to maintain the information, for every prefix,
0:15:26.400,0:15:29.520
of whether it contains an
even number of 1's or not.
0:15:30.400,0:15:33.680
Prefix-ℤ_d is the generalization
of this to different moduli.
0:15:34.560,0:15:38.480
The interest of this problem is that
Fredman and Saks have shown an
0:15:38.480,0:15:42.033
Ω(log n / log log n) lower bound for that problem.
This is where the lower bound of
0:15:42.033,0:15:46.320
Skovbjerg Frandsen et al. comes from,
and we will also reuse this.
0:15:46.320,0:15:50.422
The prefix-U_1 problem on the alphabet {0, 1} only asks if a given prefix contains a 0.
0:15:50.422,0:15:58.880
We conjecture that this problem cannot be
handled in constant time per update and query.
0:16:00.000,0:16:03.120
The reason why we believe that this is
not possible is because this problem
0:16:03.120,0:16:07.040
is connected to priority queues:
We can also see this, intuitively,
0:16:07.040,0:16:11.040
as maintaining a priority queue
of the positions containing zeroes
0:16:11.600,0:16:18.160
and comparing the current min to a query,
i.e., asking if the current smallest 0
0:16:18.160,0:16:20.800
is less than or greater
than an input prefix length.
0:16:21.680,0:16:23.840
So we do not know how to
show a lower bound on this
0:16:23.840,0:16:25.840
but we assume it cannot be done in constant time.
0:16:27.200,0:16:31.440
We then show that whenever a monoid is
not in the SG class, then there is a
0:16:31.440,0:16:36.880
modulo for which the prefix problem reduces
to the dynamic word problem for that monoid.
0:16:37.520,0:16:40.880
We also show that for monoids
that are in SG but not in ZG,
0:16:40.880,0:16:44.880
then we have a reduction from prefix-U_1
and hence a conditional lower bound.
0:16:46.400,0:16:51.440
Let me now say a few words about how our
results for monoids are extended to languages,
0:16:51.440,0:16:53.040
going via semigroups.
0:16:54.880,0:16:59.040
Semigroups are like monoids but they
might not have a neutral element.
0:16:59.040,0:17:04.320
We can of course define a dynamic word problem for
semigroups the same way that we did for monoids.
0:17:04.320,0:17:07.040
What is the difference between
monoids and semigroups when we
0:17:07.040,0:17:12.080
consider the dynamic word problem?
Well, consider first the language
0:17:12.080,0:17:18.080
Σ^* aa Σ^*, asking if a
word on a and b contains a factor aa.
0:17:18.720,0:17:24.720
This can clearly be maintained in constant time
by counting the number of factors of the form aa.
0:17:25.840,0:17:30.000
Whenever we update a position, we need at
most to consider two factors that have changed
0:17:30.000,0:17:31.840
and update the counts for these two factors.
0:17:33.040,0:17:37.280
If we add a neutral element, so if we
add a neutral letter to the language,
0:17:38.000,0:17:41.120
so that we have the possibility of
having e's between the two a's,
0:17:41.680,0:17:46.160
then this algorithm no longer works:
intuitively, we need to jump over the e's,
0:17:46.160,0:17:51.520
that can be in an arbitrary number.
So this problem would actually be in O(log log n)
0:17:53.120,0:17:56.800
and it will have a reduction from prefix-U_1
so we conjecture it cannot be
0:17:56.800,0:18:00.400
done in constant time.
So adding a neutral element
0:18:00.400,0:18:04.800
makes a difference, and so the study of monoids
where we asserted that there is a neutral element
0:18:04.800,0:18:07.760
is a coarser study than the
same problem on semigroups.
0:18:08.480,0:18:12.960
To study semigroups, a natural idea is
to look at the monoids that they contain.
0:18:13.680,0:18:18.480
A submonoid of a semigroup is simply a subset
of that semigroup that has a neutral element.
0:18:19.360,0:18:23.600
It is not difficult at all to see that
if a semigroup contains a submonoid,
0:18:24.160,0:18:28.320
then the dynamic word problem for that
monoid reduces to that of the semigroup,
0:18:28.320,0:18:31.200
simply by using the elements
corresponding to the monoid.
0:18:31.200,0:18:35.360
And so, any lower bounds that we have on
the dynamic word problem for the monoid
0:18:35.360,0:18:40.320
also apply to the semigroup. For this
reason, it's natural to study the classes
0:18:40.320,0:18:44.960
LSG of semigroups where all submonoids
are in the class SG that we identified.
0:18:45.680,0:18:50.560
We can show that LSG is actually equal
to SG as a variety of semigroups.
0:18:51.120,0:18:56.720
We can also show that our upper bound on
monoids in SG also applies to semigroups in SG,
0:18:56.720,0:19:01.040
Meaning that we have an O(log log n)
algorithm for semigroups in LSG,
0:19:01.040,0:19:06.400
and any semigroup not in LSG contains a submonoid
not in SG and so is covered by our lower bound.
0:19:07.680,0:19:13.360
The case of LZG, where all submonoids
are in ZG, is more complicated,
0:19:13.360,0:19:16.640
Because we can show that LZG
is in fact different from ZG.
0:19:17.360,0:19:19.920
However, it turns out that with a different,
0:19:20.560,0:19:25.040
very technical result, we can
characterize LZG in a different way
0:19:25.040,0:19:29.680
and show an O(1) upper bound on
semigroups in LZG. This completes
0:19:29.680,0:19:35.680
the picture, as semigroups not in LZG
contain a monoid not in ZG which is
0:19:35.680,0:19:40.080
covered by our reduction from prefix-U_1,
so is conditionally not in constant time.
0:19:41.840,0:19:45.280
Now let us move from semigroups
to languages and go back to our
0:19:45.280,0:19:49.200
original motivation of studying the dynamic
membership problem for regular languages.
0:19:50.960,0:19:54.240
This problem can be seen
as the dynamic word problem
0:19:54.240,0:19:59.200
for the syntactic semigroup of the language.
This is very similar to the transition monoid
0:19:59.200,0:20:02.800
from before but we do not assert
that we have a neutral element
0:20:02.800,0:20:05.840
to use the work that we did to
go from monoids to semigroups.
0:20:06.800,0:20:11.840
Sadly there is still a small difference:
when we work with a regular language,
0:20:11.840,0:20:16.000
not all elements of the syntactic semigroup
can be achieved as one single letter.
0:20:16.000,0:20:20.240
They can all be achieved by factors, but
these factors may not be one single letter
0:20:20.240,0:20:25.120
and so we cannot necessarily substitute them.
So we are in fact working with the syntactic
0:20:25.120,0:20:27.520
semigroup but only looking
at a subset of elements,
0:20:27.520,0:20:29.680
namely, the ones that can be
achieved by a single letter.
0:20:30.320,0:20:35.200
To remove this difficulty, and avoid any
problems with this kinds of substitutions,
0:20:36.000,0:20:39.600
we can work with the stable semigroup,
which intuitively groups together
0:20:39.600,0:20:43.840
letters into blocks of a constant size
designed to avoid these kinds of problems.
0:20:45.120,0:20:48.880
If we use this to define the classes QLZG and QSG,
0:20:48.880,0:20:55.280
the regular languages whose stable
semigroup is in LZG and SG respectively,
0:20:55.280,0:21:01.760
Then our results on semigroups extend to regular
languages. Specifically, if a language is in QLZG
0:21:01.760,0:21:06.480
then dynamic membership is in constant time.
If it is in QSG and not in QLZG
0:21:07.360,0:21:12.400
then we have an O(log log n) algorithm and
reduction from prefix-U_1 showing that it is
0:21:12.400,0:21:16.960
conditionally not in constant time.
And if the language is not in QSG,
0:21:17.680,0:21:21.680
then the dynamic membership problem has a
lower bound of Ω(log n / log log n),
0:21:21.680,0:21:24.080
So we have a tight bound of
Θ(log n / log log n).
0:21:25.600,0:21:29.120
Let me conclude the presentation by
giving some ideas for future work.
0:21:29.120,0:21:33.840
We have shown this conditional trichotomy for the
dynamic word problem for monoids and semigroups
0:21:33.840,0:21:37.200
and on dynamic membership for
regular languages. We would
0:21:37.200,0:21:42.160
be very interested in finding out how to show
a superconstant lower bound on the prefix-U_1
0:21:42.160,0:21:47.040
problem that we use in our conditional bounds.
For this, we would appreciate some help,
0:21:47.040,0:21:50.880
but we suspect that new techniques
are needed to show a bound of this kind.
0:21:52.320,0:21:56.240
We do not know what happens
between O(1) and O(log log n).
0:21:56.240,0:21:59.600
It could be the case that there are
intermediate classes of languages.
0:21:59.600,0:22:03.120
In fact, if we allow randomization
in our computation model,
0:22:03.120,0:22:06.080
we know that there are languages
in Θ(log log n), and that
0:22:06.080,0:22:11.600
there is a language in O(√(log log n))
so that there must be some subclasses to identify.
0:22:11.600,0:22:15.200
It would be interesting to characterize
these classes again algebraically.
0:22:16.480,0:22:21.280
We haven't studied in much detail the complexity
of the meta-dichotomy problem of determining
0:22:21.280,0:22:28.880
given a monoid, semigroup, or regular language,
how do we find out in which case it falls.
0:22:28.880,0:22:33.280
We believe that this is probably PSPACE-complete,
depending on the representation of the input,
0:22:33.280,0:22:34.320
but we haven't showed it.
0:22:35.840,0:22:40.240
Another question is what happens if we
study the prefix problem or infix problem
0:22:40.240,0:22:44.320
where we can query prefixes or infixes
instead of querying the entire word.
0:22:44.880,0:22:48.240
Our results give a characterization
also for these problems,
0:22:48.240,0:22:53.840
but the description of the languages is not
really natural and could be studied more closely.
0:22:54.560,0:22:58.320
And of course, we could generalize our
study to languages that are not regular,
0:22:58.320,0:23:00.480
and we do not know what happens in this case.
0:23:00.480,0:23:05.760
This is all I wanted to say.
Thanks a lot for watching.