Uniquely parsable array grammars for generating and parsing connected patterns

摘要

A uniquely parsable array grammar (UPAG) introduced by Yamamoto and Morita is a special kind of isometric array grammar (IAG) in which parsing can be performed without backtracking. Hence, we can use a UPAG as an efficient syntactic pattern recognition mechanism, if the pattern set is properly described by a UPAG. In this paper, we investigate the problem of describing and recognizing the set of all connected patterns using a UPAG formalism. As for the recognition of connected patterns, Beyer showed an efficient algorithm that operates on cellular automata. We show that his algorithm can be expressed very simply in the UPAG framework, and give two kinds of simple UPAGs that generate the set of all connected patterns.