Ontology type: schema:Chapter Open Access: True
2008-01-01
AUTHORSAlexander Okhotin , Panos Rondogiannis
ABSTRACTEquations of the form X=φ(X) are considered, where the unknown X is a set of natural numbers. The expression φ(X) may contain the operations of set addition, defined as S+T= {m+n ∣ m ∈ S, n ∈ T}, union and intersection, as well as ultimately periodic constants. An equation with a non-periodic solution of exponential growth is constructed. At the same time it is demonstrated that no sets with super-exponential growth can be represented. It is also shown that a restricted class of these equations cannot represent sets with super-linearly growing complements. The results have direct implications on the power of conjunctive grammars with one nonterminal symbol. More... »
PAGES215-227
Fifth Ifip International Conference On Theoretical Computer Science – Tcs 2008
ISBN
978-0-387-09679-7
978-0-387-09680-3
http://scigraph.springernature.com/pub.10.1007/978-0-387-09680-3_15
DOIhttp://dx.doi.org/10.1007/978-0-387-09680-3_15
DIMENSIONShttps://app.dimensions.ai/details/publication/pub.1032518557
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/08",
"inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/",
"name": "Information and Computing Sciences",
"type": "DefinedTerm"
},
{
"id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0806",
"inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/",
"name": "Information Systems",
"type": "DefinedTerm"
}
],
"author": [
{
"affiliation": {
"alternateName": "Dept. of Mathematics, University of Turku, Finland",
"id": "http://www.grid.ac/institutes/grid.1374.1",
"name": [
"Academy of Finland, Finland",
"Dept. 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"
},
{
"affiliation": {
"alternateName": "Dept. of Informatics and Telecommunications, University of Athens, Greece",
"id": "http://www.grid.ac/institutes/grid.5216.0",
"name": [
"Dept. of Informatics and Telecommunications, University of Athens, Greece"
],
"type": "Organization"
},
"familyName": "Rondogiannis",
"givenName": "Panos",
"id": "sg:person.010647771520.40",
"sameAs": [
"https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010647771520.40"
],
"type": "Person"
}
],
"datePublished": "2008-01-01",
"datePublishedReg": "2008-01-01",
"description": "Equations of the form X=\u03c6(X) are considered, where the unknown X is a set of natural numbers. The expression \u03c6(X) may contain the operations of set addition, defined as S+T=\n{m+n \u2223 m \u2208 S, n \u2208 T}, union and intersection, as well as ultimately periodic constants. An equation with a non-periodic solution of exponential growth is constructed. At the same time it is demonstrated that no sets with super-exponential growth can be represented. It is also shown that a restricted class of these equations cannot represent sets with super-linearly growing complements. The results have direct implications on the power of conjunctive grammars with one nonterminal symbol.",
"editor": [
{
"familyName": "Ausiello",
"givenName": "Giorgio",
"type": "Person"
},
{
"familyName": "Karhum\u00e4ki",
"givenName": "Juhani",
"type": "Person"
},
{
"familyName": "Mauri",
"givenName": "Giancarlo",
"type": "Person"
},
{
"familyName": "Ong",
"givenName": "Luke",
"type": "Person"
}
],
"genre": "chapter",
"id": "sg:pub.10.1007/978-0-387-09680-3_15",
"inLanguage": "en",
"isAccessibleForFree": true,
"isPartOf": {
"isbn": [
"978-0-387-09679-7",
"978-0-387-09680-3"
],
"name": "Fifth Ifip International Conference On Theoretical Computer Science \u2013 Tcs 2008",
"type": "Book"
},
"keywords": [
"natural numbers",
"non-periodic solutions",
"univariate equation",
"equations",
"form x",
"super-exponential growth",
"periodic constants",
"set addition",
"set",
"exponential growth",
"expressive power",
"number",
"solution",
"class",
"power",
"intersection",
"constants",
"same time",
"operation",
"results",
"direct implications",
"symbols",
"time",
"complement",
"conjunctive grammars",
"nonterminal symbols",
"expression",
"addition",
"growth",
"Union",
"grammar",
"implications"
],
"name": "On the expressive power of univariate equations over sets of natural numbers",
"pagination": "215-227",
"productId": [
{
"name": "dimensions_id",
"type": "PropertyValue",
"value": [
"pub.1032518557"
]
},
{
"name": "doi",
"type": "PropertyValue",
"value": [
"10.1007/978-0-387-09680-3_15"
]
}
],
"publisher": {
"name": "Springer Nature",
"type": "Organisation"
},
"sameAs": [
"https://doi.org/10.1007/978-0-387-09680-3_15",
"https://app.dimensions.ai/details/publication/pub.1032518557"
],
"sdDataset": "chapters",
"sdDatePublished": "2022-06-01T22:36",
"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_55.jsonl",
"type": "Chapter",
"url": "https://doi.org/10.1007/978-0-387-09680-3_15"
}
]
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/978-0-387-09680-3_15'
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-0-387-09680-3_15'
Turtle is a human-readable linked data format.
curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-0-387-09680-3_15'
RDF/XML is a standard XML format for linked data.
curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/978-0-387-09680-3_15'
This table displays all metadata directly associated to this object as RDF triples.
118 TRIPLES
23 PREDICATES
57 URIs
50 LITERALS
7 BLANK NODES