A Three-Dimensional Uniquely Parsable Array Grammar that Generates and Parses Cubes
Katsunobu Imai, Yukio Matsuda, Chuzo Iwamoto, Kenichi Morita · Electronic Notes in Theoretical Computer Science · 2001
A uniquely parsable array grammar (UPAG) introduced by Yamamoto and Morita is a subclass of isometric array grammar (IAG) in which parsing can be performed without backtracking. Hence, we can use a UPAG as an efficient two-dimensional pattern recognition mechanism, if the pattern set is properly described by a UPAG. Furthermore, since a UPAG admits parallel parsing, it can also be used as a formal framework for parallel pattern recognition. In this paper, we show UPAG is also useful to generate and recognize three-dimensional patterns. We construct a UPAG that generate any size of cubes. This UPAG can recognize cubes in linear time of the length of its side by maximum parallel reduction. To construct the grammar, we have made a tool for designing three-dimensional IAG.