37 citations · 53 across the 16 of their papers we have counts for
5 papers · 1 filter
Plane-Walking Automata
Ville Salo, Ilkka Törmä
In this article, we study classes of multidimensional subshifts defined by multihead finite automata, in particular the hierarchy of classes of subshifts defined as the number of h…
Complexity of Conjugacy, Factoring and Embedding for Countable Sofic Shifts of Rank 2
Ville Salo, Ilkka Törmä
In this article, we study countable sofic shifts of Cantor-Bendixson rank at most 2. We prove that their conjugacy problem is complete for GI, the complexity class of graph isomorp…
Subshifts, MSO Logic, and Collapsing Hierarchies
Ilkka Törmä
We use monadic second-order logic to define two-dimensional subshifts, or sets of colorings of the infinite plane. We present a natural family of quantifier alternation hierarchies…
Trace Complexity of Chaotic Reversible Cellular Automata
Jarkko Kari, Ville Salo, Ilkka Törmä
Delvenne, Kůrka and Blondel have defined new notions of computational complexity for arbitrary symbolic systems, and shown examples of effective systems that are computationally un…
Quantifier Extensions of Multidimensional Sofic Shifts
Ilkka Törmä
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 exten…