Quantifier Extensions of Multidimensional Sofic Shifts
: Törmä Ilkka
: 2015
: Proceedings of the American Mathematical Society
: 143
: 11
: 4775
: 4790
: 16
: 0002-9939
DOI: https://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.