A1 Vertaisarvioitu alkuperäisartikkeli tieteellisessä lehdessä

Conjunctive grammars with restricted disjunction




TekijätOkhotin Alexander, Reitwiessner Christian

KustantajaELSEVIER SCIENCE BV

Julkaisuvuosi2010

JournalTheoretical Computer Science

Tietokannassa oleva lehden nimiTHEORETICAL COMPUTER SCIENCE

Lehden akronyymiTHEOR COMPUT SCI

Numero sarjassa26-28

Vuosikerta411

Numero26-28

Aloitussivu2559

Lopetussivu2571

Sivujen määrä13

ISSN0304-3975

DOIhttps://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.



Last updated on 2024-26-11 at 20:36