<http://dbpedia.org/resource/Smallest_grammar_problem>	<http://dbpedia.org/ontology/wikiPageWikiLink>	<http://dbpedia.org/resource/Useless_rules> .
<http://dbpedia.org/resource/Smallest_grammar_problem>	<http://dbpedia.org/ontology/abstract>	"\u30C7\u30FC\u30BF\u5727\u7E2E\u3068\u5F62\u5F0F\u6587\u6CD5\u7406\u8AD6\u306B\u304A\u3044\u3066\u3001\u6700\u5C0F\u6587\u6CD5\u554F\u984C\uFF08\u3055\u3044\u3057\u3087\u3046\u3076\u3093\u307D\u3046\u3082\u3093\u3060\u3044\u3001\u82F1\u8A9E: smallest grammar problem\uFF09\u306F\u3001\u4E0E\u3048\u3089\u308C\u305F\u6587\u5B57\u5217\u3092\u751F\u6210\u3059\u308B\u6700\u5C0F\u306E\u6587\u8108\u81EA\u7531\u6587\u6CD5\u3092\u898B\u3064\u3051\u308B\u554F\u984C\u3067\u3042\u308B\u3002\u6587\u6CD5\u306E\u30B5\u30A4\u30BA\u306F\u3001\u751F\u6210\u898F\u5247\u306E\u53F3\u5074\u306E\u30B7\u30F3\u30DC\u30EB\u306E\u6570\u3068\u3057\u3066\u5B9A\u7FA9\u3059\u308B\u3068\u3057\u3066\u3044\u308B\u8005\u3084\u3001\u305D\u308C\u306B\u898F\u5247\u306E\u6570\u3092\u52A0\u3048\u308B\u3068\u3059\u308B\u8005\u3082\u3044\u308B\u3002\u3053\u306E\u554F\u984C\uFF08\u306E\u6C7A\u5B9A\u7248\uFF09\u306FNP\u5B8C\u5168\u3067\u3042\u308B\u3002"@ja .
<http://dbpedia.org/resource/Smallest_grammar_problem>	<http://dbpedia.org/ontology/wikiPageWikiLink>	<http://dbpedia.org/resource/Category:Formal_languages> .
<http://dbpedia.org/resource/Smallest_grammar_problem>	<http://www.w3.org/2000/01/rdf-schema#comment>	"\u0412 \u0442\u0435\u043E\u0440\u0438\u0438 \u0444\u043E\u0440\u043C\u0430\u043B\u044C\u043D\u044B\u0445 \u044F\u0437\u044B\u043A\u043E\u0432 \u0437\u0430\u0434\u0430\u0447\u0435\u0439 \u043E \u043D\u0430\u0438\u043C\u0435\u043D\u044C\u0448\u0435\u0439 \u0433\u0440\u0430\u043C\u043C\u0430\u0442\u0438\u043A\u0435 \u043D\u0430\u0437\u044B\u0432\u0430\u0435\u0442\u0441\u044F \u0437\u0430\u0434\u0430\u0447\u0430 \u043D\u0430\u0445\u043E\u0436\u0434\u0435\u043D\u0438\u044F \u043D\u0430\u0438\u043C\u0435\u043D\u044C\u0448\u0435\u0439 \u043A\u043E\u043D\u0442\u0435\u043A\u0441\u0442\u043D\u043E-\u0441\u0432\u043E\u0431\u043E\u0434\u043D\u043E\u0439 \u0433\u0440\u0430\u043C\u043C\u0430\u0442\u0438\u043A\u0438, \u043A\u043E\u0442\u043E\u0440\u0430\u044F \u043F\u043E\u0440\u043E\u0436\u0434\u0430\u0435\u0442 \u0443\u043D\u0438\u043A\u0430\u043B\u044C\u043D\u0443\u044E \u043F\u043E\u0441\u043B\u0435\u0434\u043E\u0432\u0430\u0442\u0435\u043B\u044C\u043D\u043E\u0441\u0442\u044C \u0441\u0438\u043C\u0432\u043E\u043B\u043E\u0432. \u0420\u0430\u0437\u043C\u0435\u0440 \u0433\u0440\u0430\u043C\u043C\u0430\u0442\u0438\u043A\u0438 \u0447\u0430\u0441\u0442\u044C\u044E \u0430\u0432\u0442\u043E\u0440\u043E\u0432 \u043E\u043F\u0440\u0435\u0434\u0435\u043B\u044F\u0435\u0442\u0441\u044F \u0447\u0438\u0441\u043B\u043E\u043C \u0441\u0438\u043C\u0432\u043E\u043B\u043E\u0432 \u0432 \u043F\u0440\u0430\u0432\u043E\u0439 \u0447\u0430\u0441\u0442\u0438 \u043F\u0440\u0430\u0432\u0438\u043B \u0432\u044B\u0432\u043E\u0434\u0430.\u041D\u043E \u0438\u043D\u043E\u0433\u0434\u0430 \u0432\u043A\u043B\u044E\u0447\u0430\u0435\u0442\u0441\u044F \u0438 \u0447\u0438\u0441\u043B\u043E \u043F\u0440\u0430\u0432\u0438\u043B."@ru .
<http://dbpedia.org/resource/Smallest_grammar_problem>	<http://www.w3.org/1999/02/22-rdf-syntax-ns#type>	<http://dbpedia.org/class/yago/WikicatFormalLanguages> .
<http://dbpedia.org/resource/Smallest_grammar_problem>	<http://www.w3.org/2000/01/rdf-schema#label>	"Smallest grammar problem"@en .
<http://dbpedia.org/resource/Smallest_grammar_problem>	<http://dbpedia.org/ontology/wikiPageWikiLink>	<http://dbpedia.org/resource/Context-free_grammar> .
<http://dbpedia.org/resource/Smallest_grammar_problem>	<http://dbpedia.org/property/wikiPageUsesTemplate>	<http://dbpedia.org/resource/Template:Cn> .
<http://dbpedia.org/resource/Smallest_grammar_problem>	<http://dbpedia.org/property/wikiPageUsesTemplate>	<http://dbpedia.org/resource/Template:Reflist> .
<http://dbpedia.org/resource/Smallest_grammar_problem>	<http://xmlns.com/foaf/0.1/isPrimaryTopicOf>	<http://en.wikipedia.org/wiki/Smallest_grammar_problem> .
<http://dbpedia.org/resource/Smallest_grammar_problem>	<http://www.w3.org/2002/07/owl#sameAs>	<http://www.wikidata.org/entity/Q4183842> .
<http://dbpedia.org/resource/Smallest_grammar_problem>	<http://dbpedia.org/ontology/wikiPageRevisionID>	"1055320788"^^<http://www.w3.org/2001/XMLSchema#integer> .
<http://dbpedia.org/resource/Smallest_grammar_problem>	<http://www.w3.org/2002/07/owl#sameAs>	<http://rdf.freebase.com/ns/m.0cvng4> .
<http://dbpedia.org/resource/Smallest_grammar_problem>	<http://dbpedia.org/ontology/wikiPageWikiLink>	<http://dbpedia.org/resource/Lossless_data_compression> .
<http://dbpedia.org/resource/Smallest_grammar_problem>	<http://www.w3.org/2000/01/rdf-schema#label>	"\u0417\u0430\u0434\u0430\u0447\u0430 \u043E \u043D\u0430\u0438\u043C\u0435\u043D\u044C\u0448\u0435\u0439 \u0433\u0440\u0430\u043C\u043C\u0430\u0442\u0438\u043A\u0435"@ru .
<http://dbpedia.org/resource/Smallest_grammar_problem>	<http://www.w3.org/ns/prov#wasDerivedFrom>	<http://en.wikipedia.org/wiki/Smallest_grammar_problem?oldid=1055320788&ns=0> .
<http://dbpedia.org/resource/Smallest_grammar_problem>	<http://purl.org/dc/terms/subject>	<http://dbpedia.org/resource/Category:Data_compression> .
<http://dbpedia.org/resource/Smallest_grammar_problem>	<http://purl.org/dc/terms/subject>	<http://dbpedia.org/resource/Category:Formal_languages> .
<http://dbpedia.org/resource/Smallest_grammar_problem>	<http://dbpedia.org/ontology/wikiPageID>	"4929352"^^<http://www.w3.org/2001/XMLSchema#integer> .
<http://dbpedia.org/resource/Smallest_grammar_problem>	<http://dbpedia.org/ontology/wikiPageWikiLink>	<http://dbpedia.org/resource/Grammar-based_code> .
<http://dbpedia.org/resource/Smallest_grammar_problem>	<http://dbpedia.org/ontology/abstract>	"In data compression and the theory of formal languages, the smallest grammar problem is the problem of finding the smallest context-free grammar that generates a given string of characters (but no other string). The size of a grammar is defined by some authors as the number of symbols on the right side of the production rules.Others also add the number of rules to that. The (decision version of the) problem is NP-complete.The smallest context-free grammar that generates a given string is always a straight-line grammar without useless rules."@en .
<http://dbpedia.org/resource/Smallest_grammar_problem>	<http://dbpedia.org/ontology/wikiPageWikiLink>	<http://dbpedia.org/resource/Data_compression> .
<http://dbpedia.org/resource/Smallest_grammar_problem>	<http://dbpedia.org/ontology/wikiPageWikiLink>	<http://dbpedia.org/resource/String_(computer_science)> .
<http://dbpedia.org/resource/Smallest_grammar_problem>	<http://www.w3.org/2002/07/owl#sameAs>	<http://ru.dbpedia.org/resource/\u0417\u0430\u0434\u0430\u0447\u0430_\u043E_\u043D\u0430\u0438\u043C\u0435\u043D\u044C\u0448\u0435\u0439_\u0433\u0440\u0430\u043C\u043C\u0430\u0442\u0438\u043A\u0435> .
<http://dbpedia.org/resource/Smallest_grammar_problem>	<http://www.w3.org/2000/01/rdf-schema#comment>	"\u30C7\u30FC\u30BF\u5727\u7E2E\u3068\u5F62\u5F0F\u6587\u6CD5\u7406\u8AD6\u306B\u304A\u3044\u3066\u3001\u6700\u5C0F\u6587\u6CD5\u554F\u984C\uFF08\u3055\u3044\u3057\u3087\u3046\u3076\u3093\u307D\u3046\u3082\u3093\u3060\u3044\u3001\u82F1\u8A9E: smallest grammar problem\uFF09\u306F\u3001\u4E0E\u3048\u3089\u308C\u305F\u6587\u5B57\u5217\u3092\u751F\u6210\u3059\u308B\u6700\u5C0F\u306E\u6587\u8108\u81EA\u7531\u6587\u6CD5\u3092\u898B\u3064\u3051\u308B\u554F\u984C\u3067\u3042\u308B\u3002\u6587\u6CD5\u306E\u30B5\u30A4\u30BA\u306F\u3001\u751F\u6210\u898F\u5247\u306E\u53F3\u5074\u306E\u30B7\u30F3\u30DC\u30EB\u306E\u6570\u3068\u3057\u3066\u5B9A\u7FA9\u3059\u308B\u3068\u3057\u3066\u3044\u308B\u8005\u3084\u3001\u305D\u308C\u306B\u898F\u5247\u306E\u6570\u3092\u52A0\u3048\u308B\u3068\u3059\u308B\u8005\u3082\u3044\u308B\u3002\u3053\u306E\u554F\u984C\uFF08\u306E\u6C7A\u5B9A\u7248\uFF09\u306FNP\u5B8C\u5168\u3067\u3042\u308B\u3002"@ja .
<http://dbpedia.org/resource/Smallest_grammar_problem>	<http://dbpedia.org/property/wikiPageUsesTemplate>	<http://dbpedia.org/resource/Template:Cite_book> .
<http://dbpedia.org/resource/Smallest_grammar_problem>	<http://www.w3.org/2002/07/owl#sameAs>	<https://global.dbpedia.org/id/3sYfY> .
<http://dbpedia.org/resource/Smallest_grammar_problem>	<http://www.w3.org/1999/02/22-rdf-syntax-ns#type>	<http://dbpedia.org/class/yago/Communication100033020> .
<http://dbpedia.org/resource/Smallest_grammar_problem>	<http://dbpedia.org/property/wikiPageUsesTemplate>	<http://dbpedia.org/resource/Template:Algorithm-stub> .
<http://dbpedia.org/resource/Smallest_grammar_problem>	<http://www.w3.org/2002/07/owl#sameAs>	<http://ja.dbpedia.org/resource/\u6700\u5C0F\u6587\u6CD5\u554F\u984C> .
<http://dbpedia.org/resource/Smallest_grammar_problem>	<http://dbpedia.org/ontology/wikiPageWikiLink>	<http://dbpedia.org/resource/Category:Data_compression> .
<http://dbpedia.org/resource/Smallest_grammar_problem>	<http://www.w3.org/2000/01/rdf-schema#comment>	"In data compression and the theory of formal languages, the smallest grammar problem is the problem of finding the smallest context-free grammar that generates a given string of characters (but no other string). The size of a grammar is defined by some authors as the number of symbols on the right side of the production rules.Others also add the number of rules to that. The (decision version of the) problem is NP-complete.The smallest context-free grammar that generates a given string is always a straight-line grammar without useless rules."@en .
<http://dbpedia.org/resource/Smallest_grammar_problem>	<http://www.w3.org/2000/01/rdf-schema#label>	"\u6700\u5C0F\u6587\u6CD5\u554F\u984C"@ja .
<http://dbpedia.org/resource/Smallest_grammar_problem>	<http://dbpedia.org/ontology/wikiPageWikiLink>	<http://dbpedia.org/resource/Straight-line_grammar> .
<http://dbpedia.org/resource/Smallest_grammar_problem>	<http://dbpedia.org/ontology/wikiPageWikiLink>	<http://dbpedia.org/resource/Formal_language> .
<http://dbpedia.org/resource/Smallest_grammar_problem>	<http://dbpedia.org/ontology/abstract>	"\u0412 \u0442\u0435\u043E\u0440\u0438\u0438 \u0444\u043E\u0440\u043C\u0430\u043B\u044C\u043D\u044B\u0445 \u044F\u0437\u044B\u043A\u043E\u0432 \u0437\u0430\u0434\u0430\u0447\u0435\u0439 \u043E \u043D\u0430\u0438\u043C\u0435\u043D\u044C\u0448\u0435\u0439 \u0433\u0440\u0430\u043C\u043C\u0430\u0442\u0438\u043A\u0435 \u043D\u0430\u0437\u044B\u0432\u0430\u0435\u0442\u0441\u044F \u0437\u0430\u0434\u0430\u0447\u0430 \u043D\u0430\u0445\u043E\u0436\u0434\u0435\u043D\u0438\u044F \u043D\u0430\u0438\u043C\u0435\u043D\u044C\u0448\u0435\u0439 \u043A\u043E\u043D\u0442\u0435\u043A\u0441\u0442\u043D\u043E-\u0441\u0432\u043E\u0431\u043E\u0434\u043D\u043E\u0439 \u0433\u0440\u0430\u043C\u043C\u0430\u0442\u0438\u043A\u0438, \u043A\u043E\u0442\u043E\u0440\u0430\u044F \u043F\u043E\u0440\u043E\u0436\u0434\u0430\u0435\u0442 \u0443\u043D\u0438\u043A\u0430\u043B\u044C\u043D\u0443\u044E \u043F\u043E\u0441\u043B\u0435\u0434\u043E\u0432\u0430\u0442\u0435\u043B\u044C\u043D\u043E\u0441\u0442\u044C \u0441\u0438\u043C\u0432\u043E\u043B\u043E\u0432. \u0420\u0430\u0437\u043C\u0435\u0440 \u0433\u0440\u0430\u043C\u043C\u0430\u0442\u0438\u043A\u0438 \u0447\u0430\u0441\u0442\u044C\u044E \u0430\u0432\u0442\u043E\u0440\u043E\u0432 \u043E\u043F\u0440\u0435\u0434\u0435\u043B\u044F\u0435\u0442\u0441\u044F \u0447\u0438\u0441\u043B\u043E\u043C \u0441\u0438\u043C\u0432\u043E\u043B\u043E\u0432 \u0432 \u043F\u0440\u0430\u0432\u043E\u0439 \u0447\u0430\u0441\u0442\u0438 \u043F\u0440\u0430\u0432\u0438\u043B \u0432\u044B\u0432\u043E\u0434\u0430.\u041D\u043E \u0438\u043D\u043E\u0433\u0434\u0430 \u0432\u043A\u043B\u044E\u0447\u0430\u0435\u0442\u0441\u044F \u0438 \u0447\u0438\u0441\u043B\u043E \u043F\u0440\u0430\u0432\u0438\u043B."@ru .
<http://dbpedia.org/resource/Smallest_grammar_problem>	<http://www.w3.org/2002/07/owl#sameAs>	<http://yago-knowledge.org/resource/Smallest_grammar_problem> .
<http://dbpedia.org/resource/Smallest_grammar_problem>	<http://dbpedia.org/ontology/wikiPageLength>	"2388"^^<http://www.w3.org/2001/XMLSchema#nonNegativeInteger> .
<http://dbpedia.org/resource/Smallest_grammar_problem>	<http://www.w3.org/1999/02/22-rdf-syntax-ns#type>	<http://dbpedia.org/class/yago/Language106282651> .
<http://dbpedia.org/resource/Smallest_grammar_problem>	<http://www.w3.org/1999/02/22-rdf-syntax-ns#type>	<http://dbpedia.org/class/yago/Abstraction100002137> .
<http://dbpedia.org/resource/Smallest_grammar_problem>	<http://dbpedia.org/ontology/wikiPageWikiLink>	<http://dbpedia.org/resource/NP-complete> .
<http://dbpedia.org/resource/Smallest_grammar_problem>	<http://dbpedia.org/ontology/wikiPageWikiLink>	<http://dbpedia.org/resource/Kolmogorov_Complexity> .
<http://dbpedia.org/resource/Smallest_grammar_problem>	<http://dbpedia.org/ontology/wikiPageExternalLink>	<http://theory.lcs.mit.edu/~arasala/papers/grammar.pdf> .