Representing Hyper-arithmetical Sets by Equations over Sets of Integers

Ontology type: schema:ScholarlyArticle      Open Access: True

Article Info

DATE

2011-08-04

AUTHORS 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
• Journal

TITLE

Theory of Computing Systems

ISSUE

2

VOLUME

51

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:

[
{
"@context": "https://springernature.github.io/scigraph/jsonld/sgcontext.json",
{
"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",
}
],
"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",
"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",
"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"
}
]

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'

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
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
22 Nfd23b620356a46a085131a68402d9290
23 sg:journal.1052098
24 schema:keywords Union
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
65 schema:url https://doi.org/10.1007/s00224-011-9352-5
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
77 rdf:type schema:PublicationVolume
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