A1 Refereed original research article in a scientific journal
Cutting corners
Authors: Salo Ville
Publisher: Academic Press
Publication year: 2022
Journal: Journal of Computer and System Sciences
Journal name in source: J. Comput. System Sci.
Volume: 128
First page : 35
Last page: 70
ISSN: 0022-0000
eISSN: 1090-2724
DOI: https://doi.org/10.1016/j.jcss.2022.03.001(external)
Web address : https://doi.org/10.1016/j.jcss.2022.03.001(external)
Self-archived copy’s web address: https://research.utu.fi/converis/portal/detail/Publication/177554087(external)
We define a class of subshifts defined by a family of allowed patterns of the same shape where, for any contents of the shape minus a corner, the number of ways to fill in the corner is the same. For such a subshift, a locally legal pattern of convex shape is globally legal, and there is a measure that samples uniformly on convex sets. We show by example that these subshifts need not admit a group structure by shift-commuting continuous operations. Our approach to convexity is axiomatic, and only requires an abstract convex geometry that is “midpointed with respect to the shape”. We construct such convex geometries on several groups, in particular strongly polycyclic groups and free groups. We also show some other methods for sampling finite patterns, and show a link to conjectures of Gottshalk and Kaplansky.
Downloadable publication This is an electronic reprint of the original article. |