Hi, I'm Georg Zeche, and I'm presenting joint work with Mika El-Kadiak and Dmitry Chistikov. And our paper is about rational subsets of Baumstag-Solytak groups.

And if that doesn't mean anything to you, there's a very simple way of phrasing the problem that we're looking at. So suppose you have a weird type of Turing machine that has a two-sided infinite tape, and each cell can contain either a digit 0 or a digit 1. So the machine has four types of instructions.

So on the one hand, you can move left, you can move to the right, you can increment at the current position, and you can decrement at the current position. So let's see what that means. So we start in the left state, and then we can take the move left transition, which means the hand moves to the left.

We can do that again, and then we can apply the increment operation, which means that the current cell, if it is currently 0, is turned to a 1. So then we move left again, and then we increment again, which means we turn the content to a 1 again. So then we go to the next state, and then we move to the right.

And then we increment again. And now the increment is done as in binary representations, which means if you add a 1 at that position, it means that this content 1 and the 1 in the next cell will be flipped to a 0, and the 1 right next to it will be turned to a 1.

So then we have this new configuration. Then we go to the next state, and we move to the left, and to the left again, and again, and again. And then we decrement. And now we decrement as in a binary expansion, which means that we treat this as the number 1000000.

And if we decrement, then we get the number all 1s, and the digit 1 that we had will be turned into a 0. Now the problem that we're looking at is, can we decide reachability?

So where does this problem come from? So first of all, we can represent the configurations of these machines in a different way. So first of all, we represent them as matrices, and we do this as follows. For the head position, so in this case, the head is at position 4. The initial position is position 0, and then we went four positions to the left.

And so in our matrix, we include 2 to the 4 to note the head position. And then for each of the 1s in the cell, we add a power of 2 to the top right entry of the matrix.

So we have a 1 at position 2, so we add 2 to the 2. And we have a 1 at position 0, so we add 2 to the 0. And then we have another 1 at position minus 1, so we add 2 to the minus 1. So in general, we do this not only for base 2, but for base q.

So then we obtain the following set of matrices. It's the matrices with 0 and 1 in the bottom row. And in the top row, we have q to the k for some number k, some integer k. And in the top right component, we have a rational number r, which is not only rational,

but it's contained in Z-adjoint 1 for q, which is the set of those numbers that have a finite q-ary representation. So it's the set of all quotients n over q to the i. So in other words, all rational numbers that you can write as a quotient with the denominator being a power of q.

So these groups, they form a group, these matrices, and this group is sometimes called Bs1q. And you can see that this group is generated by two particular matrices from the group. So q0,0,1 and 1,1,0,1.

And this is because of the following equations. So if you multiply the matrix q0,0,1 to a matrix from the group, then what change do you get? The topmost entry, the exponent in the topmost entry is incremented and the top right entry, the r, is not changed at all.

So which means if you interpret this as a configuration of the Turing machine, multiplying this matrix acts like the move left operation. And likewise, if you multiply the matrix 1,1,0,1, then the modification that you get is the top left entry is not changed

and the top right entry is incremented by q to the k, which is exactly what you do when you apply the plus operation in the Turing machine. So our group is this group Bs1q, as I just described it, with entries q to the k and r.

And the fact that we look at machines over this group is because we're looking at rational subsets. So a rational subset, that's a concept that applies to any group, and it's defined as follows. You take an automaton over the group, which is just a finite automaton whose edges are labeled by group elements,

and then it defines a subset of that group, namely the set of all elements on accepting paths. So if you have an accepting path in the automaton and you multiply all the elements of that path, that gives you an element of the group, and the set of all elements that you get in this way is the set accepted by the group.

And those are the rational subsets of your group. And the decision problem that we're looking at is the membership problem for rational subsets. So this is the following problem. You're given a rational subset and an element of the group, and you're supposed to decide, does that element belong to the rational subset?

So then you can see that the reachability problem that I mentioned in the beginning is exactly this rational subset membership problem for this group PS1Q. So now you see that the decision problem is a natural one. The question is, why would we look at this particular group of matrices? So the first reason we look at them are that these are well-known examples of groups that are definable with a single equation.

