-Automata on Square Grids
Palash Sarkar
Computer Science Unit,
Indian Statistical Institute,
203, B.T. Road,
Calcutta 700035, India
Abstract
In this paper -automata on square grids are studied using a special sequence of polynomials called the
-polynomials. It is shown that for
,
, which rules out totally irreversible
grids for
. Results are presented on the roots of
-polynomials which have direct relevance to the reversibility question for
-automata on square grids.