Array Grammars, Patterns and Recognizers

The following sections are included:

• FOREWORD

• PREFACE

• CONTENTS

We define a syntactic model for generating sets of images, where an image can be viewed as an array over finite alphabet. This model is called image grammar. Image grammar can be considered as a generalization of classical Chomsky grammar. Then we study some combinatorial and language theoretical properties such as reduction, pumping lemmas, complexity measure, closure properties and decidability results. In terms of complexity measure, we give a strict infinite hierarchy. We also characterize these families in terms of deterministic substitutions and Chomsky languages.

Regular array grammars (RAGs) are the lowest subclass in the Chomsky-like hierarchy of isometric array grammars. The left-hand side of each rewriting rule of RAGs has one nonterminal symbol and at most one “#” (a blank symbol). Therefore, the rewriting rules cannot sense contexts of non-# symbols. However, they can sense # as a kind of context. In this paper, we investigate this #-sensing ability, and study the language generating power of RAGs. Making good use of this ability, we show a method for RAGS to sense the contexts of local shapes of a host array in a derivation. Using this method, we give RAGs which generate the sets of all solid upright rectangles and all solid squares. On the other hand, it is proved that there is no context-free array grammar (and thus no RAG) which generates the set of all hollow upright rectangles.

A two-dimensional grammar for generating all possible rectangles is presented and illustrated by examples. The time and space complexity analyses of this grammar together with a parallel context-free array grammar and a tree grammar are also presented. Generating pictures using two-dimensional grammars appears to be a fertile field for further study. The study of two-dimensional grammars has useful applications in region filling, pattern recognition, robotics, pictorial information system design and related areas.

The Siromoney matrix model is a simple and elegant model for describing two-dimensional digital picture languages. The notion of attaching indices to nonterminals in a generative grammar, introduced and investigated by Aho, is considered in the vertical phase of a Siromoney matrix grammar (SMG). The advantage of this study is that the new model retains the simplicity and elegance of SMG but increases the generative power and enables us to describe pictures not generable by SMG. Besides certain closure properties and hierarchy results, applications of these two-dimensional grammars to describe tilings, polyominoes, distorted patterns and parquet deformations are studied.

Two kinds of three-way isometric array grammars are proposed as subclasses of an isometric monotonic array grammar. They are a three-way horizontally context-sensitive array grammar (3HCSAG) and a three-way immediately terminating array grammar (3ITAG). In these three-way grammars, patterns of symbols can grow only in the leftward, rightward and downward directions. We show that their generating abilities of rectangular languages are precisely characterized by some kinds of three-way two-dimensional Turing machines or related acceptors. In this paper, the following results are proved. First, 3HCSAG is characterized by a nondeterministic two-dimensional three-way Turing machine with space-bound n (n is the width of a rectangular input) and a nondeterministic one-way parallel/sequential array acceptor. Second, 3ITAG is characterized by a nondeterministic two-dimensional three-way real-time (or linear-time) restricted Turing machine, a nondeterministic one-dimensional bounded cellular acceptor and a nondeterministic two-dimensional one-line tessellation acceptor.

We investigate the factors that make it difficult to generalize pushdown automata for one-dimensional strings to two-dimensional arrays. Then we resolve the problems and construct two-dimensional pushdown array automata (PDAA). The relationship between isometric context-free array languages and pushdown array automata is established. Several examples of array automata are presented, and a pushdown array automaton is tested on VAX8650/VMS using PASCAL.

We denote a two-dimensional deterministic (nondeterministic) one-marker automaton by 2-DM₁ (2-NM₁), and a three-way two-dimensional deterministic (nondeterministic) Turing machine by TR2-DTM (TR2-NTM). In this paper, we show that the necessary and sufficient space for TR2-NTMs to simulate 2-DM₁s (2-NM₁s) is n log n (n²), and the necessary and sufficient space for TR2-DTMs to simulate 2-DM₁s (2-NM₁s) is 2^{o(n log n)}(2^o(n2)), where n is the number of columns of rectangular input tapes.

Systolic pyramid automata accepting square arrays are defined. Homogeneous and semihomogeneous pyramid automata are shown to have equal power though regular pyramid automata are more powerful. Languages accepted by these automata are compared with languages generated by array grammars and languages accepted by one-way 2-D cellular automata. Hexagonal pyramid automata are also considered and are shown to accept some languages generated by hexagonal may grammars.

In a “coordinate grammar”, the rewriting rules replace sets of symbols having been given coordinates by sets of symbols whose coordinates are given functions of the coordinates of the original symbols. It was shown in 1972 that coordinate grammars are “too powerful”; even if the rules are all of finite-state types and the functions are all computable by finite transducers, the grammar has the power of a Turing machine. This paper shows that if we require the functions to be shift-invariant and the rules to be of bounded diameter, then such grammars do have a useful hierarchy of types; in fact, when we require that their sentential forms always remain connected, they turn out to be equivalent to “isometric grammars”.

We define a graph grammar called node-replacement graph grammar with path controlled embedding (nPCE grammars) which use a sequence of edges instead of the single edge to embed a newly replaced graph into the host graph, then show some relationships between two-dimensional “coordinate grammars” and nPCE grammars. We also suggest an extension of PCE grammars to describe “disconnected coordinate languages”.

In this paper, we introduce a new device called GL-systems (i.e. Grammar-Lindenmayer systems) for generating finite images. GL-systems are sequential/parallel systems in which the horizontal rules form a Chomskian grammar and the vertical rules form a DTOL system. We obtain hierarchical results of various types of GL-systems. We study some properties like, closure properties, combinatorial results, pumping lemma and decidability results. An algebraic characterization for GL-systems (with variation) is presented.

In this paper, we will define array grammars on the hexagonal grid. One of the advantages obtained from using the hexagonal grid is that each point has only one kind of neighbor. It is shown that the class of the context-free array grammars on the hexagonal grid includes the class of the rectangular ones even if their languages are restricted to the pictures connected on the rectangular grid. It is also shown that, in the monotonic case, they own the same class of languages jointly.

Iterative patterns can be described by the component pattern of iteration and their way of connection for iteration. It is shown that the shape of the component pattern can be a rectangle for any iterative pattern, which is called a tile. The tile is related to the basis of the parallel translation group of the iterative pattern. The component pattern itself is identified by a “tessera” which is defined by a non-degenerate colored tile. The tessera is a compact representation of iterative patterns. Some natures of tesseras and tiles are also discussed. The number of the kinds of distinct iterative patterns for each way of iteration is evaluated.

Language theoretic public key cryptosystems for strings and pictures are discussed. Two methods of constructing public key cryptosystems for the safe transmission or storage of chain code pictures are presented; the first one encrypts a chain code picture as a string and the second one as a two-dimensional array.