DOI

As a direct continuation of the earlier research on conjunctive grammars - context-free grammars equipped with intersection - this paper introduces a new class of formal grammars, which allow the use of all set-theoretic operations as an integral part of the formalism of rules. Rigorous semantics for such grammars is defined by language equations in a way that allows to generalize some techniques from the theory of context-free grammars, including Chomsky normal form, Cocke-Kasami-Younger recognition algorithm and some limited extension of the notion of a parse tree, which together allow to conjecture the practical applicability of the new concept.

Original languageEnglish
Title of host publicationLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
EditorsZoltan Esik, Zoltan Fulop
PublisherSpringer Nature
Pages398-410
Number of pages13
ISBN (Electronic)3540404341, 9783540404347
DOIs
StatePublished - 2003
Externally publishedYes

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume2710
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

    Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

ID: 78926202