On the Computational Completeness of Equations over Sets of Natural Numbers View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2008-01-01

AUTHORS

Artur Jeż , Alexander Okhotin

ABSTRACT

Systems of equations of the form ϕj(X1, ..., Xn) = ψj(X1, ..., Xn) with \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$1 \leqslant j \leqslant m$\end{document} are considered, in which the unknowns Xi are sets of natural numbers, while the expressions ϕj,ψj may contain singleton constants and the operations of union (possibly replaced by intersection) and pairwise addition . It is shown that the family of sets representable by unique (least, greatest) solutions of such systems is exactly the family of recursive (r.e., co-r.e., respectively) sets of numbers. Basic decision problems for these systems are located in the arithmetical hierarchy. More... »

PAGES

63-74

Book

TITLE

Automata, Languages and Programming

ISBN

978-3-540-70582-6
978-3-540-70583-3

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-540-70583-3_6

DOI

http://dx.doi.org/10.1007/978-3-540-70583-3_6

DIMENSIONS

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


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/01", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Mathematical Sciences", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0102", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Applied Mathematics", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Institute of Computer Science, University of Wroc\u0142aw, Poland", 
          "id": "http://www.grid.ac/institutes/grid.8505.8", 
          "name": [
            "Institute of Computer Science, University of Wroc\u0142aw, Poland"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Je\u017c", 
        "givenName": "Artur", 
        "id": "sg:person.015252371751.76", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015252371751.76"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Department of Mathematics, University of Turku, Finland", 
          "id": "http://www.grid.ac/institutes/grid.1374.1", 
          "name": [
            "Academy of Finland", 
            "Department of Mathematics, University of Turku, Finland"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Okhotin", 
        "givenName": "Alexander", 
        "id": "sg:person.012144356031.48", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012144356031.48"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2008-01-01", 
    "datePublishedReg": "2008-01-01", 
    "description": "Systems of equations of the form \u03d5j(X1, ..., Xn)\u2009=\u2009\u03c8j(X1, ..., Xn) with \\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}$1 \\leqslant j \\leqslant m$\\end{document} are considered, in which the unknowns Xi are sets of natural numbers, while the expressions \u03d5j,\u03c8j may contain singleton constants and the operations of union (possibly replaced by intersection) and pairwise addition . It is shown that the family of sets representable by unique (least, greatest) solutions of such systems is exactly the family of recursive (r.e., co-r.e., respectively) sets of numbers. Basic decision problems for these systems are located in the arithmetical hierarchy.", 
    "editor": [
      {
        "familyName": "Aceto", 
        "givenName": "Luca", 
        "type": "Person"
      }, 
      {
        "familyName": "Damg\u00e5rd", 
        "givenName": "Ivan", 
        "type": "Person"
      }, 
      {
        "familyName": "Goldberg", 
        "givenName": "Leslie Ann", 
        "type": "Person"
      }, 
      {
        "familyName": "Halld\u00f3rsson", 
        "givenName": "Magn\u00fas M.", 
        "type": "Person"
      }, 
      {
        "familyName": "Ing\u00f3lfsd\u00f3ttir", 
        "givenName": "Anna", 
        "type": "Person"
      }, 
      {
        "familyName": "Walukiewicz", 
        "givenName": "Igor", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-540-70583-3_6", 
    "inLanguage": "en", 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-540-70582-6", 
        "978-3-540-70583-3"
      ], 
      "name": "Automata, Languages and Programming", 
      "type": "Book"
    }, 
    "keywords": [
      "system of equations", 
      "natural numbers", 
      "basic decision problems", 
      "unknowns Xi", 
      "family of sets", 
      "unique solution", 
      "operations of union", 
      "recursive sets", 
      "arithmetical hierarchy", 
      "decision problem", 
      "equations", 
      "such systems", 
      "computational completeness", 
      "set", 
      "pairwise addition", 
      "\u03d5j", 
      "system", 
      "problem", 
      "solution", 
      "number", 
      "constants", 
      "completeness", 
      "hierarchy", 
      "XI", 
      "operation", 
      "form", 
      "family", 
      "addition", 
      "Union"
    ], 
    "name": "On the Computational Completeness of Equations over Sets of Natural Numbers", 
    "pagination": "63-74", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1009467480"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-540-70583-3_6"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-540-70583-3_6", 
      "https://app.dimensions.ai/details/publication/pub.1009467480"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-06-01T22:31", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20220601/entities/gbq_results/chapter/chapter_291.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-540-70583-3_6"
  }
]
 

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-70583-3_6'

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-70583-3_6'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-540-70583-3_6'

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-70583-3_6'


 

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

