Narrow Results

Space-time diagrams of a one-dimensional cellular automaton can be visualized as half-plane arrays of symbols. The set of rectangular blocks extracted from such arrays forms a two-dimensional (picture) language. We initiate a study of cellular automata through the associated two dimensional languages by investigating cellular automata whose two-dimensional languages are factorial-local. We show that these cellular automata have the same characterization as one-sided cellular automata with SFT traces.

We study the two-dimensional pattern matching implemented using the deterministic two-dimensional on-line tessellation automaton. This restricted two-dimensional cellular automaton is able to simulate the Baker–Bird algorithm, which was proposed as the first algorithm for the two-dimensional pattern matching. We explore capabilities of this automaton to carry out the matching task against an arbitrary set of equal-sized patterns. To measure amount of resources needed to accomplish it, we introduce the pattern complexity of a picture language. We show that this complexity ranges from a constant to exponential one. All of these are illustrated by giving examples of two-dimensional on-line tessellation automata matching sets of patterns, describing general techniques of how to construct them and proving lower bounds on the pattern complexity of some picture languages as well as operations over them.

Two-dimensional general row jumping finite automata were recently introduced as an interesting computational model for accepting two-dimensional languages. These automata are nondeterministic. They guess an order in which rows of the input array are read and they jump to the next row only after reading all symbols in the previous row. In each row, they choose, also nondeterministically, an order in which segments of the row are read. In this paper, we study the membership problem for these automata. We show that each general row jumping finite automaton can be simulated by a nondeterministic Turing machine with space bounded by the logarithm. This means that the fixed membership problems for such automata are in NL, and so in P. On the other hand, we show that the uniform membership problem is NP-complete.

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".

The purpose of this paper is to propose a new notion of recognizability for picture (two-dimensional) languages extending the characterization of one-dimensional recognizable languages in terms of local languages and alphabetic mappings. We first introduce the family of local picture languages (denoted by LOC) and, in particular, prove the undecidability of the emptiness problem. Then we define the new family of recognizable picture languages (denoted by REC). We study some combinatorial and language theoretic properties of REC such as ambiguity, closure properties or undecidability results. Finally we compare the family REC with the classical families of languages recognized by four-way automata.

A method of learning pattern languages in time polynomial in the length of the pattern is introduced. The learning of certain picture languages can then be done by considering them as an interpretation of pattern languages. The learning of Tabled Regular k-Matrix languages describing arrays of symbols is also examined.

The emptiness problem for non-overlapping Basic puzzle grammars is shown to be decidable. An alternate proof of the decidability of the non-overlapping feature for basic puzzle grammars is given. Hierarchy among the various classes of puzzle languages is also established.

We use random context picture grammars to generate pictures through successive refinement. At any stage a picture consists of a shape divided into smaller shapes, each containing a variable or terminal. A variable may be rewritten according to a production of the underlying grammar. This entails either dividing the shape containing it into smaller shapes, or substituting a variable or terminal for it. For visualization purposes every terminal is associated with a color, and its shape is filled with that color. We show pictures generated with random context picture grammars, then concentrate on grammars which use forbidding context only and present a shrinking lemma for the corresponding languages.

We use random context picture grammars to generate pictures through successive refinement. At any stage a picture consists of a shape divided into smaller shapes, each containing a variable or terminal. A variable may be rewritten according to a production of the underlying grammar, which entails either dividing the shape containing it into smaller shapes, or substituting a variable or terminal for it. A production may depend on context randomly distributed in the intermediate picture. Context is classified as either permitting or forbidding, the former enabling the application of a production, the latter inhibiting it. For visualization purposes every terminal is associated with a color, and its shape filled with that color.

We show examples of pictures generated with random context picture grammars. Then we concentrate on grammars which use permitting context only and present a pumping lemma for the corresponding picture sets.

We use random context picture grammars to generate pictures through successive refinement. The productions of such a grammar are context-free, but their application is regulated — "permitted" or "forbidden" — by context randomly distributed in the developing picture. Grammars using this relatively weak context often succeed where context-free grammars fail, e.g. in generating the Sierpiński carpets. On the other hand it proved possible to develop iteration theorems for three subclasses of these grammars, namely a pumping–shrinking, a pumping and a shrinking lemma for context-free, random permitting and random forbidding context picture grammars, respectively. Finding necessary conditions is problematic in the case of most models of context-free grammars with context-sensing ability, since they consider a variable and its context as a finite connected array.

We have already shown that context-free picture grammars are strictly weaker than both random permitting and random forbidding context picture grammars, also that random permitting context is strictly weaker than random context. We now show that grammars which use forbidding context only are strictly weaker than random context picture grammars.

The emptiness problem for non-overlapping Basic puzzle grammars is shown to be decidable. An alternate proof of the decidability of the non-overlapping feature for basic puzzle grammars is given. Hierarchy among the various classes of puzzle languages is also established.

The purpose of this paper is to propose a new notion of recognizability for picture (two-dimensional) languages extending the characterization of one-dimensional recognizable languages in terms of local languages and alphabetic mappings. We first introduce the family of local picture languages (denoted by LOC) and, in particular, prove the undecidability of the emptiness problem. Then we define the new family of recognizable picture languages (denoted by REC). We study some combinatorial and language theoretic properties of REC such as ambiguity, closure properties or undecidability results. Finally we compare the family REC with the classical families of languages recognized by four-way automata.

A method of learning pattern languages in time polynomial in the length of the pattern is introduced. The learning of certain picture languages can then be done by considering them as an interpretation of pattern languages. The learning of Tabled Regular k-Matrix languages describing arrays of symbols is also examined.

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”.