On the expressive power of univariate equations over sets of natural numbers View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2008-01-01

AUTHORS

Alexander Okhotin , Panos Rondogiannis

ABSTRACT

Equations 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... »

PAGES

215-227

Book

TITLE

Fifth Ifip International Conference On Theoretical Computer Science – Tcs 2008

ISBN

978-0-387-09679-7
978-0-387-09680-3

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-0-387-09680-3_15

DOI

http://dx.doi.org/10.1007/978-0-387-09680-3_15

DIMENSIONS

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


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/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

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/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

Subject Predicate Object
1 sg:pub.10.1007/978-0-387-09680-3_15 schema:about anzsrc-for:08
2 anzsrc-for:0806
3 schema:author N34188f1b22ce4e56bcb0ae0a98cc8e97
4 schema:datePublished 2008-01-01
5 schema:datePublishedReg 2008-01-01
6 schema:description Equations 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.
7 schema:editor N34e09d29db3540ec96c0c7c3c2415a16
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree true
11 schema:isPartOf N7ffab4ed489a44ae8973867f8b75e93f
12 schema:keywords Union
13 addition
14 class
15 complement
16 conjunctive grammars
17 constants
18 direct implications
19 equations
20 exponential growth
21 expression
22 expressive power
23 form x
24 grammar
25 growth
26 implications
27 intersection
28 natural numbers
29 non-periodic solutions
30 nonterminal symbols
31 number
32 operation
33 periodic constants
34 power
35 results
36 same time
37 set
38 set addition
39 solution
40 super-exponential growth
41 symbols
42 time
43 univariate equation
44 schema:name On the expressive power of univariate equations over sets of natural numbers
45 schema:pagination 215-227
46 schema:productId N70fc2d52914349a386d6050ac4bc1698
47 Nb1dcbf4607794ad68d1ee8eb479148ac
48 schema:publisher Na1a9e0e71e4a47de85be721fcd31ba82
49 schema:sameAs https://app.dimensions.ai/details/publication/pub.1032518557
50 https://doi.org/10.1007/978-0-387-09680-3_15
51 schema:sdDatePublished 2022-06-01T22:36
52 schema:sdLicense https://scigraph.springernature.com/explorer/license/
53 schema:sdPublisher N581ac7a26c524f2d988e97329f901169
54 schema:url https://doi.org/10.1007/978-0-387-09680-3_15
55 sgo:license sg:explorer/license/
56 sgo:sdDataset chapters
57 rdf:type schema:Chapter
58 N035ed8c0a4f64835aa3db144c1b24e26 schema:familyName Mauri
59 schema:givenName Giancarlo
60 rdf:type schema:Person
61 N1c4b89666e104203b8ffa4abab14a3a0 schema:familyName Ausiello
62 schema:givenName Giorgio
63 rdf:type schema:Person
64 N34188f1b22ce4e56bcb0ae0a98cc8e97 rdf:first sg:person.012144356031.48
65 rdf:rest N64e504b69ada4b44b4218c2cfb3a3039
66 N34e09d29db3540ec96c0c7c3c2415a16 rdf:first N1c4b89666e104203b8ffa4abab14a3a0
67 rdf:rest N7ba66a5ebbc54edebbfb0c991d6ba08f
68 N378668a4d7ad49febd5f9248a7549fd5 schema:familyName Karhumäki
69 schema:givenName Juhani
70 rdf:type schema:Person
71 N580444066abc43aaae490dbeca6d52e4 rdf:first N035ed8c0a4f64835aa3db144c1b24e26
72 rdf:rest N5ecf2389dc4e4cf0bb50814da324075c
73 N581ac7a26c524f2d988e97329f901169 schema:name Springer Nature - SN SciGraph project
74 rdf:type schema:Organization
75 N5e7f2256bc504cafb1d41a1de1838ed0 schema:familyName Ong
76 schema:givenName Luke
77 rdf:type schema:Person
78 N5ecf2389dc4e4cf0bb50814da324075c rdf:first N5e7f2256bc504cafb1d41a1de1838ed0
79 rdf:rest rdf:nil
80 N64e504b69ada4b44b4218c2cfb3a3039 rdf:first sg:person.010647771520.40
81 rdf:rest rdf:nil
82 N70fc2d52914349a386d6050ac4bc1698 schema:name doi
83 schema:value 10.1007/978-0-387-09680-3_15
84 rdf:type schema:PropertyValue
85 N7ba66a5ebbc54edebbfb0c991d6ba08f rdf:first N378668a4d7ad49febd5f9248a7549fd5
86 rdf:rest N580444066abc43aaae490dbeca6d52e4
87 N7ffab4ed489a44ae8973867f8b75e93f schema:isbn 978-0-387-09679-7
88 978-0-387-09680-3
89 schema:name Fifth Ifip International Conference On Theoretical Computer Science – Tcs 2008
90 rdf:type schema:Book
91 Na1a9e0e71e4a47de85be721fcd31ba82 schema:name Springer Nature
92 rdf:type schema:Organisation
93 Nb1dcbf4607794ad68d1ee8eb479148ac schema:name dimensions_id
94 schema:value pub.1032518557
95 rdf:type schema:PropertyValue
96 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
97 schema:name Information and Computing Sciences
98 rdf:type schema:DefinedTerm
99 anzsrc-for:0806 schema:inDefinedTermSet anzsrc-for:
100 schema:name Information Systems
101 rdf:type schema:DefinedTerm
102 sg:person.010647771520.40 schema:affiliation grid-institutes:grid.5216.0
103 schema:familyName Rondogiannis
104 schema:givenName Panos
105 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010647771520.40
106 rdf:type schema:Person
107 sg:person.012144356031.48 schema:affiliation grid-institutes:grid.1374.1
108 schema:familyName Okhotin
109 schema:givenName Alexander
110 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012144356031.48
111 rdf:type schema:Person
112 grid-institutes:grid.1374.1 schema:alternateName Dept. of Mathematics, University of Turku, Finland
113 schema:name Academy of Finland, Finland
114 Dept. of Mathematics, University of Turku, Finland
115 rdf:type schema:Organization
116 grid-institutes:grid.5216.0 schema:alternateName Dept. of Informatics and Telecommunications, University of Athens, Greece
117 schema:name Dept. of Informatics and Telecommunications, University of Athens, Greece
118 rdf:type schema:Organization
 




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


...