We resolve several long-standing open questions regarding the power of various types of finite-state automata to recognize "picture languages," i.e. sets of two-dimensional arrays of symbols. We show that the languages recognized by 4-way alternating finite-state automata (AFAs) are incomparable...

Using mostly elementary considerations, we find out who wins the game of Domineering on all rectangular boards of width 2, 3, 5, and 7. We obtain bounds on other boards as well, and prove the existence of polynomial-time strategies for playing on all boards of width 2, 3, 4, 5, 7, 9, and 11. We...

In dynamical systems such as cellular automata and iterated maps, it is often useful to look at a {\it language} or set of symbol sequences produced by the system. There are well-established classification schemes, such as the Chomsky hierarchy, with which we can measure the complexity of these...

We study the computational complexity of solving equations and of determining the satisfiability of programs over a fixed finite monoid. We partially answer an open problem of [4] by exhibiting quasi-polynomial time algorithms for a sub-class of solvable non-nilpotent groups and relate this...

We examine the one-humped map at the period-doubling transition to chaos, and ask whether its long-term memory is stack-like (last-in, first-out) or queue-like (first-in, first-out). We show that it can be recognized by a real-time automaton with one queue, or two stacks, and give several new...

We study the algebraic conditions under which two cellular automata can commute. We show that if either rule is permutive, i.e., one-to-one on its leftmost and rightmost inputs, then the other rule can be written in terms of it; if either rule is a group, then the other is linear in it; and if...

We consider various extensions and modifications of Shannon's General Purpose Analog Computer, which is a model of computation by differential equations in continuous time. We show that several classical computation classes have natural analog counterparts, including the primitive recursive...

We calculate the generating functions for the number of tilings of rectangles of various widths by the right tromino, the L tetromino, and the T tetromino. This allows us to place lower bounds on the entropy of tilings of the plane by each of these. For the T tetromino, we also derive a lower...

Given an initial distribution of sand in an Abelian sandpile, what final state does it relax to after all possible avalanches have taken place? In d = 3*, we show that this problem is P-complete, so that explicit simulation of the system is almost certainly necessary. We also show that the...

Shannon's General Purpose Analog Computer (GPAC) is an elegant model of analog computation in continuous time. In this paper, we consider whether the set G of GPAC-computable functions is closed under iteration, that is, whether for any function f(x) 2 G there is a function F(x; t) 2 G such that...