A1 Vertaisarvioitu alkuperäisartikkeli tieteellisessä lehdessä
Conjunctive grammars with restricted disjunction
Tekijät: Okhotin Alexander, Reitwiessner Christian
Kustantaja: ELSEVIER SCIENCE BV
Julkaisuvuosi: 2010
Journal: Theoretical Computer Science
Tietokannassa oleva lehden nimi: THEORETICAL COMPUTER SCIENCE
Lehden akronyymi: THEOR COMPUT SCI
Numero sarjassa: 26-28
Vuosikerta: 411
Numero: 26-28
Aloitussivu: 2559
Lopetussivu: 2571
Sivujen määrä: 13
ISSN: 0304-3975
DOI: https://doi.org/10.1016/j.tcs.2010.03.015
Tiivistelmä
It is shown that every conjunctive language is generated by a conjunctive grammar from a special subclass, in which every nonterminal A has at most one rule of the general form A -> alpha(1)& ... &alpha(n), while the rest of the rules for A must be of the type A -> w, where w is a terminal string. For context-free grammars, a similar property does not hold (S.A. Greibach et al. (1992)[3]). If it is furthermore required that each rule A -> w has a nonempty w, then a substantial subfamily of conjunctive languages can be generated, yet it remains unknown whether such grammars are as powerful as conjunctive grammars of the general form. (C) 2010 Elsevier B.V. All rights reserved.
It is shown that every conjunctive language is generated by a conjunctive grammar from a special subclass, in which every nonterminal A has at most one rule of the general form A -> alpha(1)& ... &alpha(n), while the rest of the rules for A must be of the type A -> w, where w is a terminal string. For context-free grammars, a similar property does not hold (S.A. Greibach et al. (1992)[3]). If it is furthermore required that each rule A -> w has a nonempty w, then a substantial subfamily of conjunctive languages can be generated, yet it remains unknown whether such grammars are as powerful as conjunctive grammars of the general form. (C) 2010 Elsevier B.V. All rights reserved.