The Complexity of Membership Problems for Circuits over Sets of Positive Numbers View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2007-01-01

AUTHORS

Hans-Georg Breunig

ABSTRACT

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. More... »

PAGES

125-136

Book

TITLE

Fundamentals of Computation Theory

ISBN

978-3-540-74239-5
978-3-540-74240-1

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-540-74240-1_12

DOI

http://dx.doi.org/10.1007/978-3-540-74240-1_12

DIMENSIONS

https://app.dimensions.ai/details/publication/pub.1043462749


Indexing Status Check whether this publication has been indexed by Scopus and Web Of Science using the SN Indexing Status Tool
Incoming Citations Browse incoming citations for this publication using opencitations.net

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

HOW TO GET THIS DATA PROGRAMMATICALLY:

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

Subject Predicate Object
1 sg:pub.10.1007/978-3-540-74240-1_12 schema:about anzsrc-for:17
2 anzsrc-for:1701
3 schema:author N95e267b040a84fcaa156e278728d2528
4 schema:datePublished 2007-01-01
5 schema:datePublishedReg 2007-01-01
6 schema: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.
7 schema:editor N36cb4810f60d4eedb27d809c1d96208e
8 schema:genre chapter
9 schema:isAccessibleForFree false
10 schema:isPartOf N20e5b62833814217be9f8bb8bd176dd9
11 schema:keywords McKenzie
12 NEXPTIME
13 NL
14 Wagner
15 cases
16 circuit
17 combinational circuits
18 complexity
19 emptiness
20 general case
21 implications
22 membership
23 membership problem
24 modification
25 natural modification
26 natural numbers
27 number
28 one
29 output
30 positive number
31 problem
32 set
33 strong implications
34 subset
35 schema:name The Complexity of Membership Problems for Circuits over Sets of Positive Numbers
36 schema:pagination 125-136
37 schema:productId N5f464e2a64c64dfdb5631705dc4e1e38
38 N63da6b223e7a44c695f65b8e0d26d364
39 schema:publisher Nb004a57a11f447e88ccc775008c503b9
40 schema:sameAs https://app.dimensions.ai/details/publication/pub.1043462749
41 https://doi.org/10.1007/978-3-540-74240-1_12
42 schema:sdDatePublished 2022-08-04T17:14
43 schema:sdLicense https://scigraph.springernature.com/explorer/license/
44 schema:sdPublisher N5ffadf29a5fa4f4b96f1fb354a8a3812
45 schema:url https://doi.org/10.1007/978-3-540-74240-1_12
46 sgo:license sg:explorer/license/
47 sgo:sdDataset chapters
48 rdf:type schema:Chapter
49 N1c27547258894ab399149ceaf06fe945 schema:familyName Csuhaj-Varjú
50 schema:givenName Erzsébet
51 rdf:type schema:Person
52 N20e5b62833814217be9f8bb8bd176dd9 schema:isbn 978-3-540-74239-5
53 978-3-540-74240-1
54 schema:name Fundamentals of Computation Theory
55 rdf:type schema:Book
56 N2ea592bc5fc44d379a8d3232440b163a schema:affiliation grid-institutes:grid.8379.5
57 schema:familyName Breunig
58 schema:givenName Hans-Georg
59 rdf:type schema:Person
60 N36cb4810f60d4eedb27d809c1d96208e rdf:first N1c27547258894ab399149ceaf06fe945
61 rdf:rest N6f9f896e01644b61b9afb94ab76e694e
62 N5f464e2a64c64dfdb5631705dc4e1e38 schema:name dimensions_id
63 schema:value pub.1043462749
64 rdf:type schema:PropertyValue
65 N5ffadf29a5fa4f4b96f1fb354a8a3812 schema:name Springer Nature - SN SciGraph project
66 rdf:type schema:Organization
67 N63da6b223e7a44c695f65b8e0d26d364 schema:name doi
68 schema:value 10.1007/978-3-540-74240-1_12
69 rdf:type schema:PropertyValue
70 N6f9f896e01644b61b9afb94ab76e694e rdf:first Nf2977be69486493586fab0d11b536846
71 rdf:rest rdf:nil
72 N95e267b040a84fcaa156e278728d2528 rdf:first N2ea592bc5fc44d379a8d3232440b163a
73 rdf:rest rdf:nil
74 Nb004a57a11f447e88ccc775008c503b9 schema:name Springer Nature
75 rdf:type schema:Organisation
76 Nf2977be69486493586fab0d11b536846 schema:familyName Ésik
77 schema:givenName Zoltán
78 rdf:type schema:Person
79 anzsrc-for:17 schema:inDefinedTermSet anzsrc-for:
80 schema:name Psychology and Cognitive Sciences
81 rdf:type schema:DefinedTerm
82 anzsrc-for:1701 schema:inDefinedTermSet anzsrc-for:
83 schema:name Psychology
84 rdf:type schema:DefinedTerm
85 grid-institutes:grid.8379.5 schema:alternateName Universität Würzburg, Institut für Informatik, Am Hubland, 97074 Würzburg, Germany
86 schema:name Universität Würzburg, Institut für Informatik, Am Hubland, 97074 Würzburg, Germany
87 rdf:type schema:Organization
 




Preview window. Press ESC to close (or click here)


...