125 TRIPLES      23 PREDICATES      54 URIs      47 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-540-70583-3_6 schema:about anzsrc-for:01
2 anzsrc-for:0102
3 schema:author Nd14b9efa4d644dffbcce8746c9f188a7
4 schema:datePublished 2008-01-01
5 schema:datePublishedReg 2008-01-01
6 schema:description Systems of equations of the form ϕj(X1, ..., Xn) = ψj(X1, ..., Xn) with \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$1 \leqslant j \leqslant m$\end{document} are considered, in which the unknowns Xi are sets of natural numbers, while the expressions ϕj,ψj may contain singleton constants and the operations of union (possibly replaced by intersection) and pairwise addition . It is shown that the family of sets representable by unique (least, greatest) solutions of such systems is exactly the family of recursive (r.e., co-r.e., respectively) sets of numbers. Basic decision problems for these systems are located in the arithmetical hierarchy.
7 schema:editor Nbce41c48cfe0417aadb3fc875d42519f
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree false
11 schema:isPartOf N6c2dbc6daa224effb9c38b875e208e44
12 schema:keywords Union
13 XI
14 addition
15 arithmetical hierarchy
16 basic decision problems
17 completeness
18 computational completeness
19 constants
20 decision problem
21 equations
22 family
23 family of sets
24 form
25 hierarchy
26 natural numbers
27 number
28 operation
29 operations of union
30 pairwise addition
31 problem
32 recursive sets
33 set
34 solution
35 such systems
36 system
37 system of equations
38 unique solution
39 unknowns Xi
40 ϕj
41 schema:name On the Computational Completeness of Equations over Sets of Natural Numbers
42 schema:pagination 63-74
43 schema:productId N3039101dd3754060954176c3e1229132
44 N629e3ab7fb134eb08c633f5ed33a6b49
45 schema:publisher Nf73fe1bc19284856af3764dfe2d97e54
46 schema:sameAs https://app.dimensions.ai/details/publication/pub.1009467480
47 https://doi.org/10.1007/978-3-540-70583-3_6
48 schema:sdDatePublished 2022-06-01T22:31
49 schema:sdLicense https://scigraph.springernature.com/explorer/license/
50 schema:sdPublisher Nff14c48ed7eb4d58855d09da4c6fa927
51 schema:url https://doi.org/10.1007/978-3-540-70583-3_6
52 sgo:license sg:explorer/license/
53 sgo:sdDataset chapters
54 rdf:type schema:Chapter
55 N0f108c9b9a9a4cddb1fc222e390a385d rdf:first N5c77696f051e47b5ad399acc5d54e27d
56 rdf:rest rdf:nil
57 N2622b2f84a63490291bdbd70134a1bc4 rdf:first N3fa23e455b87431794bf8d243a3852de
58 rdf:rest Na1d8925b4b35424fba60fe81445b4305
59 N3039101dd3754060954176c3e1229132 schema:name dimensions_id
60 schema:value pub.1009467480
61 rdf:type schema:PropertyValue
62 N39cf2eff63cd420dbc33ae2d859dd31d rdf:first sg:person.012144356031.48
63 rdf:rest rdf:nil
64 N3fa23e455b87431794bf8d243a3852de schema:familyName Goldberg
65 schema:givenName Leslie Ann
66 rdf:type schema:Person
67 N4044084d01e54ebca547e2284699a195 schema:familyName Aceto
68 schema:givenName Luca
69 rdf:type schema:Person
70 N4276457eed13470a8e3f06b322f4d318 rdf:first Ne7e7d33231634dc4989e9d01a74b0e8b
71 rdf:rest N2622b2f84a63490291bdbd70134a1bc4
72 N5c77696f051e47b5ad399acc5d54e27d schema:familyName Walukiewicz
73 schema:givenName Igor
74 rdf:type schema:Person
75 N629e3ab7fb134eb08c633f5ed33a6b49 schema:name doi
76 schema:value 10.1007/978-3-540-70583-3_6
77 rdf:type schema:PropertyValue
78 N6c2dbc6daa224effb9c38b875e208e44 schema:isbn 978-3-540-70582-6
79 978-3-540-70583-3
80 schema:name Automata, Languages and Programming
81 rdf:type schema:Book
82 N9072bacae06945d09e266aef35e53322 rdf:first Nbecd22fa8d314448a335694d5c1458f7
83 rdf:rest N0f108c9b9a9a4cddb1fc222e390a385d
84 Na1d8925b4b35424fba60fe81445b4305 rdf:first Nd68f9458d4ad4fba8dcd3e1932cfa56c
85 rdf:rest N9072bacae06945d09e266aef35e53322
86 Nbce41c48cfe0417aadb3fc875d42519f rdf:first N4044084d01e54ebca547e2284699a195
87 rdf:rest N4276457eed13470a8e3f06b322f4d318
88 Nbecd22fa8d314448a335694d5c1458f7 schema:familyName Ingólfsdóttir
89 schema:givenName Anna
90 rdf:type schema:Person
91 Nd14b9efa4d644dffbcce8746c9f188a7 rdf:first sg:person.015252371751.76
92 rdf:rest N39cf2eff63cd420dbc33ae2d859dd31d
93 Nd68f9458d4ad4fba8dcd3e1932cfa56c schema:familyName Halldórsson
94 schema:givenName Magnús M.
95 rdf:type schema:Person
96 Ne7e7d33231634dc4989e9d01a74b0e8b schema:familyName Damgård
97 schema:givenName Ivan
98 rdf:type schema:Person
99 Nf73fe1bc19284856af3764dfe2d97e54 schema:name Springer Nature
100 rdf:type schema:Organisation
101 Nff14c48ed7eb4d58855d09da4c6fa927 schema:name Springer Nature - SN SciGraph project
102 rdf:type schema:Organization
103 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
104 schema:name Mathematical Sciences
105 rdf:type schema:DefinedTerm
106 anzsrc-for:0102 schema:inDefinedTermSet anzsrc-for:
107 schema:name Applied Mathematics
108 rdf:type schema:DefinedTerm
109 sg:person.012144356031.48 schema:affiliation grid-institutes:grid.1374.1
110 schema:familyName Okhotin
111 schema:givenName Alexander
112 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012144356031.48
113 rdf:type schema:Person
114 sg:person.015252371751.76 schema:affiliation grid-institutes:grid.8505.8
115 schema:familyName Jeż
116 schema:givenName Artur
117 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015252371751.76
118 rdf:type schema:Person
119 grid-institutes:grid.1374.1 schema:alternateName Department of Mathematics, University of Turku, Finland
120 schema:name Academy of Finland
121 Department of Mathematics, University of Turku, Finland
122 rdf:type schema:Organization
123 grid-institutes:grid.8505.8 schema:alternateName Institute of Computer Science, University of Wrocław, Poland
124 schema:name Institute of Computer Science, University of Wrocław, Poland
125 rdf:type schema:Organization
 




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


...