A1 Journal article – refereed
Quantifier Extensions of Multidimensional Sofic Shifts

List of Authors: Törmä Ilkka
Publication year: 2015
Journal: Proceedings of the American Mathematical Society
Volume number: 143
Issue number: 11


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.

Internal Authors/Editors

Last updated on 2019-21-08 at 23:06