Exploring Formal-Language Syntax with Multiway Systems

Hello everyone, and welcome to season 2.5, episode 2 of the Wolfram Student Podcast. I'm Sam, your host, and this is the Wolfram Student Podcast, where every fortnight we dive into a new innovative project done by high schoolers using the Wolfram language. So for this episode, let's welcome Navier, who will be discussing his project on multi way systems. Hi, Navier.

Hello.

Yeah, cool. Welcome to the podcast. Do you want to first give us like a quick intro for yourself so you know your grade, where you're from?

Yeah, sure. Hello. I'm nave. I'm from New Delhi, India. I'm. I'm an incoming freshman at Caltech and I've been coding in the Wolfram language for the past year and a half. I, I was a part of the Wolfram High School summer research program and after that I became a student ambassador. So that's, that's just a brief history of what I've been doing with the Wolfram language.

Yeah, that's really wicked. Do you want to give us like a few more details about, you know, what your experience was at camp and also, you know, what, what kind of work you do as a student ambassador?

Sure. So camp at camp, I was in the linguistics, computational linguistics group and my project was exploring the computational dynamics of formal language syntax using multi way systems. And, and so the project that we're going to be discussing today is sort of an extension of that, basically discussing the growth and complexity of multi way systems. And as a student ambassador, I've been posting a lot on Wolfram community and just in general, sort of spreading the word about Wolfram language to my friends and colleagues.

Yeah, that, that sounds really cool. Our trademark question then, I guess that we ask everyone who comes on the podcast, what would you say your favorite Wolfram function is?

My favorite Wolfram function is actually from the function repository. It's called the Knuth Bendix Completion Algorithm.

I'm going to be honest, that sounds incredibly complex and I've got no clue what it is.

Yeah, so it's sort of just this function and I'll actually be sort of discussing it later on as well. But it's this function that creates a confluent multi way system within a finite number of steps. And usually you, you use a lot of steps to sort of code that in any other language, but it's quite good that I can just have a one line function for that in the virtual language.

Yeah, I think that stuff also definitely want to like, you know, the best benefits of Wolfram language. How easy it is to model things and, you know, just run a line of code and then get a really nice graphic out of it. Okay, so first, before we start going into your project, can you first give us a quick summary of what it's about?

Sure. So multi way systems in the Wolfram language refer to sequence rules in which multiple states can be permitted at any stage. And what I've decided to do in this project is explore how you can change multi way systems and sort of look at the growth rate of multi way systems after you introduce a minimal change to them. And so I've introduced the optimal move problem for multi way systems and discussed what that means. Additionally, I've also created an algorithm that sort of works faster than traditional algorithms, such as the Knuth Appendix completion algorithm in the Wolfram language. And yeah, that's about it.

That's really impressive. I'm. Yeah, I'm really excited to see what you've done. So yeah, just take us through it.

