CONFERENCE
Recording during the thematic meeting : «Geometric and Asymptotic Group Theory with Applications » the February 05, 2024 at the Centre International de Rencontres Mathématiques (Marseille, France)
Filmmaker : Guillaume Hennenfent
Find this video and other talks given by worldwide mathematicians on CIRM’s Audiovisual Mathematics Library: http://library.cirm-math.fr. And discover all its functionalities: – Chapter markers and keywords to watch the parts of your choice in the video – Videos enriched with abstracts, bibliographies, Mathematics Subject Classification – Multi-criteria search by author, title, tags, mathematical area
Uh thank you very much and indeed it’s a great pleasure to be here back in cm in this uh what looks like a wonderful week the small problem that I would like to be able to duplicate myself in two to follow the parallel sessions at the same time and I think
I’m not the only one in this situation so let’s go immediately to the definition and I hope this is readable even like this so take a group G acting on a uh okay I hope it was still G acting on a let’s see a topological space this is
Automatic if well first you have L an Omega Reg language so this means that there’s an automaton so L let’s [Applause] say infinite words over some alphabet a that’s a finite automat with a so that’s a graph with edges labeled by a oriented edges some initial States and some accepting
States now since you’re reading infinite words you cannot use the standard formalism of autometer and say that you stop in an accepting State because you never stop so the condition is sometimes called a bu condition which is you have to go infinitely many times through an accepting
State we’re going to see very soon some examples of this but for now let’s just take this as a definition it sounds very weird the first time you hear it but actually it’s a it’s a good notion so you need this L must be a coding so let’s say this is a
Bje morphism like this and for every group element its action must be automatic and this is expressed by the graph of the action but not graph in the sense of automatan graph in the sense of classical graph for a function so we’ll say that if you look at the the set of
Say by inverse of X by inverse of GX that’s really the graph xgx of the transformation G this must be Omega regular now it’s a pair of words so it’s in L cross L if you want is the graph so that’s in Omega a to the Omega cross a
To the Omega and that’s the same thing as a cross a repeated infinitely many times so that’s an automaton that accept space of letters rather than letters okay so that’s the definition and I want to go as quickly as possible to some examples so rather than make this
Uh two formul let me go immediately to an example and explain the example and why belongs to so the example the first example we can think about is that of automatic [Applause] groups a quick note is I prepared some slides but I forced myself not put it a
Single word in the slides only pictures because I realized that when when you put words in slides it goes too fast yeah uh okay so this is not going to work uh I hope that the slides and the text were both going to be readable at the same
Time yeah so here L is a language and if you look at this language we’ll see that it’s Omega regular it goes as follows it starts at the initial state which is marked by the arrow then it either goes up and follows the plus Branch then Lo
Loops at plus then reads a zero and then it goes to the rightmost state which is a loop at zero and which is the only accepting state or you can go on the bottom Branch you start reading minuses you do this for some time but after that
You have to stop and you have to go to the zeros so plus to the infinity or minus to the infinity are not accepted because they don’t go even a single time through the accepting state so the set of Expressions that you read is just some string of pluses
Perhaps zero awesome string of minuses zero but anyway it’s a finite string and then you go to the zero to the infinity so this language is naturally injection with the integers some number of pluses or some number of minuses so this is the language we’re talking about and if you had started by
An X well find some bje between Zed your favorite set and this language here which is just counting the number of pluses or minuses and then I claim that for every G acting by translation on the integers the transformation is Omega regular now it’s easy to see that it’s enough to
Check this for generators so we could insert generators here these are classical properties of Omega regular languages that you can multiply two languages you can take the cesan product you can intersect with a projection and in this way you get composition and you get inverses of anything so here the generator
Whoops is exactly this the generator T of oh so because of the slid you don’t see here that there was supposed to be written here Zed equal generated by T So T is the generator that’s the initial State and well how do you add one to a
Number written in unary well as long as you see pluses you skip them then when you see Zero you put an extra plus and you’re done or if you see some minuses you skip them and at some moment you erase then you erase the last one in
Fact you see because after that there would be some zeros sorry yes can I ask what’s Happening Here we are checking that if we have two infinite words that one has like one more plus than the other word exactly or one minus less exactly yeah so we are
Really realizing the operation plus one on numbers written in un and in case that the number was zero so it goes directly here then we have to replace the first Zero by a plus and we’re done note that this is is um deterministic in the sense that it
Defines the graph of a bje for every input word there will be exactly one output word that realizes the number plus one and conversely for minus one on the other hand if you just look at the inputs here you’re reading some minuses and here you’re looping with the minuses
And at some moment you make a choice either you’re going to write a minus as the result of the operation or you’re going to write a zero and you don’t know but afterwards you will know if you started to go on this Branch you must
Read some zeros as an input and if you stayed here you must read some minuses on input so it is well defined and it is deterministic but if you project to the input or the output it stop being of that form it needs some look ahead it
Needs to guess what the next symbol is okay so this class of um automatic groups is very important I guess the uh the names to quote are Canon Epstein uh can I give the whole names halt I have the feeling I’m forgetting somebody Patterson thirst or maybe Levy also so th
Uh studied these groups because they’re very important in the description of fundamental groups of three manifolds in fact uh so three defaults can be cut into pieces and the hyperbolic pieces will have an automatic group as a fundamental group and uh in fact the other geometries uh well some will some will
Not but the ones that cannot have alternative description by matrices so the different pieces can either be described as automatic groups or as linear groups that’s the the main thing about uh the group theoretical study of three manifolds okay so I guess this is about everything I wanted to say about
Automatic groups and if we think about our definition hopefully this will still fit on the board here we are making some specific choices these correspond to [Applause] our group is given with a generating set s and here I used plus and minus and zero for my language but they naturally
Corresponds to t t inverse and identity in the group and S has to be equal to a and then L is a normal form it’s a paded normal form for G so here we have words and here we have the group oh I should have said also x equal
G so you look at the group with a say regular right multiplication action and then the definition of automatic group well you can accept this one as a definition it just says that if you’re given a normal form for a group element you can get a normal form for
That element multiplied say on the right by a generator and then all the algorithmic properties of these things follow from the fact that you’re working with regular languages so this notion has been generalized to a what is called K graph automatic yes what if you do the same thing with
Regular langage is a finite word yes so the classical definition of automatic group is indeed given in terms of regular languages it’s bad because a star cross a star is not the same thing as a cross a star so you have to introduce some extra padding you have to
Look at this and then you have to put extra symbols on one side or on the other apart from that yes the theory have been explained in terms of actions on finite words what I’m going to say later does not work so I really believe this is the correct definition but for
Automatic groups yes both both are equivalent really so K graph automatic is just dropping the assumption that uh L is a normal form so that’s just saying that X is equal to G regular action so I guess the people who worked on this would be who ofic and I forgetting some
Names yes nikov thank you uh probably in the ’90s no more recently around so this is a more General notion there are some groups which have this property of being K graph automatic without uh being automatic in the sense of these people and they still have exactly the same good properties for
Example that the word problem is solvable in quadratic time the D function has quadratic complexity and so on also uh yes example means the pict right like something like the acting by a generator can be done in a regular way but you don’t need to know
That exactly you don’t need to know that in fact plus can be interpreted as T and zero is identity and minus is T inverse yeah exactly is given by like a sequence Ends by INF many when in fact in the notion of kaph automatic you could also have uncountable
Groups yeah well maybe just asking H for here yes it means that there is a symbol so s contains the identity and then the words are written with infinitely many identities yeah exactly of course I don’t know very yeah so I wanted to say just a few
Words on on something which is closely related to all of this which is a notion of an automatic structure so an automatic structure is just L an Omega regular language and a collection of [Applause] relations so R I can write the middle board because on the side the other room canot see
Oh I’ll do my best so need the example or uh we can turn it off for a second yes so an automatic structure will be L some omega regular language and relations are I in L to some n i fin many so really what I am defining here with my
Automatic uh action is if you’re given a finitely generated group you give yourself L and you give yourself the graph of n generators you give n relations with n i equal 2 which are exactly the graph describing some action and then you put some axioms for example
That this is a bje so for every X there exists a unique y such that X Y is in the graph and when you talk about an automatic graph you mean exactly this that there is a regular language describing the vertex set and the relation is an automatic langage people
Talk about graph Theory but there’s no such thing as graph Theory right it’s the theory of a single binary relation that’s exactly what graph theory is so you give yourself the structure in this s and there’s a fundamental uh [Applause] property uh that’s due to nerod and
Of I guess in the ’90s if I remember it’s 95 which is that uh the first [Applause] order theory is decidable for any automatic [Applause] structure so this means you write any statement for every X there exists a y such that for every Zed there in a one and then some complicated expression
Using the relations it’s decidable whether it’s true or false and in fact this can be extended because you can give yourself a counting uh predicates so you can also write the quantifier there exists uh n Solutions exactly to something there exists countably many solutions to something there exists uh uncountably
That’s supposed to be an Alf uh the cardinalities in this kind of structure can only be countable or Alf one sorry two to the ALF so you can add that kind of quantifier to ask the number of solutions to some to something you can see there can exist exactly countably
Many solutions to this problem and you also have um so there exist K mod n Solutions you can also add that kind of of a quantifier and it’s still decidable ask the number of solutions to this equation is odd that’s something that can be decided and it all comes down to the
Fact that lots of operations are decidable on Omega regular languages so essentially for every first order formula plus each of these extra quantifiers it’s possible to construct an Omega regular language that encodes it Solutions and then test for emptiness of this language okay so this is something that we that we will definitely
Use something else I wanted to say on this in this topic yes so two small remarks one which is that in the definition here of Pi the encoding sometimes can I quick to fix this you can try to make it um more General so you can you could ask that this is
Not a bje but that it’s just onto map and that it has a kernel a relation which are the things that are glued together and this should also be Omega automatic so you represent X as a quotient of a language you encode it but not in a
Unique way and then you must remember this nonunity in the form of an automatic so that’s a useful extension you can include lots of things in this manner I won’t go too much into the details of that extra notion it’s a different right it’s a different notion yes it’s not equivalent
For example here the X I can code has to be totally disconnected V so something that I wanted to actually ask just before you that is uh what is the role of the topology on on X because you could have for example a free action of G on some topological space but we
Know that there are a bunch of different free actions but then you when you use the when you have an action on L you can have still have a free action let’s say G is a free group well L has its topology too yes but ah so you are
Saying that L should inherit the topology oh yes yes this map this what the squiggle beans yes yes okay but so we are in no way encoding the topology in the we don’t have some kind of automatic encoding of the topology we are just saying that well the topology
Is part of the Omega structure for l i mean okay so we are saying that this projection has to be a homeomorphism where L is where L already has the counter topology exactly yes okay because and then in the more General notion uh the map pice should be continuous
Subjective and the kernel will be some closed relation expressing what is glut to what yeah exactly okay the other small remark is you could have wanted to Define an automatic structure for a group by saying that its multiplication table is automatic so maybe a quick warning sign we
Could we could but we don’t do it we could ask say x is equal to G and then you look at the graph maybe equal to l you look at the at the set of cripples XY Z say that X Y is equal to Z that’s really the whole multiplication table if you
Want and you could ask this to be Omega regular that’s a very interesting notion but it’s almost entirely disjoint from what we’re doing here so here we just say that the generators individually give automatic Transformations if we were to ask this and we add on top say that g is finally
Generated then this forces G to be virtually a billion you can really not go far beyond if the whole multiplication table is automatic okay it’s high time to get back to my examples so sorry about the uh back and forth can I do both no I cannot do both
Simultaneously okay so there’s a completely different notion on which consists now of really using the fact that the action doesn’t have to be free so here I give an example of Z squ here take as a language just all the words over zero and one no restriction at all
The full shift if you want and this is another example of an automatic action it’s still an action of T but now you see what T does is it works not in un but in binary so when it reads a one it prints a zero and this is
Just writing a carry and it keep keeps working on the binary expansion of a number and then when it sees a zero it drops the carry and then it goes to the identity so you understand very well that t is plus one in binary notation and in fact I had to force T
Also to be an accepting State because minus one is represented as an infinite string of ones which goes to the infinite string of zeros so you have to remain here okay and another example is uh this group generated by two Transformations a and u which are both of order two so a just
Flips the first bit Z goes to one one goes to zero and then it does the identity while U here skips all the ones it can then preserves the next zero and then there’s a flip by a and again you has to be accepting if I am to read an infinite collection of
On so this is the whole universe of automata groups and not automatic groups uh a theory that was developed by different people but certainly Al yosin was very important uh goruk and we’re going to get very soon to his work but isenberg also contributed to this topic as did um hungarians such as
Gek and if we focus on this example here of uh this transformation with a u that loops on the one we see U loops on the one and then transitions to this operation of flipping a bit and we can take this transformation and explode the U into three states called BC and
D and they do the same thing so they they loop on a one and then they preserve the next zero and then this was supposed to be Z goes to one one goes to zero so this is the a that we had before but you see that depending on the
Value modulo three of where we in the cycle we will sometimes do an A and sometimes not do anything and preserve so this is the goruk group that’s a famous example of a group which is infinite torsion so every element has finite order and also a group of intermediate
Growth so if you look at the number of group elements that you can write as a product of n generators you will get um a function which is something like e to the N to the 6 uh 7 76 so something fractional while some some stretch exponential so it’s become a very
Important example in group Theory because of lots of other properties that it has I don’t want to go too much in details on that just this is another example of an automatic action because the generators are given by autometer here the group is generated by four
Elements and I put them together in the same automaton but with a different starting state so the starting state is in is indicated by the letter that I wrote in it okay so that’s a special case of um Omega regular or automatic action and an important feature about
These is that they have no look ahead so not only do you act on infinite strings as the definition asks we also act on finite strings when we given a string of length n we know the result as a string of length n and I said more um intrinsically these are equ continuous
Actions equ continuous means that you will not have an unbounded look ahead that is necessary to describe the action and in fact here the look ahead is zero so there’s a subass consisting of uh fre actions or free regular actions there’s a subass consisting of equ continuous actions and these are the
Two examples that we’ve seen for now but I want to go to something yet different which is oh I had another example should I skip this one yeah the Basilica that’s another a good example to know so these automatic actions also come as uh ways of describing dynamical
Systems so in particular for complex dynamical systems and the example that I gave is this the Basilica is uh the fractal the Julia set corresponding to the map z s minus one the place where the map Z squ minus one is chaotic does not converge to infinity or to a cycle 0
Minus one and the shrier graphs so the graphs of the action in fact converge towards this fractor there’s a beautiful Theory by nikich that explains very well uh The Duality between expanding dynamical systems and group actions of this kind okay but now I want to get to uh examples which really use the
Infiniteness of the words on which you act and these will be substitutional sub shifts so again it’s unfortunate that we maybe I can move the mouse and we won’t see this oop no doesn’t this yeah okay so the next example I want to to describe is that of a substitutional sub
Shift here’s the one that does not read two consecutive ones it’s called golden mean golden mean sub shift and it corresponds uh to Fibonacci numbers and in fact just as we had before the binary encoding uh for the uh plus one operation action of Zed here
We can associate a number system in a plus one operation by encoding numbers as sum of Fibonacci numbers and when you express an integer as a sum of Fibonacci numbers the rule is you must never take two consecutive Fibonacci numbers that would be exactly taking two consecutive
Ones so this is forbidden and then every number has an essentially unique description in this manner well it helps to modify a little bit the system by encoding the strips of zeros by their parity so I’m never putting two consecutive zeros or two consecutive zero tick but I’m alternating z0 tick z0
Tick and then I do a one and then I do again some sequence of zeros alternating and so on it’s important to do this so as to be able to be to express the plus one operation and this is exactly the plus one operation so it starts
Here and when it seees 0 1 0 1 01 it keeps writing some zeros instead and then it drops a carry just as we had before and then it gets to the identity that we had before so expressed in base Fibonacci this is exactly the plus one operation that we had
Before also um for the inary addition okay so the again remove this so I guess I should Define what I am talking about so fix Sigma alphabet and f a substitution just for every letter in Sigma we give ourselves a word let’s take also an initial letter and when then we look at
Iterate of our letter under the substitution and let’s assume that uh this contain means all letters then you construct a sub shift X which is the set of sequences by infinite sequences indexed by Sigma such that all subwords are subwords of 5 to the N of Sigma 0 for for sum and big
Enough so the language of the sub shift namely the subwords that you see are exactly the subwords that you see inside iterates of this substitution so this has an obvious Z action which is just shifting a sequence on the other hand to understand it as a space is pretty complicated it’s
Just the set of words that that by this property so easy theorem this is an automatic action namely you can re-encode this as an Omega regular language in such a way that the plus one operation yes so if you give any any f is it clear that X is not
Empty uh uh so if you give any f it does not satisfy this property yes then you always can find a at least one yes contains sub yes well the action on the empty set is automatic But to answer your question directly yes it will be non empty because you can
Take all these fight to the end of Sigma 0er and extend them in an arbitrary Manner and then take an accumulation point so just by compacity so oh sorry so should be finite well if I say it contains all letters that’s automatic but yeah so this is an automatic action
This is not difficult and it’s essentially rephrasing what what has been done say using theic diagrams except that most of the theory Works uh very well in the measure category and here we really want on the nose uh the the spaces okay this is an automatic action and it’s very far from
The goruk kinds of actions because this is expensive every action on a sub shift is expensive meaning distinct points can be made at a bounded distance apart using the group action okay so now I want to make a remark that all the structures that we saw for
Now so all these automatic actions have some very nice extra property and these this is that the are bounded actions so for this I will just Define a bounded Aon uh so there will be the autometer representing the actions on say alphabet a cross a so these are such that there exists bound
B says that for every n if I look at the number of paths in the automaton from a start state to a non identity State this number of paths is at most to the bound B so I could flip back to my slides but if you remember for the adding machine
The F kakutani transformation there was just a single Loop reading ones and printing zeros for the U there was a single Loop reading ones and printing ones and then it went in finitely many steps to the identity for the Goro group there was a three cycle
Going through the ones and then this was feeding away to the identity and for the last example of the Fibonacci uh sub shift with a plus one uh operation there was a cycle going from 01 to 0 tick z0 tick and so you could remain on this
Cycle as long as you wanted but then you had to go to the identity so in all of these cases there is an for every n at most probably two or three paths that do not lead to the identity it’s also clear that this uh property of being bounded is preserved under
Composition and under inverses inverses is obvious you’re flipping input and output and composition where the the constants B will multiply at wor so this defines a subgroup so there are lots of interesting examples which are not bounded yes an identity state in a state in which all the inputs and the outputs are
The same so if you remember from the previous u pictures there was always a copy of the identity of the language so the language appears L appears as the diagonal reading and Out Printing the same symbol so the there’s always a sub automaton which is the diagonal of the
Language in you count the P they do not reach they do not end in the diagonal of the language assume that they recognize functional relations so I was talking just about automatic actions so yes it’s uh so if you take if you’re given an automaton which is not
Functional then perhaps it’s a defined transformation and this is perfectly fine for us or it could be something much more complicated and then probably it will not be bounded yeah okay and I think I want to give just one theorem on these so a general theorum which is that
If G acting on X is bounded automatic and let’s see also F generated so fin many generators which are all bounded to Transformations then the orbit relation is regular so I guess this will be expressed formally as well if I keep my coding that’s what we had before for the for
The graph but here I do this for all X in the language and for all g in the group so it’s presumably a countable Union of uh relations so this is regular and even more so it’s effectively Omega regular so there is a a procedure that given a bounded automatic
Action computes for you this relation so this is really if you forget the pi about the encoding if I look at the set of XY say that the orbit of G is equal to the orbit of Y or I could also ask the orbit uh well
X say to belong to the closure of the orbit y topologically or I could also ask so that’s the same thing as this of course there are lots of variance of this result so I have to write somewhere let’s switch this I should stop in 5 minutes right sorry more ah
Okay so maybe I can just say uh one word on a sketch of the proof so idea of proof and this is really inspired by a an article by Yan ve and is he here no ah okay I’m I think bondeno I’m not entirely sure about that
Well the question mark is is for the plus uh well the question mark is for the think here so uh they prove uh they have a very nice paper that proves that given a bounded action but in a in a more restrictive setting of no look ahead it’s decidable if the group is
Infinite but in fact uh the ideas are very close to what is necess here so you construct transducer so you construct an automaton for this relation R let’s call this orbit relation and the states will be graphs so it will be a Shri graphs so the re action of
G and at your initial State your graph just has finitely many generators that say how you act on a point and then you will recognize some pairs of letters a and this is exactly how you recognize the relation now if you’re at a graph that will look like this and some
Of these will be labeled by generators JH and so on to look at its transitions see under the letter AB the first thing you do is you multiply every state every vertex of this graph by the alphabet and then you put the transitions here as they should be say
Given by the automatan so these G and H are automata so they have a successor State under the input A or B also these graphs I should say must have a starting and ending vertex and then this choice of ab tells you which is the correct starting and which is the correct ending
Vertex and now because of the bounded condition when you look at the successive action in the automaton very often you will see identity in fact only 100 many times you will not see an identity so lots of these labels will be a one and you compress them and sometimes also these two things
Will not be in the same connected component and then you die there’s just no way of going from here to here by the action and then every once in a while you will also allow yourself some accepting transitions which are those where there is a single Loop there is
Single uh there is a single G and this is essentially the automaton okay so now in the last few minutes I want to show how this general fact is useful to answer uh quite a few important questions so in particular if you’re given a substitutional sub shift meaning you’re given the
Substitution and you’re just told well it is what is defined by this substitution it’s decidable so it’s decidable if the shift is empty but this was already known right you had asked this question yeah so we can decide other things we can decide if it’s periodic so every point is periodic
Let me put empty it’s decide if it’s a periodic it’s decidable if it’s minimal it’s def def decidable if it’s topologically transitive and quite a few other such things so for example to decide if it’s periodic well you have to ask is it true that for every X there are not
Infinitely many points that you can reach by The Zed action this is exactly a first order formula in the what was erased here it’s expressed with these counting quantifiers to know if it’s a periodic you have to say for every X there exist Omega points which are reachable under
The orbit relation this is also decidable thanks to these uh quantif I enhanced first order formulas minimal means every Point has a dense orbit so using this one that’s also directly testable because you can express it its first order topologically transitive means there exists an X for
Which the closure of the orbit is everything it’s also oh you’re here y Phil oh I was told that you were in the other room so this is Joint with uh with Y Gen right yes good so these are decidable but for complexity we have to go VI this crazy first
Order uh yes if you want to estimate the complexity in terms of how difficult the substitution is that’s a very interesting question and uh I haven’t thought enough about it I would expect this to be very difficult I mean does that need to be bound action or every substitution oh sorry I I
Completely forgot yes so that’s another theorem for substitutional sub shift action is bounded in fact I have sort of an idea uh it’s um it’s purely speculation but I expect in fact that a zed action on a canos set will be bounded if and only if it can be written as a
Substitutional sub shift and um here’s a notion that I have never seen in the literature but maybe some people on substitution know this take a substitution uh no so take a sub shift for which the language is the set of subwords of an ed0 L language right so this
Defines uh a sub shift if the EDT Z language happens to be just iterating one morphism then it’s substitutional so I would expect that a Z action on a can set is automatic if and only if it can be written as an ed0 L sub shift you have the Dynamics on the EDT
ZL by substitution I talked to Sebastian about this in the bus okay so uh yeah that’s uh that’s a general result and it gives you lots of decidability properties and yeah um another corer is that it’s [Applause] decidable if uh an element or if a g given say G again bounded automatic
So given this decidable I should switch the order given G in the group f g has infinite order so the order problem for a group of bounded Transformations is decidable and that’s again because well you look at the restricted action to the cyclic group generated by G and you use
Exactly these results so this was already known for uh equ continuous actions actions on trees with no look ahead but it’s true in this much more general setting and I want to give a warning sign also and this is uh myself plus Metrano which is that it’s undecidable for General automatic
Actions so a general automatic action can do so many things in different places that you can simulate during machines but with this bounded property you can only work in like One Direction and this is why the orbits structure is so much nicer uh I guess I’m out of time now
Okay thank you very much is there any questions Dima so would that be uh correct to say most likely at least true in One Direction so if you have um uh automatic action uh then uh say of uh finally generated group then uh every sh graph
Of this action will be uh automatic in the automatic structureal sense and then is that true in the opposite direction as well well if it’s a marked uh graph in which you remember which generator is which Edge then it’s exactly the same notion yes it’s exactly I could have defined them as frer
Automatic as opposed to K automatic if you want remember with labeled graphs you you have uh infinite family of the sh graph like for example talking about the group on on the boundary of Ro three right so there is uncountable number of TR graphs and then the original action
On this boundary will be I guess automatic if only if all the tri graphs will be automatic is that the case um so what what does it mean to say a shog graph is automatic as a graph as automatic structure okay so that’s not true that’s my question yeah it’s not
True because because um the sh graph that you look at if you just look at one graph requires you to take one Ray and then look at the action on that Ray yeah so in many cases uh this action on that let you recover what the ray
Is so different Tri graphs will be non-isomorphic and then you have uncountably many you have a Continuum of different Tri graphs so they cannot all be encoded by finite data as here what is true is that if you look at all the tri graphs of periodic sequences for
Example then this will be automatic if and only if the whole structure is automatic right so for example so you can get down to the countable world if you want uh if you consider just some automatan group and its action on the bound of the tree on this canet it will
Essentially never be automatic oh no the the whole action will be automatic yes just extracting a leaf is not automatic thank you and uh if you are given given uh the actions of finitely many group elements then is boundedness itself decidable well how are you given the uh the
Transformations uh I guess you are given the Omega these Omega regular yes so if you’re given an Omega regular language that defines the action you can minimize it and the minimal automaton will be bounded if the action is bounded so to test boundedness you’re already given the automaton you don’t have to do
Something crazy to find the bounded automaton for the element it will be the minimal one and it is easy to recognize whether it is bounded yes yeah yes it’s very easy because uh essentially you look at the adjacency Matrix of the graph and it must uh must have a single
Ion value one probably if there’s an igon value bigger than one it means you have connecting loops and if the multiplicity is bigger than when it means you have chained Loops so for example that kind of well this this it’s a finite structure on which you well there are lots of ways of
Saying it but you can uh say that will given two vertices you can ask if there’s a path from one to the other so you can compute strongly connected components and then the assertion is that there’s a single strongly connected component which is a cycle and then everything else feeds to another
Component which is the identity yeah an interesting notion which I have not exped BL enough would be something like relative boundedness so you’re given a sub automaton and you’re bounded on top of something so this is just looking at bounded on top of the identity but it it would make a lot of
Sense to look at bounded on top of something different and all of this is easily checkable by straightforward graph algorithms these all finite structures no more questions then is uh suffix sub shift on Z and automatic action oh yes yes so um if um so if you’re given a well first U sub
Shift of finite type h you can look at the one-sided shift and that’s automatically going to be a a sopic uh sorry um automatic action because the automat can just delete a letter and keep acting if you’re working with a two-sided shift you can also use a trick like this one
Pushing and pulling a conveyor belt kind of of of description um whether this fits in all cases you can then take quotients so take quotients of sub shifts of finite type so sopic shifts by putting an extra layer of encoding I’m slightly nervous whether it’s it will only work for n actions and
Not Zed actions but then definitely sopic for n actions is is part of this yes okay sorry so then the automaticity of the action is kind of easy but I guess that the structure of the space is encoded on that L which requires to be for sopic shift yeah you would you would
Uh directly have the L and the action will be by deleting a letter on L so um here the importance of substitutional sub shifts in connection to this story is that you have two Dynamics you have a translation Dynamics the Z action on sequences and you have a blow up
Or um The Substitute Dynamics in the other direction just as here you have autometer which read words and print words sort of at the same speed synchronously and you have the shifting operation like deleting a word which is moving one step further in the automat so a lot of the of the
Properties come from playing one of these action against the other and in particular some sort of a contraction property so when you want to encode uh say sub shifts or finite type or sopic shifts you’re not seeing both they they become the same action and you’re not going to gain much from expressing
Them in this language but they are part of it thanks uh then let’s thank Laur again that