A1 Vertaisarvioitu alkuperäisartikkeli tieteellisessä lehdessä
Quantifier Extensions of Multidimensional Sofic Shifts
Tekijät: Törmä Ilkka
Julkaisuvuosi: 2015
Journal: Proceedings of the American Mathematical Society
Vuosikerta: 143
Numero: 11
Aloitussivu: 4775
Lopetussivu: 4790
Sivujen määrä: 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.