Complexity of Equations over Sets of Natural Numbers View Full Text


Ontology type: schema:ScholarlyArticle      Open Access: True


Article Info

DATE

2009-12-23

AUTHORS

Artur Jeż, Alexander Okhotin

ABSTRACT

Systems of equations of the form Xi=φi(X1,…,Xn) (1≤i≤n) are considered, in which the unknowns are sets of natural numbers. Expressions φi may contain the operations of union, intersection and elementwise addition \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$S+T=\{m+n\mid m\in S$\end{document} , n∈T}. A system with an EXPTIME-complete least solution is constructed in the paper through a complete arithmetization of EXPTIME-completeness. At the same time, it is established that least solutions of all such systems are in EXPTIME. The general membership problem for these equations is proved to be EXPTIME-complete. Among the consequences of the result is EXPTIME-completeness of the compressed membership problem for conjunctive grammars. More... »

PAGES

319-342

References to SciGraph publications

  • 2007-01-01. Equivalence Problems for Circuits over Sets of Natural Numbers in COMPUTER SCIENCE – THEORY AND APPLICATIONS
  • 2007-10-05. The Complexity of Membership Problems for Circuits Over Sets of Natural Numbers in COMPUTATIONAL COMPLEXITY
  • 2007-06. The Power of Commuting with Finite Sets of Words in THEORY OF COMPUTING SYSTEMS
  • 2007-01-01. The Complexity of Membership Problems for Circuits over Sets of Positive Numbers in FUNDAMENTALS OF COMPUTATION THEORY
  • 2008-08-21. Conjunctive Grammars over a Unary Alphabet: Undecidability and Unbounded Growth in THEORY OF COMPUTING SYSTEMS
  • 1985. On the recognition of context-free languages in COMPUTATION THEORY
  • 2007-01-01. What Do We Know About Language Equations? in DEVELOPMENTS IN LANGUAGE THEORY
  • 1999. Complexity of Language Recognition Problems for Compressed Words in JEWELS ARE FOREVER
  • Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1007/s00224-009-9246-y

    DOI

    http://dx.doi.org/10.1007/s00224-009-9246-y

    DIMENSIONS

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


    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, Wroc\u0142aw, Poland", 
              "id": "http://www.grid.ac/institutes/grid.8505.8", 
              "name": [
                "Institute of Computer Science, University of Wroc\u0142aw, 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": "Academy of Finland, Helsinki, Finland", 
              "id": "http://www.grid.ac/institutes/grid.15098.35", 
              "name": [
                "Department of Mathematics, University of Turku, Turku, Finland", 
                "Academy of Finland, Helsinki, 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-540-74240-1_12", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1043462749", 
              "https://doi.org/10.1007/978-3-540-74240-1_12"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-540-74510-5_15", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1008732500", 
              "https://doi.org/10.1007/978-3-540-74510-5_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"
          }, 
          {
            "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/978-3-642-60207-8_23", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1050084589", 
              "https://doi.org/10.1007/978-3-642-60207-8_23"
            ], 
            "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/3-540-16066-3_26", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1044960546", 
              "https://doi.org/10.1007/3-540-16066-3_26"
            ], 
            "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"
          }
        ], 
        "datePublished": "2009-12-23", 
        "datePublishedReg": "2009-12-23", 
        "description": "Systems of equations of the form Xi=\u03c6i(X1,\u2026,Xn) (1\u2264i\u2264n) are considered, in which the unknowns are sets of natural numbers. Expressions \u03c6i may contain the operations of union, intersection and elementwise addition \n\\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+T=\\{m+n\\mid m\\in S$\\end{document}\n, n\u2208T}. A system with an EXPTIME-complete least solution is constructed in the paper through a complete arithmetization of EXPTIME-completeness. At the same time, it is established that least solutions of all such systems are in EXPTIME. The general membership problem for these equations is proved to be EXPTIME-complete. Among the consequences of the result is EXPTIME-completeness of the compressed membership problem for conjunctive grammars.", 
        "genre": "article", 
        "id": "sg:pub.10.1007/s00224-009-9246-y", 
        "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": "48"
          }
        ], 
        "keywords": [
          "least solution", 
          "complexity of equations", 
          "system of equations", 
          "natural numbers", 
          "membership problem", 
          "operations of union", 
          "form xi", 
          "equations", 
          "such systems", 
          "arithmetization", 
          "problem", 
          "solution", 
          "unknowns", 
          "set", 
          "system", 
          "complexity", 
          "number", 
          "intersection", 
          "EXPTIME", 
          "same time", 
          "XI", 
          "operation", 
          "results", 
          "time", 
          "conjunctive grammars", 
          "addition", 
          "consequences", 
          "expression", 
          "Union", 
          "grammar", 
          "paper"
        ], 
        "name": "Complexity of Equations over Sets of Natural Numbers", 
        "pagination": "319-342", 
        "productId": [
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1003872386"
            ]
          }, 
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/s00224-009-9246-y"
            ]
          }
        ], 
        "sameAs": [
          "https://doi.org/10.1007/s00224-009-9246-y", 
          "https://app.dimensions.ai/details/publication/pub.1003872386"
        ], 
        "sdDataset": "articles", 
        "sdDatePublished": "2022-06-01T22:08", 
        "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/article/article_484.jsonl", 
        "type": "ScholarlyArticle", 
        "url": "https://doi.org/10.1007/s00224-009-9246-y"
      }
    ]
     

    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-009-9246-y'

    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-009-9246-y'

    Turtle is a human-readable linked data format.

    curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/s00224-009-9246-y'

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

    curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/s00224-009-9246-y'


     

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

    132 TRIPLES      22 PREDICATES      64 URIs      48 LITERALS      6 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/s00224-009-9246-y schema:about anzsrc-for:01
    2 anzsrc-for:0101
    3 schema:author N5128c2f034af4d3086132e4b90a68cf5
    4 schema:citation sg:pub.10.1007/3-540-16066-3_26
    5 sg:pub.10.1007/978-3-540-73208-2_3
    6 sg:pub.10.1007/978-3-540-74240-1_12
    7 sg:pub.10.1007/978-3-540-74510-5_15
    8 sg:pub.10.1007/978-3-642-60207-8_23
    9 sg:pub.10.1007/s00037-007-0229-6
    10 sg:pub.10.1007/s00224-006-1321-z
    11 sg:pub.10.1007/s00224-008-9139-5
    12 schema:datePublished 2009-12-23
    13 schema:datePublishedReg 2009-12-23
    14 schema:description Systems of equations of the form Xi=φi(X1,…,Xn) (1≤i≤n) are considered, in which the unknowns are sets of natural numbers. Expressions φi may contain the operations of union, intersection and elementwise addition \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$S+T=\{m+n\mid m\in S$\end{document} , n∈T}. A system with an EXPTIME-complete least solution is constructed in the paper through a complete arithmetization of EXPTIME-completeness. At the same time, it is established that least solutions of all such systems are in EXPTIME. The general membership problem for these equations is proved to be EXPTIME-complete. Among the consequences of the result is EXPTIME-completeness of the compressed membership problem for conjunctive grammars.
    15 schema:genre article
    16 schema:inLanguage en
    17 schema:isAccessibleForFree true
    18 schema:isPartOf N1bc0e4e5746e4559bfddc54677b6d4f8
    19 Ne647fa1547b347d393f91aced7455403
    20 sg:journal.1052098
    21 schema:keywords EXPTIME
    22 Union
    23 XI
    24 addition
    25 arithmetization
    26 complexity
    27 complexity of equations
    28 conjunctive grammars
    29 consequences
    30 equations
    31 expression
    32 form xi
    33 grammar
    34 intersection
    35 least solution
    36 membership problem
    37 natural numbers
    38 number
    39 operation
    40 operations of union
    41 paper
    42 problem
    43 results
    44 same time
    45 set
    46 solution
    47 such systems
    48 system
    49 system of equations
    50 time
    51 unknowns
    52 schema:name Complexity of Equations over Sets of Natural Numbers
    53 schema:pagination 319-342
    54 schema:productId N09dc94eb88344344a3d0859e0e46395c
    55 N47171ee7026242b894b3f120fd501c51
    56 schema:sameAs https://app.dimensions.ai/details/publication/pub.1003872386
    57 https://doi.org/10.1007/s00224-009-9246-y
    58 schema:sdDatePublished 2022-06-01T22:08
    59 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    60 schema:sdPublisher Ncdb7461e1d0641dea80fcaefe17ddbd8
    61 schema:url https://doi.org/10.1007/s00224-009-9246-y
    62 sgo:license sg:explorer/license/
    63 sgo:sdDataset articles
    64 rdf:type schema:ScholarlyArticle
    65 N09dc94eb88344344a3d0859e0e46395c schema:name dimensions_id
    66 schema:value pub.1003872386
    67 rdf:type schema:PropertyValue
    68 N1bc0e4e5746e4559bfddc54677b6d4f8 schema:volumeNumber 48
    69 rdf:type schema:PublicationVolume
    70 N47171ee7026242b894b3f120fd501c51 schema:name doi
    71 schema:value 10.1007/s00224-009-9246-y
    72 rdf:type schema:PropertyValue
    73 N5128c2f034af4d3086132e4b90a68cf5 rdf:first sg:person.015252371751.76
    74 rdf:rest N9a4bd0a4a1f0473fa812f15c2ab30b88
    75 N9a4bd0a4a1f0473fa812f15c2ab30b88 rdf:first sg:person.012144356031.48
    76 rdf:rest rdf:nil
    77 Ncdb7461e1d0641dea80fcaefe17ddbd8 schema:name Springer Nature - SN SciGraph project
    78 rdf:type schema:Organization
    79 Ne647fa1547b347d393f91aced7455403 schema:issueNumber 2
    80 rdf:type schema:PublicationIssue
    81 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
    82 schema:name Mathematical Sciences
    83 rdf:type schema:DefinedTerm
    84 anzsrc-for:0101 schema:inDefinedTermSet anzsrc-for:
    85 schema:name Pure Mathematics
    86 rdf:type schema:DefinedTerm
    87 sg:journal.1052098 schema:issn 1432-4350
    88 1433-0490
    89 schema:name Theory of Computing Systems
    90 schema:publisher Springer Nature
    91 rdf:type schema:Periodical
    92 sg:person.012144356031.48 schema:affiliation grid-institutes:grid.15098.35
    93 schema:familyName Okhotin
    94 schema:givenName Alexander
    95 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012144356031.48
    96 rdf:type schema:Person
    97 sg:person.015252371751.76 schema:affiliation grid-institutes:grid.8505.8
    98 schema:familyName Jeż
    99 schema:givenName Artur
    100 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015252371751.76
    101 rdf:type schema:Person
    102 sg:pub.10.1007/3-540-16066-3_26 schema:sameAs https://app.dimensions.ai/details/publication/pub.1044960546
    103 https://doi.org/10.1007/3-540-16066-3_26
    104 rdf:type schema:CreativeWork
    105 sg:pub.10.1007/978-3-540-73208-2_3 schema:sameAs https://app.dimensions.ai/details/publication/pub.1021196966
    106 https://doi.org/10.1007/978-3-540-73208-2_3
    107 rdf:type schema:CreativeWork
    108 sg:pub.10.1007/978-3-540-74240-1_12 schema:sameAs https://app.dimensions.ai/details/publication/pub.1043462749
    109 https://doi.org/10.1007/978-3-540-74240-1_12
    110 rdf:type schema:CreativeWork
    111 sg:pub.10.1007/978-3-540-74510-5_15 schema:sameAs https://app.dimensions.ai/details/publication/pub.1008732500
    112 https://doi.org/10.1007/978-3-540-74510-5_15
    113 rdf:type schema:CreativeWork
    114 sg:pub.10.1007/978-3-642-60207-8_23 schema:sameAs https://app.dimensions.ai/details/publication/pub.1050084589
    115 https://doi.org/10.1007/978-3-642-60207-8_23
    116 rdf:type schema:CreativeWork
    117 sg:pub.10.1007/s00037-007-0229-6 schema:sameAs https://app.dimensions.ai/details/publication/pub.1001544925
    118 https://doi.org/10.1007/s00037-007-0229-6
    119 rdf:type schema:CreativeWork
    120 sg:pub.10.1007/s00224-006-1321-z schema:sameAs https://app.dimensions.ai/details/publication/pub.1001978765
    121 https://doi.org/10.1007/s00224-006-1321-z
    122 rdf:type schema:CreativeWork
    123 sg:pub.10.1007/s00224-008-9139-5 schema:sameAs https://app.dimensions.ai/details/publication/pub.1032338044
    124 https://doi.org/10.1007/s00224-008-9139-5
    125 rdf:type schema:CreativeWork
    126 grid-institutes:grid.15098.35 schema:alternateName Academy of Finland, Helsinki, Finland
    127 schema:name Academy of Finland, Helsinki, Finland
    128 Department of Mathematics, University of Turku, Turku, Finland
    129 rdf:type schema:Organization
    130 grid-institutes:grid.8505.8 schema:alternateName Institute of Computer Science, University of Wrocław, Wrocław, Poland
    131 schema:name Institute of Computer Science, University of Wrocław, Wrocław, Poland
    132 rdf:type schema:Organization
     




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


    ...