This was the joint session of Kolmogorov seminar and TCS Lab of HSE.
June 28, 2023
Speaker: Nikolay Vereshchagin
Title:"Goodman-Strauss theorem and its versions"
Abstract:
Goodman-Strauss theorem theorem states that for any substitution satisfying some conditions the family of substitutional tilings is sofic. Those conditions were not formulated explicitly and the proof is very long (about 70 pages). Therefore is very hard to verify it. Also Goodman-Strauss claims that under those conditions the family of hierarchical tilings is sofic. (Every substitutional tiling is hierarchical, but the other way around.) In an attempt to clarify the statement, Fernique and Ollinger formulated explicitly some requirements for substitutions, under which the family of hierarchical tilings its sofic. In the talk I will state Fernique and Ollinger theorem in all details and prove it in a specific interesting case.
