Sierpinski Triangles

I have already introduced my approach to graph parsing via Graph Parser Combinators on this blog recently. This time I provide a nice sample parser; at RTA I will present the concepts and how the used framework can actually be realized in the functional-logic programming language Curry.



The example I am going to discuss are Sierpinski triangles. This graph language is particularly interesting for several reasons. First of all, Sierpinski triangles are beautiful thanks to their self-similarity. Second, they can be described by a hyperedge replacement grammar as shown in the image below. And finally, depending on the generation, Sierpinski triangles grow exponentially in size making them an ideal candidate for tool benchmarks (see Taentzer et al. '08).



Note that the given grammar does not ensure that only regular Sierpinski triangles are generated. For instance, the graph shown below is also a member of its language. Regularity can be enforced by using a parallel replacement mechanism or control structures, though (see Habel, Kreowski '87).



Let's see how we can map this grammar to a parser using our framework:

s (Succ depth) (n1,n2,n3) = s depth (n1,n4,n5) *> 
                            s depth (n4,n2,n6) *>
                            s depth (n5,n6,n3)
                            where n4,n5,n6 free
s One (n1,n2,n3) = edge ("line",[n1,n2]) *> 
                   edge ("line",[n2,n3]) *>
                   edge ("line",[n3,n1]) 

sierpinski = s depth (n1,n2,n3) 
             where depth,n1,n2,n3 free

The actual mapping is described in the RTA paper, but you will probably have no difficulties figuring out how it works. Note that inner nodes of a production are guessed using free variables. The regularity is ensured by a parameter depth. As a parser these functions are not very interesting, since parsing can't be done efficiently. However, due to the logic nature of the framework, it can be directly used for the generation of Sierpinski triangles. Compared to other tools (see Taentzer et al. '08) this generation even is reasonably efficient. For instance, we have generated a Sierpinski triangle of generation 11 with nearly 200.000 edges in about a minute.

Further reading:

• Sierpinski Triangle for the AGTIVE 2007 Tool Contest


• G. Taentzer et al., Generation of Sierpinski triangles: A case study for graph transformation tools. In: Applications of Graph Transformations with Industrial Relevance AGTIVE ’07 (eds.: A. Schürr, M. Nagl, A. Zündorf), International Workshop Kassel, Oct. 10-12, 2007, LNCS, Springer, 2008


• A. Habel, H.-J. Kreowski, Pretty Patterns Produced by Hyperedge Replacement, Proceedings of the International Workshop on Graph-Theoretic Concepts in Computer Science, LNCS, Springer, 1987


• S. Mazanek, M. Minas, Functional-logic Graph Parser Combinators. To appear in Proceedings of 19th International Conference on Rewriting Techniques and Applications (RTA 2008), LNCS, Springer, 2008