Sure. So here's a brief introduction to multi way systems. Multi way systems are defined as substitution systems in which multiple states are permitted at any stage. And in the Wolfram language we can implement it using the resource function multi way system. So here's an example of a multi way system. You start with ABA and then you apply these rules and you can see that you get various states at the same time. And here's another example of a multi way system. It was found in the New Kind of Science book by Stephen Wolfram. And just implementing it using the Wolfram language is fairly easy. Now, before we actually discuss what the optimal move means for multi based systems, we have to define two very important notions of causal invariance and confluency. And they might sound like scary terms, and that's because they probably are, but getting an intuitive grasp from them isn't that difficult. So causal invariance is a property of multi way graphs whereby all possible parts yield the same isomorphic causal graph. And okay, that might sound scary again, but getting a grasp on it, as I'll explain, is quite easy. Essentially, when causal invariance exists, every branch in the multi way system must eventually merge together. And causal invariance is a core property associated with relativistic invariance and some other physics project things which I'm not too sure about. But it's just cool to see how you could relate causal invariance to physics. Now we demonstrate the property of causal invariance over here. Let's look at this multi way system with AA goes to ABA and AAA goes to B and you start with aabaa. And so when you start at the first step, it's just AABAA goes to these two states. And as you increase the number of steps you realize that this multi way system remains stagnant. And every branch in this multi way system has eventually merged into a singular branch. And therefore if we look at the causal graph instances of this multi way system, it's just a blank state. And that's how we know that this multi way system is actually causal invariant. We can verify this by using the causal invariant Q function in the Wolfram language multi way system. And instead of states graph over here, we just replace it with causal invariant Q. And that just sort of says true for all values from 2 to 10 and it'll say true for all the other values as well, because the multi way system is stagnant. Now confluence is a property of multi way systems describing the term in which a system can be rewritten in more than one way to yield the same result. And here's an example of confluent substitution system. So let's say we have 11 +9 times 2 +4 and both of them are in parentheses. So it doesn't matter whether you evaluate from the right first and then from the left or from the left first and then from the right, ultimately you yield the same result which is 120. And that's because of the parenthesis. So you can sort of look at confluency in a term rewriting system as a thing in which no matter which rule you apply this, you're going to get the same result. And that brings us to the optimal move for a multi way system. The optimal move in multi way systems is defined as a singular change to the end state of a rule in a multi way system that leads to the maximal change in the number of vertices. Now again this sounds quite scary, but let me demonstrate what this means. We have this rule. S goes to a blank string, S goes to B and S goes to aab. And we know that the symbols in this are simply S, A and B. So therefore the list of possible moves for this rule would would simply be changes to the right hand side of the rule. So here are the possible moves. You can change one state at a time. So let's say we want to change, change this rule first we can insert S to this to get S goes to S, S goes to B and S goes to aab. Now let's say I want to change this rule. Next we'll do it as we'll consider that as a separate move. So the next move would be S goes to a blank string, S goes to sb, and S goes to aab. So you can see that it's essentially just a singular change in the right hand side of a substitution system. It's just an insertion of one of the symbols to the right hand side one at a time. And the reason we're doing it one at a time is because if we didn't limit it, well, you could just continue adding the symbols infinitely many times and that would just yield an infinite multi way rewriting system. And no one wants that. So that's why we've limited it to one at a time. Now that we have coined what constitutes a move, we can try and explore the optimal move for a given substitution system. And so we can define the optimal move in the following two ways. We can either define the optimal move in terms of vertices, which is the move that leads to the maximum number of vertices, or we can define the optimal move in terms of edges, that is the move which leads to the maximum number of edges. And in this project, I've considered the optimal move to be the one that leads to the maximum number of vertices. And a further exploration will be done on the maximal number of edges. So now that we have the definition for the optimal move, we can actually begin coding in the Wolfram language. Here's a quick helper function that helps us insert a string into another string at every possible position. So SA gets inserted before the string at the first position, at the second position, so on and so forth. And now we move on to the main functions. This is the list of possible moves function which lists all the possible moves. As we saw here earlier, the findoptimal moves function finds the optimal move in terms of vertex count. This brings us to the most important part of the project, which is the Knuth Appendix Completion algorithm. Before we introduce the Knuth Appendix Completion algorithm, we must introduce the word problem, which is a very famous problem in computational mathematics. The word problem essentially asks, are these two real numbers or functions or grammars or mathematical statements equivalent? And a very deep result in computational mathematics is that in many important cases, the word problem is undecidable. You cannot decide whether two given expressions are equivalent with respect to a set of rewriting rules. That is undecidable. Moreover, in general, determining whether a substitution system is confluent or not is also undecidable. But combining these two things, we get quite a beautiful algorithm. The Knuth Pendix Completion Algorithm, named after Donald Kenneth and Peter Bendix is a semi decision algorithm for transforming a set of equations into a confluent term rewriting system. It effectively solves the word problem in mathematics. Note that this is a semi decision algorithm. So that does not mean that it works all the time. There are cases where the Knuth Bendix algorithm will fail, but it works marvelously well for a lot of cases.

Can you give an example of one case where the Knuth Bendix algorithm wouldn't give you a result?

Sure. So if you already have a confluent term rewriting system, then the Knuth Bendix algorithm would just return an empty string. And so that's not really useful for, for us, but, but that would be quite useful for us to check whether a string rewriting system is confluent or causal invariant or not. In fact, one of if you look at the causal invariant function in the Wolfram language in the description, it's written that one of a sufficient condition for a substitution system to be causal invariant is that the Knuth Bendix completion algorithm results empty string. Yeah. Yeah.

Okay.

Yields.

Yeah, it's really interesting. Thank you.

