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 Nb5d05189ad764847bd4a6b7dd487f0bc
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 Nefc7a90d814848edacdf550fece41da5
8 schema:genre chapter
9 schema:isAccessibleForFree false
10 schema:isPartOf Nf3392705448c4f3f875528ce423e3c99
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 N66c34836b78d491bb7dcd8119070bdb2
38 N79d11fc91624473b9df85bb8a6a1c380
39 schema:publisher Nc382b05e25c949b3a7f17c0ffcde36e9
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 N092ef7f3bdac42a298bd998191b34af9
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 N021474b8d030445e9b1c479a6922d5b9 schema:familyName Ésik
50 schema:givenName Zoltán
51 rdf:type schema:Person
52 N092ef7f3bdac42a298bd998191b34af9 schema:name Springer Nature - SN SciGraph project
53 rdf:type schema:Organization
54 N66c34836b78d491bb7dcd8119070bdb2 schema:name dimensions_id
55 schema:value pub.1043462749
56 rdf:type schema:PropertyValue
57 N6e005822d98a4e419a5431edccd90276 rdf:first N021474b8d030445e9b1c479a6922d5b9
58 rdf:rest rdf:nil
59 N79d11fc91624473b9df85bb8a6a1c380 schema:name doi
60 schema:value 10.1007/978-3-540-74240-1_12
61 rdf:type schema:PropertyValue
62 Nb5d05189ad764847bd4a6b7dd487f0bc rdf:first Nf51d7dfec40047c0b85b559f1e3b22a9
63 rdf:rest rdf:nil
64 Nc382b05e25c949b3a7f17c0ffcde36e9 schema:name Springer Nature
65 rdf:type schema:Organisation
66 Nc69d932a5dde4b6b805f9a6fd7b5526c schema:familyName Csuhaj-Varjú
67 schema:givenName Erzsébet
68 rdf:type schema:Person
69 Nefc7a90d814848edacdf550fece41da5 rdf:first Nc69d932a5dde4b6b805f9a6fd7b5526c
70 rdf:rest N6e005822d98a4e419a5431edccd90276
71 Nf3392705448c4f3f875528ce423e3c99 schema:isbn 978-3-540-74239-5
72 978-3-540-74240-1
73 schema:name Fundamentals of Computation Theory
74 rdf:type schema:Book
75 Nf51d7dfec40047c0b85b559f1e3b22a9 schema:affiliation grid-institutes:grid.8379.5
76 schema:familyName Breunig
77 schema:givenName Hans-Georg
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)


...