A uniquely parsable unification grammar (UPUG) is a formal grammar with the following features: (1) parsing is performed without backtracking, and (2) each nonterminal symbol can have arguments, and derivation and parsing processes accompany unification of terms as in Prolog (or logic programming). We newly introduce a uniquely parallel parsable unification grammar (UPPUG) by extending the framework of a UPUG so that parallel parsing is also possible. We show that, in UPPUG, parsing can be done without backtracking in both cases of parallel and sequential reductions. We give examples of UPPUGs where a given input string can be parsed in sublinear number of steps of the length of the input by parallel reduction.

A uniquely parsable grammar (UPG) introduced by Morita et al. is a kind of generative grammar, in which parsing can be performed without backtracking. It is known that UPGs and their three subclasses form the "deterministic Chomsky hierarchy. " In this paper, we introduce three kinds of normal forms for UPGs, i.e., Type-0, Type-1 and Type-2 UPGs by restricting the forms of rules to very simple ones. We show that the upper three classes in the deterministic Chomsky hierarchy can be exactly characterized by the three types of UPGs.

This paper studies the propagation and crossing of signals in cellular automata whose cells are updated at random times. The signals considered consist of a core part, surrounded by an insulating sheath that is missing at the side of the core that corresponds to the direction into which the signal moves. We study two types of signals: (1) signals by which the sheath at the left and right sides of the core advance first in a propagation step, followed by the core, and (2) signals by which the core advances first, followed by the sheath at its left and right sides. These types naturally arise in, respectively, Moore neighborhood cellular automata with semi-totalistic rules and von Neumann neighborhood cellular automata with symmetric transition rules. The type of a signal has a profound impact on the way signals cross each other, as we show by the construction of one signal of each type. The results we obtained should be of assistance in constructing asynchronous circuits on asynchronous cellular automata.