RESTARTING TILING AUTOMATA
Abstract
We present a new model of a two-dimensional computing device called restarting tiling automaton. The automaton defines a set of tile-rewriting, weight-reducing rules and a scanning strategy by which a tile to rewrite is being searched. We investigate properties of the induced families of picture languages. Special attention is paid to picture languages that can be accepted independently of the scanning strategy. We show that this family strictly includes REC and exhibits similar closure properties. Moreover, we prove that its intersection with the set of one-row languages coincides with the regular languages.
The authors were supported by the Grant Agency of the Czech Republic: the first author under the project P103/10/0783 and the second author under the projects P103/10/0783 and P202/10/1333.
The paper is an extension of [12], giving full proofs of all presented theorems.
| Remember to check out the Most Cited Articles! |
|---|
|
Check out these Handbooks in Computer Science |
