Unary language (original) (raw)
En théorie des langages, en théorie de la complexité, un langage unaire est un langage qui ne contient que des mots sur une seule et même lettre, généralement notée 1.
| Property | Value | ||||
|---|---|---|---|---|---|
| dbo:abstract | En théorie des langages, en théorie de la complexité, un langage unaire est un langage qui ne contient que des mots sur une seule et même lettre, généralement notée 1. (fr) In computational complexity theory, a unary language or tally language is a formal language (a set of strings) where all strings have the form 1k, where "1" can be any fixed symbol. For example, the language {1, 111, 1111} is unary, as is the language {1k | k is prime}. The complexity class of all such languages is sometimes called TALLY. The name "unary" comes from the fact that a unary language is the encoding of a set of natural numbers in the unary numeral system. Since the universe of strings over any finite alphabet is a countable set, every language can be mapped to a unique set A of natural numbers; thus, every language has a unary version {1k | k in A}. Conversely, every unary language has a more compact binary version, the set of binary encodings of natural numbers k such that 1k is in the language. Since complexity is usually measured in terms of the length of the input string, the unary version of a language can be "easier" than the original language. For example, if a language can be recognized in O(2n) time, its unary version can be recognized in O(n) time, because n has become exponentially larger. More generally, if a language can be recognized in O(f(n)) time and O(g(n)) space, its unary version can be recognized in O(n + f(log n)) time and O(g(log n)) space (we require O(n) time just to read the input string). However, if membership in a language is undecidable, then membership in its unary version is also undecidable. (en) Em teoria da complexidade computacional, uma linguagem unária ou linguagem de registro é uma linguagem formal (um conjunto de ), onde todas as strings têm a forma de 1k, onde "1" pode ser qualquer símbolo arbitrário. Por exemplo, a linguagem {1, 111, 1111} é unária, como é a linguagem {1k | k é primo}. A classe de complexidade de todas essas linguagens pode ser chamada de TALLY. O nome "unário" vem do fato de que uma língua unário é a codificação de um conjunto de números naturais no . Como o universo das strings sobre qualquer alfabeto finito é um conjunto contável, todas as linguagens podem ser mapeadas para um único conjunto A de números naturais, assim, cada linguagem tem uma versão unária {1k | k in A}. Por outro lado, todas linguagem unária tem uma versão binária mais compacta, o conjunto de codificações binárias de números naturaisk tal que 1k está na linguagem. Como complexidade é normalmente medida em termos de tamanho da string de entrada, a versão unária da linguagem pode ser "mais fácil" que a linguagem original. Por exemplo, se a linguagem for reconhecível em tempo O(2n), sua versão unária pode ser reconhecida em tempo O(n), pois trocando cada simbolo por um "1" torana o tamanho da linguagem logaritmicamente menor. De forma mais geral, se uma linguagem pode ser reconhecida num tempo O(f(n)) e num espaçoO(g(n)), sua versão unária pode ser reconhecida num tempo O(n+f(logn)) e num espaço O(g(log n)) (nós requerimos um tempo O(n) só para ler a string de entrada). Entretanto, se o fato de ela pertencer ou não a uma linguagem é indecidível, então o fato de sua versão unária pertender ou não é indecidível também. (pt) 在計算複雜度理論內，一元語言或者結算語言是一種形式語言 (由字串組成的集合)，裡面所有的字串都是像1k的形式(這裡的"1"可以是任何的符號）。例如，{1, 111, 1111}就是一個一元語言,或是像{1k | k是 質數}。這一類語言的複雜度類有時被叫做TALLY。 (zh) |
| dbo:wikiPageExternalLink | http://weblog.fortnow.com/2006/04/favorite-theorems-small-sets.html | ||||
| dbo:wikiPageID | 12769341 (xsd:integer) | ||||
| dbo:wikiPageLength | 4279 (xsd:nonNegativeInteger) | ||||
| dbo:wikiPageRevisionID | 1073316598 (xsd:integer) | ||||
| dbo:wikiPageWikiLink | dbr:Countable_set dbr:NP-complete dbr:NP-hard dbr:Complexity_class dbr:Computational_complexity_theory dbr:Sharp-P dbr:Sparse_language dbr:String_(computer_science) dbr:P/poly dbr:Formal_language dbr:Unary_numeral_system dbr:Regular_language dbr:Prime_number dbc:Computational_complexity_theory dbc:Formal_languages dbr:Recursive_language dbr:Natural_number dbr:Kleene_star dbr:P_(class) dbr:P_=_NP_problem dbr:Counting_class dbr:NP_(class) | ||||
| dbp:wikiPageUsesTemplate | dbt:Reflist dbt:Short_description dbt:CZoo | ||||
| dct:subject | dbc:Computational_complexity_theory dbc:Formal_languages | ||||
| gold:hypernym | dbr:Language | ||||
| rdf:type | dbo:Language yago:Abstraction100002137 yago:Communication100033020 yago:Language106282651 yago:WikicatFormalLanguages | ||||
| rdfs:comment | En théorie des langages, en théorie de la complexité, un langage unaire est un langage qui ne contient que des mots sur une seule et même lettre, généralement notée 1. (fr) 在計算複雜度理論內，一元語言或者結算語言是一種形式語言 (由字串組成的集合)，裡面所有的字串都是像1k的形式(這裡的"1"可以是任何的符號）。例如，{1, 111, 1111}就是一個一元語言,或是像{1k | k是 質數}。這一類語言的複雜度類有時被叫做TALLY。 (zh) In computational complexity theory, a unary language or tally language is a formal language (a set of strings) where all strings have the form 1k, where "1" can be any fixed symbol. For example, the language {1, 111, 1111} is unary, as is the language {1k | k is prime}. The complexity class of all such languages is sometimes called TALLY. (en) Em teoria da complexidade computacional, uma linguagem unária ou linguagem de registro é uma linguagem formal (um conjunto de ), onde todas as strings têm a forma de 1k, onde "1" pode ser qualquer símbolo arbitrário. Por exemplo, a linguagem {1, 111, 1111} é unária, como é a linguagem {1k | k é primo}. A classe de complexidade de todas essas linguagens pode ser chamada de TALLY. (pt) | ||
| rdfs:label | Langage unaire (fr) Linguagem unária (pt) Unary language (en) 一元語言 (zh) | ||||
| owl:sameAs | freebase:Unary language wikidata:Unary language dbpedia-fr:Unary language dbpedia-he:Unary language dbpedia-pt:Unary language dbpedia-zh:Unary language https://global.dbpedia.org/id/4wVzF yago-res:Unary language | ||||
| prov:wasDerivedFrom | wikipedia-en:Unary_language?oldid=1073316598&ns=0 | ||||
| foaf:isPrimaryTopicOf | wikipedia-en:Unary_language | ||||
| is dbo:wikiPageRedirects of | dbr:Tally_language dbr:Tally_set dbr:TALLY | ||||
| is dbo:wikiPageWikiLink of | dbr:Space_hierarchy_theorem dbr:Sparse_language dbr:Tally_language dbr:P/poly dbr:Alternating_finite_automaton dbr:AC0 dbr:Tally_set dbr:TALLY | ||||
| is foaf:primaryTopic of | wikipedia-en:Unary_language |