Search

The recursive descent parsing method for the context-free grammars is extended for their generalization, Boolean grammars, which include explicit set-theoretic operations in the formalism of rules and which are formally defined by language equations. The algorithm is applicable to a subset of Boolean grammars. The complexity of a direct implementation varies between linear and exponential, while memoization keeps it down to linear. [ABSTRACT FROM AUTHOR]

Abstract. Synchronized extension systems (SE-systems, for short) are 4-tuples G = (V, L[sub 1], L[sub 2], S), where V is an alphabet and L[sub 1], L[sub 2] and S are languages over V. They generate languages extending L[sub 1] by L[sub 2] to the left or to the right, and synchronizing on words in S. Such systems appear naturally when considering stacks, queues, grammar-like generative devices, splicing systems, zigzag-codes etc. [ABSTRACT FROM AUTHOR]