So more generally, the groups B as PQ are the groups generated by two generators that satisfy the equation that you can see here. And they've been introduced by Baumslack and Solita already in 1962 as examples of groups definable by a single equation with certain properties.

And they have, of course, received a lot of attention, and especially from an algorithmic perspective in the last decade. But there's a much more specific reason why we look at the rational subset problem here. So there's a long-standing open problem whether the rational subset membership problem is decidable for GL2Q,

which is the group of all invertible matrices, two times two matrices over the rational numbers. And they have a subgroup, namely the invertible matrices, two times two matrices with integer entries. And here decidability is well-known because essentially they have a similar description as we mentioned here for Turing machines.

But in that case, you essentially get pushed on automata. So here decidability is well-known. So if you want to approach the group GL2Q, what you can do is look at groups that sit in between GL2Z and GL2Q.

And there's a recent result by Dikat, Portapov, and Semukhin, which says that all of these groups, they're of two types. So these groups between GL2Z and GL2Q, they're either isomorphic to a group GL2Z and a direct product with some power of the integers,

or they contain the group B as one queue for some number q. Now these groups, GL2Z times Z to the k, they're very well-known to be decidable. So just as you can use pushed on automata there, you can use a slight extension to show that rational subset membership is decidable.

So if you want to make any progress in terms of a group that sits in between, B as one queue is the simplest example that you can look at. And the main result of our paper is that the rational subset membership problem in B as one queue is decidable and PSPACE-complete.

And in fact, we prove a stronger description of these rational subsets. And for that, I have to explain what a pointed expansion is. So if you have an element, you remember it's essentially a number in a queue-area representation that may have a fractional part,

but it also contains the head position. So this has a very natural representation as a word where you just list the digits, you have a decoration for the radix point of your queue area number, and you have a decoration for the current head position. So we have a little check mark here.

And our second main result is that for each rational subset, so in other words, for every reachability set of these Turing machines, the set of pointed expansions is an effectively regular set, which implies decidability in particular of the reachability problem.

And introducing this class of sets with regular pointed expansions is, in our opinion, the third main contribution of this paper. Because this is a very expressive class, it includes all the rational subsets. Furthermore, it's quite robust because they're closed under Boolean combinations,

as opposed to the rational subsets, they are not closed even under intersection. And we believe that they have a lot of applications. So the first example, of course, is that they show that not only is membership in rational subsets decidable, but emptiness of arbitrary Boolean combinations.

So you can decide equality, inclusion, and so on. And we also showed that recognizability is decidable for these PE regular sets. So, which means in particular that recognizability is decidable for rational subsets. And we believe that there are probably many more applications in the future.

So how do we show this effect of regularity? So one easy observation is that if you only look at thin runs, which means you bound the number of visits that a computation can make in each cell, then the set of reachable configurations is easily seen to be regular.

The construction is just like in two-way finite automata, you keep track of some crossing sequences, and then you just have to add k numbers in binary or in q-ary representation, which is a very classical construction.

So that's easy. And in fact, if you take any computation, you can bring it into that form by cutting out loops. So if you take any computation and you visit one particular cell more times than you have states, then of course one state has to repeat.

So in this case, in this cell where we noted the p, one state p has to repeat. So you can take the part of the run in between these two occurrences and remove it, and then you get a run that has fewer occurrences in that cell.

So of course you can do that and you get a thin run, but then you lose the effect of all the loops. So this is to say the difficult part of the construction is how to capture the effects of loops. And we do this by starting with the following trick.

We move loops. So suppose you have one loop that is applied in a certain position. So in this case, this is a loop that starts in p and ends in p. We also call this a p-loop. Then it moves to the left and it then increments, then moves to the right again and then decrements.

What you can do is you can apply this loop one position further to the right. So now you start one position further to the right and you execute this loop two times. So in case q is two. And in the general case, you do this q times.

Then the effect of these two computations will be exactly the same. The effect on the configuration. Because you apply the same operation twice, one position further to the right. Which means you can do the following decomposition of your run. First you remove loops.