Yeah. And so the main hypothesis that we have now is, well, firstly we define longest canonical, which is a function that finds the substitution system that takes the longest time to attain confluency in terms of length using the Knuth Bendix completion algorithm. So note that we have a substitution system. We have a list of possible moves. We have the optimal moves that we can find using a brute force algorithm. And then we have the longest canonical function which determines which of the the substitution systems made after a move take the longest time to attain confluency. Now the main hypothesis of this research is that the substitution system that takes the longest time to attain confluency is also the substitution system that grows the fastest, with some exceptions that I'll explain later on. And the following function check equivalency simply checks whether the define optimal moves and longest canonical are equivalent to each other. And now we can actually go and check the optimal moves for different substitution systems. Now we start by checking the optimal moves for different types of grammars. There are regular grammars, context free grammars, context sensitive grammars, and recursively innumerable grammars as defined by the Chomsky hierarchy. And we start by listing out the optimal move for each one of them. So we have a rule over here and we find the optimal moves and the longest canonical and both of them are the same. And just to verify this, you could just do something like this. And yeah, both of them are the same. However, we also notice the fact that the find optimal moves function returns two different strings substitution systems for the third step. But the longest canonical function only returns a single substitution system. And the reason for this inequivalence is simple. One of the substitution systems grows faster than the other. But the number of vertices produced by their multi way system is the same after three iterations. But S goes to A, S, S, S goes to B, A, A goes to blackstring and A goes to ca. The first one overtakes the second one after the third iteration. Therefore, you can see that there's an equivalence in this. However, as the states continue to grow as you increase the steps, the inequivalence does. The equivalence works. And now we check the equivalence for other regular grammars as well. This is another regular grammar, and so is this. And the equivalence yields true in both cases. We now move on to context free grammars and we do the same thing. We have a context free grammar and an initial string S, and we check the equivalency which yields true. We also check the equivalency for another context free grammar and another one, and basically all of them yield true. We do the same for context sensitive grammars and the equivalency also yields true. And for recursively enumerable, it also yields true. And now we define the pessimal move. So we've defined the optimal move to be a move that yields the maximum number of vertices. Well, the pessimal move is the exact opposite. It's a substitution system that yields the minimum number of vertices. However, it seems as if the fine decimal move function does not coincide with the substitution system that takes the shortest time to attain confluency, which indicates that there isn't a one to one bijection between the substitution systems that take time to attain confluency and their growth rates, which is sort of disappointing, but that's just the way it rolls. And so now that we've looked at all of this, we can actually look at the growth rate of multi way systems. So the growth rate of multi way systems have been studied extensively by Orek Zeschke, who's a Wolfram researcher. He determined that finding the growth rate of a multi way system in general is undecidable. And he also divided the growth rates of multi way systems into various classes such as polynomial, exponential, super exponential and intermediate growth, which is faster than polynomial but slower than exponential. And so the hypothesis that I currently have is that the optimal move boosts the growth rate of a multi way system from polynomial and intermediate growth to exponential growth rate and from exponential growth rate to super exponential growth rate. And we can sort of verify this by taking an example of this rule which has a constant growth rate before the optimal move and after the optimal move you can see that it has an exponential growth rate. We can plot them on the same graph now. And you can see after optimal move the growth rate increases dramatically and before the optimal move it's just a constant growth rate. And we did the same.

Yeah, sorry, one sec, I might have missed it when you said it earlier, but is there like what particular reason I guess do you believe that is your hypothesis that the optimal move boosts it up by a level? In a sense?

Well, just based on empirical data I haven't been able to prove it conclusively.

As a. Yeah, but like what relationship would cause this? I guess or like even if it's like a rough hypothesis, if you.

So, so the reason this would be possible is you're looking at a. Firstly you have a substitution system and then you have a bunch of moves that you can make to it and then you're selecting the one that grows the fastest. So it sort of makes sense that even a small change in the substitution system would yield unimaginable growth after a certain time. And that's sort of what like chaos theory tells us.

It's that the butterfly effect kind of thing.

Yeah, yeah, yeah. Simple changes to deterministic systems can yield to unimaginable results. And so I like to think of it as that. But yes, I haven't been able to conclusively prove it yet. That's just on the basis of some evidence that I've gathered.

Okay, yeah, so it's really cool. Thank you.

