Decidability and universality of quasiminimal subshifts

作者：

Highlights：

• We solve a conjecture of [3] by constructing a universal Z-subshift with finitely many subsystems.

• We give many examples of such subshifts, showing that this class is much richer than that of minimal subshifts.

• We show that, in contrast, N-subshifts with finitely many subsystems are decidable.

• We show that the model-checking problem of context-free languages is undecidable for minimal subshifts.

摘要

•We solve a conjecture of [3] by constructing a universal Z-subshift with finitely many subsystems.•We give many examples of such subshifts, showing that this class is much richer than that of minimal subshifts.•We show that, in contrast, N-subshifts with finitely many subsystems are decidable.•We show that the model-checking problem of context-free languages is undecidable for minimal subshifts.

论文关键词：Quasiminimal,Minimal,Subshift,Universality,Decidability

论文评审过程：Received 21 January 2015, Revised 17 February 2017, Accepted 31 May 2017, Available online 17 June 2017, Version of Record 7 August 2017.

论文官网地址：https://doi.org/10.1016/j.jcss.2017.05.017