But when doing that, you make sure that you keep the rightmost occurrence of each state. Which you can still do and get a thin remaining part of the run. And then each of the loops that you cut out, you move to the right, to the rightmost occurrence of the state where it started.

And because you kept that occurrence, you can do that. So now what you have is a thin run where you insert thin loops at at most q positions. So now since we only insert at the rightmost occurrence of each state,

we have a bounded number of positions where we would insert loops. And each of these loops that you would now insert has an effect in z-adjoint one over q. It has an integer part, which is the effect to the left of the head. But it also has a fractional part, which is the effect it has on the right of the head.

Now you can observe, since these are loops that we insert, that the set of possible effects is closed under addition, right? Because whenever we can insert two loops, we can just insert them one after the other.

So the set of possible effects forms a submonoid of z-adjoint one over q. And now there's a well-known fact that submonoids of the integers are all ultimately periodic. Which means that there's a certain period k, so that all numbers in the submonoid above a certain bound,

membership there only depends on the remainder modulo k, modulo this period k. So now one might hope that is an analogous fact for z-adjoint one over q.

So maybe since all these effects form a submonoid, we can conclude that they have a simple structure. Unfortunately, this group z-adjoint one over q has uncountably many submonoids. So there's no hope whatsoever that just saying, oh, this is a submonoid will imply that there's a simple description.

But then you might observe, okay, but our submonoid is generated by thin loops, right? Because they're all the loops that we move to the right are thin. But unfortunately, if you take a regular subset, then the set of effects that it generates can still be non-regular.

So this seems like the decomposition that we've chosen is perhaps completely inappropriate. So what else can we do? We apply the second trick, which is rebasing loops.

So here's what we do. You take a loop. Suppose it starts and ends at state p, and it also moves to the right. So it has an effect potentially in z-adjoint one over q. So it has a fractional part to its effect. Then what you do is you look at one of the states that are visited at the rightmost point in this run, in this loop.

So let's say r is the state at this rightmost point in the computation. Then we decompose this into two parts, the parts until this rightmost point and the part of the run afterwards.

So from r back to p. And then we execute these two parts in opposite order. So we start from r and go to p. So we execute the second part of the loop. And then we go back from p to r by executing the first part of the loop. Now you can observe that these two runs have the same effect.

Because we execute the same instructions just in a different order. And on the other hand, since now we start at a different position, while the old computation had an effect in z-adjoint one over q,

the new computation, the new loop has an effect in the integers. So this allows us to do a slightly different decomposition. So what we do is we take our run, we find a thin p-loop, and then we rebase it into an r-loop, where r is again a rightmost state in this loop,

which then has an effect in z. And then using the moving trick, we move it to the rightmost occurrence of r in the whole run. Because that's the one we're keeping while removing all the loops. And then this decomposition yields regularity of the set of all effects.

And this is because, as I said, each submonoid of the integers is ultimately periodic. And now at each point where we insert loops, so each rightmost occurrence of a state in the whole computation,

now there we insert effects of loops, which is now an ultimately periodic set. And ultimately periodic sets have regular sets of q-ary expansions. That's a very classic effect. So this was partly a non-effective construction that I showed,

because we said, since it's a submonoid, this will be an ultimately periodic set. But in fact, you can do this effectively. You have to compute certain greatest common divisors and certain bounds above which things are periodic. But this can all be done.

And in fact, one can compute a succinct finite automaton that is of polynomial size, which then yields PSPACE completeness. So to recap, our main result is that the rational subset membership is decidable and PSPACE complete.

And we've introduced the class of PE regular, which means regular pointed expansion sets, which is a robust class. It's very expressive because it includes the rational subsets and it has very nice closure properties. It's closed under Boolean combinations and other operations, which leads to further applications.

So first of all, even emptiness of Boolean combinations of rational subsets is decidable. Furthermore, it's decidable whether a given rational subset is recognizable, because this is decidable for PE regular sets. And we believe that there will probably be further applications of this concept in the future.

So thank you for your attention.