The #a = #b Pictures Are Recognizable

摘要

We show that the language of pictures over {a,b} (with a reasonable relation between height and width), where the number of a's is equal to the number of b's, is recognizable using a finite tiling system. This means that counting in rectangular arrays is definable in existential monadic second-order logic.