Ontology type: schema:ScholarlyArticle Open Access: True
2009-12-23
AUTHORS ABSTRACTSystems 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... »
PAGES319-342
http://scigraph.springernature.com/pub.10.1007/s00224-009-9246-y
DOIhttp://dx.doi.org/10.1007/s00224-009-9246-y
DIMENSIONShttps://app.dimensions.ai/details/publication/pub.1003872386
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
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