{
"@context": "http://schema.org",
"@type": "ScholarlyArticle",
"@id": "https://doi.org/10.4230/lipics.stacs.2008.1363",
"identifier": {
"@type": "PropertyValue",
"propertyID": "DOI",
"value": "https://doi.org/10.4230/lipics.stacs.2008.1363"
},
"url": "http://drops.dagstuhl.de/opus/volltexte/2008/1363/",
"additionalType": "ConferencePaper",
"name": "Space Hierarchy Results for Randomized Models",
"author": [
{
"name": "Jeff Kinne",
"givenName": "Jeff",
"familyName": "Kinne",
"@type": "Person"
},
{
"name": "Dieter Van Melkebeek",
"givenName": "Dieter",
"familyName": "Van Melkebeek",
"@type": "Person"
}
],
"editor": {
"name": "Marc Herbstritt",
"givenName": "Marc",
"familyName": "Herbstritt",
"contributorType": "Editor",
"@type": "Person"
},
"description": "We prove space hierarchy and separation results for randomized and\n other semantic models of computation with advice. Previous works\n on hierarchy and separation theorems for such models focused on\n time as the resource. We obtain tighter results with space as the\n resource. Our main theorems are the following. Let $s(n)$ be any\n space-constructible function that is $Omega(log n)$ and such that\n $s(a n) = O(s(n))$ for all constants $a$, and let $s'(n)$ be any\n function that is $omega(s(n))$.\n \n - There exists a language computable by two-sided error randomized\n machines using $s'(n)$ space and one bit of advice that is not\n computable by two-sided error randomized machines using $s(n)$\n space and $min(s(n),n)$ bits of advice.\n \n - There exists a language computable by zero-sided error randomized\n machines in space $s'(n)$ with one bit of advice that is not\n computable by one-sided error randomized machines using $s(n)$\n space and $min(s(n),n)$ bits of advice.\n \n The condition that $s(a n)=O(s(n))$ is a technical condition\n satisfied by typical space bounds that are at most linear. We also\n obtain weaker results that apply to generic semantic models of\n computation.",
"keywords": "Computer Science, 000 Computer science, knowledge, general works",
"inLanguage": "eng",
"contentSize": "12 pages",
"encodingFormat": "application/pdf",
"datePublished": "2008",
"schemaVersion": "http://datacite.org/schema/kernel-2.1",
"publisher": {
"@type": "Organization",
"name": "Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH, Wadern/Saarbruecken, Germany"
}
}