TY - GEN

T1 - Conjunctive grammars with restricted disjunction

AU - Okhotin, Alexander

AU - Reitwiener, Christian

N1 - Funding Information: Supported by the Academy of Finland under grant 118540. Corresponding author. Tel.: +49 931 31 86664. E-mail addresses: alexander.okhotin@utu.fi (A. Okhotin), reitwiessner@informatik.uni-wuerzburg.de (C. Reitwießner).

PY - 2009

Y1 - 2009

N2 - 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 ? a1&an, 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, W. Shi, S. Simonson, "Single tree grammars", 1992).

AB - 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 ? a1&an, 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, W. Shi, S. Simonson, "Single tree grammars", 1992).

UR - http://www.scopus.com/inward/record.url?scp=67650705988&partnerID=8YFLogxK

U2 - 10.1007/978-3-540-95891-8_39

DO - 10.1007/978-3-540-95891-8_39

M3 - Conference contribution

AN - SCOPUS:67650705988

SN - 3540958908

SN - 9783540958901

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 425

EP - 436

BT - SOFSEM 2009

T2 - 35th Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2009

Y2 - 24 January 2009 through 30 January 2009

ER -