Ontology type: schema:Chapter
2007-01-01
AUTHORSHans-Georg Breunig
ABSTRACTWe investigate the problems of testing membership in the subset of the positive numbers produced at the output of combinational circuits. These problems are a natural modification of those studied by McKenzie and Wagner (2003), where circuits computed sets of natural numbers. It turns out that the missing 0 has strong implications, not only because 0 can be used to test for emptiness. We show that the membership problem for the general case and for is PSPACE-complete, whereas it is NEXPTIME-hard if one allows 0. Furthermore, testing membership for is NL-complete (as opposed to -hard), and several other cases are resolved. More... »
PAGES125-136
Fundamentals of Computation Theory
ISBN
978-3-540-74239-5
978-3-540-74240-1
http://scigraph.springernature.com/pub.10.1007/978-3-540-74240-1_12
DOIhttp://dx.doi.org/10.1007/978-3-540-74240-1_12
DIMENSIONShttps://app.dimensions.ai/details/publication/pub.1043462749
JSON-LD is the canonical representation for SciGraph data.
TIP: You can open this SciGraph record using an external JSON-LD service: JSON-LD Playground Google SDTT
[
{
"@context": "https://springernature.github.io/scigraph/jsonld/sgcontext.json",
"about": [
{
"id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/17",
"inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/",
"name": "Psychology and Cognitive Sciences",
"type": "DefinedTerm"
},
{
"id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/1701",
"inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/",
"name": "Psychology",
"type": "DefinedTerm"
}
],
"author": [
{
"affiliation": {
"alternateName": "Universit\u00e4t W\u00fcrzburg, Institut f\u00fcr Informatik, Am Hubland, 97074 W\u00fcrzburg, Germany",
"id": "http://www.grid.ac/institutes/grid.8379.5",
"name": [
"Universit\u00e4t W\u00fcrzburg, Institut f\u00fcr Informatik, Am Hubland, 97074 W\u00fcrzburg, Germany"
],
"type": "Organization"
},
"familyName": "Breunig",
"givenName": "Hans-Georg",
"type": "Person"
}
],
"datePublished": "2007-01-01",
"datePublishedReg": "2007-01-01",
"description": "We investigate the problems of testing membership in the subset of the positive numbers produced at the output of combinational circuits. These problems are a natural modification of those studied by McKenzie and Wagner (2003), where circuits computed sets of natural numbers. It turns out that the missing 0 has strong implications, not only because 0 can be used to test for emptiness. We show that the membership problem for the general case and for is PSPACE-complete, whereas it is NEXPTIME-hard if one allows 0. Furthermore, testing membership for is NL-complete (as opposed to -hard), and several other cases are resolved.",
"editor": [
{
"familyName": "Csuhaj-Varj\u00fa",
"givenName": "Erzs\u00e9bet",
"type": "Person"
},
{
"familyName": "\u00c9sik",
"givenName": "Zolt\u00e1n",
"type": "Person"
}
],
"genre": "chapter",
"id": "sg:pub.10.1007/978-3-540-74240-1_12",
"isAccessibleForFree": false,
"isPartOf": {
"isbn": [
"978-3-540-74239-5",
"978-3-540-74240-1"
],
"name": "Fundamentals of Computation Theory",
"type": "Book"
},
"keywords": [
"cases",
"subset",
"number",
"NL",
"implications",
"modification",
"strong implications",
"problem",
"circuit",
"positive number",
"output",
"membership",
"McKenzie",
"one",
"set",
"emptiness",
"complexity",
"natural modification",
"Wagner",
"natural numbers",
"combinational circuits",
"general case",
"membership problem",
"NEXPTIME"
],
"name": "The Complexity of Membership Problems for Circuits over Sets of Positive Numbers",
"pagination": "125-136",
"productId": [
{
"name": "dimensions_id",
"type": "PropertyValue",
"value": [
"pub.1043462749"
]
},
{
"name": "doi",
"type": "PropertyValue",
"value": [
"10.1007/978-3-540-74240-1_12"
]
}
],
"publisher": {
"name": "Springer Nature",
"type": "Organisation"
},
"sameAs": [
"https://doi.org/10.1007/978-3-540-74240-1_12",
"https://app.dimensions.ai/details/publication/pub.1043462749"
],
"sdDataset": "chapters",
"sdDatePublished": "2022-08-04T17:14",
"sdLicense": "https://scigraph.springernature.com/explorer/license/",
"sdPublisher": {
"name": "Springer Nature - SN SciGraph project",
"type": "Organization"
},
"sdSource": "s3://com-springernature-scigraph/baseset/20220804/entities/gbq_results/chapter/chapter_117.jsonl",
"type": "Chapter",
"url": "https://doi.org/10.1007/978-3-540-74240-1_12"
}
]
Download the RDF metadata as: json-ld nt turtle xml License info
JSON-LD is a popular format for linked data which is fully compatible with JSON.
curl -H 'Accept: application/ld+json' 'https://scigraph.springernature.com/pub.10.1007/978-3-540-74240-1_12'
N-Triples is a line-based linked data format ideal for batch operations.
curl -H 'Accept: application/n-triples' 'https://scigraph.springernature.com/pub.10.1007/978-3-540-74240-1_12'
Turtle is a human-readable linked data format.
curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-540-74240-1_12'
RDF/XML is a standard XML format for linked data.
curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/978-3-540-74240-1_12'
This table displays all metadata directly associated to this object as RDF triples.
87 TRIPLES
22 PREDICATES
48 URIs
41 LITERALS
7 BLANK NODES