| dbo: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)
- データ圧縮と形式文法理論において、最小文法問題（さいしょうぶんぽうもんだい、英語: smallest grammar problem）は、与えられた文字列を生成する最小の文脈自由文法を見つける問題である。文法のサイズは、生成規則の右側のシンボルの数として定義するとしている者や、それに規則の数を加えるとする者もいる。この問題（の決定版）はNP完全である。 (ja)
- В теории формальных языков задачей о наименьшей грамматике называется задача нахождения наименьшей контекстно-свободной грамматики, которая порождает уникальную последовательность символов. Размер грамматики частью авторов определяется числом символов в правой части правил вывода.Но иногда включается и число правил. (ru)
|
| dbo:wikiPageExternalLink
| |
| dbo:wikiPageID
| |
| dbo:wikiPageLength
|
- 2388 (xsd:nonNegativeInteger)
|
| dbo:wikiPageRevisionID
| |
| dbo:wikiPageWikiLink
| |
| dbp:wikiPageUsesTemplate
| |
| dcterms:subject
| |
| rdf:type
| |
| rdfs: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)
- データ圧縮と形式文法理論において、最小文法問題（さいしょうぶんぽうもんだい、英語: smallest grammar problem）は、与えられた文字列を生成する最小の文脈自由文法を見つける問題である。文法のサイズは、生成規則の右側のシンボルの数として定義するとしている者や、それに規則の数を加えるとする者もいる。この問題（の決定版）はNP完全である。 (ja)
- В теории формальных языков задачей о наименьшей грамматике называется задача нахождения наименьшей контекстно-свободной грамматики, которая порождает уникальную последовательность символов. Размер грамматики частью авторов определяется числом символов в правой части правил вывода.Но иногда включается и число правил. (ru)
|
| rdfs:label
|
- 最小文法問題 (ja)
- Smallest grammar problem (en)
- Задача о наименьшей грамматике (ru)
|
| owl:sameAs
| |
| prov:wasDerivedFrom
| |
| foaf:isPrimaryTopicOf
| |
| is dbo:wikiPageRedirects
of | |
| is dbo:wikiPageWikiLink
of | |
| is foaf:primaryTopic
of | |
