• TUCS Publication Series
• How to Publish in TUCS Series
• Publication Search
• Publication Graph
• Publication Input
• Publication Input Guide
• JuFo Browser

Conjunctive grammars with restricted disjunction

Alexander Okhotin, Christian Reitwiessner, Conjunctive grammars with restricted disjunction. TUCS Technical Reports 915, Turku Centre for Computer Science, 2009.

Abstract:

It is shown that every conjunctive language is generated by a conjunctive grammar of a special form, in which every nonterminal $A$ has at most one rule of the general form $A \to \alpha_1 \& \ldots \& \alpha_n$, while the rest of the rules for $A$ must be of the type $A \to w$, where $w$ is a terminal string. For context-free grammars, a similar property does not hold (S. A. Greibach, W. Shi, S. Simonson, "Single tree grammars", 1992).

Files:

Full publication in PDF-format

BibTeX entry:

@TECHREPORT{tOkRe08a,
  title = {Conjunctive grammars with restricted disjunction},
  author = {Okhotin, Alexander and Reitwiessner, Christian},
  number = {915},
  series = {TUCS Technical Reports},
  publisher = {Turku Centre for Computer Science},
  year = {2009},
  keywords = {conjunctive grammars, single tree grammars, normal form, language equations},
  ISBN = {978-952-12-2151-4},
}

Belongs to TUCS Research Unit(s): FUNDIM, Fundamentals of Computing and Discrete Mathematics

Edit publication