Matches in DBpedia 2014 for { <http://dbpedia.org/resource/Unary_language> ?p ?o. }
Showing items 1 to 22 of
22
with 100 items per page.
- Unary_language abstract "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 replacing every symbol with a "1" has made the language size logarithmically smaller. 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.".
- Unary_language wikiPageExternalLink favorite-theorems-small-sets.html.
- Unary_language wikiPageID "12769341".
- Unary_language wikiPageRevisionID "546658652".
- Unary_language hasPhotoCollection Unary_language.
- Unary_language subject Category:Computational_complexity_theory.
- Unary_language subject Category:Formal_languages.
- Unary_language type Abstraction100002137.
- Unary_language type Communication100033020.
- Unary_language type FormalLanguages.
- Unary_language type Language106282651.
- Unary_language comment "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.".
- Unary_language label "Linguagem unária".
- Unary_language label "Unary language".
- Unary_language label "一元語言".
- Unary_language sameAs Linguagem_unária.
- Unary_language sameAs m.02x43s2.
- Unary_language sameAs Q7882310.
- Unary_language sameAs Q7882310.
- Unary_language sameAs Unary_language.
- Unary_language wasDerivedFrom Unary_language?oldid=546658652.
- Unary_language isPrimaryTopicOf Unary_language.