Complex Systems

-Automata on Square Grids Download PDF

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.