Three-way automata on rectangular types over a one-letter alphabet (Q1075759)

Three-way automata (in short: TWA) are automata working on 2-dimensional tapes which can only move in the three directions: ''down'', ''right'' and ''left'', - but not in the direction ''up'' as the usual 2-dimensional automata, thus being somehow the generalization of 1-way finite automata. For deterministic TWA over rectangular tapes with a 1-letter alphabet a necessary criterion for a 2-dimensional language to be acceptable is given, which is based on the calculation of linear and bilinear forms by which such a language has to be representable as a set of pairs of non- negative integers. Using this criterion it is shown that the non- deterministic version of these TWA is more powerful than the deterministic one, and also that the disjointness and the inclusion problems are decidable for languages acceptable by such TWA, while these problems are proved to be undecidable if non-unary alphabets are allowed.