Equivalence Problems for Circuits over Sets of Natural Numbers View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2007-01-01

AUTHORS

Christian Glaßer , Katrin Herr , Christian Reitwießner , Stephen Travers , Matthias Waldherr

ABSTRACT

We investigate the complexity of equivalence problems for { ∪ , ∩ , −, + ,×}-circuits computing sets of natural numbers. These problems were first introduced by Stockmeyer and Meyer (1973). We continue this line of research and give a systematic characterization of the complexity of equivalence problems over sets of natural numbers. Our work shows that equivalence problems capture a wide range of complexity classes like NL, C=L, P,\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}${\rm \Pi^P_{2}}$\end{document}, PSPACE, NEXP, and beyond. McKenzie and Wagner (2003) studied related membership problems for circuits over sets of natural numbers. Our results also have consequences for these membership problems: We provide an improved upper bound for the case of { ∪ , ∩ , −, + ,×}-circuits. More... »

PAGES

127-138

Book

TITLE

Computer Science – Theory and Applications

ISBN

978-3-540-74509-9
978-3-540-74510-5

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-540-74510-5_15

DOI

http://dx.doi.org/10.1007/978-3-540-74510-5_15

DIMENSIONS

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


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/08", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Information and Computing Sciences", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0802", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Computation Theory and Mathematics", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Julius-Maximilians-Universit\u00e4t W\u00fcrzburg, Theoretische Informatik, Germany", 
          "id": "http://www.grid.ac/institutes/grid.8379.5", 
          "name": [
            "Julius-Maximilians-Universit\u00e4t W\u00fcrzburg, Theoretische Informatik, Germany"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Gla\u00dfer", 
        "givenName": "Christian", 
        "id": "sg:person.010502766006.46", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010502766006.46"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Julius-Maximilians-Universit\u00e4t W\u00fcrzburg, Theoretische Informatik, Germany", 
          "id": "http://www.grid.ac/institutes/grid.8379.5", 
          "name": [
            "Julius-Maximilians-Universit\u00e4t W\u00fcrzburg, Theoretische Informatik, Germany"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Herr", 
        "givenName": "Katrin", 
        "id": "sg:person.010127676033.33", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010127676033.33"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Julius-Maximilians-Universit\u00e4t W\u00fcrzburg, Theoretische Informatik, Germany", 
          "id": "http://www.grid.ac/institutes/grid.8379.5", 
          "name": [
            "Julius-Maximilians-Universit\u00e4t W\u00fcrzburg, Theoretische Informatik, Germany"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Reitwie\u00dfner", 
        "givenName": "Christian", 
        "id": "sg:person.013115600033.81", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013115600033.81"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Julius-Maximilians-Universit\u00e4t W\u00fcrzburg, Theoretische Informatik, Germany", 
          "id": "http://www.grid.ac/institutes/grid.8379.5", 
          "name": [
            "Julius-Maximilians-Universit\u00e4t W\u00fcrzburg, Theoretische Informatik, Germany"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Travers", 
        "givenName": "Stephen", 
        "id": "sg:person.07734242057.72", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07734242057.72"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Julius-Maximilians-Universit\u00e4t W\u00fcrzburg, Theoretische Informatik, Germany", 
          "id": "http://www.grid.ac/institutes/grid.8379.5", 
          "name": [
            "Julius-Maximilians-Universit\u00e4t W\u00fcrzburg, Theoretische Informatik, Germany"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Waldherr", 
        "givenName": "Matthias", 
        "id": "sg:person.07404271733.31", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07404271733.31"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2007-01-01", 
    "datePublishedReg": "2007-01-01", 
    "description": "We investigate the complexity of equivalence problems for {\u2009\u222a\u2009,\u2009\u2229\u2009, \u2212,\u2009+\u2009,\u00d7}-circuits computing sets of natural numbers. These problems were first introduced by Stockmeyer and Meyer (1973). We continue this line of research and give a systematic characterization of the complexity of equivalence problems over sets of natural numbers. Our work shows that equivalence problems capture a wide range of complexity classes like NL, C=L, P,\\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}${\\rm \\Pi^P_{2}}$\\end{document}, PSPACE, NEXP, and beyond. McKenzie and Wagner (2003) studied related membership problems for circuits over sets of natural numbers. Our results also have consequences for these membership problems: We provide an improved upper bound for the case of {\u2009\u222a\u2009,\u2009\u2229\u2009, \u2212,\u2009+\u2009,\u00d7}-circuits.", 
    "editor": [
      {
        "familyName": "Diekert", 
        "givenName": "Volker", 
        "type": "Person"
      }, 
      {
        "familyName": "Volkov", 
        "givenName": "Mikhail V.", 
        "type": "Person"
      }, 
      {
        "familyName": "Voronkov", 
        "givenName": "Andrei", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-540-74510-5_15", 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-540-74509-9", 
        "978-3-540-74510-5"
      ], 
      "name": "Computer Science \u2013 Theory and Applications", 
      "type": "Book"
    }, 
    "keywords": [
      "natural numbers", 
      "equivalence problem", 
      "membership problem", 
      "complexity classes", 
      "problem", 
      "set", 
      "complexity", 
      "PSPACE", 
      "circuit", 
      "Stockmeyer", 
      "wide range", 
      "NEXP", 
      "number", 
      "class", 
      "line of research", 
      "McKenzie", 
      "Wagner", 
      "systematic characterization", 
      "cases", 
      "Meyer", 
      "work", 
      "results", 
      "range", 
      "NL", 
      "lines", 
      "characterization", 
      "consequences", 
      "research"
    ], 
    "name": "Equivalence Problems for Circuits over Sets of Natural Numbers", 
    "pagination": "127-138", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1008732500"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-540-74510-5_15"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-540-74510-5_15", 
      "https://app.dimensions.ai/details/publication/pub.1008732500"
    ], 
    "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_13.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-540-74510-5_15"
  }
]
 

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-74510-5_15'

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-74510-5_15'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-540-74510-5_15'

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-74510-5_15'


 

This table displays all metadata directly associated to this object as RDF triples.

125 TRIPLES      22 PREDICATES      52 URIs      45 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-540-74510-5_15 schema:about anzsrc-for:08
2 anzsrc-for:0802
3 schema:author N3c18acae4e674107a3bfedd836de2cb9
4 schema:datePublished 2007-01-01
5 schema:datePublishedReg 2007-01-01
6 schema:description We investigate the complexity of equivalence problems for { ∪ , ∩ , −, + ,×}-circuits computing sets of natural numbers. These problems were first introduced by Stockmeyer and Meyer (1973). We continue this line of research and give a systematic characterization of the complexity of equivalence problems over sets of natural numbers. Our work shows that equivalence problems capture a wide range of complexity classes like NL, C=L, P,\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}${\rm \Pi^P_{2}}$\end{document}, PSPACE, NEXP, and beyond. McKenzie and Wagner (2003) studied related membership problems for circuits over sets of natural numbers. Our results also have consequences for these membership problems: We provide an improved upper bound for the case of { ∪ , ∩ , −, + ,×}-circuits.
7 schema:editor N7c16b04cd29d43c6a6496ea78fc796b5
8 schema:genre chapter
9 schema:isAccessibleForFree false
10 schema:isPartOf N614b2466f02048dc986be09d9c49e61a
11 schema:keywords McKenzie
12 Meyer
13 NEXP
14 NL
15 PSPACE
16 Stockmeyer
17 Wagner
18 cases
19 characterization
20 circuit
21 class
22 complexity
23 complexity classes
24 consequences
25 equivalence problem
26 line of research
27 lines
28 membership problem
29 natural numbers
30 number
31 problem
32 range
33 research
34 results
35 set
36 systematic characterization
37 wide range
38 work
39 schema:name Equivalence Problems for Circuits over Sets of Natural Numbers
40 schema:pagination 127-138
41 schema:productId N03f1607bc36c425d93987803f787a317
42 N6a9636a774224c38a60ddbae6776f3f5
43 schema:publisher N49f686ffd4f24ac595a86b446b3d2411
44 schema:sameAs https://app.dimensions.ai/details/publication/pub.1008732500
45 https://doi.org/10.1007/978-3-540-74510-5_15
46 schema:sdDatePublished 2022-08-04T17:14
47 schema:sdLicense https://scigraph.springernature.com/explorer/license/
48 schema:sdPublisher Ncf76b4ceb8794536a2635c68b6f7bc6b
49 schema:url https://doi.org/10.1007/978-3-540-74510-5_15
50 sgo:license sg:explorer/license/
51 sgo:sdDataset chapters
52 rdf:type schema:Chapter
53 N03f1607bc36c425d93987803f787a317 schema:name doi
54 schema:value 10.1007/978-3-540-74510-5_15
55 rdf:type schema:PropertyValue
56 N3c18acae4e674107a3bfedd836de2cb9 rdf:first sg:person.010502766006.46
57 rdf:rest N573c5746718e4535abbcc235acfbc756
58 N49f686ffd4f24ac595a86b446b3d2411 schema:name Springer Nature
59 rdf:type schema:Organisation
60 N5220053eafb74a9cb4bca9b597a29861 rdf:first sg:person.07734242057.72
61 rdf:rest Nc533832bdb7b45f798ae5ce04222f113
62 N573c5746718e4535abbcc235acfbc756 rdf:first sg:person.010127676033.33
63 rdf:rest N5dba0b3fe421450e9d9c87cd8bdba60b
64 N5dba0b3fe421450e9d9c87cd8bdba60b rdf:first sg:person.013115600033.81
65 rdf:rest N5220053eafb74a9cb4bca9b597a29861
66 N614b2466f02048dc986be09d9c49e61a schema:isbn 978-3-540-74509-9
67 978-3-540-74510-5
68 schema:name Computer Science – Theory and Applications
69 rdf:type schema:Book
70 N6a9636a774224c38a60ddbae6776f3f5 schema:name dimensions_id
71 schema:value pub.1008732500
72 rdf:type schema:PropertyValue
73 N7c16b04cd29d43c6a6496ea78fc796b5 rdf:first Nbb27862618c74146b52bb592ab5c4edc
74 rdf:rest N8ca59d28a6bd4d65b4fd1d326ec73dd6
75 N8ca59d28a6bd4d65b4fd1d326ec73dd6 rdf:first Ne9d26f20776b4ad38d4c930d97e305bd
76 rdf:rest Nd9f50f5becbe41bcb3ddeda51f1dc528
77 Nbb27862618c74146b52bb592ab5c4edc schema:familyName Diekert
78 schema:givenName Volker
79 rdf:type schema:Person
80 Nbe380385e09840229aa237b4b6aeb096 schema:familyName Voronkov
81 schema:givenName Andrei
82 rdf:type schema:Person
83 Nc533832bdb7b45f798ae5ce04222f113 rdf:first sg:person.07404271733.31
84 rdf:rest rdf:nil
85 Ncf76b4ceb8794536a2635c68b6f7bc6b schema:name Springer Nature - SN SciGraph project
86 rdf:type schema:Organization
87 Nd9f50f5becbe41bcb3ddeda51f1dc528 rdf:first Nbe380385e09840229aa237b4b6aeb096
88 rdf:rest rdf:nil
89 Ne9d26f20776b4ad38d4c930d97e305bd schema:familyName Volkov
90 schema:givenName Mikhail V.
91 rdf:type schema:Person
92 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
93 schema:name Information and Computing Sciences
94 rdf:type schema:DefinedTerm
95 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
96 schema:name Computation Theory and Mathematics
97 rdf:type schema:DefinedTerm
98 sg:person.010127676033.33 schema:affiliation grid-institutes:grid.8379.5
99 schema:familyName Herr
100 schema:givenName Katrin
101 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010127676033.33
102 rdf:type schema:Person
103 sg:person.010502766006.46 schema:affiliation grid-institutes:grid.8379.5
104 schema:familyName Glaßer
105 schema:givenName Christian
106 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010502766006.46
107 rdf:type schema:Person
108 sg:person.013115600033.81 schema:affiliation grid-institutes:grid.8379.5
109 schema:familyName Reitwießner
110 schema:givenName Christian
111 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013115600033.81
112 rdf:type schema:Person
113 sg:person.07404271733.31 schema:affiliation grid-institutes:grid.8379.5
114 schema:familyName Waldherr
115 schema:givenName Matthias
116 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07404271733.31
117 rdf:type schema:Person
118 sg:person.07734242057.72 schema:affiliation grid-institutes:grid.8379.5
119 schema:familyName Travers
120 schema:givenName Stephen
121 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07734242057.72
122 rdf:type schema:Person
123 grid-institutes:grid.8379.5 schema:alternateName Julius-Maximilians-Universität Würzburg, Theoretische Informatik, Germany
124 schema:name Julius-Maximilians-Universität Würzburg, Theoretische Informatik, Germany
125 rdf:type schema:Organization
 




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


...