Okay, so moving on, just some more. Okay, this, this rule is actually quite interesting. So this rule grows with an exponential growth rate. You can see 6, 12, 24. So, so the growth rate is just 3 into 2 to the n. And after the optimal move the optimal move seems to grow way faster than even an exponential growth rate. And I've classified these as super exponential growth rate. Moving on, we now discuss a fast implementation of the multi way system. Note that this implementation of the multi way system is only relevant for determining what the states are. It doesn't have any fancy sort of functionality such as determining whether a multi way system is causal invariant or not or displaying the states graph of the multi way system. It's just for determining the states of a multi way system. But actually it works Very, very fast. The fast implementation, as you can see, is way faster than the resource function implementation. And even the resource function implementation downloaded locally and the resource function implementation downloaded locally without graphs, all of them are slower than the fast implementation of the multi way system. So that was quite interesting. And now we can sort of check the equivalency of multi way systems of different signatures. So a signature can sort of depend on, well, given a signature, you can sort of get a substitution system. So if you have two goes to one and two goes to three, and you have two characters, that means that the first first string will be of length two, it'll go to a string of length one, and the second string will also be of length two and it'll go to a string of length three. And the two over here denotes the letters that you're using. You're using just the first two letters of the Alphabet, which is A and B. If you were to change it to three, you could use A, B and C. And the rules would increase, the number of rules would increase. We now check the equivalency for all of them, and we realize that there are cases where the equivalency does not hold. And these cases occur when the rule is already causal invariant. As we discussed before, a rule being causal invariant causes some problems with the Appendix completion algorithm. And therefore we realize that the equivalency breaks down when the rules are causal invariant. We now modify the equivalence condition to check when rules are causal invariant. And so we check the equivalency for 2 goes to 1, 3 goes to 2, 2 with ABA and all of them are true. And we check the equivalency for the same function at another step. And over here we get all the cases where the equivalency does not hold are indeed causal invariant. There is a certain case where the equivalency does not hold and the rule is not causal invariant. And that's simply when the multi way system stagnates after one iteration. And therefore it poses a problem for the find optimal moves function. We can now modify our hypothesis to state that the optimal move function is equivalent to the longest canonical function if the substitution system is A not causal invariant and B not confluent or not stagnant after some time. And in this last section we aim to generalize the properties that we have observed so far. We now propose the question, given a set of different substitution systems, which one takes the longest time to attain confluency? Well, we realized that the fine optimal moves function is quite a useful heuristic for determining the substitution systems that take the longest time to attain confluency. And if you look at data that's given by the Knuth Mendix completion algorithm and data that's given by the Find optimal moves algorithm, both of them yield the same. Therefore, we can see that our hypothesis holds for certain small values and it's time to check it for different signatures and to optimize the functions. And the rest of it is just checking it on different signatures with different characters and checking the sort of speed of the optimal move function. And something that's quite interesting. The Knuth Mendix completion algorithm is approximately 100 times slower in terms of time taken than the optimal move heuristic. And you can see this on by this preliminary test, but also by subsequent graphs, you can see the Knuth Bendix completion algorithm takes exponentially more time compared to the optimal moves heuristic in every case. And just for fun, I downloaded the Knuth Mendix Completion algorithms notebook locally and it still grows exponentially faster compared to the optimal move heuristic, which is quite good. Which means that the optimal move heuristic is way faster than the traditional knittmandix completion algorithm. So in order to determine which substitution system grows the fastest, instead of using the traditional knittmandix completion algorithm, we can instead use the optimal moves functionality and reduce the time by a lot. And that's it. Some more functions, including this one signature where there were more than 44,000 substitution systems. After checking more than 65,000 rules, the hypothesis still holds. The substitution system that grows the fastest is the one that takes the longest time to attain confluency. And additionally, the optimal moves heuristic is way faster than than the Knuth Appendix Completion of the. And so that was my project.

Well, yeah, that's really cool actually. It's wicked to see, you know, how you come up with this hypothesis and then you test it across 65,000 cases and find one that works really well. So I don't know, really impressive.

Thank you.

Um, so after seeing and having done this entire project, what do you think are going to be your next steps with Wolfram? Any future projects either in just this or, you know, any topic that comes to mind.

So, so the next step is to conclusively prove the hypothesis holds using group theory and a lot of, a lot of computer science and mathematics. There's a whole branch of a computer science of term rewriting systems. So the next step would be to formally prove that the heuristic works for a lot of cases and just has trivial exceptions. And yeah, that's, that's sort of my next step and I'll definitely be utilizing the Wolfram language for that and formalizing proofs in it.

Yeah, that would be really cool. Once you do that, please do show it to us over here at the podcast because I would love to see a formal proof of this. But yeah, I think that's really cool. Thank you so much for coming onto the podcast. We really appreciate it and yeah, we had a great time hearing about your project.

Yeah, thank you for having me.

Thanks for listening to this episode of the Wolfram Student Podcast. I hope you learned something new and took away insights from today's discussion. If you want to be featured in a future episode, fill out the form@tinyurl.com WSP-S2 interest and be sure to tune back in a month's time to hear our next episode. Once again, thanks for listening to this episode of the Wolfram Student Podcast.