Related papers:  

Uniquely Parallel Parsable Unification Grammars

Jia Lee, Kenichi Morita

Abstract:
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.

IEICE Transactions on Information and Systems (2001),
Vol. E84-D, No. 1, pp. 21-27

Generation and Parsing  of Morphism Languages by
Uniquely Parallel Parsable Grammars

Jia Lee, Kenichi Morita

Abstract:
In this paper, we give a simple sufficient condition on morphism languages, and show
that every such morphism language can be parsed efficiently in parallel by a UPPG.
We show that the Fibonacci and Thue-Morse languages, which are
instances of such languages, can be parsed in logarithmic time in parallel by UPPGs.

Preliminary version appeared  in Words, Semigroups, and Transductions,
Festschrift in Honor of Gabriel Thierrin (2001),
(Eds: M. Ito, G. Paun, S. Yu), World Scientific, Singapore, 303-314