Representing Hyper-arithmetical Sets by Equations over Sets of Integers View Full Text


Ontology type: schema:ScholarlyArticle      Open Access: True


Article Info

DATE

2011-08-04

AUTHORS

Artur Jeż, Alexander Okhotin

ABSTRACT

Systems of equations with sets of integers as unknowns are considered. It is shown that the class of sets representable by unique solutions of equations using the operations of union and addition, defined as S+T={m+n∣m∈S,n∈T}, and with ultimately periodic constants is exactly the class of hyper-arithmetical sets. Equations using addition only can represent every hyper-arithmetical set under a simple encoding. All hyper-arithmetical sets can also be represented by equations over sets of natural numbers equipped with union, addition and subtraction \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$S \mathop {\mbox {$-^{\hspace {-.5em}\cdot }\,\,$}}T=\{m-n \mid m \in S, n \in T, m \geq n\}$\end{document}. Testing whether a given system has a solution is \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\varSigma ^{1}_{1}$\end{document}-complete for each model. These results, in particular, settle the expressive power of the most general types of language equations, as well as equations over subsets of free groups. More... »

PAGES

196-228

References to SciGraph publications

  • 2007-10-05. The Complexity of Membership Problems for Circuits Over Sets of Natural Numbers in COMPUTATIONAL COMPLEXITY
  • 2009-12-23. Complexity of Equations over Sets of Natural Numbers in THEORY OF COMPUTING SYSTEMS
  • 2007-06. The Power of Commuting with Finite Sets of Words in THEORY OF COMPUTING SYSTEMS
  • 2011-03-10. One-Nonterminal Conjunctive Grammars over a Unary Alphabet in THEORY OF COMPUTING SYSTEMS
  • 2010. On Language Equations XXK = XXL and XM = N over a Unary Alphabet in DEVELOPMENTS IN LANGUAGE THEORY
  • 2008-01-01. On the expressive power of univariate equations over sets of natural numbers in FIFTH IFIP INTERNATIONAL CONFERENCE ON THEORETICAL COMPUTER SCIENCE – TCS 2008
  • 2008-08-21. Conjunctive Grammars over a Unary Alphabet: Undecidability and Unbounded Growth in THEORY OF COMPUTING SYSTEMS
  • 2010. Least and Greatest Solutions of Equations over Sets of Integers in MATHEMATICAL FOUNDATIONS OF COMPUTER SCIENCE 2010
  • 2007-01-01. What Do We Know About Language Equations? in DEVELOPMENTS IN LANGUAGE THEORY
  • 1975. Languages over free groups in MATHEMATICAL FOUNDATIONS OF COMPUTER SCIENCE 1975 4TH SYMPOSIUM, MARIÁNSKÉ LÁZNĚ, SEPTEMBER 1–5, 1975
  • 2008-01-01. On the Computational Completeness of Equations over Sets of Natural Numbers in AUTOMATA, LANGUAGES AND PROGRAMMING
  • Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1007/s00224-011-9352-5

    DOI

    http://dx.doi.org/10.1007/s00224-011-9352-5

    DIMENSIONS

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


    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/0101", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Pure Mathematics", 
            "type": "DefinedTerm"
          }
        ], 
        "author": [
          {
            "affiliation": {
              "alternateName": "Institute of Computer Science, University of Wroc\u0142aw, Wroclaw, Poland", 
              "id": "http://www.grid.ac/institutes/grid.8505.8", 
              "name": [
                "Institute of Computer Science, University of Wroc\u0142aw, Wroclaw, 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, Turku, Finland", 
              "id": "http://www.grid.ac/institutes/grid.1374.1", 
              "name": [
                "Department of Mathematics, University of Turku, 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"
          }
        ], 
        "citation": [
          {
            "id": "sg:pub.10.1007/978-3-642-15155-2_39", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1017752782", 
              "https://doi.org/10.1007/978-3-642-15155-2_39"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-540-73208-2_3", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1021196966", 
              "https://doi.org/10.1007/978-3-540-73208-2_3"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/s00224-011-9319-6", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1047527460", 
              "https://doi.org/10.1007/s00224-011-9319-6"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/s00224-009-9246-y", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1003872386", 
              "https://doi.org/10.1007/s00224-009-9246-y"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/3-540-07389-2_191", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1029991616", 
              "https://doi.org/10.1007/3-540-07389-2_191"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-642-14455-4_27", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1036694593", 
              "https://doi.org/10.1007/978-3-642-14455-4_27"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/s00037-007-0229-6", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1001544925", 
              "https://doi.org/10.1007/s00037-007-0229-6"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-540-70583-3_6", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1009467480", 
              "https://doi.org/10.1007/978-3-540-70583-3_6"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/s00224-008-9139-5", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1032338044", 
              "https://doi.org/10.1007/s00224-008-9139-5"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-0-387-09680-3_15", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1032518557", 
              "https://doi.org/10.1007/978-0-387-09680-3_15"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/s00224-006-1321-z", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1001978765", 
              "https://doi.org/10.1007/s00224-006-1321-z"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "2011-08-04", 
        "datePublishedReg": "2011-08-04", 
        "description": "Systems of equations with sets of integers as unknowns are considered. It is shown that the class of sets representable by unique solutions of equations using the operations of union and addition, defined as S+T={m+n\u2223m\u2208S,n\u2208T}, and with ultimately periodic constants is exactly the class of hyper-arithmetical sets. Equations using addition only can represent every hyper-arithmetical set under a simple encoding. All hyper-arithmetical sets can also be represented by equations over sets of natural numbers equipped with union, addition and subtraction \\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}$S \\mathop {\\mbox {$-^{\\hspace {-.5em}\\cdot }\\,\\,$}}T=\\{m-n \\mid m \\in S, n \\in T, m \\geq n\\}$\\end{document}. Testing whether a given system has a solution is \\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}$\\varSigma ^{1}_{1}$\\end{document}-complete for each model. These results, in particular, settle the expressive power of the most general types of language equations, as well as equations over subsets of free groups.", 
        "genre": "article", 
        "id": "sg:pub.10.1007/s00224-011-9352-5", 
        "inLanguage": "en", 
        "isAccessibleForFree": true, 
        "isPartOf": [
          {
            "id": "sg:journal.1052098", 
            "issn": [
              "1432-4350", 
              "1433-0490"
            ], 
            "name": "Theory of Computing Systems", 
            "publisher": "Springer Nature", 
            "type": "Periodical"
          }, 
          {
            "issueNumber": "2", 
            "type": "PublicationIssue"
          }, 
          {
            "type": "PublicationVolume", 
            "volumeNumber": "51"
          }
        ], 
        "keywords": [
          "system of equations", 
          "set of integers", 
          "class of sets", 
          "unique solution", 
          "equations", 
          "operations of union", 
          "free group", 
          "natural numbers", 
          "periodic constants", 
          "language equations", 
          "general type", 
          "integers", 
          "simple encoding", 
          "set", 
          "solution", 
          "class", 
          "unknowns", 
          "expressive power", 
          "system", 
          "model", 
          "constants", 
          "power", 
          "subtraction", 
          "number", 
          "operation", 
          "subset", 
          "results", 
          "addition", 
          "encoding", 
          "types", 
          "Union", 
          "group"
        ], 
        "name": "Representing Hyper-arithmetical Sets by Equations over Sets of Integers", 
        "pagination": "196-228", 
        "productId": [
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1047985109"
            ]
          }, 
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/s00224-011-9352-5"
            ]
          }
        ], 
        "sameAs": [
          "https://doi.org/10.1007/s00224-011-9352-5", 
          "https://app.dimensions.ai/details/publication/pub.1047985109"
        ], 
        "sdDataset": "articles", 
        "sdDatePublished": "2022-05-10T10:04", 
        "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
        "sdPublisher": {
          "name": "Springer Nature - SN SciGraph project", 
          "type": "Organization"
        }, 
        "sdSource": "s3://com-springernature-scigraph/baseset/20220509/entities/gbq_results/article/article_535.jsonl", 
        "type": "ScholarlyArticle", 
        "url": "https://doi.org/10.1007/s00224-011-9352-5"
      }
    ]
     

    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/s00224-011-9352-5'

    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/s00224-011-9352-5'

    Turtle is a human-readable linked data format.

    curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/s00224-011-9352-5'

    RDF/XML is a standard XML format for linked data.

    curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/s00224-011-9352-5'


     

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

    144 TRIPLES      22 PREDICATES      68 URIs      49 LITERALS      6 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/s00224-011-9352-5 schema:about anzsrc-for:01
    2 anzsrc-for:0101
    3 schema:author N6302eebf26cb4f85a921d314f62f8318
    4 schema:citation sg:pub.10.1007/3-540-07389-2_191
    5 sg:pub.10.1007/978-0-387-09680-3_15
    6 sg:pub.10.1007/978-3-540-70583-3_6
    7 sg:pub.10.1007/978-3-540-73208-2_3
    8 sg:pub.10.1007/978-3-642-14455-4_27
    9 sg:pub.10.1007/978-3-642-15155-2_39
    10 sg:pub.10.1007/s00037-007-0229-6
    11 sg:pub.10.1007/s00224-006-1321-z
    12 sg:pub.10.1007/s00224-008-9139-5
    13 sg:pub.10.1007/s00224-009-9246-y
    14 sg:pub.10.1007/s00224-011-9319-6
    15 schema:datePublished 2011-08-04
    16 schema:datePublishedReg 2011-08-04
    17 schema:description Systems of equations with sets of integers as unknowns are considered. It is shown that the class of sets representable by unique solutions of equations using the operations of union and addition, defined as S+T={m+n∣m∈S,n∈T}, and with ultimately periodic constants is exactly the class of hyper-arithmetical sets. Equations using addition only can represent every hyper-arithmetical set under a simple encoding. All hyper-arithmetical sets can also be represented by equations over sets of natural numbers equipped with union, addition and subtraction \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$S \mathop {\mbox {$-^{\hspace {-.5em}\cdot }\,\,$}}T=\{m-n \mid m \in S, n \in T, m \geq n\}$\end{document}. Testing whether a given system has a solution is \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\varSigma ^{1}_{1}$\end{document}-complete for each model. These results, in particular, settle the expressive power of the most general types of language equations, as well as equations over subsets of free groups.
    18 schema:genre article
    19 schema:inLanguage en
    20 schema:isAccessibleForFree true
    21 schema:isPartOf N746be2f4b0e94dad94eb712907c6b949
    22 Nfd23b620356a46a085131a68402d9290
    23 sg:journal.1052098
    24 schema:keywords Union
    25 addition
    26 class
    27 class of sets
    28 constants
    29 encoding
    30 equations
    31 expressive power
    32 free group
    33 general type
    34 group
    35 integers
    36 language equations
    37 model
    38 natural numbers
    39 number
    40 operation
    41 operations of union
    42 periodic constants
    43 power
    44 results
    45 set
    46 set of integers
    47 simple encoding
    48 solution
    49 subset
    50 subtraction
    51 system
    52 system of equations
    53 types
    54 unique solution
    55 unknowns
    56 schema:name Representing Hyper-arithmetical Sets by Equations over Sets of Integers
    57 schema:pagination 196-228
    58 schema:productId N3e3be14646fd4cdda33e4ecccbf3cda2
    59 Nd50dc79126cd4b659bab01d40f6dd28e
    60 schema:sameAs https://app.dimensions.ai/details/publication/pub.1047985109
    61 https://doi.org/10.1007/s00224-011-9352-5
    62 schema:sdDatePublished 2022-05-10T10:04
    63 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    64 schema:sdPublisher Nd151f092c9564f09bade5e9ade27790b
    65 schema:url https://doi.org/10.1007/s00224-011-9352-5
    66 sgo:license sg:explorer/license/
    67 sgo:sdDataset articles
    68 rdf:type schema:ScholarlyArticle
    69 N3e3be14646fd4cdda33e4ecccbf3cda2 schema:name doi
    70 schema:value 10.1007/s00224-011-9352-5
    71 rdf:type schema:PropertyValue
    72 N3e9241f046414bf588a05f1871ef8728 rdf:first sg:person.012144356031.48
    73 rdf:rest rdf:nil
    74 N6302eebf26cb4f85a921d314f62f8318 rdf:first sg:person.015252371751.76
    75 rdf:rest N3e9241f046414bf588a05f1871ef8728
    76 N746be2f4b0e94dad94eb712907c6b949 schema:volumeNumber 51
    77 rdf:type schema:PublicationVolume
    78 Nd151f092c9564f09bade5e9ade27790b schema:name Springer Nature - SN SciGraph project
    79 rdf:type schema:Organization
    80 Nd50dc79126cd4b659bab01d40f6dd28e schema:name dimensions_id
    81 schema:value pub.1047985109
    82 rdf:type schema:PropertyValue
    83 Nfd23b620356a46a085131a68402d9290 schema:issueNumber 2
    84 rdf:type schema:PublicationIssue
    85 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
    86 schema:name Mathematical Sciences
    87 rdf:type schema:DefinedTerm
    88 anzsrc-for:0101 schema:inDefinedTermSet anzsrc-for:
    89 schema:name Pure Mathematics
    90 rdf:type schema:DefinedTerm
    91 sg:journal.1052098 schema:issn 1432-4350
    92 1433-0490
    93 schema:name Theory of Computing Systems
    94 schema:publisher Springer Nature
    95 rdf:type schema:Periodical
    96 sg:person.012144356031.48 schema:affiliation grid-institutes:grid.1374.1
    97 schema:familyName Okhotin
    98 schema:givenName Alexander
    99 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012144356031.48
    100 rdf:type schema:Person
    101 sg:person.015252371751.76 schema:affiliation grid-institutes:grid.8505.8
    102 schema:familyName Jeż
    103 schema:givenName Artur
    104 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015252371751.76
    105 rdf:type schema:Person
    106 sg:pub.10.1007/3-540-07389-2_191 schema:sameAs https://app.dimensions.ai/details/publication/pub.1029991616
    107 https://doi.org/10.1007/3-540-07389-2_191
    108 rdf:type schema:CreativeWork
    109 sg:pub.10.1007/978-0-387-09680-3_15 schema:sameAs https://app.dimensions.ai/details/publication/pub.1032518557
    110 https://doi.org/10.1007/978-0-387-09680-3_15
    111 rdf:type schema:CreativeWork
    112 sg:pub.10.1007/978-3-540-70583-3_6 schema:sameAs https://app.dimensions.ai/details/publication/pub.1009467480
    113 https://doi.org/10.1007/978-3-540-70583-3_6
    114 rdf:type schema:CreativeWork
    115 sg:pub.10.1007/978-3-540-73208-2_3 schema:sameAs https://app.dimensions.ai/details/publication/pub.1021196966
    116 https://doi.org/10.1007/978-3-540-73208-2_3
    117 rdf:type schema:CreativeWork
    118 sg:pub.10.1007/978-3-642-14455-4_27 schema:sameAs https://app.dimensions.ai/details/publication/pub.1036694593
    119 https://doi.org/10.1007/978-3-642-14455-4_27
    120 rdf:type schema:CreativeWork
    121 sg:pub.10.1007/978-3-642-15155-2_39 schema:sameAs https://app.dimensions.ai/details/publication/pub.1017752782
    122 https://doi.org/10.1007/978-3-642-15155-2_39
    123 rdf:type schema:CreativeWork
    124 sg:pub.10.1007/s00037-007-0229-6 schema:sameAs https://app.dimensions.ai/details/publication/pub.1001544925
    125 https://doi.org/10.1007/s00037-007-0229-6
    126 rdf:type schema:CreativeWork
    127 sg:pub.10.1007/s00224-006-1321-z schema:sameAs https://app.dimensions.ai/details/publication/pub.1001978765
    128 https://doi.org/10.1007/s00224-006-1321-z
    129 rdf:type schema:CreativeWork
    130 sg:pub.10.1007/s00224-008-9139-5 schema:sameAs https://app.dimensions.ai/details/publication/pub.1032338044
    131 https://doi.org/10.1007/s00224-008-9139-5
    132 rdf:type schema:CreativeWork
    133 sg:pub.10.1007/s00224-009-9246-y schema:sameAs https://app.dimensions.ai/details/publication/pub.1003872386
    134 https://doi.org/10.1007/s00224-009-9246-y
    135 rdf:type schema:CreativeWork
    136 sg:pub.10.1007/s00224-011-9319-6 schema:sameAs https://app.dimensions.ai/details/publication/pub.1047527460
    137 https://doi.org/10.1007/s00224-011-9319-6
    138 rdf:type schema:CreativeWork
    139 grid-institutes:grid.1374.1 schema:alternateName Department of Mathematics, University of Turku, Turku, Finland
    140 schema:name Department of Mathematics, University of Turku, Turku, Finland
    141 rdf:type schema:Organization
    142 grid-institutes:grid.8505.8 schema:alternateName Institute of Computer Science, University of Wrocław, Wroclaw, Poland
    143 schema:name Institute of Computer Science, University of Wrocław, Wroclaw, Poland
    144 rdf:type schema:Organization
     




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


    ...