A1 Refereed original research article in a scientific journal
Quantifier Extensions of Multidimensional Sofic Shifts
Authors: Törmä Ilkka
Publication year: 2015
Journal: Proceedings of the American Mathematical Society
Volume: 143
Issue: 11
First page : 4775
Last page: 4790
Number of pages: 16
ISSN: 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.