Matches in DBpedia 2014 for { <http://dbpedia.org/resource/Conjunctive_grammar> ?p ?o. }
Showing items 1 to 23 of
23
with 100 items per page.
- Conjunctive_grammar abstract "Conjunctive grammars are a class of formal grammarsstudied in formal language theory.They extend the basic type of grammars,the context-free grammars,with a conjunction operation.Besides explicit conjunction,conjunctive grammars allow implicit disjunctionrepresented by multiple rules for a single nonterminal symbol,which is the only logical connective expressible in context-free grammars.Conjunction can be used, in particular,to specify intersection of languages.A further extension of conjunctive grammarsknown as Boolean grammarsadditionally allows explicit negation.The rules of a conjunctive grammar are of the formwhere is a nonterminal and, ..., are strings formed of symbols in and (finite sets of terminal and nonterminal symbols respectively).Informally, such a rule asserts that every string over that satisfies each of the syntactical conditions representedby , ..., therefore satisfies the condition defined by .Two equivalent formal definitionsof the language specified by a conjunctive grammar exist.One definition is based upon representing the grammaras a system of language equations with union, intersection and concatenationand considering its least solution.The other definition generalizesChomsky's generative definition of the context-free grammarsusing rewriting of terms over conjunction and concatenation.Though the expressive means of conjunctive grammarsare greater than those of context-free grammars,conjunctive grammars retain some practically useful properties of the latter.Most importantly, there are generalizations of the main context-free parsing algorithms,including the linear-time recursive descent,the cubic-time generalized LR,the cubic-time Cocke-Kasami-Younger,as well as Valiant's algorithm running as fast as matrix multiplication.A number of theoretical properties of conjunctive grammars have been researched,including the expressive power of grammars over a one-letter alphabetand numerous undecidable decision problems.This work provided a basisfor the study language equations of a more general form.".
- Conjunctive_grammar wikiPageExternalLink conjunctive.
- Conjunctive_grammar wikiPageExternalLink conjunctive.pdf.
- Conjunctive_grammar wikiPageExternalLink conjunctive_overview_ct.pdf.
- Conjunctive_grammar wikiPageExternalLink TR012007.pdf.
- Conjunctive_grammar wikiPageExternalLink PresentationDLT.pdf.
- Conjunctive_grammar wikiPageExternalLink insight.php?id=tOkhotin06a.
- Conjunctive_grammar wikiPageID "3237776".
- Conjunctive_grammar wikiPageRevisionID "548514059".
- Conjunctive_grammar hasPhotoCollection Conjunctive_grammar.
- Conjunctive_grammar subject Category:Formal_languages.
- Conjunctive_grammar type Abstraction100002137.
- Conjunctive_grammar type Communication100033020.
- Conjunctive_grammar type FormalLanguages.
- Conjunctive_grammar type Language106282651.
- Conjunctive_grammar comment "Conjunctive grammars are a class of formal grammarsstudied in formal language theory.They extend the basic type of grammars,the context-free grammars,with a conjunction operation.Besides explicit conjunction,conjunctive grammars allow implicit disjunctionrepresented by multiple rules for a single nonterminal symbol,which is the only logical connective expressible in context-free grammars.Conjunction can be used, in particular,to specify intersection of languages.A further extension of conjunctive grammarsknown as Boolean grammarsadditionally allows explicit negation.The rules of a conjunctive grammar are of the formwhere is a nonterminal and, ..., are strings formed of symbols in and (finite sets of terminal and nonterminal symbols respectively).Informally, such a rule asserts that every string over that satisfies each of the syntactical conditions representedby , ..., therefore satisfies the condition defined by .Two equivalent formal definitionsof the language specified by a conjunctive grammar exist.One definition is based upon representing the grammaras a system of language equations with union, intersection and concatenationand considering its least solution.The other definition generalizesChomsky's generative definition of the context-free grammarsusing rewriting of terms over conjunction and concatenation.Though the expressive means of conjunctive grammarsare greater than those of context-free grammars,conjunctive grammars retain some practically useful properties of the latter.Most importantly, there are generalizations of the main context-free parsing algorithms,including the linear-time recursive descent,the cubic-time generalized LR,the cubic-time Cocke-Kasami-Younger,as well as Valiant's algorithm running as fast as matrix multiplication.A number of theoretical properties of conjunctive grammars have been researched,including the expressive power of grammars over a one-letter alphabetand numerous undecidable decision problems.This work provided a basisfor the study language equations of a more general form.".
- Conjunctive_grammar label "Conjunctive grammar".
- Conjunctive_grammar sameAs m.090g07.
- Conjunctive_grammar sameAs Q5161176.
- Conjunctive_grammar sameAs Q5161176.
- Conjunctive_grammar sameAs Conjunctive_grammar.
- Conjunctive_grammar wasDerivedFrom Conjunctive_grammar?oldid=548514059.
- Conjunctive_grammar isPrimaryTopicOf Conjunctive_grammar.