March 11, 2022

About the speaker

Sonya Cirlos is a Graduate Research Assistant, graduating this May with her Master of Science in Computer Science. Sonya teamed up with other Hispanic women in computer science and started a coding community, Frontera Devs, where they host technology and career preparation workshops for High School students in the Rio Grande Valley. She is also a User Experience Designer for a telemedicine start-up in Nigeria and plans to continue contributing to biotechnology and medical fields.

Assembling Patterned Lines with Freezing Tile Automata

Self-Assembly is the process by which small particles randomly agitate and combine through rules and local interactions to assemble into complex structures. Tile Automata is a model of self-assembly defined as a marriage of two models, Cellular Automata and Tile Assembly. This powerful fusion gives us the tools to study the strength of Tile Automata by relating the different existing models. Demaine et al. (2012) uncovered the power of the staged assembly model by developing a connection between the smallest context-free grammars and the staged self-assembly systems for one-dimensional strings and assemblies. In this work, we explore the strength of Tile Automata by studying the problem of finding the smallest tile automata system producing a one-dimensional patterned line assembly and comparing it to the well-known problem of finding the minimum context-free grammar. We introduce a restricted version of Tile Automata, where states are given designated color attribute and rule that a state must remain ”color-locked” (i.e. states cannot change color). We prove that this restricted Tile Automata model is at least as strong as Context-Free Grammars in describing strings.