Remote Access Proceedings of the American Mathematical Society
Green Open Access

Proceedings of the American Mathematical Society

ISSN 1088-6826(online) ISSN 0002-9939(print)

Request Permissions   Purchase Content 
 

 

Quantifier extensions of multidimensional sofic shifts


Author: Ilkka Törmä
Journal: Proc. Amer. Math. Soc. 143 (2015), 4775-4790
MSC (2010): Primary 37B50
DOI: https://doi.org/10.1090/proc/12628
Published electronically: April 10, 2015
MathSciNet review: 3391035
Full-text PDF

Abstract | References | Similar Articles | Additional Information

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 two-dimensional sofic shifts may not be sofic, even if the subshift we extend by is very simple.


References [Enhancements On Off] (What's this?)


Similar Articles

Retrieve articles in Proceedings of the American Mathematical Society with MSC (2010): 37B50

Retrieve articles in all journals with MSC (2010): 37B50


Additional Information

Ilkka Törmä
Affiliation: TUCS – Turku Centre for Computer Science, University of Turku, Finland
Email: iatorm@utu.fi

DOI: https://doi.org/10.1090/proc/12628
Received by editor(s): January 9, 2014
Received by editor(s) in revised form: June 10, 2014, and July 23, 2014
Published electronically: April 10, 2015
Additional Notes: This research was supported by the Academy of Finland Grant 131558
Communicated by: Nimish Shah
Article copyright: © Copyright 2015 American Mathematical Society