About: Log-space transducer     Goto   Sponge   NotDistinct   Permalink

An Entity of Type : owl:Thing, within Data Space : dbpedia.demo.openlinksw.com associated with source document(s)
QRcode icon
http://dbpedia.demo.openlinksw.com/describe/?url=http%3A%2F%2Fdbpedia.org%2Fresource%2FLog-space_transducer&invfp=IFP_OFF&sas=SAME_AS_OFF

In computational complexity theory, a log space transducer (LST) is a type of Turing machine used for log-space reductions. A log space transducer, , has three tapes: * A read-only input tape. * A read/write work tape (bounded to at most symbols). * A write-only, write-once output tape. will be designed to compute a log-space computable function (where is the alphabet of both the input and output tapes). If is executed with on its input tape, when the machine halts, it will have remaining on its output tape.

AttributesValues
rdfs:label
  • Log-space transducer (en)
rdfs:comment
  • In computational complexity theory, a log space transducer (LST) is a type of Turing machine used for log-space reductions. A log space transducer, , has three tapes: * A read-only input tape. * A read/write work tape (bounded to at most symbols). * A write-only, write-once output tape. will be designed to compute a log-space computable function (where is the alphabet of both the input and output tapes). If is executed with on its input tape, when the machine halts, it will have remaining on its output tape. (en)
dct:subject
Wikipage page ID
Wikipage revision ID
Link from a Wikipage to another Wikipage
Link from a Wikipage to an external page
sameAs
dbp:wikiPageUsesTemplate
has abstract
  • In computational complexity theory, a log space transducer (LST) is a type of Turing machine used for log-space reductions. A log space transducer, , has three tapes: * A read-only input tape. * A read/write work tape (bounded to at most symbols). * A write-only, write-once output tape. will be designed to compute a log-space computable function (where is the alphabet of both the input and output tapes). If is executed with on its input tape, when the machine halts, it will have remaining on its output tape. A language is said to be log-space reducible to a language if there exists a log-space computable function that will convert an input from problem into an input to problem in such a way that . This seems like a rather convoluted idea, but it has two useful properties that are desirable for a reduction: 1. * The property of transitivity holds. (A reduces to B and B reduces to C implies A reduces to C). 2. * If A reduces to B, and B is in L, then we know A is in L. Transitivity holds because it is possible to feed the output tape of one reducer (A→B) to another (B→C). At first glance, this seems incorrect because the A→C reducer needs to store the output tape from the A→B reducer onto the work tape in order to feed it into the B→C reducer, but this is not true. Each time the B→C reducer needs to access its input tape, the A→C reducer can re-run the A→B reducer, and so the output of the A→B reducer never needs to be stored entirely at once. (en)
prov:wasDerivedFrom
page length (characters) of wiki page
foaf:isPrimaryTopicOf
is Link from a Wikipage to another Wikipage of
is Wikipage redirect of
is Wikipage disambiguates of
is foaf:primaryTopic of
Faceted Search & Find service v1.17_git145 as of Aug 30 2024


Alternative Linked Data Documents: ODE     Content Formats:   [cxml] [csv]     RDF   [text] [turtle] [ld+json] [rdf+json] [rdf+xml]     ODATA   [atom+xml] [odata+json]     Microdata   [microdata+json] [html]    About   
This material is Open Knowledge   W3C Semantic Web Technology [RDF Data] Valid XHTML + RDFa
OpenLink Virtuoso version 08.03.3331 as of Sep 2 2024, on Linux (x86_64-generic-linux-glibc212), Single-Server Edition (378 GB total memory, 50 GB memory in use)
Data on this page belongs to its respective rights holders.
Virtuoso Faceted Browser Copyright © 2009-2024 OpenLink Software