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 N22368eaf812a4c2c84168a94becd0a72
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 N072a4709e0a3410b9e9a4487a7eb49ed
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree true
11 schema:isPartOf N538531c619674daaa948e47b810f18e9
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 N026a94936d144096804ac032c7cb4011
47 Ncbc3a550fa6f4f109b200fe503a6f68d
48 schema:publisher Nd16e567ac4d947b88d869718b6367163
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 Nfd204d81787d46668ca204ce2857d9a7
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 N026a94936d144096804ac032c7cb4011 schema:name doi
59 schema:value 10.1007/978-0-387-09680-3_15
60 rdf:type schema:PropertyValue
61 N072a4709e0a3410b9e9a4487a7eb49ed rdf:first N26a9e34dceb34f14aaec6b921d18c31e
62 rdf:rest N8a11a7c6e283400bbe03f761d30001fe
63 N22368eaf812a4c2c84168a94becd0a72 rdf:first sg:person.012144356031.48
64 rdf:rest Na37b695d31dc4ff0be284d16b93dce34
65 N26a9e34dceb34f14aaec6b921d18c31e schema:familyName Ausiello
66 schema:givenName Giorgio
67 rdf:type schema:Person
68 N2b3650f54c954c48afc814116ec2a5a5 schema:familyName Mauri
69 schema:givenName Giancarlo
70 rdf:type schema:Person
71 N538531c619674daaa948e47b810f18e9 schema:isbn 978-0-387-09679-7
72 978-0-387-09680-3
73 schema:name Fifth Ifip International Conference On Theoretical Computer Science – Tcs 2008
74 rdf:type schema:Book
75 N831624b30abb4c24b7df8f0b59c6f34f schema:familyName Karhumäki
76 schema:givenName Juhani
77 rdf:type schema:Person
78 N8a11a7c6e283400bbe03f761d30001fe rdf:first N831624b30abb4c24b7df8f0b59c6f34f
79 rdf:rest N94b917dafb964709a0844658795f640b
80 N94b917dafb964709a0844658795f640b rdf:first N2b3650f54c954c48afc814116ec2a5a5
81 rdf:rest Nf45120be987e47b08bebbe94d899eab5
82 N99f1912267a6424e86b2ffad3b73d4f0 schema:familyName Ong
83 schema:givenName Luke
84 rdf:type schema:Person
85 Na37b695d31dc4ff0be284d16b93dce34 rdf:first sg:person.010647771520.40
86 rdf:rest rdf:nil
87 Ncbc3a550fa6f4f109b200fe503a6f68d schema:name dimensions_id
88 schema:value pub.1032518557
89 rdf:type schema:PropertyValue
90 Nd16e567ac4d947b88d869718b6367163 schema:name Springer Nature
91 rdf:type schema:Organisation
92 Nf45120be987e47b08bebbe94d899eab5 rdf:first N99f1912267a6424e86b2ffad3b73d4f0
93 rdf:rest rdf:nil
94 Nfd204d81787d46668ca204ce2857d9a7 schema:name Springer Nature - SN SciGraph project
95 rdf:type schema:Organization
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)


...