Matches in DBpedia 2016-04 for { <http://dbpedia.org/resource/Unary_language> ?p ?o }
Showing triples 1 to 46 of
46
with 100 triples 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 wikiPageLength "4197".
- Unary_language wikiPageOutDegree "21".
- Unary_language wikiPageRevisionID "682199783".
- Unary_language wikiPageWikiLink Category:Computational_complexity_theory.
- Unary_language wikiPageWikiLink Category:Formal_languages.
- Unary_language wikiPageWikiLink Complexity_class.
- Unary_language wikiPageWikiLink Computational_complexity_theory.
- Unary_language wikiPageWikiLink Countable_set.
- Unary_language wikiPageWikiLink Counting_problem_(complexity).
- Unary_language wikiPageWikiLink Formal_language.
- Unary_language wikiPageWikiLink Kleene_star.
- Unary_language wikiPageWikiLink NP-completeness.
- Unary_language wikiPageWikiLink NP_(complexity).
- Unary_language wikiPageWikiLink Natural_number.
- Unary_language wikiPageWikiLink poly.
- Unary_language wikiPageWikiLink P_(complexity).
- Unary_language wikiPageWikiLink P_versus_NP_problem.
- Unary_language wikiPageWikiLink Prime_number.
- Unary_language wikiPageWikiLink Recursive_language.
- Unary_language wikiPageWikiLink Regular_language.
- Unary_language wikiPageWikiLink Sharp-P.
- Unary_language wikiPageWikiLink Sparse_language.
- Unary_language wikiPageWikiLink String_(computer_science).
- Unary_language wikiPageWikiLink Unary_numeral_system.
- Unary_language wikiPageWikiLinkText "Unary language".
- Unary_language wikiPageWikiLinkText "unary language".
- Unary_language wikiPageUsesTemplate Template:CZoo.
- Unary_language wikiPageUsesTemplate Template:Reflist.
- Unary_language subject Category:Computational_complexity_theory.
- Unary_language subject Category:Formal_languages.
- Unary_language hypernym Language.
- Unary_language type Language.
- Unary_language type Combinatoric.
- Unary_language type Language.
- 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 "Unary language".
- Unary_language sameAs Q7882310.
- Unary_language sameAs Linguagem_unária.
- Unary_language sameAs m.02x43s2.
- Unary_language sameAs Q7882310.
- Unary_language sameAs 一元語言.
- Unary_language wasDerivedFrom Unary_language?oldid=682199783.
- Unary_language isPrimaryTopicOf Unary_language.