Narrow Results

We consider the minimal height of a derivation tree as a complexity measure for context-free languages and show that this leads to a strict and dense hierarchy between logarithmic and linear (arbitrary) tree height. In doing so, we improve a result obtained by Gabarro in [7]. Furthermore, we provide a counter-example to disprove a conjecture of Čulik and Maurer in [6] who suggested that all languages with logarithmic tree height would be regular. As a new method, we use counter-representations where the successor relation can be handled as the complement of context-free languages.

A similar hierarchy is obtained considering the ambiguity as a complexity measure.

We propose a new system of generating array languages in parallel, based on a partitioned cellular automaton (PCA), a kind of cellular automaton. This system is called a PCA array generator (PCAAG). The characteristic of PCAAG is that a”reversible” version is easily defined. A reversible PCA (RPCA) is a backward deterministic PCA, and we can construct a deterministic “inverse” PCA that undoes the operations of the RPCA. Thus if an array language is generated by an RPCA, it can be parsed in parallel by a deterministic inverse PCA without backtracking. We also define two subclasses of PCAAG, and give examples of them that generate geometrical figures.

In this paper, we will introduce some variations of tree adjoining grammars which generate the sets of quadtrees as their languages and investigate their effectiveness to describe the sets of digital images. In those variations, two types of parallel operations, multicomponent and multifoot adjoining, will be introduced. Both of them are quite different parallelisms from ordinary ones (such as Indian parallelism of grammars, or L-systems).

We propose a new system of generating array languages in parallel, based on a partitioned cellular automaton (PCA), a kind of cellular automaton. This system is called a PCA array generator (PCAAG). The characteristic of PCAAG is that a “reversible” version is easily defined. A reversible PCA (RPCA) is a backward deterministic PCA, and we can construct a deterministic “inverse” PCA that undoes the operations of the RPCA. Thus if an array language is generated by an RPCA, it can be parsed in parallel by a deterministic inverse PCA without backtracking. We also define two subclasses of PCAAG, and give examples of them that generate geometrical figures.