Quantifier Extensions of Multidimensional Sofic Shifts




Törmä Ilkka

2015

Proceedings of the American Mathematical Society

143

11

4775

4790

16

0002-9939

DOIhttps://doi.org/10.1090/proc/12628



Abstract. We define a pair of simple combinatorial operations on subshifts, called existential and universal extensions, and study their basic properties. We prove that the existential extension of a sofic shift by another sofic shift is always sofic, and the same holds for the universal extension in one dimension. However, we also show by a construction that universal extensions of twodimensional sofic shifts may not be sofic, even if the subshift we extend by is very simple.



Last updated on 2024-26-11 at 20:09