Fundamenta Informaticae · 1996 · 16 citations · 2 references
ComputingComputer ScienceComputational LinguisticsNatural Language ProcessingSyntaxGrammarGrammar DerivationRegular LanguagesSyntactic AnalysisSyntax AnalysisContext-free GrammarsDerivation TheoryLanguage GenerationSyntactic Derivation
Continuing the work begun in [14], we consider contextual grammars (as introduced in [6] with linguistic motivation) with parallel derivations, in which the whole current string participates to a derivation step in the sense that it is splitted into substrings to which contexts are adjoined in a parallel manner. The generative power of such grammars is investigated, when the parallelism is total or partial, and when the selection of contexts is limited to strings in sets of a given type (finite, regular etc.) Then we consider the languages consisting of strings which cannot be further derived (we call them blocking languages). Some open problems are also formulated.
2