A two-valued recurrent double sequence that is not automatic (Q2437852): Difference between revisions

A double sequence is an infinite (towards right and down) matrix consisting of symbols of an alphabet \(\Sigma\). A recurrent double sequence is determined by its given borders: zero's row, zero's column, and a finite function assigning to each inner position a symbol based on the three symbols contained in the left neighbor, the upper left diagonal neighbor and the upper neighbor of the position. A double sequence \(a\) on \(\Sigma\) is \(k,l\)-automatic, if there is a finite automaton with an input alphabet consisting of pairs of digits in base \(k,l\geq2\), respectively and the set of states partitioned to classes denoted by symbols from \(\Sigma\), such that processing a sequence of pairs encoding the two coordinates of a position (in base \(k,l\geq2\), respectively) in \(a\) leads to a state from the class denoted by the symbol of \(a\) in that position. The paper provides a recurrent double sequence \(t\) on a binary alphabet having constant borders, which is not \(k,l\)-automatic for any \(k,l\geq2\), while all its rows are periodic, the \(n\)-th row with minimal period of \(2^{n}\). It is documented that, among all recurrent double sequences on a binary alphabet with constant borders, there are 3 sequences analogue to \(t\), 4 other sequences with unknown automaticity properties, while all the remaining sequences are \(k,l\)-automatic (each for a suitable \(k,l\)).